Space Complexity of Streaming Algorithms on Universal Quantum Computers

• URL: http://arxiv.org/abs/2011.00302v1
• Date: Sat, 31 Oct 2020 16:16:35 GMT
• Title: Space Complexity of Streaming Algorithms on Universal Quantum Computers
• Authors: Yanglin Hu, Darya Melnyk, Yuyi Wang and Roger Wattenhofer
• Abstract summary: 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.
• Score: 13.941598115553957
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Quantum Frequential Computing: a quadratic run time advantage for all algorithms [0.0]
  We introduce a new class of computer called a quantum frequential computer. They harness quantum properties in a different way to conventional quantum computers. They generate a quadratic computational run time advantage for all algorithms as a function of the power consumed.
  arXiv  Detail & Related papers  (2024-03-04T19:00:02Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• A prototype of quantum von Neumann architecture [0.0]
  We propose a model of universal quantum computer system, the quantum version of the von Neumann architecture. It uses ebits as elements of the quantum memory unit, and qubits as elements of the quantum control unit and processing unit. Our primary study demonstrates the manifold power of quantum information and paves the way for the creation of quantum computer systems.
  arXiv  Detail & Related papers  (2021-12-17T06:33:31Z)
• A universal qudit quantum processor with trapped ions [1.4675095722281566]
  We demonstrate a universal qudit quantum processor using trapped ions with a local Hilbert space dimension of up to 7. This approach enables native simulation of high-dimensional quantum systems, as well as more efficient implementation of qubit-based algorithms.
  arXiv  Detail & Related papers  (2021-09-14T18:02:25Z)
• Universal quantum computation via quantum controlled classical operations [0.0]
  A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. We show that even a primitive computer capable of implementing only SWAP gates, can be lifted to universal quantum computing.
  arXiv  Detail & Related papers  (2021-04-13T18:00:13Z)
• Quantum Computing without Quantum Computers: Database Search and Data Processing Using Classical Wave Superposition [101.18253437732933]
  We present experimental data on magnetic database search using spin wave superposition. We argue that in some cases the classical wave-based approach may provide the same speedup in database search as quantum computers.
  arXiv  Detail & Related papers  (2020-12-15T16:21:53Z)
• Quantum Deformed Neural Networks [83.71196337378022]
  We develop a new quantum neural network layer designed to run efficiently on a quantum computer. It can be simulated on a classical computer when restricted in the way it entangles input states.
  arXiv  Detail & Related papers  (2020-10-21T09:46:12Z)
• A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
  In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm. Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function.
  arXiv  Detail & Related papers  (2020-10-05T17:22:22Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.