Interactive shallow Clifford circuits: quantum advantage against NC$^1$\n and beyond
Bibliographic record
Abstract
Recent work of Bravyi et al. and follow-up work by Bene Watts et al.\ndemonstrates a quantum advantage for shallow circuits: constant-depth quantum\ncircuits can perform a task which constant-depth classical (i.e., AC$^0$)\ncircuits cannot. Their results have the advantage that the quantum circuit is\nfairly practical, and their proofs are free of hardness assumptions (e.g.,\nfactoring is classically hard, etc.). Unfortunately, constant-depth classical\ncircuits are too weak to yield a convincing real-world demonstration of quantum\nadvantage. We attempt to hold on to the advantages of the above results, while\nincreasing the power of the classical model.\n Our main result is a two-round interactive task which is solved by a\nconstant-depth quantum circuit (using only Clifford gates, between neighboring\nqubits of a 2D grid, with Pauli measurements), but such that any classical\nsolution would necessarily solve $\\oplus$L-hard problems. This implies a more\npowerful class of constant-depth classical circuits (e.g., AC$^0[p]$ for any\nprime $p$) unconditionally cannot perform the task. Furthermore, under standard\ncomplexity-theoretic conjectures, log-depth circuits and log-space Turing\nmachines cannot perform the task either.\n Using the same techniques, we prove hardness results for weaker complexity\nclasses under more restrictive circuit topologies. Specifically, we give\nQNC$^0$ interactive tasks on $2 \\times n$ and $1 \\times n$ grids which require\nclassical simulations of power NC$^1$ and AC$^{0}[6]$, respectively. Moreover,\nthese hardness results are robust to a small constant fraction of error in the\nclassical simulation.\n We use ideas and techniques from the theory of branching programs, quantum\ncontextuality, measurement-based quantum computation, and Kilian randomization.\n
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.003 | 0.015 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.002 | 0.006 |
| Scholarly communication | 0.004 | 0.013 |
| Open science | 0.003 | 0.007 |
| Research integrity | 0.003 | 0.005 |
| Insufficient payload (model declined to judge) | 0.014 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".