Quantum Speedups Require Structure or Depth

• URL: http://arxiv.org/abs/2608.19158v1
• Date: Wed, 19 Aug 2026 17:42:10 GMT
• Title: Quantum Speedups Require Structure or Depth
• Abstract summary: 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.
• Score: 6.942576237126963
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

Related papers

• Parallel Quantum Advantage with Limited Adaptivity Requires Structure [2.6546344072296084]
  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.
  arXiv  Detail & Related papers  (2026-08-20T17:37:03Z)
• Limitation of Quantum Walk Approach to the Maximum Matching Problem [0.0]
  The Maximum Matching problem has a quantum query complexity lower bound of $Omega(n3/2)$ for graphs on $n$ vertices represented by an adjacency matrix.<n>The current best quantum algorithm has the query complexity $O(n7/4)$, which is an improvement over the trivial bound $O(n2)$.<n>We show that the quantum walk technique fails to produce a fast algorithm improving the known (or even the trivial) upper bound on the query complexity.
  arXiv  Detail & Related papers  (2025-10-30T08:29:44Z)
• Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
  We learn a constant depth quantum circuit that prepares $vertpsirangle$ on a finite-dimensional lattice. The algorithm extends to the case when the depth of $U$ is $mathrmpolylog(n)$, with a quasi-polynomial run-time. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
  arXiv  Detail & Related papers  (2024-10-31T04:12:49Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Quantum Speedups for Bayesian Network Structure Learning [12.02309220445177]
  For networks with $n$ nodes, the fastest known algorithms run in time $O(2n n2)$ in the worst case, with no improvement in two decades.<n>Inspired by recent advances in quantum computing, we ask whether the problem can be solved by a quantum algorithm in time $O(cn)$ for some constant $c$ less than $2$.
  arXiv  Detail & Related papers  (2023-05-31T09:15:28Z)
• 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 Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• 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)
• Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
  We prove optimal lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup.
  arXiv  Detail & Related papers  (2021-06-03T17:22:08Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• 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.