Parallel Quantum Advantage with Limited Adaptivity Requires Structure

• URL: http://arxiv.org/abs/2608.20297v1
• Date: Thu, 20 Aug 2026 17:37:03 GMT
• Title: Parallel Quantum Advantage with Limited Adaptivity Requires Structure
• Abstract summary: We prove Aaronson and Ambainis conjecture that quantum query algorithms admit almost-everywhere classical simulation.<n>We show that exponential quantum speedups are possible only on sufficiently structured inputs.<n>Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions.
• Score: 2.6546344072296084
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any $T$-query quantum algorithm, its acceptance probability can be approximated on a $(1-δ)$ fraction of inputs, up to $ε$ additive error, using $\mathrm{poly}(T, 1/ε, 1/δ)$ classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting, obtaining simulation theorems both for algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage, and for hybrid algorithms that make an arbitrary polynomial number of adaptive classical queries before the massively parallel quantum-query stage. Finally, using the parallel-query simulation theorem as a base case, we obtain simulation theorems for quantum algorithms with constant rounds of adaptivity.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Quantum Speedups Require Structure or Depth [6.942576237126963]
  We show that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $tO(d2)$ classical queries.<n>For unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require depth.
  arXiv  Detail & Related papers  (2026-08-19T17:42:10Z)
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
  arXiv  Detail & Related papers  (2024-09-06T03:32:02Z)
• The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
  We study the depth-computation trade-off in the query model, where the depth corresponds to the number of adaptive query rounds and the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with $r$ versus $r-1$ rounds of adaptivity.
  arXiv  Detail & Related papers  (2023-11-27T18:21:32Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• 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)
• 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)
• 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)
• Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
  We consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We apply our method to some simple quantum speedups of classical algorithms for solving the well-studied MAX-$k$-SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines.
  arXiv  Detail & Related papers  (2022-03-09T19:00:00Z)
• 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.