Quantum Algorithms for Data Streams

“数据流的量子算法“Wim货车大坝，加州大学，圣巴巴拉在这个项目中，研究人员开发了新的算法来处理数据流，这些数据流比执行量子算法的量子计算机的内部存储器大得多。这样的算法在“在线”设置中特别相关，在该设置中，计算机处理必须在真实的时间中处理的连续且不可预测的信息流，而不可能存储信息以供进一步分析。该项目的研究重点是，与我们目前的经典计算机相比，（未来的）量子力学计算机在执行此类任务方面会有多好。虽然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.