Learning stabilizer structure of quantum states
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914140041248768 |
|---|---|
| author | Arunachalam, Srinivasan Dutt, Arkopal |
| author_facet | Arunachalam, Srinivasan Dutt, Arkopal |
| contents | We consider the task of learning a structured stabilizer decomposition of an arbitrary $n$-qubit quantum state $|ψ\rangle$: for $ε> 0$, output a state $|ϕ\rangle$ with stabilizer-rank $\textsf{poly}(1/ε)$ such that $|ψ\rangle=|ϕ\rangle+|ϕ'\rangle$ where $|ϕ'\rangle$ has stabilizer fidelity $< ε$. We first show the existence of such decompositions using the recently established inverse theorem for the Gowers-$3$ norm of states [AD,STOC'25].
To learn this structure, we initiate the task of self-correction of a state $|ψ\rangle$ with respect to a class of states $S$: given copies of $|ψ\rangle$ which has fidelity $\geq τ$ with a state in $S$, output $|ϕ\rangle \in S$ with fidelity $|\langle ϕ| ψ\rangle|^2 \geq τ^C$ for a constant $C>1$. Assuming the algorithmic polynomial Frieman-Rusza (APFR) conjecture in the high doubling regime (whose combinatorial version was recently resolved [GGMT,Annals of Math.'25]), we give a polynomial-time algorithm for self-correction of stabilizer states. Given access to the state preparation unitary $U_ψ$ for $|ψ\rangle$ and its controlled version $cU_ψ$, we give a polynomial-time protocol that learns a structured decomposition of $|ψ\rangle$. Without assuming APFR, we give a quasipolynomial-time protocol for the same task.
As our main application, we give learning algorithms for states $|ψ\rangle$ promised to have stabilizer extent $ξ$, given access to $U_ψ$ and $cU_ψ$. We give a protocol that outputs $|ϕ\rangle$ which is constant-close to $|ψ\rangle$ in time $\textsf{poly}(n,ξ^{\log ξ})$, which can be improved to polynomial-time assuming APFR. This gives an unconditional learning algorithm for stabilizer-rank $k$ states in time $\textsf{poly}(n,k^{k^2})$. As far as we know, learning arbitrary states with even stabilizer-rank $2$ was unknown. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05890 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning stabilizer structure of quantum states Arunachalam, Srinivasan Dutt, Arkopal Quantum Physics Computational Complexity Combinatorics We consider the task of learning a structured stabilizer decomposition of an arbitrary $n$-qubit quantum state $|ψ\rangle$: for $ε> 0$, output a state $|ϕ\rangle$ with stabilizer-rank $\textsf{poly}(1/ε)$ such that $|ψ\rangle=|ϕ\rangle+|ϕ'\rangle$ where $|ϕ'\rangle$ has stabilizer fidelity $< ε$. We first show the existence of such decompositions using the recently established inverse theorem for the Gowers-$3$ norm of states [AD,STOC'25]. To learn this structure, we initiate the task of self-correction of a state $|ψ\rangle$ with respect to a class of states $S$: given copies of $|ψ\rangle$ which has fidelity $\geq τ$ with a state in $S$, output $|ϕ\rangle \in S$ with fidelity $|\langle ϕ| ψ\rangle|^2 \geq τ^C$ for a constant $C>1$. Assuming the algorithmic polynomial Frieman-Rusza (APFR) conjecture in the high doubling regime (whose combinatorial version was recently resolved [GGMT,Annals of Math.'25]), we give a polynomial-time algorithm for self-correction of stabilizer states. Given access to the state preparation unitary $U_ψ$ for $|ψ\rangle$ and its controlled version $cU_ψ$, we give a polynomial-time protocol that learns a structured decomposition of $|ψ\rangle$. Without assuming APFR, we give a quasipolynomial-time protocol for the same task. As our main application, we give learning algorithms for states $|ψ\rangle$ promised to have stabilizer extent $ξ$, given access to $U_ψ$ and $cU_ψ$. We give a protocol that outputs $|ϕ\rangle$ which is constant-close to $|ψ\rangle$ in time $\textsf{poly}(n,ξ^{\log ξ})$, which can be improved to polynomial-time assuming APFR. This gives an unconditional learning algorithm for stabilizer-rank $k$ states in time $\textsf{poly}(n,k^{k^2})$. As far as we know, learning arbitrary states with even stabilizer-rank $2$ was unknown. |
| title | Learning stabilizer structure of quantum states |
| topic | Quantum Physics Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2510.05890 |