Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.02037

Complexity and Applications of Nearest Stabilizer Product State Problems

Daniel Grier, Hakop Pashayan, Luke Schaeffer

quant-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Consider the following optimization problem over stabilizer product states: given an $n$-qubit stabilizer state $\left|ψ\right\rangle$ and a set of single-qubit stabilizer states $S$, maximize $\left|\langle ψ| φ_1, \ldots, φ_n \rangle\right|^2$ over single-qubit stabilizer states $\left|φ_i\right\rangle \in S$. By varying the set $S$, we show that solutions to this problem can be useful in a variety of settings: tighter runtime bounds for certain classical simulation algorithms; measures of entanglement; and the complexity of low-rank matrix completion. Moreover, we give a complete complexity classification of this nearest stabilizer product state problem. After accounting for the symmetries in the Clifford group, there are $9$ distinct possible sets $S$, and we show that all but the two simplest of these are $\NP$-complete.

Comments
30 pages, 2 figures

Related papers

Single-Copy Stabilizer Testing

Marcel Hinsche, Jonas Helsen

We consider the problem of testing whether an unknown $n$-qubit quantum state $|ψ\rangle$ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using $O(n)$ copies, and conversely prove that $Ω(\sqrt{n})$ copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.

arXiv:2410.07986•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•4 citations

Single-copy stabilizer learning: average case and worst case

Gyungmin Cho, Dohun Kim

We study single-copy stabilizer learning, the problem of identifying a stabilizer group of dimension $n-t$ from an $n$-qubit quantum state $ρ$. We obtain two complementary results. First, in the average case, logarithmic-depth local Clifford circuits suffice to efficiently learn almost all stabilizer groups with $t=O(\log n)$, instead of the linear-depth measurements required in previous approaches. We support this result with numerical simulations for systems of up to 100 qubits. Second, we show that, in the worst case, any adaptive single-copy measurement scheme requires a number of samples that scales exponentially in $t$. Together with existing results on two-copy learning, our findings suggest that, for large $t$, identifying Pauli symmetries of a quantum system exhibits a quantum advantage in the learning setting.

quant-pharXiv:2604.24099•Apr 28, 2026•0 citations

Single-Copy Stabilizer Testing

Marcel Hinsche, Jonas Helsen

We consider the problem of testing whether an unknown n-qubit quantum state is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(√n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.

•Jan 1, 2025•0 citations

Stabilizer rank bounds for magic-state orbits

Farrokh Labib, Vincent Russo

Distinct Clifford orbits of magic states can exhibit different stabilizer ranks at small tensor powers. We establish this for qutrits, where the single-qutrit Clifford group has four inequivalent orbits of magic states: Strange, Norrell, Hadamard-eigenstate, and the qutrit T-state, but a nontrivial upper bound on the asymptotic exponent had been pinned down for only the qutrit T-state. For the other three orbits we give explicit stabilizer decompositions, yielding upper bounds on the per-copy asymptotic stabilizer-rank exponent: $γ_S \le \log_3(2)/2 \approx 0.316$ for the Strange state, and $γ_{H_3}, γ_N \le \log_3(4)/3 \approx 0.421$ for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior $γ_{T_3} \le 1/2$ baseline. We also prove the first nontrivial $Ω(m / \log m)$ asymptotic lower bounds for the Hadamard-eigenstate and Norrell orbits, and exhibit two-qutrit Clifford circuits that convert two copies of these states into an injectable phase state with constant success probability, enabling constant-overhead injection of one non-Clifford diagonal gate per orbit. In the case of qubits, we give a closed-form decomposition of the qubit T-type orbit at four copies matching the existing $γ_T \le \log_2(3)/4 \approx 0.396$ exponent via a direct algebraic identity rather than an entangled cat-state construction. An open-source library stabrank accompanies the paper, with Lean 4 proof formalizations of all the decompositions.

quant-pharXiv:2605.28586•May 28, 2026•0 citations

Improved Bounds for Testing Low Stabilizer Complexity States

Saeed Adel Mehraban, Mehrdad Tahmasbi

Stabilizer states are fundamental families of quantum states with crucial applications such as error correction, quantum computation, and simulation of quantum circuits. In this paper, we study the problem of testing how close or far a quantum state is to a stabilizer state. We make two contributions: First, we improve the state-of-the-art parameters for the tolerant testing of stabilizer states. In particular, we show that there is an efficient quantum primitive to distinguish if the maximum fidelity of a quantum state with a stabilizer state is $\geq ε_1$ or $\leq ε_2$, given one of them is the case, provided that $ε_2 \leq ε_1^{O(1)}$. This result improves the parameters in the previous work [AD24] which assumed $ε_2 \leq e^{- 1/ε^{O(1)}_1}$ [AD24]. Our proof technique extends the toolsets developed in [AD24] by applying a random Clifford map which balances the characteristic function of a quantum state, enabling the use of standard proof techniques from higher-order Fourier analysis for Boolean functions [HHL19, Sam07], where improved testing bounds are available. Second, we study the problem of testing low stabilizer rank states. We show that if for an infinite family of quantum states stabilizer rank is lower than a constant independent of system size, then stabilizer fidelity is lower bounded by an absolute constant. Using a result of [GIKL22], one of the implications of this result is that low approximate stabilizer rank states are not pseudo-random. At the same time our work was completed and posted on arXiv, two other groups [BvDH24, ABD24] independently achieved similar exponential to polynomial improvements for tolerant testing, each using a different approach.

arXiv:2410.24202•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•1 citation

Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits

Yifei Huang, Peter J. Love

Bravyi and Gosset [S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016)] recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of $T$ gates in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimension. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations and give an $O({n}^{3})$ algorithm for calculating the inner product of two $n$-qudit stabilizer states.

arXiv:1808.02406•Physical Review A•May 6, 2019•15 citations
Consider the following optimization problem over stabilizer product states: given an nnn-qubit stabilizer state ∣ψ⟩\left|ψ\right\rangle∣ψ⟩ and a set of single-qubit stabilizer states SSS, maximize ∣⟨ψ∣φ1,…,φn⟩∣2\left|\langle ψ| φ_1, \ldots, φ_n \rangle\right|^2∣⟨ψ∣φ1​,…,φn​⟩∣2 over single-qubit stabilizer states ∣φi⟩∈S\left|φ_i\right\rangle \in S∣φi​⟩∈S. By varying the set SSS, we show that solutions to this problem can be useful in a variety of settings: tighter runtime bounds for certain classical simulation algorithms; measures of entanglement; and the complexity of low-rank matrix completion. Moreover, we give a complete complexity classification of this nearest stabilizer product state problem. After accounting for the symmetries in the Clifford group, there are 999 distinct possible sets SSS, and we show that all but the two simplest of these are \NP\NP\NP-complete.
We consider the problem of testing whether an unknown nnn-qubit quantum state ∣ψ⟩|ψ\rangle∣ψ⟩ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n)O(n)O(n) copies, and conversely prove that Ω(n)Ω(\sqrt{n})Ω(n​) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.
We study single-copy stabilizer learning, the problem of identifying a stabilizer group of dimension n−tn-tn−t from an nnn-qubit quantum state ρρρ. We obtain two complementary results. First, in the average case, logarithmic-depth local Clifford circuits suffice to efficiently learn almost all stabilizer groups with t=O(log⁡n)t=O(\log n)t=O(logn), instead of the linear-depth measurements required in previous approaches. We support this result with numerical simulations for systems of up to 100 qubits. Second, we show that, in the worst case, any adaptive single-copy measurement scheme requires a number of samples that scales exponentially in ttt. Together with existing results on two-copy learning, our findings suggest that, for large ttt, identifying Pauli symmetries of a quantum system exhibits a quantum advantage in the learning setting.
We consider the problem of testing whether an unknown n-qubit quantum state is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(√n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.
Distinct Clifford orbits of magic states can exhibit different stabilizer ranks at small tensor powers. We establish this for qutrits, where the single-qutrit Clifford group has four inequivalent orbits of magic states: Strange, Norrell, Hadamard-eigenstate, and the qutrit T-state, but a nontrivial upper bound on the asymptotic exponent had been pinned down for only the qutrit T-state. For the other three orbits we give explicit stabilizer decompositions, yielding upper bounds on the per-copy asymptotic stabilizer-rank exponent: γS≤log⁡3(2)/2≈0.316γ_S \le \log_3(2)/2 \approx 0.316γS​≤log3​(2)/2≈0.316 for the Strange state, and γH3,γN≤log⁡3(4)/3≈0.421γ_{H_3}, γ_N \le \log_3(4)/3 \approx 0.421γH3​​,γN​≤log3​(4)/3≈0.421 for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior γT3≤1/2γ_{T_3} \le 1/2γT3​​≤1/2 baseline. We also prove the first nontrivial Ω(m/log⁡m)Ω(m / \log m)Ω(m/logm) asymptotic lower bounds for the Hadamard-eigenstate and Norrell orbits, and exhibit two-qutrit Clifford circuits that convert two copies of these states into an injectable phase state with constant success probability, enabling constant-overhead injection of one non-Clifford diagonal gate per orbit. In the case of qubits, we give a closed-form decomposition of the qubit T-type orbit at four copies matching the existing γT≤log⁡2(3)/4≈0.396γ_T \le \log_2(3)/4 \approx 0.396γT​≤log2​(3)/4≈0.396 exponent via a direct algebraic identity rather than an entangled cat-state construction. An open-source library stabrank accompanies the paper, with Lean 4 proof formalizations of all the decompositions.
Stabilizer states are fundamental families of quantum states with crucial applications such as error correction, quantum computation, and simulation of quantum circuits. In this paper, we study the problem of testing how close or far a quantum state is to a stabilizer state. We make two contributions: First, we improve the state-of-the-art parameters for the tolerant testing of stabilizer states. In particular, we show that there is an efficient quantum primitive to distinguish if the maximum fidelity of a quantum state with a stabilizer state is ≥ε1\geq ε_1≥ε1​ or ≤ε2\leq ε_2≤ε2​, given one of them is the case, provided that ε2≤ε1O(1)ε_2 \leq ε_1^{O(1)}ε2​≤ε1O(1)​. This result improves the parameters in the previous work [AD24] which assumed ε2≤e−1/ε1O(1)ε_2 \leq e^{- 1/ε^{O(1)}_1}ε2​≤e−1/ε1O(1)​ [AD24]. Our proof technique extends the toolsets developed in [AD24] by applying a random Clifford map which balances the characteristic function of a quantum state, enabling the use of standard proof techniques from higher-order Fourier analysis for Boolean functions [HHL19, Sam07], where improved testing bounds are available. Second, we study the problem of testing low stabilizer rank states. We show that if for an infinite family of quantum states stabilizer rank is lower than a constant independent of system size, then stabilizer fidelity is lower bounded by an absolute constant. Using a result of [GIKL22], one of the implications of this result is that low approximate stabilizer rank states are not pseudo-random. At the same time our work was completed and posted on arXiv, two other groups [BvDH24, ABD24] independently achieved similar exponential to polynomial improvements for tolerant testing, each using a different approach.
Bravyi and Gosset [S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016)] recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of TTT gates in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimension. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations and give an O(n3)O({n}^{3})O(n3) algorithm for calculating the inner product of two nnn-qudit stabilizer states.