arXiv:2610.02037
Complexity and Applications of Nearest Stabilizer Product State Problems
Daniel Grier, Hakop Pashayan, Luke Schaeffer
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.
AI Summary
The paper studies nearest stabilizer product state optimization: given an $n$-qubit stabilizer state and an allowed set $S$ of single-qubit stabilizer states, maximize the squared overlap with a product of states from $S$. It also allows projection on only $k$ qubits. The question is where optimization becomes hard despite efficient evaluation of individual stabilizer overlaps. The $63$ nonempty choices of $S$ fall into nine single-qubit Clifford-equivalence classes. The decision problem is polynomial-time solvable when $S$ contains one state or one orthogonal pair, and NP-complete in the other seven classes. Search, optimization, and decision variants are polynomial-time equivalent. Hardness for sets containing an incomplete Pauli basis follows from reductions from Max-Lin2. For unions of complete bases, the proof translates overlap optimization into induced-subgraph nullity maximization over $\mathbb F_2$, with optional diagonal modifications. For the graph $H(G)$ obtained by replacing every edge of $G$ with a three-edge path, the key identity is $-\log_2 m=\tau(G)+|E(G)|$, both for allowed $X/Z$ eigenstates and for all six stabilizer states. This establishes hardness via independent set and gives an $O^*(1.1996^{|V(G)|})$ algorithm on this graph family. Connections include restricted binary rank minimization, circuit-dependent Monte Carlo simulation bounds, and stabilizer-restricted entanglement measures. An optimal overlap supplies an orthogonal stabilizer-product decomposition with $1/m$ terms. The computational entanglement applications apply to restricted graph families or related states; unrestricted product-state entanglement measures remain distinct. Efficient simulation bounds and detailed simulation improvements are deferred to future work.
Significant parts of the hardness proofs for $\probdec{220}$ and $\probdec{222}$ were found by an interactive prompting of Gemini 3.1 Pro.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 30 pages, 2 figures