Verifiable quantum advantage in extremely low depth

• URL: http://arxiv.org/abs/2609.01448v1
• Date: Tue, 01 Sep 2026 15:54:34 GMT
• Title: Verifiable quantum advantage in extremely low depth
• Abstract summary: 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.
• Score: 52.51019642214249
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

Related papers

• Efficient compilation of quantum circuits using multi-qubit gates [0.0]
  We present a compilation scheme which implements a general-circuit decomposition to a sequence of Ising-type, long-range, multi-qubit entangling gates.<n>We numerically test our compilation and show that, compared to conventional realizations with two-qubit gates, our compilations improves the logarithm of quantum volume by $20%$ to $25%$.
  arXiv  Detail & Related papers  (2025-01-28T19:08:13Z)
• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage [17.38734393793605]
  We propose an approximate method for compiling target quantum circuits into brick-wall layouts.<n>This new circuit design consists of two-qubit CNOT gates that can be directly implemented on real quantum computers.
  arXiv  Detail & Related papers  (2025-01-13T15:04:39Z)
• An unconditional distribution learning advantage with shallow quantum circuits [0.0]
  We prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses.<n>We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC0) are superior compared to constant-depth bounded fan-in classical circuits (NC0) as a choice for hypothesis classes.
  arXiv  Detail & Related papers  (2024-11-23T13:03:22Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  We introduce a multiple-circuit algorithm for a quantum lattice Boltzmann method (QLBM) solve of the incompressible Navier--Stokes equations.<n>The presented method is validated and demonstrated for 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Robust sparse IQP sampling in constant depth [3.670008893193884]
  NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation. We propose a scheme to achieve a provable superpolynomial quantum advantage that is robust to noise with minimal error correction requirements.
  arXiv  Detail & Related papers  (2023-07-20T09:41:08Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  We consider biased-noise qubits affected only by bit-flip errors, which is motivated by existing systems of stabilized cat qubits. For realistic noise models, phase-flip will not be negligible, but in the Pauli-Twirling approximation, we show that our benchmark could check the correctness of circuits containing up to $106$ gates.
  arXiv  Detail & Related papers  (2023-05-03T11:27:50Z)
• 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)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)

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.