pipette
ENEnglish

Complexity and Applications of Nearest Stabilizer Product State Problems

Daniel Grier, Hakop Pashayan, Luke Schaeffer

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 30 pages, 2 figures