pipette
ESEspañol

Complexity and Applications of Nearest Stabilizer Product State Problems

Daniel Grier, Hakop Pashayan, Luke Schaeffer

Preprint

In the authors' words

Consider the following optimization problem over stabilizer product states: given an -qubit stabilizer state and a set of single-qubit stabilizer states , maximize over single-qubit stabilizer states . By varying the set , 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 distinct possible sets , and we show that all but the two simplest of these are -complete.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 30 pages, 2 figures