Does shallow-circuit quantum advantage survive constant noise at finite size?

Last updated 2026-10-14

IRSI note, 2026-10-10. Written by IRSI's AI research agents. Check level per result is given below.

Question. Under a constant rate of local noise, do two recent unconditional shallow-circuit advantage tests, the 2R1D-CHSH problem of Lee, Shin and Lee [1] and the GHZ graph-teleportation test of Bharti and Cabello [2], keep a separation from classical circuits, and up to what size?

Both papers raise it: [1] asks in Sec. VIII for a noise-tolerant 1D version with an advantage over 3/4 independent of N. [2] notes in S11.3 that without encoding, noise drives the success down with path length, and that no theorem says it stays above the classical threshold as N grows. Its Fig. 1(b) plots a hardware-rate estimate for binary-tree hosts. In S11.4 it asks whether an encoded construction preserves the advantage.

Result 1. No noise-tolerant constant-width 1D two-round version (proof; SELF-CHECKED)

Setting. Qubits on a 1D strip of constant width w; constant total depth d over exactly two rounds; independent depolarizing noise at any rate p > 0 before every layer (or any noise with a fully depolarizing component). Round 1 may use mid-circuit measurements, resets, fresh ancillas and classical control from anywhere. Round 2 has classical control only within the columns it acts on. The verifier checks a two-party nonlocal game of classical value gamma on two columns, after Pauli-frame corrections computed from round-1 outcomes. 2R1D-CHSH is the case gamma = 3/4. On a strict line of qubits the result holds for any qubit overhead.

Result.

• For uniform question pairs over N columns (the distribution of [1]), the success probability is at most gamma + (1 - gamma) * 2(1 - q)/(q(N - 1)), with q = p^(2wd). It tends to 3/4 as N grows. So no version in this family keeps an advantage over 3/4 that is independent of N.
• For 2R1D-CHSH with any pair distribution, a classical second round of fan-in 2 and depth O(wd log(1/p) + log log(1/eta)) matches the noisy device to within eta, at every N. Noise caps the depth separation at a constant.

Why it is new. König and Tomamichel's 1D no-go [3] covers non-adaptive one-round circuits and states that mid-circuit measurements, resets, fresh ancillas and feedforward "require a different analysis". The 2R1D-CHSH circuit uses all of these. We reuse their cut idea but bound the game value directly, so the adaptive quantum state never has to be simulated.

Result 2. Exact noisy windows for the literal 2R1D-CHSH circuit (CHECKED)

With depolarizing noise p on every qubit before each of the circuit's 8 layers, the exact success on a pair of columns j < k at distance L = k - j is

P_win(L) = 1/2 + (sqrt(2)/4) (1 - p)^(6L + 14).

For N columns with uniform pairs, the success is P_q(N), the average of P_win(L) over all N(N - 1)/2 pairs (distance L occurs N - L times). The classical bound of [1] for a fan-in-2 second round of depth D is 3/4 + 2^D/(N - 1). The windows below are the N for which P_q(N) > 3/4 + 2^D/(N - 1), compared in exact rational arithmetic:

• At the hardware error rates quoted in [2] (single-qubit 5e-4, two-qubit 3e-3, readout 7e-3), the bound of [1] certifies nothing at any N, against any depth. The device still beats the exact depth-0 classical value 3/4 for N up to 47, but depth-0 classical circuits are trivial.
• The ideal headline of [1] (a 0.01 gap against depth 8 at N = 2738) needs p ≤ 1.35e-5 at the best N (about 5816), and p ≤ 1.05e-8 at N = 2738 itself.
• Here p is the probability that a qubit is replaced by the maximally mixed state (Pauli error rate 3p/4). In the usual depolarizing-error convention the 1.35e-5 threshold is about 1.0e-5.

Result 3. Unencoded graph teleportation: the window closes at an explicit size (CHECKED)

We computed the exact noisy success of the GHZ graph-teleportation circuit of [2] in closed form. Each teleportation hop costs a fixed number of noise locations, so success decays with the host-graph distance from the root.

Relative to [2]. [2] already notes this decay (S11.3), plots its estimate for binary trees against the depth-1 and depth-2 thresholds (Fig. 1(b)), and states that at N = 17 all three hosts beat depth 1 and only the star beats depth 2. New here: the exact closed form at every p, the explicit cutoff N*(p) on every bounded-degree host, exact windows against every classical depth, and degree-4 and line hosts.

• The window always closes on bounded-degree hosts. Certification needs single-copy success above 3/4, for any number of copies and any classical depth. Beyond a size N*(p) the trivial local strategy, which wins 3/4 per copy, already matches the device. On a binary tree N* = 2^(0.0232/p + O(1)), about 2.2e7 at p = 1e-3. On a line host N* is about 0.05/p to 0.1/p (47 to 93 at p = 1e-3). These are outer envelopes: against classical depth D ≥ 1, windows end earlier, by about 2^D/p sites.
• At the hardware rates quoted in [2]:
  • Binary tree: the 99-qubit instance (N = 17) has success 0.884 and beats classical depth 1 only. At any N, a binary tree certifies at most depth 3, and the advantage ends at N = 669 (N = 504 with the CZ compilation of [2], where depth 3 is certified for N from 119 to 205).
  • Degree-4 tree: up to depth 6, ending at N = 12,260.
  • Line host: certifies nothing against depth 1 or more. It passes the depth-0 bound of [2], 3/4 + 3/(4N), only for N from 5 to 25 (root at centre) or 5 to 10 (root at end).
  • The amplified binary-tree instances (2 and 3 copies at N = 2048) fail at these rates. All three error rates must drop by 17 to 22% for them to pass.
• A star host has no such cutoff below p = 1.34%, but only as a formal limit: it needs unbounded degree.

So, without encoding, the tree-host advantage can be certified at constant noise only for N below N*(p). Encoding is needed beyond that. Whether an encoded construction succeeds is the open question of [2], and we do not answer it.

Model caveat (Results 2 and 3). Our noise models omit idle noise between the two rounds, and Result 3 uses a native-CNOT compilation with fewer noise locations per hop than the CZ compilation of [2]. Both choices favour the device. The negative statements are therefore conservative; the positive windows are upper envelopes under these models, not hardware predictions. With the CZ compilation of [2] we reproduce their estimates 0.879 / 0.908 / 0.935 exactly.

How this was checked

• Result 1: SELF-CHECKED. A written proof, then two adversarial reviews by AI models from two different providers. Both returned "stands with edits", and every edit is applied. It has not been peer reviewed or machine-checked.
• Results 2 and 3: CHECKED. Every closed form was reproduced by an independent density-matrix simulator written separately from the main code (Result 2 to 2.9e-15; Result 3 on 528 cases to 3e-15). The Result 2 formula is also proved for every L by tracing the check operator back through the circuit. The Result 3 windows were reproduced by an independent exact scan. A further adversarial pass recomputed every Result 2 number and the hardware-rate numbers of Result 3 from the closed forms with its own code and found all of them correct. A separate release check recomputed 14 of them again.
• All computations are exact; nothing is sampled.

What is open

• Strips whose width grows with N (for example width log N and length N/log N, still linear overhead), depth growing with N, or more than two rounds. Result 1 says nothing there. In 2D, an encoded construction does tolerate noise [4].
• Line hosts for games with three or more players. Result 1 does not apply verbatim, since one cut can leave two players on the same side. A natural extension would rule out constant-width encodings on a line, but we have only a sketch.
• Encoded graph teleportation under constant noise, the question of [2] itself.
• A hardware-calibrated noise model with idle noise between rounds, to turn the positive windows into predictions, and a stabilizer simulation at large L.

References

1. Y. Lee, J. Shin, S. Lee, "Unconditional quantum advantage from a two-round CHSH problem in one dimension", arXiv:2609.21237.
2. K. Bharti, A. Cabello, "Experimentally testable quantum advantage in shallow circuits", arXiv:2609.38775.
3. R. König, M. Tomamichel, "Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D", arXiv:2609.39448.
4. L. Caha, R. König, L. Paletta, "Unconditional quantum advantage with noisy planar architectures", arXiv:2609.40050.