Caltech Logo

IQI Weekly Seminar

Tuesday, August 30, 2016
3:00pm to 4:00pm
Add to Cal
Annenberg 107
A Complete Characterization of Unitary Quantum Space
Bill Fefferman, UMD JQI,


  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)
For more information, please contact Jackie O'Sullivan by phone at 626.395.4964 or by email at [email protected].