Fefferman, Bill ;
Lin, Cedric YenYu
A Complete Characterization of Unitary Quantum Space
Abstract
Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a wellconditioned efficiently encoded 2^k(n) x 2^k(n) matrix is complete for the class of problems solvable by quantum circuits acting on O(k(n)) qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian 2^k(n) x 2^k(n) matrix is also complete for this class. In the logspace case, our results improve on previous results of TaShma by giving new spaceefficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results.
Additionally, as a consequence we show that preciseQMA, the version of QMA with exponentially small completenesssoundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACEcomplete, which we show holds even in the frustrationfree case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states.
Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.
BibTeX  Entry
@InProceedings{fefferman_et_al:LIPIcs:2018:8324,
author = {Bill Fefferman and Cedric YenYu Lin},
title = {{A Complete Characterization of Unitary Quantum Space}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {4:14:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8324},
URN = {urn:nbn:de:0030drops83242},
doi = {10.4230/LIPIcs.ITCS.2018.4},
annote = {Keywords: Quantum complexity, space complexity, complete problems, QMA}
}
2018
Keywords: 

Quantum complexity, space complexity, complete problems, QMA 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

2018 