Pith. sign in

REVIEW 1 major objections 5 minor 10 cited by

The vast world of quantum advantage

T0 review · 1 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that some genuine quantum advantages cannot be detected by any efficient classical algorithm, assuming quantum computers are truly more powerful than classical ones, and that the act of predicting a quantum advantage is it

desk verdict A perspective with a genuinely new conditional meta-complexity theorem; the main gap in the written proof is real but fixable, and the abstract overstates it. read the letter →

arxiv 2508.05720 v2 pith:UT6VXELE submitted 2025-08-07 quant-ph cs.CCcs.ITmath.IT

Hsin-Yuan Huang , Soonwon Choi , Jarrod R. McClean , John Preskill This is my paper · ORCID
classification quant-phcs.CCcs.ITmath.IT MSC 68Q1281P68 PACS 03.67.-a
keywords quantumadvantagemeta-complexityBQPBPPPaulipropagationclassicalsimulationheuristicssensingverifiability
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is a perspective on how to recognize quantum advantages, organized around five keystone properties—predictability, typicality, robustness, verifiability, and usefulness—and a survey of advantages in computation, learning and sensing, cryptography and communication, and memory. Its main theorem states that, assuming BPP≠BQP, the problem of deciding whether a given quantum circuit beats a standard classical simulation heuristic is itself in BQP but not in BPP. That means some genuine quantum advantages cannot be certified by classical computation; the act of predicting quantum advantage requires quantum computation. The authors use this to argue that the full landscape of quantum advantage is richer and more surprising than current classical theory can foresee.

What carries the argument

The low-weight Pauli propagation heuristic is the classical baseline: it evolves an observable backward through the circuit and truncates to Pauli operators of weight at most 1. The proof's other ingredients are random two-qubit circuit layers that form approximate unitary 2-designs, and Lemma 1, which says that one layer of backward propagation shrinks the expected squared Frobenius norm of the truncated observable by exactly 2/5, so after enough layers the heuristic produces exponentially small outputs. A coherent majority vote of the BQP circuit controls whether the random unitary is applied or cancelled, creating the YES/NO separation on which the hardness reduction rests.

What would settle it

Sample many instances of an L-layer random two-qubit brickwork circuit, run LowWeightPauliProp with k=1 on the observable Z_1, and record the squared Frobenius norm of the truncated backward-evolved operator; if its average over circuits deviates from (2/5)^L or if the fraction of circuits with norm above $2^{{-L/2}}$ does not decay exponentially, Lemma 1 fails. Also check directly whether the omitted high-weight Pauli components contribute significantly to the true expectation value for the constructed circuit C_new on NO instances.

Watch

Extended reading notes

Core claim

The paper's central proof result is that the decision problem DetectingQuantumAdvantage—which asks whether a given quantum circuit's output statistics differ from the predictions of the low-weight Pauli propagation heuristic on a typical input—is solvable in quantum polynomial time but not in classical polynomial time unless BPP=BQP. In other words, if quantum computers are genuinely more powerful than classical ones, then the task of telling a genuine quantum advantage from a pseudo-advantage is itself a problem with a quantum advantage. The proof takes any BQP decision problem, amplifies it by a coherent majority vote, and splices it into a random scrambling circuit so that YES instances m

Load-bearing premise

The proof assumes that one step of weight-1 Pauli propagation shrinks the expected squared Frobenius norm of the observable by exactly 2/5 per random two-qubit layer; if that constant is wrong or does not concentrate well enough, the heuristic's outputs on the constructed circuits would not be uniformly small and the YES/NO separation used to prove classical hardness collapses.

Editorial extensions

If this is right

  • Under BPP≠BQP, no polynomial-time classical algorithm can reliably certify absence of quantum advantage relative to a heuristic whose failure set is unknown; the certification problem itself is quantum.
  • A quantum computer can detect such an advantage by sampling a constant number of random inputs, comparing measured output probabilities with the heuristic's predictions, and applying a Chernoff bound.
  • The meta-complexity message extends beyond LowWeightPauliProp: any classical heuristic with unknown failure set inherits the hardness, so claims that a circuit is classically simulable should be treated as conjectural unless backed by quantum sampling.
  • For sensing, entanglement-based Heisenberg-limited sensitivity is not robust to generic local noise; separable strategies achieve the optimal scaling, meaning robustness must be part of any claimed sensing advantage.
  • The five keystone properties give a checklist for evaluating whether a proposed quantum advantage is likely to survive noise, apply to typical instances, and deliver practical value.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: Lemma 1's contraction constant 2/5 should be measurable in small random brickwork circuits; if its decay rate departs from (2/5)^L, the theorem's gap would need a different heuristic analysis.
  • Editorial extension: If detecting advantage is hard for every classical heuristic, then quantum computers may be needed to audit classical simulation software, shaping benchmarking protocols for near-term quantum processors.
  • Editorial extension: The theorem suggests a hierarchy of meta-advantages—achieving a quantum advantage can be easier than recognizing or verifying one—so 'useful quantum utility' claims may require quantum-assisted verification.
  • Editorial extension: Analogous detection problems for other quantum resources, such as quantum memory in learning or entanglement in communication, might exhibit similar classical unpredictability, extending the argument beyond computation.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. This perspective paper proposes five keystone properties for assessing quantum advantages (predictability, typicality, robustness, verifiability, usefulness), surveys four realms of quantum advantage, and discusses empirical and conceptual forms of future advantage. Its technical center is Theorem 4 (Appendix D), formalizing the informal Theorem 1: for the fixed classical heuristic LowWeightPauliProp with k=1, the promise problem DetectingQuantumAdvantage—decide whether a given circuit disagrees with the heuristic by at least 1/3 on at least 2/3 of inputs—is in BQP and, assuming BPP≠BQP, is not in BPP. The proof constructs an amplified BQP instance, appends a random circuit U with a controlled inverse, and shows that for YES instances the true expectation of Z1 is essentially ±1 while the heuristic estimate decays as (2/5)^L; for NO instances the true expectation is pseudo-random while the heuristic remains tiny. The paper also contains self-contained material on noisy quantum sensing (Appendix B) and a survey of classical simulation heuristics (Appendix C).

Significance. If the main theorem is correct after repair, it is a substantive meta-complexity-style result: detecting advantage over a specific classical simulation heuristic is itself quantumly easy and classically hard, conditional on BPP≠BQP. The paper is explicit that this is a conditional separation and that it concerns a promise decision problem, not a property of every individual circuit. The reduction is well structured and largely elementary. I checked the key contraction estimate in Lemma 1: the claimed 2/5 factor per random two-qubit gate layer follows from the Weingarten calculation in Eqs. (D.22)–(D.25), so the reader's flagged concern about Lemma 1 is not the main weakness. The broader ‘unpredictability’ rhetoric in Section IV.C should be read with the formal theorem's caveats, but as a conditional separation the result is interesting and appropriate for a perspective aiming to connect complexity theory with the quantum-advantage debate.

major comments (1)
  1. [Appendix D, Step 3 (NO case), Eqs. (D.6)–(D.7) and (D.40)] The NO-case separation is not rigorously established as written. The text asserts that because U is an approximate unitary 2-design, |<x|U†Z1U|x>| ≤ 1/poly(n) with high probability, and then concludes that this holds for any input bitstring x. This does not follow: for a fixed x, a 2-design controls the first two moments of Y_x = <x|U†Z1U|x>, giving P(|Y_x| > 1/poly(n)) = O(poly(n)/2^n); a union bound over all 2^n inputs yields only constant failure probability, not a high-probability uniform bound. Inequality (D.40) relies on this uniform bound, and the NO case collapses without it. The gap is repairable: the 2-design property gives E_U[(1/2^n)Σ_x |Y_x|^2] ≈ O(1/2^n). By Markov over U, with probability at least 1−1/poly(n), the fraction of x with |Y_x| ≥ 1/3 is at most 9/poly(n) < 1/3, which is all that Definition 7's ‘no advantage’ condition requires. The proof should be revised to use
minor comments (5)
  1. [Eq. (D.22)] The Weingarten calculation is correct, but the step is quite terse. A short derivation or an explicit citation to the precise second-moment formula for Haar-random two-qubit unitaries would make the lemma easier to verify.
  2. [Appendix D, Step 1] The paper states that depth L linear in n gives an ε=O(1/2^n)-approximate unitary 2-design, citing [19, 132, 133]. Since the proof later chooses L > 6(n+mℓ+1), please state explicitly the metric for the approximation and the required depth dependence (including constants), so that the choice of L is visibly compatible with the cited results.
  3. [Theorem 1 and Section IV.C] The informal theorem and the discussion of ‘unpredictable quantum advantages’ should be careful to say that the formal result concerns a promise decision problem about a fixed classical heuristic (LowWeightPauliProp with k=1), not an intrinsic property of every quantum circuit or all conceivable classical methods. The current wording is acceptable for a perspective but could mislead readers outside complexity theory.
  4. [Appendix D, Quantumly Easy part] The BQP upper bound assumes that LowWeightPauliProp with k=1 can be evaluated classically in polynomial time for arbitrary polynomial-size circuits. This is true but should be stated explicitly, since Appendix C's runtime theorem is stated only for locally scrambling circuit ensembles.
  5. [Definition 7 and Step 4 of the BQP algorithm] The sampling step uses the 2/3 versus 1/3 gap correctly, but the presentation would be clearer if it explicitly noted that the promise excludes the intermediate regime and that the Chernoff bound applies to the estimated fraction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central conditional theorem is derived from in-paper lemmas plus an external BPP≠BQP conjecture; self-citations are not load-bearing.

full rationale

The paper's central original claim is Theorem 4 / informal Theorem 1: assuming BPP≠BQP, DetectingQuantumAdvantage is in BQP but not in BPP. The proof is essentially self-contained in Appendix D. The BQP upper bound directly evaluates the defining predicate: it samples inputs, computes the classical heuristic's prediction from the circuit description, estimates the true output probability on a quantum computer, and compares. This is a direct check of the definition, not a fitted parameter renamed as a prediction. The classical-hardness direction constructs, from any BQP circuit C?, a new circuit C_new whose YES/NO status is separated by the heuristic's success/failure; the separation rests on Lemma 1 (an in-paper Weingarten calculation giving the 2/5 Frobenius-norm decay per layer), Lemma 2 (projection does not increase the Frobenius norm), and the standard random-circuit 2-design property. The 2-design property is cited to [19,132,133]; although [19] includes a present author, [132] and [133] are independent, and the property is a standard external result, so this citation is not load-bearing self-citation. Theorem 3 of Appendix C is cited to [40] (which includes a present author), but that theorem only motivates the heuristic; the proof of Theorem 4 does not invoke it, so it is not load-bearing. The noisy-sensing Theorem 2 is proved from an independent Demigod/classical-hypothesis-testing argument. The only caveats are non-circular: the theorem is conditional on BPP≠BQP, an external conjecture; and the NO-case uniform bound at (D.6)-(D.7) contains a technical gap (a 2-design controls fixed-x moments, and the union bound over all x is not spelled out), which is a correctness/rigor issue, not a circular reduction to the paper's own inputs. The paper's phrase 'profound circularity' in Section IV.C is rhetorical, not an admission of a methodological circularity. No equation is shown to be equivalent to its own input by construction, and no fitted value is relabeled as a prediction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The result has no fitted parameters and no invented physical entities. It rests on the unproven conjecture BPP≠BQP, on standard 2-design results, and on the paper's own Weingarten-based contraction lemma. The 'Demigod' in Appendix B is a proof device, not a new entity.

assumptions (3)
  • domain assumption BPP ≠ BQP
    The theorem's separation is conditional on this unproven conjecture, stated in Theorem 1 and Theorem 4.
  • standard math Random circuits of depth L form approximate unitary 2-designs
    Used in the NO case to bound <x|U†Z1U|x>; cited to Refs. [19,132,133].
  • standard math Lemma 1 Weingarten contraction factor (2/5) for weight-1 Pauli propagation through Haar-random 2-qubit layers
    Derived in Appendix D using Haar integration, but the key expectation (eq. D.22) is quoted without derivation; it is the quantitative engine of the hardness proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The vast world of quantum advantage." pith.science (2026). https://pith.science/paper/UT6VXELE

@misc{pith2026250805720,
  author       = {Pith},
  title        = {Pith review of: The vast world of quantum advantage},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UT6VXELE}},
  note         = {Machine review of arXiv:2508.05720}
}
read the original abstract

The quest to identify quantum advantages lies at the heart of quantum technology. While quantum devices promise extraordinary capabilities, from exponential computational speedups to unprecedented measurement precision, distinguishing genuine advantages from mere illusions remains a formidable challenge. In this endeavor, quantum theorists are like prophets attempting to foretell the future, yet the boundary between visionary insight and unfounded fantasy is perilously thin. In this perspective, we examine our mathematical tools for navigating the vast world of quantum advantages across computation, learning, sensing, and communication. We explore five keystone properties: predictability, typicality, robustness, verifiability, and usefulness that define an ideal quantum advantage, and envision what new quantum advantages could arise in a future with ubiquitous quantum technology. We prove that some quantum advantages are inherently unpredictable using classical resources alone, suggesting a landscape far richer than what we can currently foresee. While mathematical rigor remains our indispensable guide, the ultimate power of quantum technologies may emerge from advantages we cannot yet conceive.

Figures

Figures reproduced from arXiv: 2508.05720 by the authors.

Figure 1
Figure 1. Conceptual overview of the vast world of quantum advantage. (a) Keystones of quan￾tum advantage. We propose five essential properties that collectively define an ideal quantum advantage: Pre￾dictability (supported by rigorous evidence), Typicality (applying to a substantial fraction of naturally occurring problem instances), Robustness (maintaining advantage despite noise and imperfections), Verifiability (enabling … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 10 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Logarithmic growth of operator entanglement in a clean non-integrable circuit

    cond-mat.stat-mech 2026-03 conditional novelty 7.0 of 10

    In a clean non-integrable semi-ergodic dual-unitary circuit, operator entanglement of a local Pauli grows at most logarithmically in time, with bimodal operator-size distributions and late-time autocorrelations matchi...

  2. Machine learning for sample-based quantum diagonalization: generative configuration recovery and the classical-simulability frontier

    quant-ph 2026-08 conditional novelty 6.0 of 10

    A critical review plus small exact-FCI experiments concludes that sample-based quantum diagonalization has not beaten classical selected CI and maps where, if anywhere, a quantum or generative advantage could survive.

  3. Explainable quantum-compressed machine learning for complex fluid flows

    physics.flu-dyn 2026-07 conditional novelty 6.0 of 10

    A hybrid quantum-classical surrogate compresses the latent time-stepping operator of flow models to as few as 8 trainable parameters and achieves stable long rollouts via exact unitarity, matching a classical baseline...

  4. Universal Quantum Computation with Multi-Mode Schr\"odinger Cat States Stabilized by Non-Local Dissipation Engineering

    quant-ph 2026-07 conditional novelty 6.0 of 10

    Dissipatively stabilized multi-mode Schrödinger-cat qubits are made universal by adding a self-Kerr Z(π/2) gate and a beam-splitter-induced XX(π/2) entangling gate.

  5. Provable learning separation for predicting time-evolution of quantum many-body systems

    quant-ph 2026-07 accept novelty 6.0 of 10

    A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.

  6. Simple broadband signal detection at the fundamental limit

    quant-ph 2026-01 conditional novelty 6.0 of 10

    Broadband AC-field detection at the Grover-like limit can be achieved by a single analog experiment using a randomized SSH control Hamiltonian and a GHZ probe, with the lower bound derived from an integrated-quantum-F...

  7. Efficient certification of intractable quantum states with few Pauli measurements

    quant-ph 2025-11 reject novelty 6.0 of 10

    The paper claims Clifford-enhanced product states can be certified with O(n^2/epsilon^2) Pauli measurements in the i.i.d. setting and polynomially many in the adversarial setting, but the central estimator is derived ...

  8. Towards Chemically Accurate and Scalable Quantum Simulations on IQM Quantum Hardware: A Quantum-HPC Hybrid Approach

    quant-ph 2026-04 accept novelty 5.5 of 10

    SQD with LUCJ (and a new LCNot-UCCSD variant) on IQM Sirius recovers chemically accurate energies, 1D/2D PES, and DMET-embedded ligand/amantadine results versus FCI/CASCI references.

  9. Quantum Telepathy: A Quantum Technology with Near-Term Applications

    quant-ph 2026-03 conditional novelty 4.0 of 10

    Quantum telepathy—using entanglement to beat Bell inequalities in communication-restricted coordination—is reviewed as a near-term quantum technology, but the paper is an overview of the authors' prior results rather ...

  10. Quantum Computing : A New Frontier for Science and Society

    quant-ph 2026-07 unverdicted

    A review surveying quantum computing hardware platforms, control layers, error correction, and software stacks as of 2023–2025.

Reference graph

Works this paper leans on

166 extracted references · 43 canonical work pages · cited by 10 Pith papers

  1. [1]

    Puzzle 1: Is this spooky? Let us analyze this puzzle in two steps: first considering measurements in a single basis, then examining what changes when we allow measurements in multiple bases. First scenario: Single-basis measurements.When Alice and Bob only measure in the standard basis {|↑⟩,|↓⟩}, their quantum state 1√ 2(|↑⟩⊗|↑⟩−|↓⟩⊗|↓⟩)(A.1) produces per...

  2. [2]

    Take a pair of socks that are either both black or both white with equal probability

  3. [3]

    Place each sock in an opaque gift box

  4. [4]

    Give one box to Alice and one to Bob

  5. [5]

    When Alice and Bob open their boxes, they see perfectly correlated colors instantaneously

    Let them separate to arbitrary distances. When Alice and Bob open their boxes, they see perfectly correlated colors instantaneously. The classical protocol exactly reproduces the quantum statistics: each party sees a random outcome (up/down or black/white) with 50-50 probability, and the outcomes are always perfectly correlated. Second scenario: Multiple-...

  6. [6]

    Puzzle 2: Exponential quantum advantage in analyzing big data? The solution to Puzzle 2 reveals how classical techniques can match quantum computation for this specific task. The key insight is that Bob’s classical random access memory (RAM) can be enhanced to provide two crucial capabilities, each taking onlypoly(𝑛)time: 1.Query:Given any indices𝑘and𝑖, o...

  7. [7]

    quantum fingerprint

    Puzzle 3: Can quantum systems encode exponential classical information? The answer to this puzzle is a nuanced “yes,” that reveals a subtle but powerful form of quantum advantage. The apparent conflict between exponential encoding and Holevo’s bound is resolved by understanding that the usefulness of an encoding depends entirely on the task for which the ...

  8. [8]

    Our goal is to detect the signal as quickly as possible; that is, to distinguish between the two cases using as few resources as possible

    Entanglement-enhanced sensitivity In the noiseless version of this model, our task is to distinguish between two single-qubit unitary channels.𝒞 𝜃 rotates the qubit about the𝑍-axis by the positive angle𝜃, and𝒞0 acts trivially: 𝒞𝜃[𝜌] =𝑒−𝑖𝜃 2𝑍𝜌𝑒𝑖𝜃 2𝑍 and𝒞 0[𝜌] =𝜌.(B.1) The rotation angle𝜃is the strength of the signal we wish to detect. Our goal is to detect...

Show all 166 references
  1. [9]

    Fragility of entanglement-enhanced sensitivity in noisy sensors We now consider a simple model of noisy quantum sensing. In realistic settings, noise arises from a variety of physical sources such as thermal fluctuations in the environment, imperfections in laser beams or micr...

  2. [10]

    The key idea is to truncate high-weight Pauli terms during the simulation, maintaining only the most important contributions

    Overview and Context The low-weight Pauli propagation algorithm [33–41] provides a powerful classical heuristic for sim- ulating quantum circuits. The key idea is to truncate high-weight Pauli terms during the simulation, maintaining only the most important contributions. Cons...

  3. [11]

    Algorithm Description The low-weight Pauli propagation algorithm proceeds in the Heisenberg picture, where the observable is evolved backward through the circuit

  4. [12]

    Here, the weight of a Pauli operator is the number of non-identity terms it contains

    We begin by initializing the operator𝑂𝐿 as the projection of the observable𝑂onto the subspace of Pauli operators with weight at most𝑘. Here, the weight of a Pauli operator is the number of non-identity terms it contains

  5. [13]

    (b) Project the result back onto the low-weight Pauli basis to get the new operator: 𝑂𝑗−1 = ∑︁ 𝑃∈{𝐼,𝑋,𝑌,𝑍}⊗𝑛 |𝑃|≤𝑘 tr[𝑂′ 𝑗−1𝑃] 2𝑛 𝑃.(C.3)

    Working backwards from𝑗=𝐿down to1, we iteratively apply the following two steps: (a) Evolve the operator through the𝑗-th layer:𝑂′ 𝑗−1 =𝑈† 𝑗𝑂𝑗𝑈𝑗. (b) Project the result back onto the low-weight Pauli basis to get the new operator: 𝑂𝑗−1 = ∑︁ 𝑃∈{𝐼,𝑋,𝑌,𝑍}⊗𝑛 |𝑃|≤𝑘 tr[𝑂′ 𝑗−1𝑃] 2𝑛 𝑃.(C.3)

  6. [14]

    In practice, one can typically consider𝑘to be a small constant

    The final estimate for the expectation value is computed using the fully evolved and truncated operator𝑂 0 and the initial state𝜌: Estimate= tr[𝑂 0𝜌].(C.4) The larger𝑘is, the more accurate the low-weight Pauli propagation algorithm is. In practice, one can typically consider𝑘t...

  7. [15]

    Intuitively, the locally scrambling property means each layer is generic on a local scale and mixes the local basis

    Theoretical Guarantees When each circuit layer𝑈𝑗 is drawn from alocally scramblingdistribution [122–126], which corre- sponds to a probability distribution that remains invariant under single-qubit Clifford rotations, [40] has established the following theorem to provide a rig...

  8. [16]

    The runtime is polynomial in system size𝑛and circuit depth𝐿for any small constant𝜖,𝛿

  9. [17]

    The accuracy parameters𝜖and𝛿appear only logarithmically in the exponent

  10. [18]

    The error scales naturally with the observable’s normalized Hilbert-Schmidt norm. 24

  11. [19]

    Applicability and Scope This theoretical result encompasses various quantum circuit architectures. For the computational complexity bounds to hold, we require that for any Pauli operator𝑃of weight𝑘, its Heisenberg evolution 𝑈† 𝑗𝑃𝑈𝑗 contains at most𝑛𝒪(𝑘) distinct Pauli terms an...

  12. [20]

    Brickwork circuits of𝑆𝑈(4)gates in 1D, 2D, and 3D [127–129]

  13. [21]

    Circuits with universal single-qubit rotations followed by entangling Clifford gates [130]

  14. [22]

    Despite this broad applicability, the fundamental limitations of this approach warrant careful consider- ation

    Quantum Convolutional Neural Networks without feed-forward [131]. Despite this broad applicability, the fundamental limitations of this approach warrant careful consider- ation. The low-weight Pauli propagation method remains inherently a classical heuristic. Its theoretical g...

  15. [23]

    It runs in classical polynomial time

  16. [24]

    computational advantage

    It correctly approximates the output probability𝐶(𝑥)for a subclass of polynomial-size quantum circuits𝐶, but it is known to fail, or is not proven to succeed, for some circuits in this class and generally the set of circuits for which it fails is unknown. The algorithm is cons...

  17. [25]

    Given the circuit description𝐶, choose a set of𝑠=𝒪(1)random input strings{𝑥 1,...,𝑥 𝑠}

  18. [26]

    (b) Estimate the true probability𝐶(𝑥𝑖)on a quantum computer

    For each𝑥𝑖 for𝑖= 1,...,𝑠: (a) Compute the heuristic’s prediction𝒜𝐶(𝑥𝑖)using the classicalLowWeightPauliPropalgo- rithm as described in Appendix C. (b) Estimate the true probability𝐶(𝑥𝑖)on a quantum computer. This is done by preparing the state𝐶(|𝑥 𝑖⟩|0𝑚⟩)and measuring the firs...

  19. [27]

    For each𝑥𝑖 for𝑖= 1,...,𝑠, check if|𝒜 𝐶(𝑥𝑖)−𝐶(𝑥 𝑖)|≥1/3

  20. [28]

    Otherwise, output0

    If the fraction of inputs𝑥𝑖 satisfying this condition is greater than1/2, output1. Otherwise, output0. By a standard Chernoff bound with an appropriate sample size𝑠, this sampling procedure correctly distinguishes the case where the true fraction is≥2/3from the case where it i...

  21. [29]

    Runℓcopies of𝐶 ? on separate ancilla registers

  22. [30]

    Apply a coherent majority vote circuit to the first qubits of each copy, storing the result in a designated ancilla qubit𝑞maj. By standard concentration inequalities, such as the Chernoff bound, this amplified circuit satisfies: •If𝐶 ? is a YES instance:Pr[Measuring𝑞 maj in𝑍ba...

  23. [31]

    Construct the circuit𝐶new from𝐶 ? as described above

  24. [32]

    Apply the assumed classical algorithm𝒟to determine if a quantum computer executing quantum circuit𝐶 new does not exhibit a computational advantage overLowWeightPauliProp

  25. [33]

    Since this procedure works for anyBQPproblem and runs in polynomial time, we would haveBPP= BQP, contradicting our assumption thatBPP̸=BQP

    Output the result of𝒟. Since this procedure works for anyBQPproblem and runs in polynomial time, we would haveBPP= BQP, contradicting our assumption thatBPP̸=BQP. Therefore, no polynomial-time classical algorithm can solveDetectingQuantumAdvantage, completing the proof. 31

  26. [34]

    J. S. Bell, On the einstein podolsky rosen paradox, Physics Physique Fizika1, 195 (1964)

    1964

  27. [35]

    Jaques and A

    S. Jaques and A. G. Rattew, Qram: A survey and critique, arXiv preprint arXiv:2305.10310 (2023)

    2023

  28. [36]

    A. M. Dalzell, A. Gilyén, C. T. Hann, S. McArdle, G. Salton, Q. T. Nguyen, A. Kubica, and F. G. Brandão, A distillation-teleportation protocol for fault-tolerant qram, arXiv preprint arXiv:2505.20265 (2025)

    2025 arXiv

  29. [37]

    A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters103, 150502 (2009)

    2009

  30. [38]

    Tang, A quantum-inspired classical algorithm for recommendation systems, inProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing(2019) pp

    E. Tang, A quantum-inspired classical algorithm for recommendation systems, inProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing(2019) pp. 217–228

    2019

  31. [39]

    Tang, Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions, Physical Review Letters127, 060503 (2021)

    E. Tang, Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions, Physical Review Letters127, 060503 (2021)

    2021

  32. [40]

    A. S. Holevo, Bounds for the quantity of information transmitted by a quantum communication channel, Problems of Information Transmission9, 177 (1973)

    1973

  33. [41]

    Raz, Exponential separation of quantum and classical communication complexity, inProceedings of the thirty-first annual ACM symposium on Theory of computing(ACM, 1999) pp

    R. Raz, Exponential separation of quantum and classical communication complexity, inProceedings of the thirty-first annual ACM symposium on Theory of computing(ACM, 1999) pp. 358–367

    1999

  34. [42]

    Gilboa, H

    D. Gilboa, H. Michaeli, D. Soudry, and J. McClean, Exponential quantum communication advantage in distributed inference and learning, Advances in Neural Information Processing Systems37, 30425 (2024)

    2024

  35. [43]

    Zimborás, B

    Z. Zimborás, B. Koczor, Z. Holmes, E.-M. Borrelli, A. Gilyén, H.-Y. Huang, Z. Cai, A. Acín, L. Aolita, L. Banchi,et al., Myths around quantum computation before full fault tolerance: What no-go theorems rule out and what they don’t, arXiv preprint arXiv:2501.05694 (2025)

    2025 arXiv

  36. [44]

    Aaronson, A

    S. Aaronson, A. M. Childs, E. Farhi, A. W. Harrow, and B. C. Sanders, Future of quantum computing, arXiv preprint arXiv:2506.19232 (2025)

    2025

  37. [45]

    King, Quantum algorithms: A call to action,https://quantumfrontiers.com/2025/04/20/ quantum-algorithms-a-call-to-action/(2025)

    R. King, Quantum algorithms: A call to action,https://quantumfrontiers.com/2025/04/20/ quantum-algorithms-a-call-to-action/(2025)

    2025

  38. [46]

    Lanes, M

    O. Lanes, M. Beji, A. D. Corcoles, C. Dalyac, J. M. Gambetta, L. Henriet, A. Javadi-Abhari, A. Kandala, A. Mezzacapo, C. Porter,et al., A framework for quantum advantage, arXiv preprint arXiv:2506.20658 (2025)

    2025 arXiv

  39. [47]

    Kerenidis and A

    I. Kerenidis and A. Prakash, Quantum recommendation systems, inProceedings of the 8th Innovations in Theoretical Computer Science Conference(Schloss Dagstuhl, 2017) pp. 49:1–49:21

    2017

  40. [48]

    L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical computer science3, 1 (1976)

    1976

  41. [49]

    P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review41, 303 (1999)

    1999

  42. [50]

    Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM 56, 1 (2009)

    O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM 56, 1 (2009)

    2009

  43. [51]

    Mahadev, Classical verification of quantum computations, in2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2018) pp

    U. Mahadev, Classical verification of quantum computations, in2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2018) pp. 259–267

    2018

  44. [52]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science389, 92 (2025)

    2025

  45. [53]

    UN Conference on Trade and Development, Digital economy report 2024: Shaping an environmentally sustainable and inclusive digital future (2024), business e-commerce sales reached $27 trillion in 2022 across 43 countries

    2024

  46. [54]

    Forrester Research, Global digital economy forecast, 2023 to 2028 (2024), digital economy projected to reach $16.5 trillion by 2028

    2023

  47. [55]

    National Institute of Standards and Technology, Digital signature standard (dss) (2013), federal standard specifying RSA, DSA, and ECDSA for digital signatures

    2013

  48. [56]

    Chen, H.-Y

    C.-F. Chen, H.-Y. Huang, J. Preskill, and L. Zhou, Local minima in quantum systems, inProceedings of the 56th Annual ACM Symposium on Theory of Computing(ACM, 2024) pp. 1845–1858

    2024

  49. [57]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 (2014)

    2014 arXiv

  50. [58]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model, arXiv preprint arXiv:2110.14206 https://doi.org/10.4230/LIPIcs.TQC.2022.7 (2021)

    2022 arXiv

  51. [59]

    Basso, D

    J. Basso, D. Gamarnik, S. Mei, and L. Zhou, Performance and limitations of the qaoa at constant levels on large sparse hypergraphs and spin glass models, in2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2022) pp. 335–343

    2022

  52. [60]

    Farhi, S

    E. Farhi, S. Gutmann, D. Ranard, and B. Villalonga, Lower bounding the maxcut of high girth 3-regular graphs using the qaoa, arXiv preprint arXiv:2503.12789 (2025)

    2025

  53. [61]

    S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, T. Khattar, and R. Babbush, Optimization by decoded quantum interferometry, arXiv preprint arXiv:2408.08292 (2024)

    2024

  54. [62]

    A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem, arXiv preprint quant-ph/9511026 (1995)

    1995 arXiv

  55. [63]

    Lin and Y

    L. Lin and Y. Tong, Near-optimal ground state preparation, Quantum4, 372 (2020)

    2020

  56. [64]

    D. Wu, R. Rossi, F. Vicentini, N. Astrakhantsev, F. Becca, X. Cao, J. Carrasquilla, F. Ferrari, A. Georges, M. Hibat-Allah,et al., Variational benchmarks for quantum many-body problems, Science386, 296 (2024)

    2024

  57. [65]

    S. R. White, Density matrix formulation for quantum renormalization groups, Physical Review Letters69, 32 2863 (1992)

    1992

  58. [66]

    Aharonov, X

    D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, A polynomial-time classical algorithm for noisy random circuit sampling, inProceedings of the 55th Annual ACM Symposium on Theory of Computing (2023) pp. 945–957

    2023

  59. [67]

    Y. Shao, F. Wei, S. Cheng, and Z. Liu, Simulating quantum mean values in noisy variational quantum algorithms: A polynomial-scale approach, arXiv preprint arXiv:2306.05804 (2023)

    2023 arXiv

  60. [68]

    N. A. Nemkov, E. O. Kiktenko, and A. K. Fedorov, Fourier expansion in variational quantum algorithms, Phys. Rev. A108, 032406 (2023)

    2023

  61. [69]

    Begušić, J

    T. Begušić, J. Gray, and G. K.-L. Chan, Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance, Science Advances10, 10.1126/sciadv.adk4321 (2024)

    2024 doi

  62. [70]

    Begušić, K

    T. Begušić, K. Hejazi, and G. K. Chan, Simulating quantum circuit expectation values by clifford pertur- bation theory, The Journal of Chemical Physics162(2025)

    2025

  63. [71]

    E.Fontana, M.S.Rudolph, R.Duncan, I.Rungger,andC.Cîrstoiu,Classicalsimulationsofnoisyvariational quantum circuits, npj Quantum Information11, 84 (2025)

    2025

  64. [72]

    M. S. Rudolph, E. Fontana, Z. Holmes, and L. Cincio, Classical surrogate simulation of quantum systems with lowesa, arXiv preprint arXiv:2308.09109 (2023)

    2023 arXiv

  65. [73]

    Angrisani, A

    A. Angrisani, A. Schmidhuber, M. S. Rudolph, M. Cerezo, Z. Holmes, and H.-Y. Huang, Classically esti- mating observables of noiseless quantum circuits, arXiv preprint arXiv:2409.01706 (2024)

    2024

  66. [74]

    Dowling, P

    N. Dowling, P. Kos, and X. Turkeshi, Magic resources of the heisenberg picture, Physical Review Letters 135, 050401 (2025)

    2025

  67. [75]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin,...

    2019

  68. [76]

    Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong,et al., Quantum computational advantage via 60-qubit 24-cycle random circuit sampling, Science bulletin67, 240 (2022)

    2022

  69. [77]

    Morvan, B

    A. Morvan, B. Villalonga, X. Mi, S. Mandra, A. Bengtsson, P. Klimov, Z. Chen, S. Hong, C. Erickson, I. Drozdov,et al., Phase transitions in random circuit sampling, Nature634, 328 (2024)

    2024

  70. [78]

    D. A. Abanin, R. Acharya, L. Aghababaie-Beni, G. Aigeldinger, A. Ajoy, R. Alcaraz, I. Aleiner, T. I. Andersen, M.Ansmann, F.Arute,et al.,Constructiveinterferenceattheedgeofquantumergodicdynamics, arXiv preprint arXiv:2506.10191 (2025)

    2025 arXiv

  71. [79]

    D. Gao, D. Fan, C. Zha, J. Bei, G. Cai, J. Cai, S. Cao, F. Chen, J. Chen, K. Chen,et al., Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor, Physical Review Letters134, 090601 (2025)

    2025

  72. [80]

    Boneh, The decision diffie-hellman problem, inInternational algorithmic number theory symposium (Springer, 1998) pp

    D. Boneh, The decision diffie-hellman problem, inInternational algorithmic number theory symposium (Springer, 1998) pp. 48–63

    1998

  73. [81]

    Shoup, Lower bounds for discrete logarithms and related problems, inInternational Conference on the Theory and Applications of Cryptographic Techniques(Springer, 1997) pp

    V. Shoup, Lower bounds for discrete logarithms and related problems, inInternational Conference on the Theory and Applications of Cryptographic Techniques(Springer, 1997) pp. 256–266

    1997

  74. [82]

    Schmidhuber, R

    A. Schmidhuber, R. O’Donnell, R. Kothari, and R. Babbush, Quartic quantum speedups for planted infer- ence, Physical Review X15, 021077 (2025)

    2025

  75. [83]

    Gottesman, Fault-tolerant quantum computation with constant overhead, Quantum Information & Com- putation14, 1338 (2014)

    D. Gottesman, Fault-tolerant quantum computation with constant overhead, Quantum Information & Com- putation14, 1338 (2014)

    2014

  76. [84]

    Q. T. Nguyen and C. A. Pattison, Quantum fault tolerance with constant-space and logarithmic-time overheads, inProceedings of the 57th Annual ACM Symposium on Theory of Computing(2025) pp. 730– 737

    2025

  77. [85]

    S. Zhou, M. Zhang, J. Preskill, and L. Jiang, Achieving the heisenberg limit in quantum metrology using quantum error correction, Nature communications9, 78 (2018)

    2018

  78. [86]

    M. A. Fischler and R. C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM24, 381 (1981)

    1981

  79. [87]

    Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society Series B: Statistical Methodology58, 267 (1996)

    R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society Series B: Statistical Methodology58, 267 (1996)

    1996

  80. [88]

    Natarajan, I

    N. Natarajan, I. S. Dhillon, P. K. Ravikumar, and A. Tewari, Learning with noisy labels, Advances in neural information processing systems26, 1196 (2013)

    2013

  81. [89]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Information-theoretic bounds on quantum advantage in machine learning, Phys. Rev. Lett.126, 190505 (2021)

    2021

  82. [90]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponential separations between learning with and without quantum memory, in2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2022) pp. 574–585

    2022

  83. [91]

    Huang, M

    H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, 33 J. Preskill, and J. R. McClean, Quantum advantage in learning from experiments, Science376, 1182 (2022)

    2022

  84. [92]

    Huang, S

    H.-Y. Huang, S. T. Flammia, and J. Preskill, Foundations for learning from noisy quantum experiments, arXiv preprint arXiv:2204.13691 (2022)

    2022 arXiv

  85. [93]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, The complexity of nisq, Nature Communications14, 6001 (2023)

    2023

  86. [94]

    Z.-H. Liu, R. Brunel, E. E. Østergaard, O. Cordero, S. Chen, Y. Wong, J. A. Nielsen, A. B. Bregnsbo, S. Zhou, H.-Y. Huang,et al., Quantum learning advantage on a scalable photonic platform, arXiv preprint arXiv:2502.07770 (2025)

    2025

  87. [95]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Proceedings of the forty-third annual ACM symposium on Theory of computing , 333 (2011)

    2011

  88. [96]

    Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics349, 117 (2014)

    R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics349, 117 (2014)

    2014

  89. [97]

    C. L. Degen, F. Reinhard, and P. Cappellaro, Quantum sensing, Rev. Mod. Phys.89, 035002 (2017)

    2017

  90. [98]

    Pirandola, U

    S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani,et al., Advances in quantum cryptography, Advances in Optics and Photonics12, 1012 (2020)

    2020

  91. [99]

    A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-F. Chen, A. Gilyén, C. T. Hann, M. J. Kastoryano, E. T. Khabiboulline, A. Kubica,et al., Quantum algorithms: A survey of applications and end-to-end complexities, arXiv preprint arXiv:2310.03011 (2023)

    2023 arXiv

  92. [100]

    S. P. Jordan, Quantum algorithm zoo,https://quantumalgorithmzoo.org

  93. [101]

    Bernstein and U

    E. Bernstein and U. Vazirani, Quantum complexity theory, inProceedings of the twenty-fifth annual ACM symposium on Theory of computing(1993) pp. 11–20

    1993

  94. [102]

    D. R. Simon, On the power of quantum computation, SIAM journal on computing26, 1474 (1997)

    1997

  95. [103]

    L. K. Grover, A fast quantum mechanical algorithm for database search, inProceedings of the twenty-eighth annual ACM symposium on Theory of computing(1996) pp. 212–219

    1996

  96. [104]

    Farhi and S

    E. Farhi and S. Gutmann, Quantum computation and decision trees, Physical Review A58, 915 (1998)

    1998

  97. [105]

    A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorith- mic speedup by a quantum walk, inProceedings of the thirty-fifth annual ACM symposium on Theory of computing(2003) pp. 59–68

    2003

  98. [106]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quantum algorithm for the hamiltonian nand tree, arXiv preprint quant-ph/0702144 (2007)

    2007 arXiv

  99. [107]

    R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics21, 467 (1982)

    1982

  100. [108]

    Lloyd, Universal quantum simulators, Science273, 1073 (1996)

    S. Lloyd, Universal quantum simulators, Science273, 1073 (1996)

    1996

  101. [109]

    Carleo and M

    G. Carleo and M. Troyer, Solving the quantum many-body problem with artificial neural networks, Science 355, 602 (2017)

    2017

  102. [110]

    S. Lee, J. Lee, H. Zhai, Y. Tong, A. M. Dalzell, A. Kumar, P. Helms, J. Gray, Z.-H. Cui, W. Liu,et al., Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry, Nature Communications14, 1952 (2023)

    1952

  103. [111]

    Huang, M

    H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and J. R. McClean, Power of data in quantum machine learning, Nature communications12, 2631 (2021)

    2021

  104. [112]

    Huang, R

    H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, Provably efficient machine learning for quantum many-body problems, Science377, eabk3333 (2022)

    2022

  105. [113]

    Lewis, H.-Y

    L. Lewis, H.-Y. Huang, V. T. Tran, S. Lehner, R. Kueng, and J. Preskill, Improved machine learning algorithm for predicting ground state properties, Nature Communications15, 895 (2024)

    2024

  106. [114]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Quantum-enhanced measurements: beating the standard quan- tum limit, Science306, 1330 (2004)

    2004

  107. [115]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Quantum metrology, Physical Review Letters96, 010401 (2006)

    2006

  108. [116]

    Demkowicz-Dobrzański, J

    R. Demkowicz-Dobrzański, J. Kołodyński, and M. Guță, The elusive heisenberg limit in quantum-enhanced metrology, Nature communications3, 1063 (2012)

    2012

  109. [117]

    T. L. S. Collaboration, A gravitational wave observatory operating beyond the quantum shot-noise limit, Nature Physics7, 962 (2011)

    2011

  110. [118]

    B. P. Abbottet al., Observation of gravitational waves from a binary black hole merger, Physical review letters116, 061102 (2016)

    2016

  111. [119]

    Schnabel, Squeezed states of light and their applications in laser interferometers, Physics Reports684, 1 (2017)

    R. Schnabel, Squeezed states of light and their applications in laser interferometers, Physics Reports684, 1 (2017)

    2017

  112. [120]

    Ganapathy, W

    D. Ganapathy, W. Jia, M. Nakano, V. Xu, N. Aritomi, T. Cullen, N. Kijbunchoo, S. Dwyer, A. Mullavey, L. McCuller,et al., Broadband quantum enhancement of the ligo detectors with frequency-dependent squeezing, Physical Review X13, 041021 (2023)

    2023

  113. [121]

    J. M. Taylor, P. Cappellaro, L. Childress, L. Jiang, D. Budker, P. Hemmer, A. Yacoby, R. Walsworth, and M. Lukin, High-sensitivity diamond magnetometer with nanoscale resolution, Nature Physics4, 810 (2008)

    2008

  114. [122]

    Lovchinsky, A

    I. Lovchinsky, A. Sushkov, E. Urbach, N. P. de Leon, S. Choi, K. De Greve, R. Evans, R. Gertner, E. Bersin, C. Müller,et al., Nuclear magnetic resonance detection and spectroscopy of single proteins using quantum logic, Science351, 836 (2016)

    2016

  115. [123]

    Bhattacharyya, W

    P. Bhattacharyya, W. Chen, X. Huang, S. Chatterjee, B. Huang, B. Kobrin, Y. Lyu, T. J. Smart, M. Block, E. Wang,et al., Imaging the meissner effect in hydride superconductors using quantum sensors, Nature627, 73 (2024). 34

    2024

  116. [124]

    M. Wang, Y. Wang, Z. Liu, G. Xu, B. Yang, P. Yu, H. Sun, X. Ye, J. Zhou, A. F. Goncharov,et al., Imaging magnetic transition of magnetite to megabar pressures using quantum sensors in diamond anvil cell, Nature Communications15, 8843 (2024)

    2024

  117. [125]

    A. D. Ludlow, M. M. Boyd, J. Ye, E. Peik, and P. O. Schmidt, Optical atomic clocks, Reviews of Modern Physics87, 637 (2015)

    2015

  118. [126]

    Bothwell, C

    T. Bothwell, C. J. Kennedy, A. Aeppli, D. Kedar, J. M. Robinson, E. Oelker, A. Staron, and J. Ye, Resolving the gravitational redshift across a millimetre-scale atomic sample, Nature602, 420 (2022)

    2022

  119. [127]

    T. L. Nicholson, S. Campbell, R. Hutson, G. E. Marti, B. Bloom, R. L. McNally, W. Zhang, M. Barrett, M. S. Safronova, G. Strouse,et al., Systematic evaluation of an atomic clock at 2×10- 18 total uncertainty, Nature communications6, 6896 (2015)

    2015

  120. [128]

    Schine, A

    N. Schine, A. W. Young, W. J. Eckner, M. J. Martin, and A. M. Kaufman, Long-lived bell states in an array of optical clock qubits, Nature Physics18, 1067 (2022)

    2022

  121. [129]

    Aharonov, J

    D. Aharonov, J. Cotler, and X.-L. Qi, Quantum algorithmic measurement, Nature Communications13, 1 (2022)

    2022

  122. [130]

    S. Chen, C. Oh, S. Zhou, H.-Y. Huang, and L. Jiang, Tight bounds on pauli channel learning without entanglement, Physical Review Letters132, 180805 (2024)

    2024

  123. [131]

    C. Oh, S. Chen, Y. Wong, S. Zhou, H.-Y. Huang, J. A. Nielsen, Z.-H. Liu, J. S. Neergaard-Nielsen, U. L. Andersen, L. Jiang,et al., Entanglement-enabled advantage for learning a bosonic random displacement channel, Physical Review Letters133, 230604 (2024)

    2024

  124. [132]

    R. R. Allen, F. Machado, I. L. Chuang, H.-Y. Huang, and S. Choi, Quantum computing enhanced sensing, arXiv preprint arXiv:2501.07625 (2025)

    2025 arXiv

  125. [133]

    C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Theo- retical computer science560, 7 (2014)

    2014

  126. [134]

    Colbeck and R

    R. Colbeck and R. Renner, Free randomness can be amplified, Nature Physics8, 450 (2012)

    2012

  127. [135]

    M. Liu, R. Shaydulin, P. Niroula, M. DeCross, S.-H. Hung, W. Y. Kon, E. Cervero-Martín, K. Chakraborty, O. Amer, S. Aaronson,et al., Certified randomness using a trapped-ion quantum processor, Nature , 1 (2025)

    2025

  128. [136]

    Wiesner, Conjugate coding, ACM Sigact News15, 78 (1983)

    S. Wiesner, Conjugate coding, ACM Sigact News15, 78 (1983)

    1983

  129. [137]

    Broadbent and R

    A. Broadbent and R. Islam, Quantum encryption with certified deletion, inTheory of Cryptography Con- ference, Lecture Notes in Computer Science, Vol. 12552 (Springer, 2020) pp. 92–122

    2020

  130. [138]

    Aaronson, Quantum copy-protection and quantum money, inProceedings of the 24th Annual IEEE Conference on Computational Complexity(IEEE, 2009) pp

    S. Aaronson, Quantum copy-protection and quantum money, inProceedings of the 24th Annual IEEE Conference on Computational Complexity(IEEE, 2009) pp. 229–242

    2009

  131. [139]

    Goldwasser, Y

    S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, One-time programs, inAnnual International Cryptology Conference(Springer, 2008) pp. 39–56

    2008

  132. [140]

    Ding and L

    D. Ding and L. Jiang, Coordinating decisions via quantum telepathy, arXiv preprint arXiv:2407.21723 (2024)

    2024 arXiv

  133. [141]

    Kallaugher, O

    J. Kallaugher, O. Parekh, and N. Voronova, Exponential quantum space advantage for approximating maximum directed cut in the streaming model, inProceedings of the 56th Annual ACM Symposium on Theory of Computing(2024) pp. 1805–1815

    2024

  134. [142]

    Ren and R

    H. Ren and R. Santhanam, A relativization perspective on meta-complexity, in39th International Sympo- sium on Theoretical Aspects of Computer Science (STACS 2022)(Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022) pp. 54–1

    2022

  135. [143]

    URL:https://simons.berkeley.edu/programs/meta23

    Simons Institute for the Theory of Computing, Meta-complexity program, Online Program with Videos and Materials (2023), accessed July 3, 2025. URL:https://simons.berkeley.edu/programs/meta23

    2023

  136. [144]

    Bernien, S

    H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner,et al., Probing many-body dynamics on a 51-atom quantum simulator, Nature551, 579 (2017)

    2017

  137. [145]

    C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, and Z. Papić, Weak ergodicity breaking from quantum many-body scars, Nature Physics14, 745 (2018)

    2018

  138. [146]

    Ippoliti and W

    M. Ippoliti and W. W. Ho, Solvable model of deep thermalization with distinct design times, Quantum6, 886 (2022)

    2022

  139. [147]

    J. S. Cotler, D. K. Mark, H.-Y. Huang, F. Hernández, J. Choi, A. L. Shaw, M. Endres, and S. Choi, Emergent quantum state designs from individual many-body wave functions, PRX quantum4, 010311 (2023)

    2023

  140. [148]

    Aspect, J

    A. Aspect, J. Dalibard, and G. Roger, Experimental test of bell’s inequalities using time-varying analyzers, Phys. Rev. Lett.49, 1804 (1982)

    1982

  141. [149]

    S. J. Freedman and J. F. Clauser, Experimental test of local hidden-variable theories, Phys. Rev. Lett.28, 938 (1972)

    1972

  142. [150]

    Preskill, Lecture notes for physics 229: Quantum Information and Computation, Lecture notes, California Institute of Technology (1998), september 1998

    J. Preskill, Lecture notes for physics 229: Quantum Information and Computation, Lecture notes, California Institute of Technology (1998), september 1998

    1998

  143. [151]

    Devroye, Nonuniform random variate generation, Handbooks in operations research and management science13, 83 (2006)

    L. Devroye, Nonuniform random variate generation, Handbooks in operations research and management science13, 83 (2006)

    2006

  144. [152]

    M. D. Vose, A linear algorithm for generating random numbers with a given distribution, IEEE Transactions on software engineering17, 972 (1991)

    1991

  145. [153]

    Buhrman, R

    H. Buhrman, R. Cleve, S. Massar, and R. De Wolf, Nonlocality and communication complexity, Reviews of modern physics82, 665 (2010)

    2010

  146. [154]

    M. W. Mahoney, Randomized algorithms for matrices and data, Foundations and Trends in Machine Learn- ing3, 123 (2011). 35

    2011

  147. [155]

    W.-T. Kuo, A. Akhtar, D. P. Arovas, and Y.-Z. You, Markovian entanglement dynamics under locally scrambled quantum evolution, Physical Review B101, 224202 (2020)

    2020

  148. [156]

    H.-Y. Hu, S. Choi, and Y.-Z. You, Classical shadow tomography with locally scrambled quantum dynamics, Physical Review Research5, 023027 (2023)

    2023

  149. [157]

    M. C. Caro, H.-Y. Huang, N. Ezzell, J. Gibbs, A. T. Sornborger, L. Cincio, P. J. Coles, and Z. Holmes, Out-of-distributiongeneralizationforlearningquantumdynamics,NatureCommunications14,3751(2023)

    2023

  150. [158]

    Gibbs, Z

    J. Gibbs, Z. Holmes, M. C. Caro, N. Ezzell, H.-Y. Huang, L. Cincio, A. T. Sornborger, and P. J. Coles, Dy- namical simulation via quantum machine learning with provable generalization, Physical Review Research 6, 013241 (2024)

    2024

  151. [159]

    Huang, S

    H.-Y. Huang, S. Chen, and J. Preskill, Learning to predict arbitrary quantum processes, PRX Quantum4, 040337 (2023)

    2023

  152. [160]

    Zhang, S

    H.-K. Zhang, S. Liu, and S.-X. Zhang, Absence of barren plateaus in finite local-depth circuits with long- range entanglement, Physical Review Letters132, 150603 (2024)

    2024

  153. [161]

    Napp, Quantifying the barren plateau phenomenon for a model of unstructured variational ansätze, arXiv preprint arXiv:2203.06174 (2022)

    J. Napp, Quantifying the barren plateau phenomenon for a model of unstructured variational ansätze, arXiv preprint arXiv:2203.06174 (2022)

    2022 arXiv

  154. [162]

    Braccia, P

    P. Braccia, P. Bermejo, L. Cincio, and M. Cerezo, Computing exact moments of local random quantum circuits via tensor networks, Quantum Machine Intelligence6, 54 (2024)

    2024

  155. [163]

    Letcher, S

    A. Letcher, S. Woerner, and C. Zoufal, Tight and efficient gradient bounds for parameterized quantum circuits, Quantum8, 1484 (2024)

    2024

  156. [164]

    Pesah, M

    A. Pesah, M. Cerezo, S. Wang, T. Volkoff, A. T. Sornborger, and P. J. Coles, Absence of barren plateaus in quantum convolutional neural networks, Physical Review X11, 041011 (2021)

    2021

  157. [165]

    A. W. Harrow and R. A. Low, Random quantum circuits are approximate 2-designs, Communications in Mathematical Physics291, 257 (2009)

    2009

  158. [166]

    F. G. Brandao, A. W. Harrow, and M. Horodecki, Local random quantum circuits are approximate polynomial-designs, Communications in Mathematical Physics346, 397 (2016)

    2016

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.