论文标题
通用量子计算机上流算法的空间复杂性
Space Complexity of Streaming Algorithms on Universal Quantum Computers
论文作者
论文摘要
通用量子计算机是已知可以实现的唯一通用量子计算机。这些计算机由控制量子内存的经典内存组件组成。在本文中，在通用量子计算机上研究了某些数据流问题的空间复杂性，例如部分模型和平等。这些问题的量子算法被认为优于其经典算法。但是，通用量子计算机还需要经典的位，以控制量子门以外的量子门。我们的分析表明，量子算法中使用的经典位数等于甚至大于相应经典算法中使用的经典位。这些结果表明，当考虑空间复杂性时，在通用量子计算机上而不是古典计算机上实现某些数据流问题没有优势。
Universal quantum computers are the only general purpose quantum computers known that can be implemented as of today. These computers consist of a classical memory component which controls the quantum memory. In this paper, the space complexity of some data stream problems, such as PartialMOD and Equality, is investigated on universal quantum computers. The quantum algorithms for these problems are believed to outperform their classical counterparts. Universal quantum computers, however, need classical bits for controlling quantum gates in addition to qubits. Our analysis shows that the number of classical bits used in quantum algorithms is equal to or even larger than that of classical bits used in corresponding classical algorithms. These results suggest that there is no advantage of implementing certain data stream problems on universal quantum computers instead of classical computers when space complexity is considered.
