Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
For quantum computing researchers, this work challenges the foundational assumption linking anticoncentration to quantum advantage, potentially enabling efficient classical simulation of certain random circuit sampling tasks.
The authors show that anticoncentrated n-bit distributions can be generated using only O(log n) qubits via holographic random circuit sampling, contradicting the belief that such distributions require many qubits. They experimentally demonstrate sampling up to 200 classical bits using 20 qubits on IBM Quantum devices.
Random circuit sampling (RCS) is a leading approach to demonstrate quantum advantage, with its believed classical hardness rooted in anticoncentration of output distributions and average-case hardness of probability estimation. Here we show that this association is not fundamental. We introduce holographic random circuit sampling (HRCS), a spatiotemporal protocol that interleaves random unitary evolution with mid-circuit measurements. We prove that $n$ classical bits exhibiting $ε$-approximate anticoncentration of Haar random states can be generated using only $\mathcal{O}(\log n)$ physical qubits and linear depth, establishing a precise space-time trade-off and indicating efficient classical simulation. Our analyses is built upon exact formulas for collision probability and higher-order power sums. Our experimental validation on IBM Quantum devices demonstrates sampling up to 200 classical bits using only 20 qubits.