A complete characterization of unitary quantum space

Опубликовано 1 февраля 2017, 0:57

"We give two complete characterizations of unitary quantum space-bounded classes. The first is based on the Matrix Inversion problem for well-conditioned matrices. We show that given the size-n efficient encoding of a 2^{O[k(n)]} x 2^{O[k(n)]} well-conditioned matrix H, approximating a particular entry of H^{-1} is complete for the class of problems solvable by a quantum algorithm that uses O[k(n)] space and performs all quantum measurements at the end of the computation. In particular, the problem of computing entries of H^{-1} for an explicit well-conditioned nxn matrix H is complete for unitary quantum logspace.

We then show that the problem of approximating to high precision the least eigenvalue of a positive semidefinite matrix H, encoded as a classical algorithm, gives a second characterization of unitary quantum space complexity. In the process we also establish an equivalence between unitary quantum space-bounded classes and certain QMA proof systems. As consequences, we establish that $\QMA$ with exponentially small completeness-soundness gap is equal to PSPACE, that determining whether a local Hamiltonian is frustration-free is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states gives less computational power than the ability to prepare the ground state of a generic local Hamiltonian."