Paper Verdicts

Claim: Most known quantum algorithms (Grover, amplitude amplification, amplitude estimation, Hamiltonian simulation, HHL, ground-state finding) are special cases of polynomial transformations of singular values of block-encoded matrices.

Evidence: Define block encoding of A; show that quantum signal processing extends to QSVT, applying degree-d polynomial f to singular values of A with O(d) queries. Derive existing algorithms as special cases.

Claim: An arbitrary linear combination of unitaries A = Σ αi Ui can be implemented probabilistically with PREP / SELECT / PREP† circuits, with success probability 1/||α||₁².

Evidence: Encode coefficients in an ancilla; controlled-Ui on the system; uncompute coefficients. Measuring 0 on ancilla heralds successful application of A/||α||₁.

Claim: Unstructured search on N items takes O(√N) quantum queries, vs Θ(N) classically.

Evidence: Construct an oracle that flips the sign of marked states; apply the diffusion operator (reflection about |+⟩^n) to amplify their amplitude geometrically. After ≈π√N/4 iterations, measure the marked state with high probability.

Classical baseline: Linear scan Θ(N). For structured search problems (SAT, k-SAT, CSPs) classical solvers exploit structure that Grover cannot — Schöning's algorithm beats Grover's √2^n for 3-SAT.

Follow-up: Boyer-Brassard-Høyer-Tapp (1998) proved Grover is optimal in the query model. ↗

Claim: Quantum computers factor n-bit integers and solve discrete log in time polynomial in n — breaking RSA, Diffie-Hellman, and elliptic-curve cryptography.

Evidence: Reduces factoring to order-finding modulo N; solves order-finding via QFT-based quantum phase estimation on the modular-exponentiation unitary. The classical reduction (continued fractions) recovers the period with high probability.

Classical baseline: General Number Field Sieve: sub-exponential O(exp(c · n^{1/3} · (log n)^{2/3})). Best known classical algorithm; not threatened by anything classical in sight.

Claim: Surface-code logical qubits suppress logical error exponentially with code distance: going from d=3 to d=5 to d=7 halves the logical error rate each step, demonstrating operation below the threshold.

Evidence: Willow (105 superconducting qubits) runs distance-3, 5, and 7 surface codes for ~10^6 cycles each. Logical error per cycle: ≈2.9% at d=3, ≈1.5% at d=5, ≈0.7% at d=7 — Λ ≈ 2 per distance step.

Classical baseline: Classical error correction (LDPC codes, repetition codes) is mature for classical bits; quantum error correction is the unique technology needed for FTQC. Below-threshold operation has been a 25-year goal.

Claim: Neutral-atom array implements 48 logical qubits with [[7,1,3]] color-code error correction; demonstrates non-local logical gates and entanglement.

Evidence: 280 physical qubits reorganized into 48 logical qubits with d=3 color-code encoding. Logical CNOT and entanglement-generation demonstrated below physical-qubit error rates.

Classical baseline: n/a — this is a fundamental capability demonstration, not an advantage claim.

Claim: Trapped-ion logical qubits with [[7,1,3]] color code and lattice surgery operate below physical-qubit error rate, with active syndrome extraction and feed-forward correction.

Evidence: 12 logical qubits demonstrated with logical error per round below physical qubit error per round. Universal Clifford gate set demonstrated fault-tolerantly.

Claim: Tensor-network methods reproduce the Kim et al. 2023 IBM Eagle kicked-Ising-model results in laptop-time, contradicting the 'beyond classical' framing of the IBM paper.

Evidence: Belief-propagation-based MPS contraction reproduces expectation values for the same 127-qubit circuits Kim et al. ran on Eagle, at lower computational cost.

Claim: A 127-qubit IBM Eagle device with zero-noise extrapolation outperforms tensor-network classical simulation on a kicked-Ising-model expectation value computation at large depth.

Evidence: Run a kicked-Ising-model circuit on Eagle with up to 60 Trotter steps; apply zero-noise extrapolation to recover expectation values; compare with brute-force classical methods.

Classical baseline: Tensor-network methods (Begusic, Gray, Chan 2024; Tindall, Fishman, Stoudenmire, Sels 2024; Patra, Akagi, Sels 2023) reproduced the IBM result classically within months — at lower computational cost than the original IBM run on similar problem sizes.

Follow-up: Multiple follow-up papers from independent groups produced equal or better classical results. IBM acknowledged the classical improvements but maintains that the Eagle result is a useful benchmark of hardware capability. ↗

Claim: Even with infinite-shot ideal QAOA at p=11, classical simulated annealing on benchmark MaxCut graphs achieves equivalent or better approximation ratios in less wall-clock time.

Evidence: Large-scale numerical comparison of QAOA (up to p=11) against simulated annealing on graph instances drawn from standard benchmark suites. SA matches or beats QAOA on every tested instance class.

Claim: Classical tensor-network methods can reproduce the Sycamore 2019 sampling task in ~15 hours on a supercomputer — dramatically less than Google's claimed 10,000-year classical-equivalence figure.

Evidence: Use tensor-network contraction with stem-optimization heuristics to compute amplitudes for arbitrary bitstrings; sample from the resulting distribution with XEB fidelity matching Sycamore's experimental fidelity.

Classical baseline: Their own classical algorithm.

Claim: Sycamore (53 qubits) samples from a random-circuit output distribution in 200 seconds; the same task on the Summit supercomputer was claimed to require ~10,000 years.

Evidence: Cross-entropy benchmarking (XEB) showed Sycamore's output is consistent with the target distribution at fidelity 0.002. Classical simulation cost estimated via the Schrödinger-Feynman algorithm.

Classical baseline: Pan & Zhang (2022) reproduced the Sycamore distribution in 15 hours on a Sunway supercomputer using tensor-network methods. Later improvements pushed the classical cost lower still.

Follow-up: The 10,000-year claim did not survive contact with improved tensor-network methods. Google's 2024 Willow XEB result reframed the 'years equivalent' framing similarly. ↗

Claim: Variational Hartree-Fock simulation of H6, H8, H10, and H12 on Sycamore with up to 12 qubits and 72 two-qubit gates, recovering chemical accuracy with active error mitigation.

Evidence: Run Hartree-Fock circuit ansatz with Givens-rotation parameters optimized classically; measure ⟨H⟩ via Pauli decomposition. Apply purification and Richardson extrapolation for error mitigation.

Classical baseline: Classical Hartree-Fock for these molecule sizes is trivial (minutes on a laptop). The point of the paper was *not* to beat classical — it was to demonstrate that variational methods scale on real hardware. Read accordingly.

Claim: Any quantum many-body Hamiltonian with local interactions can be simulated efficiently on a quantum computer via Trotter decomposition.

Evidence: Decompose H = Σ Hk into local terms, approximate e^{-iHt} ≈ (Π e^{-iHk Δt})^r with r steps. First-order Trotter error scales as t²/r.

Classical baseline: Tensor-network methods (DMRG, MPS) handle 1D and weakly-entangled 2D systems extremely well. Strongly correlated 2D and 3D systems remain hard classically.

Claim: There exists a classification problem (based on the discrete-log problem) where a quantum kernel SVM has a provable exponential separation from any efficient classical learning algorithm — and the separation is robust to noise.

Evidence: Construct a synthetic dataset whose hardness is reducible to discrete log. Show that classical learners cannot solve the task efficiently unless discrete log is easy classically; show the quantum kernel SVM solves it efficiently.

Classical baseline: Any classical algorithm with samples — by the discrete-log assumption, none can succeed in polynomial time.

Claim: Local noise in parameterized quantum circuits also induces barren plateaus, independently of expressibility — making variational training even harder than the noiseless case suggests.

Evidence: Analytical proof for depolarizing-noise channel: gradient variance decays exponentially in circuit depth. Numerical verification across several ansatz families.

Claim: Recommendation systems can be solved classically in poly(log N) time with sample-and-query data access — matching the Kerenidis-Prakash 2017 quantum algorithm's asymptotic complexity.

Evidence: Tang gives classical algorithms that, given sample-and-query access to the input matrix (analogous to QRAM), output samples from the same distribution as the quantum algorithm. The exponential gap collapses to a polynomial.

Classical baseline: Tang's algorithms become the classical baseline. The implication for QML: any 'exponential speedup' that requires QRAM-style input access is suspect unless robust to dequantization.

Follow-up: A long series of follow-up dequantizations (PCA, supervised clustering, low-rank linear regression, SDP) by Tang and others through 2019-2022. ↗

Claim: Random parameterized quantum circuits exhibit exponentially vanishing gradients (in the number of qubits) for cost functions sensitive to global properties — making gradient-based training intractable.

Evidence: Compute the variance of partial derivatives over random initialization of parameterized circuits at depth poly(n). For 'sufficiently random' ansätze, variance decays as 2^{-O(n)} — gradients vanish.

Classical baseline: Classical neural networks don't have this problem because their parameter landscapes have favorable structure (lottery-ticket hypothesis, neural tangent kernel theory).

Follow-up: Cerezo et al. (2021): noise-induced barren plateaus. Holmes et al. (2022): expressibility-trainability tradeoff. Mitigation strategies (warm starts, problem-inspired ansätze, local cost functions) developed but none fully solve the issue at scale. ↗

Claim: The exponential speedups claimed for HHL-style QML algorithms require four input-and-output conditions that are rarely all met in practice.

Evidence: Aaronson identifies the four 'fine print' caveats: (1) the matrix must be sparse and well-conditioned, (2) the right-hand side must be efficiently preparable as a quantum state (QRAM), (3) the matrix must be efficiently constructible as a Hamiltonian, (4) the output must be extractable as a useful classical answer with few measurements.

Claim: ML-KEM (formerly CRYSTALS-Kyber) is the NIST standard for post-quantum key encapsulation, based on module learning-with-errors hardness assumptions.

Evidence: Six-year NIST process with public scrutiny. Parameter sets ML-KEM-512/768/1024 targeting 128/192/256-bit security levels respectively. Specified for use in TLS, IPsec, SSH, S/MIME, and other protocols.

Classical baseline: RSA, ECDH — both broken by Shor. Lattice problems remain quantum-hard for known algorithms.

Follow-up: ML-DSA (FIPS 204) for signatures; SLH-DSA (FIPS 205) for hash-based signatures. Cloudflare, Apple, Google, and major cloud providers all deployed ML-KEM in production TLS during 2024-2025. ↗

Claim: RSA-2048 can be factored in 8 hours using approximately 20 million physical qubits with 10⁻³ gate-error superconducting hardware and surface-code FTQC.

Evidence: Detailed resource estimate: surface code at distance 27, T-state distillation factories, modular-exponentiation circuit decomposition. Includes magic-state injection costs.

Classical baseline: GNFS on a classical supercomputer: estimated centuries for RSA-2048 even with substantial classical speedups.

Follow-up: Subsequent estimates with better algorithms (Hänggi et al. 2024, Gidney 2024 updates) bring the qubit count down — but still in the millions. Lattice-surgery improvements and qLDPC codes promise further reductions.

Claim: Original 2018 paper claimed observation of quantized Majorana zero-mode conductance in InSb-Al nanowire devices. Retracted 2021 after the authors acknowledged the data-selection methodology did not justify the original conclusion.

Evidence: Independent re-analysis by other groups (notably the Frolov-Mourik collaboration) showed the conductance plateaus were not robust to data-selection criteria. The authors agreed and retracted.

Claim: Sampling from the output distribution of n indistinguishable photons through a linear interferometer is classically hard, assuming standard complexity assumptions and the permanent-of-Gaussians conjecture.

Evidence: Reduce exact boson sampling to computing matrix permanents (#P-hard). Approximate sampling is hard modulo additional conjectures (anti-concentration, permanent of Gaussian random matrices is hard on average).

Follow-up: Zhong et al. (2020) Jiuzhang Gaussian boson sampling claimed advantage; Oh et al. (2023) PRL classical algorithms reduced the gap dramatically when accounting for photon loss. ↗