Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917409181401088 |
|---|---|
| author | Zhang, Bingzhi Zhuang, Quntao |
| author_facet | Zhang, Bingzhi Zhuang, Quntao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_05433 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Anticoncentrated $n$-bit distribution from $\log(n)$ qubits Zhang, Bingzhi Zhuang, Quntao Quantum Physics Computational Complexity 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. |
| title | Anticoncentrated $n$-bit distribution from $\log(n)$ qubits |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2511.05433 |