Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

• URL: http://arxiv.org/abs/2510.07808v1
• Date: Thu, 09 Oct 2025 05:34:42 GMT
• Title: Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
• Authors: Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu,
• Abstract summary: We construct a family of distributions $mathcalD_nn$ with $mathcalD_n$ over $0, 1n$ and a family of depth-$7$ quantum circuits.<n>Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on work of Bravyi, Gosset, and K"onig (Science), to separate shallow quantum and classical circuits for relational problems.
• Score: 6.252607743959949
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct a family of distributions $\{\mathcal{D}_n\}_n$ with $\mathcal{D}_n$ over $\{0, 1\}^n$ and a family of depth-$7$ quantum circuits $\{C_n\}_n$ such that $\mathcal{D}_n$ is produced exactly by $C_n$ with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance $1 - e^{-\Omega(n)}$ from $\mathcal{D}_n$. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and K\"onig (Science, 2018) to separate shallow quantum and classical circuits for relational problems.

Related papers

• On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
  The problem of encoded quantum gate generation is studied in this paper. The emphReference Input Generation Algorithm (RIGA) is generalized in this work.
  arXiv  Detail & Related papers  (2024-09-02T10:41:15Z)
• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  One of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. We prove new separations between classical and quantum constant-depth circuits. In the infinite-size gateset case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
  arXiv  Detail & Related papers  (2024-04-28T07:44:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Unitary k-designs from random number-conserving quantum circuits [0.0]
  Local random circuits scramble efficiently and accordingly have a range of applications in quantum information and quantum dynamics. We show that finite moments cannot distinguish the ensemble that local random circuits generate from the Haar ensemble on the entire group of number-conserving unitaries.
  arXiv  Detail & Related papers  (2023-06-01T18:00:00Z)
• Unconditional Quantum Advantage for Sampling with Shallow Circuits [0.0]
  Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve. We show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out.
  arXiv  Detail & Related papers  (2023-01-03T08:07:55Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)

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.