PaperlayerView exact revision on arXiv

Source-linked AI summary

Verifiable quantum advantage in extremely low depth

Alexandru Gheorghiu

arXiv:2609.01448v1quant-phcs.CR

TL;DR

The paper addresses whether extremely shallow quantum circuits can produce classically hard outputs that remain efficiently verifiable. It constructs such a sampling task with two very-low-depth implementations and no mid-circuit measurements or feed-forward.

  • Problem

    Known shallow-circuit results do not simultaneously provide classical hardness, efficient verification, and extremely low-depth quantum computation.

  • Method

    The construction compiles a single-round LWE-based proof of quantumness using lattice knowledge and adaptive-hardcore-bit assumptions into shallow quantum sampling circuits.

  • Results

    The task is classically hard under lattice assumptions, polynomial-time verifiable, and implementable by both QNC^0[log log] and constant-depth QAC^0 circuits; quantum sampling is accepted with probability 1 − negl(λ), versus at most 3/4 + negl(λ) for uniform classical samplers running in time 2^o(λ).

  • Takeaways & Limitations

    Shallow quantum circuits can solve certain classically hard tasks whose outputs retain enough structure for efficient classical verification.

  • Takeaways & Limitations

    The construction relies on less standard assumptions, and width-based factoring approaches can retain quasipolynomial classical running time or logarithmic depth relative to actual input size.

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether very shallow quantum circuits can solve classically hard sampling problems whose outputs are efficiently verifiable. It provides such a task under lattice-based assumptions, with QNC0[log log] and QAC0 implementations that use only a final measurement.

  • Motivation: The work targets a gap: no known task was simultaneously QNC0-solvable, hard for polynomial-time classical computation, and efficiently classically verifiable.Prior approaches either restricted classical hardness, used interactive protocols or mid-circuit measurements, or relied on random-oracle access.
  • Contribution: The construction gives a sampling task that is classically hard under lattice assumptions, polynomial-time verifiable, and implementable in QNC0[log log] and QAC0.The QNC0[log log] implementation uses one- and two-qubit gates, while QAC0 uses unbounded fan-in gates.
  • Results: 18?

2 Technical Overview

The construction compiles an interactive LWE-based proof of quantumness into a shallow, single-round protocol using randomized encodings. It combines extractability, adaptive-hardcore-bit assumptions, and local arithmetic to obtain efficient verification and classical soundness.

  • BCMVV and AGGM: The original protocol uses a TCF from LWE, with computational- and Hadamard-basis measurements implementing the preimage and equation tests.The quantum prover must otherwise keep the state coherent until receiving the verifier’s challenge.
  • BCMVV and AGGM: AGGM replaces the challenge round by combining an extractable injective function g with an indistinguishable TCF f.The LK assumption supplies extraction for g, while LWE-based AHCB supplies the relevant hardness for f.
  • A randomized encoding for affine maps over a ring: Randomized encodings replace global affine computation with locally computable strings whose decoder recovers the original output and whose distribution reveals only that output.The construction also supports randomness reconstruction and constant input/output locality over Zq.
  • A randomized encoding for affine maps over a ring: The two mask layers separately prevent input reuse across matrix rows and decompose each row’s correction sum into local terms, preserving the interference between preimages.This makes the coherent computation local while retaining the structure needed by the original protocol.
  • Classical hardness: The carry-predicate assumption strengthens adaptive-hardcore-bit security, and together with LK extraction yields soundness bounded by 3/4 + negl(λ).The carry predicates allow nonlinear parity predictions involving partial-sum carries.

3 Related Work

Prior work established classical hardness for sampling from shallow quantum circuits and several shallow quantum separations, but did not provide the same combination of efficient verification and a final-measurement-only prover. This work targets that gap with a white-box shallow circuit under less standard assumptions.

  • Shallow sampling hardness: Prior sampling results established hardness for constant-depth quantum circuits, including average-case hardness, but their tasks were not known to be efficiently verifiable.These results adapted hardness arguments for IQP circuits to other constant-depth architectures.
  • Unconditional separations: Unconditional shallow-circuit separations and certifiable-randomness results established quantum advantages against restricted classical circuit classes, rather than general polynomial-time computation.The cited work includes separations against AC0 and NC1 and depth hierarchies for shallow circuits.
  • Verification of quantumness: Earlier verification-oriented proposals include LWE-based tests of quantumness, Mahadev-style protocols, and low-depth protocols using mid-circuit measurements and classical feed-forward.The present prover instead runs one white-box shallow circuit followed by a final measurement layer.
  • QAC0 and fan-out: The QAC0 approach uses exact polylogarithmic fan-out constructions, while prior work connected fan-out to constant-depth arithmetic and pseudorandom unitaries.The distinction between unbounded fan-in and unbounded fan-out motivates the paper’s focus on QAC0.
  • Randomized encodings: The randomized encoding generalizes an NC0 cryptographic technique for binary affine maps to q-ary affine maps over a ring.It is also described as a q-ary path-mask analogue of a recent binary encoding for constant-depth pseudoentanglement.

4 Discussion

The paper’s two implementations approach true QNC^0 from complementary directions, but neither achieves constant depth with only one- and two-qubit gates. The construction also faces practicality and assumption-strength limitations.

  • The bounded-arity implementation has depth O(log log λ), while the constant-depth implementation uses unbounded fan-in gates; neither is constant-depth over only one- and two-qubit gates.
  • A true QNC^0 implementation would require constant-size-modulus functions or a more local randomized encoding, but current candidates lack properties needed for verifiable quantumness.
  • The construction relies on a carry-predicate adaptive-hardcore-bit assumption not currently derived from standard LWE, whose reductions establish only the linear version.
  • Under LWE, the supporting evidence rules out several efficient classical strategies for predicting carry-inclusive parities, including adaptive challenge selection under suitable min-entropy.
  • The alternative Kahanamoku–Meyer et al. route avoids adaptive hardcore bits but uses three rounds, and collapsing it to one round remains unclear.
  • The circuit width is eO(λ^4 log^6 λ), making near-term implementation unlikely; encoding masks and parallel arithmetic workspace cause much of the overhead.

5 Preliminaries

The preliminaries define the circuit and proof-of-quantumness models, review the quantum and LWE machinery, and state the assumptions underlying the construction. They also record that the instantiated hiding error is negligible under the carry-predicate assumption.

  • QNC^0 consists of polynomial-size constant-depth circuits over one- and two-qubit gates, while QNC^0[log log] permits depth O(log log λ).
  • QAC^0 additionally permits generalized Toffoli gates with unbounded fan-in, while each qubit still participates in at most one gate per layer.
  • The constant-depth implementation uses fan-out to prepare GHZ states and distribute register contents to many gates in parallel; all measurements occur in one final layer.
  • A single-round proof of quantumness generates a public challenge and private verification data, receives one classical prover response, and then accepts or rejects.
  • Completeness measures honest-prover acceptance, whereas classical soundness bounds acceptance probability for every fixed uniform probabilistic polynomial-time classical prover.
  • LWE gives a secret-noisy linear system indistinguishable from a uniform vector, and the paper uses it for partial evidence rather than as the main assumption.
  • The trapdoor generator produces a statistically near-uniform public matrix with bounded-distance inversion, with public statistical distance and trapdoor-failure probability at most 2^-Ω(n).
  • In the instantiation, ε_hid is negligible under the carry-predicate assumption, so key-mode indistinguishability contributes only a negligible term to soundness.

6 The Encoded-LWE Sampling Problem

The section constructs an encoded-LWE sampling problem whose security relies on LK-1/4 and a carry-predicate adaptive-hardcore-bit assumption. The protocol has shallow quantum implementations, efficient verification, and a constant completeness–soundness gap.

  • Construction and assumptions: The encoded-LWE family supports a single-round proof of quantumness with polynomial width and nearly exponential assumed hardness.The assumptions target adversaries of time 2^Θ(λ) because n = Θ(λ^2).
  • Completeness and soundness: The encoded preimage construction preserves valid paired images except for quantified boundary, shifted-noise-overlap, and trapdoor-failure events.The associated honest-probability loss is bounded by 2n/Q + mBV/W.
  • Circuit implementations: The honest quantum sampler has exact QNC0[log log] and QAC0 implementations using only final measurements.The bounded-arity implementation uses one- and two-qubit gates, while the QAC0 implementation uses unbounded fan-in gates.
  • Completeness and soundness: The honest quantum prover is accepted with probability 1 − negl(λ), whereas uniform classical provers running in time 2^o(λ) are accepted with probability at most 3/4 + negl(λ).The resulting acceptance probabilities are separated by a constant for sufficiently large λ.

A The Admissibility Predicate

The admissibility predicate is supported by explicit evidence against elementary classical strategies, but its passage to a hardcore-bit guarantee remains an assumption rather than a derived consequence of LWE.

  • A The Admissibility Predicate: The carry-predicate assumption uses an explicit predicate designed to accept almost all honest challenges while excluding carry-cancellation and padding strategies.The appendix also notes that the BCMVV result uses a similar admissible set.
  • A The Admissibility Predicate: Passing the balance tests is not known to imply a hardcore bit, and the argument does not derive the carry-predicate assumption from LWE.The tests rule out several elementary classical strategies but do not establish the full cryptographic assumption.

A.1 Preimage differences and the decomposition

The appendix decomposes the verifier’s parity across encoded register blocks, expressing secret dependence through a linear term while isolating branch-dependent contributions.

  • A.1 Preimage differences and the decomposition: The two extended preimages differ by structured shifts in the x-, r-, and h-registers, with the h-register relation obtained by telescoping along each row.The terminal branch column restores the boundary condition at j = n + 1.
  • A.1 Preimage differences and the decomposition: The verifier’s parity splits into a secret-linear component ⟨a_b(D), s⟩ and a remaining term independent of the secret.The branch and terminal h-columns contribute to the branch-dependent offset β_b(D).
  • A.1 Preimage differences and the decomposition: For every sign, vector a, and predicate list, a polynomial-time computable transcript realizes the corresponding induced data on valid paired images.The realization holds for every supported (s, e), except on the trapdoor-failure event.
  • A.1 Preimage differences and the decomposition: The explicit construction chooses branch-dependent x, noise, path-mask, and direction data so both encoded relations hold by construction.It ensures the relevant domains contain x and x − χs and that the noise values remain in E.

A.2 Polynomial-time checkability and pointwise density

The admissibility predicate is deterministically checkable in polynomial time, and its sensitivity tests have pointwise failure probability 2^−Ω(n) without requiring joint independence.

  • A.2 Polynomial-time checkability and pointwise density: The predicate Adm is deterministic polynomial time because its tested bits require only polynomially many modular operations, canonical encodings, and binary inner products.The number of tested bits is O(n + mL).
  • A.2 Polynomial-time checkability and pointwise density: Each vector tested by the sensitivity condition is individually uniform; joint independence among these vectors is neither claimed nor needed.The proof conditions on other direction blocks and uses disjoint blocks to establish uniformity.
  • A.2 Polynomial-time checkability and pointwise density: The sensitivity tests fail with probability 2^−Ω(n) for every valid paired image, by applying concentration bounds across branches, signs, and shifts.A union bound remains valid despite correlations among the tests.
  • A.2 Polynomial-time checkability and pointwise density: The admissibility predicate does not increase quantum depth because the honest prover samples the direction uniformly using final Hadamards rather than conditionally sampling from the direction set.This preserves the shallow-circuit implementation while the predicate filters classical strategies.

A.3 Elementary attacks excluded by the balance tests

The balance tests exclude elementary strategies that cancel or localize the predicate’s dependence on the secret, including padding concentrated on few coordinates or rows. They also require sensitivity across many rows and scales, although these tests do not by themselves establish unpredictability.

  • Coordinate sensitivity: Carry cancellation is inadmissible when the predicate is locally constant or has nonzero derivatives in fewer than one third of either secret half.This rules out cancellations involving only a bounded number of secret coordinates and XOR padding by locally constant functions.
  • Coordinate sensitivity: The balance test prevents setting the linear coefficient to zero or concentrating it on a few selected coordinates.The terminal column cannot repair a failed test because its partial sum is public and it contributes only a known bit.
  • Row sensitivity: Row tests reject predicate lists supported outside the central columns or on only a few rows, because their row-sensitivity vectors fall below the balanced range.Lists supported only near the ends cannot be made admissible by padding with endpoint columns.
  • Row sensitivity: A fixed carry word can pass the row tests when placed on three quarters of the rows, forcing dependence on a constant fraction of rows at every tested scale.The tests enforce spread of dependence but do not ensure that this dependence is unpredictable.
  • Residual security gap: The construction’s remaining assumption allows jointly adaptive choices of the linear function, carry predicates, and base points after the public key is seen.The appendix establishes only restricted consequences, such as security against predictors that commit to base points and can be reset on uniform challenges.

B.1 The LWE assumption

The paper assumes a fine-grained, subexponential prime-modulus LWE regime and uses it to support key-mode indistinguishability and the ordinary adaptive-hardcore-bit property for the decoded family. These results provide partial evidence but do not establish the stronger carry-predicate assumption used in the main theorem.

  • Parameterization: The construction uses a binary secret of length n, while the assumption is stated for a uniform secret of dimension ℓ.The paper invokes a lossy-mode argument to relate the binary-secret ensemble to LWE at dimension ℓ.
  • Assumption: The LWE assumption states that no uniform quantum algorithm running in time at most 2^(ℓ^δLWE) distinguishes equation keys from image keys with non-negligible advantage.It applies to polynomially bounded sample counts and a prime modulus with quasipolynomial magnitude.
  • Parameterization: The parameter check verifies BCMVV Conditions A.1–A.4, including dimension requirements, the definition of BP, and superpolynomial noise gaps.The modulus is prime, as required by the BCMVV construction, and the statistical losses in the cited hybrids are negligible.
  • Consequences: Under the prime-modulus LWE assumption, both key-mode distinguishing advantage and the ordinary decoded adaptive-hardcore-bit advantage are negligible for uniform quantum polynomial-time algorithms.The reductions use BCMVV’s lossy-matrix hybrid and adaptive-hardcore-bit lemma with polynomial running-time overhead.
  • Scope: These consequences do not establish the stronger carry-predicate assumption, which admits carry bits of partial LWE sums.The appendix presents them as a standard-LWE basis for partial evidence rather than as a hypothesis of the main result.

B.2 The decoded relation

The decoded relation translates a chosen linear function of the binary secret into a direction and preimage pair for the decoded family. The construction guarantees compatibility on the selected branch while making the opposite-branch coefficient unlikely to vanish.

  • Game and direction set: The ordinary adaptive-hardcore-bit game lets the adversary choose a branch, preimage, direction, and predicted bit, with the partner preimage determined by the secret shift.The direction sets Gk,b,x restrict d to those whose induced coefficient is nonzero on the selected branch.
  • Fiber realization: A polynomial-time fiber-realization procedure maps any sign and target coefficient vector ϕ to a compatible branch, preimage, and uniformly sampled direction.The resulting preimages remain in their respective branch domains for every secret in the key-generation support.
  • Branch behavior: On zero secret coordinates, distinct nonzero opposite-branch words make the corresponding coefficients uniform, so the entire opposite-branch coefficient vanishes with probability at most 2^-z.A Chernoff bound gives z ≥ n/8 except with probability 2^-Ω(n).

B.3 Uniform independent challenges

The appendix reduces resettable prediction under uniform independent challenges to distinguishing equation keys from image keys. Goldreich–Levin reconstruction turns noticeable prediction correlation into a candidate secret, contradicting the LWE-based indistinguishability result.

  • Challenge experiment: Each challenge consists of a direction a and carry-bit data Dh, and the resulting prediction is a parity of the hidden string Z.Answering correctly corresponds to the carry-predicate game up to an inadmissibility event of probability 2^-Ω(n).
  • Predictor model: A resettable uniform-challenge predictor commits to a sign, base points, and restorable snapshot, then predicts one bit for each fresh challenge.Its advantage is the absolute expected correlation over the first-stage transcript.
  • Conclusion: Therefore every efficient resettable uniform-challenge predictor has negligible advantage under the prime-modulus LWE consequences.The result remains structurally weaker than the main carry-predicate assumption because it requires committed base points and reset access.
  • Reduction: Noticeable correlation µ yields a distinguisher with advantage at least µ/3 minus negligible error.The reduction uses reset access and Goldreich–Levin list decoding to recover a candidate secret.
  • Reduction: The distinguisher accepts a recovered candidate when its residual against the public key has centered infinity norm at most BV.On equation keys the true candidate passes with probability at least µ/3, while on image keys the acceptance probability is negligible.

B.4 High-min-entropy equation samplers

This section formalizes high-min-entropy equation samplers and shows that sufficiently random, mostly correct equations can be converted into an adaptive-hardcore-bit attack, ruling out such efficient samplers.

  • Definition: High-min-entropy samplers bound each conditional challenge probability by 2^-NZ+κent and each equation error probability by ε.The bounds hold for every transcript and positive-probability history, using worst-case conditional min-entropy.
  • Reduction: Proposition B.7 converts a resettable sampler with bounded deficiency and equation error into an ordinary decoded-family adaptive-hardcore-bit adversary.The reduction collects sampled equations, checks rank and consistency, and uses Gaussian elimination to obtain an affine solution space containing the true string.
  • Consequence: For δrk = 2^-n/8, T = O(NZ), and Proposition B.2 rules out efficient resettable samplers satisfying the stated conditions.The conclusion applies whenever the resulting quantity in Equation (27) is non-negligibly positive.
  • Advantage bound: The reduction’s signed advantage is controlled by rank failure, equation error, and direction-condition failure, with βfail = δrk + Tε and γdir bounded explicitly.On the success event, direction failures contribute at most γdir; otherwise the reduction’s output contributes zero or at least −1 as specified.
  • Scope: The result tolerates entropy deficiency of up to n/4 bits, while allowing successive challenge distributions to depend on preceding equations.The equations themselves must remain correct with overwhelming probability.

B.5 Linear predicates

This section treats linear predicates as a restricted case of the carry-predicate framework and proves that sufficiently biased linear samplers yield adaptive-hardcore-bit adversaries.

  • Linear case: With empty predicate lists, the predicted bit is linear, and the carry-predicate assumption reduces to the linearity condition.The case with no carry predicates follows from Assumption B.1 at the security level of Proposition B.2.
  • Empty predicate lists: Proposition B.8 shows that quantum algorithms with empty predicate lists have negligible signed advantage under Assumption B.1.The reduction checks admissibility publicly, realizes the fiber, and incurs only 2^-n/8 + 2^-Ω(n) error in transferring the advantage.
  • Definition: A linear sampler outputs a challenge vector and equation bit whose joint distribution is otherwise arbitrary, with error allowed to depend on the challenge vector.The sampler is defined using uniform polynomial-time classical algorithms and a copyable snapshot.
  • Biased samplers: Proposition B.10 converts a biased linear sampler into an ordinary decoded-family adaptive-hardcore-bit adversary with an explicit signed-advantage lower bound.The proof uses one sampler invocation and filters according to direction conditions; min-entropy bounds the probability of an inadmissible challenge.
  • Open scope: The complementary results leave open the fully adaptive game, where linear functions, predicate lists, and base points may be chosen jointly and used once.The other results respectively require reset access, many correct equations for one snapshot, or empty predicate lists.

C Parameters for the Encoded Construction

This section establishes parameter estimates for the encoded construction, including separated noise scales, negligible completeness errors, no-wrap conditions, trapdoor radii, and register sizes.

  • Noise hierarchy: For sufficiently large λ, the noise scales satisfy BL < BV < BP, with both successive ratios superpolynomial in λ.These are the two noise-gap conditions used in the BCMVV construction.
  • Completeness and wrap-around: The completeness error mBV/W + 2n/Q is negligible in λ.The parameter estimates also establish interval overlap and no wrap-around through 2BV < W and 2W + 2BV < q.
  • Trapdoor uniqueness: The trapdoor-uniqueness bounds place centered noise vectors and their key-error shifts within radius rG.The estimates include √m BV < rG and corresponding Euclidean-norm bounds for centered vectors.
  • LK-1/4 radius: The LK-1/4 radius condition ensures ||centerq(η)||∞ ≤ 1 for every generated matrix K and η ∈ Em.This is the inequality used in Lemma 6.15.
  • Completeness and wrap-around: The no-wrap inequalities are deterministic conditions rather than completeness-error terms.For sufficiently large λ, they imply 2BV < W and 2W + 2BV < q.
  • Register sizes: The main register lengths are nL = Θ(λ^2 log^2 λ), mL = Θ(λ^2 log^4 λ), and mnL = Θ(λ^4 log^4 λ).The final quantity is, up to a constant factor, the number of qubits in the source and output registers of Lemma 6.13.
Loading 2609.01448v1…