Approximate hardness of random-circuit sampling
Consider qubits on a square grid, with layers cycling through the four horizontal/vertical even/odd matchings and independent Haar-random two-qubit gates. Prove that a polynomial-time classical sampler within total-variation distance of the ide
Problem statement
Consider qubits on a square grid, with layers cycling through the four horizontal/vertical even/odd matchings and independent Haar-random two-qubit gates. Prove that a polynomial-time classical sampler within total-variation distance of the ideal output on at least a fraction of these circuits would collapse the polynomial hierarchy, using only standard worst-case complexity assumptions.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
The ideal experiment prepares the all-zero state and measures the output in the computational basis. For finite input, each sampled gate is specified to operator-norm precision using polynomially many bits. This deliberately deep benchmark fixes the ensemble, precision, error and success fraction; a shallower depth or a constant-error theorem is a distinct stronger target.
What is known: Bouland–Fefferman–Nirkhe–Vazirani give worst-to-average reductions for exact output probabilities. Movassagh's Cayley-path approach strengthens robustness at high precision. Anticoncentration is available for suitable sufficiently deep ensembles. The missing ingredient is hardness at an approximation scale strong enough for the total-variation sampling reduction, not exact arithmetic alone.
Noisy experimental output distributions are separate targets. Classical simulation results at constant noise strength have assumptions on the noise, depth, circuit ensemble and approximation criterion; they are not a universal theorem for every noisy quantum circuit. The question above is for ideal circuits. Related: A12, A11.
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.