A Quantum Advantage for a Natural Streaming Problem

• URL: http://arxiv.org/abs/2106.04633v2
• Date: Fri, 12 Nov 2021 23:25:52 GMT
• Title: A Quantum Advantage for a Natural Streaming Problem
• Abstract summary: We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph counting. Almost-tight parametrized upper and lower bounds are known for streaming.
• Score: 0.07614628596146598
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

Related papers

• Exponential quantum space advantage for Shannon entropy estimation in data streams [4.740331063526406]
  Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model.<n>We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting.
  arXiv  Detail & Related papers  (2026-04-20T09:37:19Z)
• Toward speedup without quantum coherent access [0.0]
  We propose a variant of quantum algorithms, leveraging both classical and quantum resources.<n>We show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, and data fitting.
  arXiv  Detail & Related papers  (2026-02-24T11:21:44Z)
• Realization of a Quantum Streaming Algorithm on Long-lived Trapped-ion Qubits [2.886955168147019]
  In this work, we realize a data-streaming model using a trapped-ion quantum computer with long-lived qubits that communicate with an external server.<n>We show that the quantum space advantage persists even with the overheads of fault-tolerance.
  arXiv  Detail & Related papers  (2025-11-05T18:16:21Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model [0.24554686192257422]
  We show an exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem. Our result is based on a recent $widetildetextO(sqrtn)$ space classical streaming approach.
  arXiv  Detail & Related papers  (2023-11-23T17:38:16Z)
• Limitations of Noisy Quantum Devices in Computational and Entangling Power [5.178527492542246]
  We show that noisy quantum devices with a circuit depth of more than $O(log n)$ provide no advantages in any quantum algorithms. We also study the maximal entanglement that noisy quantum devices can produce under one- and two-dimensional qubit connections.
  arXiv  Detail & Related papers  (2023-06-05T12:29:55Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NP-hard problems are not believed to be exactly solvable through general time algorithms. In this paper, we build upon a proprietary methodology which logarithmically scales with problem size. These algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256.
  arXiv  Detail & Related papers  (2023-01-17T16:03:33Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [3.5707423185282665]
  We present an improved quantum algorithm for computing persistent Betti numbers.<n>We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
  arXiv  Detail & Related papers  (2022-09-26T17:56:11Z)
• 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)
• Distributed quantum algorithm for Simon's problem [2.26741603346646]
  We study the Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits.
  arXiv  Detail & Related papers  (2022-04-25T01:22:22Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles. We use a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases.
  arXiv  Detail & Related papers  (2022-03-17T19:26:00Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• One-shot inner bounds for sending private classical information over a quantum MAC [0.0]
  We provide the first inner bounds for sending private classical information over a quantum multiple access channel. We do so by using three powerful information theoretic techniques: rate splitting, quantum simultaneous decoding for multiple access channels, and a novel smoothed distributed covering lemma for classical quantum channels.
  arXiv  Detail & Related papers  (2021-05-13T06:31:27Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.