Improved Stabilizer Estimation via Bell Difference Sampling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908543873974272 |
|---|---|
| author | Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel |
| author_facet | Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel |
| contents | We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results:
- We prove that $Ω(n)$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist.
- Given an $n$-qubit pure quantum state $|ψ\rangle$ that has fidelity at least $τ$ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least $τ- \varepsilon$. The algorithm uses $O(n/(\varepsilon^2τ^4))$ samples and $\exp\left(O(n/τ^4)\right) / \varepsilon^2$ time. In the regime of $τ$ constant, this algorithm estimates stabilizer fidelity substantially faster than the naïve $\exp(O(n^2))$-time brute-force algorithm over all stabilizer states.
- In the special case of $τ> \cos^2(π/8)$, we show that a modification of the above algorithm runs in polynomial time.
- We exhibit a tolerant property testing algorithm for stabilizer states.
The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_13915 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Stabilizer Estimation via Bell Difference Sampling Grewal, Sabee Iyer, Vishnu Kretschmer, William Liang, Daniel Quantum Physics Computational Complexity Data Structures and Algorithms We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: - We prove that $Ω(n)$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. - Given an $n$-qubit pure quantum state $|ψ\rangle$ that has fidelity at least $τ$ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least $τ- \varepsilon$. The algorithm uses $O(n/(\varepsilon^2τ^4))$ samples and $\exp\left(O(n/τ^4)\right) / \varepsilon^2$ time. In the regime of $τ$ constant, this algorithm estimates stabilizer fidelity substantially faster than the naïve $\exp(O(n^2))$-time brute-force algorithm over all stabilizer states. - In the special case of $τ> \cos^2(π/8)$, we show that a modification of the above algorithm runs in polynomial time. - We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory. |
| title | Improved Stabilizer Estimation via Bell Difference Sampling |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2304.13915 |