Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916953542623232 |
|---|---|
| author | Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel |
| author_facet | Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel |
| contents | We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an $n$-qubit pure state $|ψ\rangle$, we give an efficient algorithm that distinguishes whether $|ψ\rangle$ is (i) Haar-random or (ii) a state with stabilizer fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$ with some stabilizer state), promised that one of these is the case. With black-box access to $|ψ\rangle$, our algorithm uses $O\!\left( k^{12} \log(1/δ)\right)$ copies of $|ψ\rangle$ and $O\!\left(n k^{12} \log(1/δ)\right)$ time to succeed with probability at least $1-δ$, and, with access to a state preparation unitary for $|ψ\rangle$ (and its inverse), $O\!\left( k^{3} \log(1/δ)\right)$ queries and $O\!\left(n k^{3} \log(1/δ)\right)$ time suffice.
As a corollary, we prove that $ω(\log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_14530 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel Quantum Physics Computational Complexity Machine Learning We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an $n$-qubit pure state $|ψ\rangle$, we give an efficient algorithm that distinguishes whether $|ψ\rangle$ is (i) Haar-random or (ii) a state with stabilizer fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$ with some stabilizer state), promised that one of these is the case. With black-box access to $|ψ\rangle$, our algorithm uses $O\!\left( k^{12} \log(1/δ)\right)$ copies of $|ψ\rangle$ and $O\!\left(n k^{12} \log(1/δ)\right)$ time to succeed with probability at least $1-δ$, and, with access to a state preparation unitary for $|ψ\rangle$ (and its inverse), $O\!\left( k^{3} \log(1/δ)\right)$ queries and $O\!\left(n k^{3} \log(1/δ)\right)$ time suffice. As a corollary, we prove that $ω(\log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound. |
| title | Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom |
| topic | Quantum Physics Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2209.14530 |