Quantum Algorithms for Data Streams

数据流的量子算法

• 批准号: 0729172
• 负责人: Willem van Dam
• 金额: $ 6.92万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729172&HistoricalAwards=false
• 关键词: Quantum; Algorithms; Data; Streams

"Quantum Algorithms for Data Stream"Wim van Dam, University of California, Santa BarbaraIn this project the investigator develops new algorithms for processing data streams that are much larger than the internal memory of the quantum computer that executes the quantum algorithm. Such algorithms are especially relevant in an "online" setting where the computer deals with a continuous and unpredictable flow of information that has to be processed in real time without the possibility of storing the information for further analysis. The research of this project focuses on the question how much better (future) quantum mechanical computers will be at performing such tasks in comparison with our current, classical computers.While N quantum bits can carry no more than N bits of classical information, there is ample evidence from earlier work on quantum finite automata and quantum communication that for specific tasks the required amount of quantum bits can be significantly lower than the required number of classical bits. Here it is investigated if these kinds of quantum improvements can also be obtained in the data stream model. The research applies ideas from the theory of quantum computation to the new setting of data stream algorithms, which gives a computational model that sits at the intersection of the theories of quantum finite automata and quantum communication complexity. As quantum devices in the near future will most likely have a very limited amount of memory, this data stream model is arguably more realistic, from an experimental point of view at least, than the general quantum circuit model with its more generous assumptions regarding the availability of memory.

“数据流的量子算法” WIM VAN DAM，加利福尼亚大学圣巴拉林分校该项目研究人员开发了用于处理数据流的新算法，该算法比执行量子算法的量子计算机的内部内存大得多。此类算法在“在线”设置中尤其重要，在该设置中，计算机处理的是连续且不可预测的信息流，该信息必须实时处理，而无需存储信息以进行进一步分析。该项目的研究重点是与当前的经典计算机相比，将执行此类任务的更好（未来）量子机械计算机将有多大（n量子位都可以携带的n量子含量超过经典信息的n位，但从较早的量子有限自动机和量子通信的早期工作中，需要比量子的量相当大的量子，而量子的数量要低。在这里，研究是否还可以在数据流模型中获得这些量子改进。该研究将量子计算理论的思想应用于数据流算法的新设置，该算法提供了一个计算模型，该模型位于量子有限自动机理论和量子通信复杂性的相交的相交。由于不久的将来的量子设备很可能具有非常有限的内存，因此至少从实验的角度来看，这种数据流模型可以说是更现实的，比通用量子电路模型具有对内存可用性的更慷慨的假设。