Quantum Algorithms for Data Streams

“数据流的量子算法”Wim van Dam，加州大学圣巴巴拉分校在这个项目中，研究者开发了处理数据流的新算法，这些数据流比执行量子算法的量子计算机的内存要大得多。这种算法尤其适用于“在线”环境，在这种环境中，计算机处理连续的、不可预测的信息流，这些信息流必须被实时处理，而不可能存储这些信息以供进一步分析。这个项目的研究重点是（未来）量子力学计算机在执行这些任务时比我们现在的经典计算机好多少。虽然N个量子比特可以携带不超过N位的经典信息，但从量子有限自动机和量子通信的早期工作中有充分的证据表明，对于特定任务，所需的量子比特数量可以显著低于所需的经典比特数量。本文探讨了在数据流模型中是否也能获得这些量子改进。该研究将量子计算理论的思想应用于数据流算法的新设置，从而提供了一个位于量子有限自动机和量子通信复杂性理论交叉点的计算模型。由于量子设备在不久的将来很可能只有非常有限的内存，至少从实验的角度来看，这种数据流模型可以说比一般的量子电路模型更现实，因为它对内存的可用性有更慷慨的假设。

"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.