Experimentally Testable Quantum Advantage in Shallow Circuits

AI summary

Overview

• Research area: Quantum information science, specifically unconditional quantum advantage in shallow (constant-depth) circuits, nonlocal games, and experimental benchmarking of quantum processors.
• Technical level: Intermediate. The core ideas are accessible with a basic grasp of quantum circuits and nonlocal games; the full proofs in the Supplemental Material are advanced.
• Scope (1 sentence): The paper sharpens a finite-size classical soundness bound for a graph-distributed shallow-circuit construction and uses it to specify a two-round, single-processor test of quantum advantage with explicit thresholds, including a 99-qubit GHZ proposal.

What This Paper Is About

Claims of quantum advantage must state which classical computational model is being ruled out, and existing shallow-circuit separations such as Bravyi–Gosset–König give guarantees only for sufficiently large instances, while nonlocal-game tests on a single processor rely on a no-communication assumption that spacelike separation does not enforce. The authors turn a graph-distributed construction (Aasnæss) into a finite, experimentally specified test: play many disjoint copies of a game, teleport each player's register to a uniformly random site before the questions are revealed, and bound the chance that a depth-limited classical circuit can exploit cross-player dependencies. The goal is a test where the ideal quantum device wins with certainty, the classical success probability has an explicit closed-form bound that can be made arbitrarily small, and the acceptance rule works for a finite number of trials.

Key Contributions

1. Linear-in-players collision bound. The finite-size classical soundness bound of Aasnæss's graph-distributed construction is refined from quadratic to linear dependence on the number of players, changing published estimates such as min{1, b²K^D/N} into min{1, a b K^D/N}.
2. A two-round, single-processor protocol. Standard disjoint-player repetition is combined with teleporting every player's register to one of N uniformly random sites before question reveal, yielding the explicit bound p_c ≤ γ^m + (1 − γ^m) min{1, a b K^D / N} for any finite game with a finite-dimensional perfect quantum strategy and classical value γ < 1.
3. Asymptotic and tightness results. With m = ⌈log_{1/γ} N⌉ the bound becomes O(log N / N) and vanishes for D = o(log N) at fixed K; classical depth Ω(log N) is shown necessary for any fixed positive success probability, and depth O(log N) suffices to win with certainty.
4. A concrete experimental proposal and certification rule. A 99-qubit GHZ instance (m = 1, N = 17) with thresholds 57/68 ≈ 0.8382 (depth one) and 63/68 ≈ 0.9265 (depth two), multi-copy instances with thresholds below 3/4, a noise-model estimate, and a Hoeffding-based acceptance rule.

Main Findings

• Classical soundness bound: For a game with b₀ players, at most a answer bits per player, and classical value γ, every randomized classical device whose online response has depth D and fan-in K wins with probability p_c ≤ γ^m + (1 − γ^m) min{1, a b K^D / N}, where b = b₀m. The proof counts question blocks that can influence each answer via backward lightcones (at most aK^D input wires) and takes a union bound over the b targets.
• Vanishing classical success: Choosing m = ⌈log_{1/γ} N⌉ gives γ^m ≤ 1/N and p_c ≤ [1 + a b₀ K^D (log_{1/γ} N + 1)] / N, which is O(log N / N) at fixed depth and tends to zero for every D = o(log N) at fixed K.
• Quantum completeness: The ideal quantum device starts in a product state, has constant depth in each of two rounds, and wins with probability one. For Pauli measurements the frame correction is a classical bit flip, r ⊕ B ⊕ Ax, so no quantum feed-forward is required.
• Depth tightness: A classical circuit of fan-in two and depth O(log N) wins with certainty by collecting each sparse question through an OR tree, so the classical depth scaling Θ(log N) is tight up to constants in this amplified regime; optimality of the finite winning-probability bound is not claimed.
• 99-qubit thresholds exceed the base game value: The m = 1, N = 17 instance has 99 qubits and thresholds 57/68 ≈ 0.8382 (D = 1) and 63/68 ≈ 0.9265 (D = 2). Both exceed the GHZ value 3/4 because the competitor may wire all 51 sites together.
• Multi-copy instances: For m = 2 the base classical value drops from 3/4 to 9/16 before the finite-N correction; at N = 512 the thresholds are 0.573 for depth one and 0.583 for depth two.
• Table 1 values: The table lists, among others, m = 1, N = 17, Q = 99 with thresholds 0.8382 (D = 1), 0.9265 (D = 2), 1, 1; m = 1, N = 64, Q = 381 with 0.7734, 0.7969, 0.8438, 0.9375; m = 2, N = 256, Q = 3066 with 0.5830, 0.6035, 0.6445, 0.7266; m = 2, N = 512, Q = 6138 with 0.5728, 0.5830, 0.6035, 0.6445; and m = 3, N = 2048, Q = 36855 with 0.4270, 0.4320, 0.4422, 0.4625.
• Qubit count formula: For a tree host with N vertices per player, the register has Q = 3m(2N − 1) qubits (3m game qubits plus one Bell pair per edge, excluding readout ancillas and routing overhead).
• Host geometry matters for noise: At N = 17 the balanced binary tree has mean path length 42/17 ≈ 2.5, a degree-four tree of depth two (1 + 4 + 12 vertices) has 28/17 ≈ 1.6, and a star has one hop for every non-root site.
• Correlator requirements: The winning probability is (1 + V)/2, so the depth-one threshold requires V > 23/34 ≈ 0.6765, the depth-two threshold requires V > 29/34 ≈ 0.8529, and a target winning probability of 0.96 requires V ≈ 0.92. For a measured preparation-and-readout visibility V₀ = 0.95, the attenuation model gives about 0.4% correlator attenuation per teleportation for the binary tree and about 1% for the star.
• Noise-model estimates: Using gate and readout error rates from Ref. [40], the model gives success probabilities of 0.879 for the 99-qubit binary tree, 0.908 for the degree-four tree, and 0.935 for the star, before additional idling and routing errors. All three exceed the depth-one threshold; the star estimate also exceeds the depth-two threshold. These are model estimates, not measured scores.
• Certification: For independent identically distributed trials, Hoeffding's inequality gives L_α = p̂ − sqrt(ln(1/α)/(2M)), and advantage is certified when L_α > B_c. At 99% confidence, an observed fraction of at least 0.96 on the 99-qubit instance exceeds the depth-one threshold with 156 trials, and a fraction of at least 0.94 does so with 223 trials; the corresponding depth-two counts are 2049 and 12580. A margin of 0.03 above a declared threshold requires 2559 trials.
• Losses and postselection: A missing outcome, leakage event, timeout, or unheralded loss counts as a loss; no postselection is used, and any postselected acceptance rule would have to be declared in advance with Eq. (2) rederived.
• Scope limitations: The test assumes a trusted verifier and an implementation satisfying the stated circuit restrictions; it is not device independent. The ideal theorem is noiseless and gives no fault-tolerance threshold, since a constant error per hop degrades the winning probability with path length.

Methodology in Plain English

The authors start from a "pseudo-telepathy" game: a finite game with a classical winning probability γ strictly below one but a perfect quantum strategy, such as the three-player GHZ game with (ω_c, ω_q) = (3/4, 1). They first play m copies of that game with completely disjoint sets of players, so the classical winning probability becomes exactly γ^m while the quantum players still win every copy. Second, they add a teleportation layer: each player's quantum register is moved through Bell pairs to one uniformly random site out of N, and the questions are only revealed after the Bell measurement outcomes are recorded and delivered to those sites. The classical competitor is allowed arbitrary fixed wiring, unlimited shared randomness, and unlimited pre-question computation, but its response from the question wires to the answer wires is limited to depth D and fan-in K. The key observation is that any single answer bit in such a circuit can depend on at most K^D input wires, so the chance that a player's randomly chosen site overlaps another player's question wires is at most aK^D/N; a union bound over all players gives the collision probability, and when no collision occurs the answers are a local strategy worth at most γ^m. The bound is then converted into a practical acceptance test by running M trials fixed in advance and comparing a one-sided confidence lower bound on the observed winning frequency against the declared threshold.

Why This Matters

The paper converts an asymptotic shallow-circuit separation into a finite, falsifiable protocol with explicit numbers, which is what experimentalists need to make a defensible advantage claim on a single processor. It replaces the no-communication assumption of Bell and GHZ tests with a depth restriction on a globally wired classical competitor, and it removes the restriction of earlier game-based benchmarks to the quantum device's own connectivity or to isolated players.

Potential applications (the paper itself does not report deployed applications):

• Processor benchmarking and acceptance tests: using the winning-frequency threshold as a hardware milestone with a predeclared statistical rule.
• Certifying nonclassical correlations on a single device: testing correlations without requiring spacelike separation between players.
• Error-budget planning for teleportation-based architectures: the per-hop attenuation targets (about 0.4% for the binary tree, about 1% for the star) translate circuit-noise requirements into hardware specifications.
• Guiding architecture choices: comparing host graphs such as binary trees, degree-four trees, and stars by mean path length and predicted success probability.

Industry relevance: The work targets near-term device sizes (a 99-qubit instance is the headline proposal) and is framed around the practical constraints of quantum hardware, with one author affiliated with IonQ Inc. It gives hardware teams a concrete, predeclared pass/fail criterion rather than a complexity-theoretic statement about asymptotically large circuits.

Future Directions

• A one-round version for general measurements, which would simplify the experimental sequence and remove the two-round structure.
• Separations from stronger classical classes such as AC⁰ using switching-lemma methods.
• Small-input perfect games with classical values well below 3/4, which could reduce the resources required relative to the contextuality construction in Fig. S1.
• Fault-tolerant encoded constructions such as Ref. [10], needed to reach the m = Θ(log N) regime at constant physical noise, since the ideal theorem gives no fault-tolerance threshold and a constant error per hop degrades the winning probability with path length.

Target Audience

Quantum information researchers working on shallow-circuit separations and nonlocal games; experimentalists designing benchmarks for intermediate-scale processors; complexity theorists interested in unconditional separations from bounded-depth classical circuits; and hardware teams who need explicit, predeclared thresholds and trial counts for an advantage claim. Readers seeking a device-independent security result or a fault-tolerance threshold will not find one here, as the authors state both limitations explicitly.

Authors’ abstract

Experimental tests of shallow-circuit quantum advantage require explicit classical bounds at finite circuit sizes. We refine the finite-size classical soundness bound of Aasnaess's graph-distributed construction to depend linearly on the number of players. Combined with standard disjoint-player repetition, this gives a two-round test on a single processor for any finite nonlocal game with a finite-dimensional perfect quantum strategy and classical winning probability $γ&lt;1$, with arbitrarily small classical success. The method is based on playing $m$ copies with disjoint players and teleporting each player's register to a uniformly random one of $N$ sites before the questions are revealed. Each answer bit of a depth-$D$, fan-in-$K$ classical response with fixed wiring depends on at most $K^D$ question wires, making cross-player dependencies unlikely when $N$ is large. The quantum implementation has constant depth per round and wins with certainty. A classical device wins with probability at most $γ^m+O(mK^D/N)$, which vanishes as $O(\log N/N)$ for $m=\lceil\log_{1/γ}N\rceil$ at fixed $D$ and $K$. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.