A complete characterization of unitary quantum space

259 views · Published 1 February 2017 · 37:23 · Indexed 8 November 2026

Channel: Microsoft Research · 2017 · Science & Technology

Watch on YouTube

"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."

More from this channel