Skip to content
DraconiticResearch
Search Sources API
189,273 studies31 sourcesUpdated 53 min ago
PreprintCC BY 4.0arXiv

Complexity and Applications of Nearest Stabilizer Product State Problems

  • Daniel Grier
  • Hakop Pashayan
  • Luke Schaeffer
Open at sourcePDFDOICite

Abstract

Consider the following optimization problem over stabilizer product states: given an n-qubit stabilizer state |ψ⟩ and a set of single-qubit stabilizer states S, maximize |⟨ ψ| ϕ1, …, ϕn ⟩|2 over single-qubit stabilizer states |ϕi⟩ ∈ 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.

Related

  1. Learning unknown stabilizer codes using product measurements
    Heather Leitch, Sri. S. Tirukkovalluri, Yingkai Ouyang
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Quantum Complexity and Stabilizer-State Expansions: From Pairing to Deformation in Fermionic Systems
    S. Momme Hengstenberg, Caroline E. P. Robin
    arXivPreprintarXiv licenceFull textCondensed matterNuclear physicsarXiv
  3. Normal Factor Graph Representations of Stabilizer Quantum Codes with Applications
    July X. Li, Pascal O. Vontobel
    arXivPreprintCC BY-NC-ND 4.0Full textQuantum physics & quantum informationarXiv
  4. Clifford-hierarchy stabilizer formalism with applications to twisted quantum doubles
    Christopher Fechisin, Kieran Cooney, Mathi Raja +4
    arXivPreprintCC BY 4.0Full textCondensed matterQuantum physics & quantum informationarXiv
  5. The quantum query complexity of the semigroup product problem
    Troy Lee, Miklos Santha
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{grier2026complexity,
  title = {{Complexity and Applications of Nearest Stabilizer Product State Problems}},
  author = {Daniel Grier and Hakop Pashayan and Luke Schaeffer},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.02037},
  eprint = {2610.02037},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.02037},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Complexity and Applications of Nearest Stabilizer Product State Problems
AU  - Daniel Grier
AU  - Hakop Pashayan
AU  - Luke Schaeffer
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.02037
UR  - https://arxiv.org/abs/2610.02037
AB  - Consider the following optimization problem over stabilizer product states: given an n-qubit stabilizer state |ψ⟩ and a set of single-qubit stabilizer states S, maximize |⟨ ψ| ϕ_1, …, ϕ_n ⟩|^2 over single-qubit stabilizer states |ϕ_i⟩ ∈ 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.
ER  -