A complete characterization of unitary quantum space

Subscribers:
345,000
Published on ● Video Link: https://www.youtube.com/watch?v=RtH8sOdr12w



Duration: 37:23
237 views
1


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




Other Videos By Microsoft Research


2017-01-31Mischa Woods: Applications of recoverability in quantum information
2017-01-31Anand Natarajan: Limitations of semidefinite programs for separable states and entangled games
2017-01-31A parallel repetition theorem for all entangled games
2017-01-31Guillaume Dauphinais: Fault-tolerant error correction for non-abelian anyons
2017-01-31Dominic Williamson: Anyons and matrix product operator algebras
2017-01-31Jonathan Oppenheim: From quantum thermodynamical identities to a second law equality
2017-01-31Operator scaling and applications
2017-01-31Xin Wang: Asymptotic entanglement manipulation under PPT operations: new SDP bounds&irreversibility
2017-01-31Srinivasan Arunachalam: Optimal quantum sample complexity of learning algorithms
2017-01-311. Catalytic Decoupling 2. Deconstruction and conditional erasure of quantum correlations
2017-01-31A complete characterization of unitary quantum space
2017-01-31David Reutter: Biunitary constructions in quantum information
2017-01-31Fernando Brandao: Quantum speed-ups for semidefinite programming
2017-01-31Joseph M. Renes: Belief propagation decoding of quantum channels by passing quantum messages
2017-01-31Anupam Prakash: Quantum recommendation systems
2017-01-31Garnet Chan: Simulating quantum systems on classical computers
2017-01-31Rigetti Computing Software Demo: Forest
2017-01-31Frank Verstraete: The entanglement of distillation for gauge theories
2017-01-31Aram Harrow: Sequential measurements, disturbance and property testing
2017-01-31Carlo Sparaciari: A resource theory for work and heat
2017-01-31Mark Howard: Application of a resource theory for magic states to fault-tolerant quantum computing



Tags:
microsoft research