IQI Weekly Seminar

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 2^{O(k(n))} ×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 n × 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.    This is joint work with Cedric Lin (QuICS, University of Maryland)