quant-ph — Quantum Physics

Exact amplitudes of sparse quantum circuits in subexponential time, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

Classical simulation lower bounds for quantum circuits have been derived from the Exponential Time Hypothesis (ETH). However, in October 2026 OpenAI and Anthropic claimed deterministic subexponential algorithms for #k-SAT, refuting ETH, and neither manuscript mentions quantum circuits. We record the corollary. Assuming three internal results of the Anthropic manuscript, one deterministic Turing machine computes the amplitude $\langle y|C|x\rangle$ of a Clifford+T circuit with $G$ two-qubit gates in arbitrary connectivity exactly, as an element of $\mathbb{Z}[\omega]/\sqrt2^{\,k}$ with $\omega=e^{i\pi/4}$, in time $2^{O(G/\sqrt{\log G})}$ whenever the input length $L$ satisfies $\log L\le G^{0.9}$. The proof reads the sum over paths, one bit per wire segment, as an Anthropic-type network, with a Kronecker map for $\mathbb{Z}[\omega]$ and a Galois bound. We machine-check this theorem in Lean 4 (amplitude_TM_rate', amplitude_TM_rate, amplitude_TM; axioms propext, Classical.choice, Quot.sound) on top of Anthropic's Lean development (sources at https://github.com/xennygrimmato/eth-hamiltonicity). On paper only, the method gives exact marginals and exact sampling, depth-$d$ circuits in $2^{O(dn/\sqrt{\log n})}$, and, through OpenAI's tensor-contraction theorem, polynomial space when the number of Hadamard-type gates is $O(G)$. Conversely, constant-depth circuits with $O(n)$ gates encode #3-SAT with $O(n)$ clauses, so the rate matches that of the refutations. We check the fine-grained supremacy conjectures we found against their sources; a counting form of the Calabro-Impagliazzo-Paturi width reduction refutes the gap conjecture of Morimae and Tamaki's depth-scaling paper. Dense statements (cubic phases, permanents, random circuits) survive. Nothing here concerns approximate sampling, the constants are galactic, and everything is conditional on the claimed refutations, which are under review.