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比特的经典信息，但从早期关于量子有限自动机和量子通信的工作中有充分的证据表明，对于特定的任务，所需的量子比特的数量可以显著低于所需的经典比特的数量。这里研究的是这些量子改进是否也可以在数据流模型中获得。该研究将量子计算理论的思想应用到数据流算法的新设置中，给出了一个位于量子有限自动机理论和量子通信复杂性理论的交叉点上的计算模型。由于在不久的将来，量子设备的内存很可能非常有限，因此至少从实验的角度来看，这个数据流模型可以说比一般的量子电路模型更现实，因为它对内存的可用性做出了更慷慨的假设。