Complexity and Applications of Nearest Stabilizer Product State Problems
En palabras de los autores
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.
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 30 pages, 2 figures