@article {1760,
title = {A Complete Characterization of Unitary Quantum Space},
year = {2016},
month = {2016/04/05},
abstract = {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 2O(k(n)){\texttimes}2O(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 n{\texttimes}n 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 circuit, 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.},
url = {http://arxiv.org/abs/1604.01384},
author = {Bill Fefferman and Cedric Yen-Yu Lin}
}