REVIEW 6 cited by
Quantum Supremacy and the Complexity of Random Circuit Sampling
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum Supremacy and the Complexity of Random Circuit Sampling
read the original abstract
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.
Forward citations
Cited by 6 Pith papers
-
Emergence of the Scrooge Ensemble in the Sachdev-Ye-Kitaev Model
All moments of the projected ensemble in the SYK model exactly coincide with those of the Scrooge ensemble, generated by replica-permutation saddles of the measurement path integral, even at arbitrarily short times.
-
Weak Poincar\'e Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
-
A Kernel-Based Density of States Estimator for Quantum Computing
Haar-averaged Rodeo responses equal the density of states convolved with a kernel fixed by the evolution-time distribution, yielding a single-ancilla quantum DoS estimator.
-
Efficient certification of intractable quantum states with few Pauli measurements
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 ...
-
Generative AI Beyond Tokens: Quantum Resource Consumption of IQP Circuits
γ-sparse IQP generative circuits show weak but consistent magic-to-progress correlation driven by two-qubit gates and produce intermediate states with far lower magic than phase-randomised states sharing the same Born...
-
Position: Quantum Program Generation Must Prioritize Validity Over Probabilistic Scaling
The paper argues that probabilistic scaling alone cannot fix the validity gap in quantum circuit generation, so quantum code assistants must build verification into generation rather than filter outputs after the fact.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.