Abstract
A celebrated result in classical complexity theory is Savitchâ€™s theorem, which states that nondeterministic polynomialspace computations (NPSPACE) can be simulated by deterministic polyspace computations (PSPACE). In this work, we initiate the study of a quantum analogue of NPSPACE, denoted StreamingQCMASPACE (SQCMASPACE), in which an exponentially long classical proof is streamed to a polyspace quantum verifier. We first show that a quantum analogue of Savitchâ€™s theorem is unlikely to hold, in that SQCMASPACE = NEXP. For completeness, we also introduce the companion class StreamingQMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE = QMAEXP (the quantum analogue of NEXP). Our primary focus, however, is on the study of exponentially long streaming classical proofs, where we next show the following two main results.
The first result shows that, in strong contrast to the classical setting, the solution space of a quantum constraint satisfaction problem (i.e. a local Hamiltonian) is always connected when exponentially long proofs are permitted. For this, we show how to simulate any Lipschitz continuous path on the unit hypersphere via a sequence of local unitary gates, at the expense of blowing up the circuit size. This shows that quantum errorcorrecting codes can be unable to detect one codeword erroneously evolving to another if the evolution happens sufficiently slowly, and answers an open question of [Gharibian, Sikora, ICALP 2015] regarding the Ground State Connectivity problem.
Our second main result is that any SQCMASPACE computation can be embedded into "unentanglement", i.e. into a quantum constraint satisfaction problem with unentangled provers. Formally, we show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, CCC 2012] (QMA(2)complete for 1/poly promise gap), at the expense of scaling the promise gap with the streamed proof size. As a corollary, we obtain the first systematic construction for obtaining QMA(2)type upper bounds on arbitrary multiprover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof. Our construction uses a new technique for exploiting unentanglement to simulate quadratic Boolean functions, which in some sense allows history states to encode the future.
BibTeX  Entry
@InProceedings{gharibian_et_al:LIPIcs.ITCS.2023.53,
author = {Gharibian, Sevag and Rudolph, Dorian},
title = {{Quantum Space, Ground Space Traversal, and How to Embed MultiProver Interactive Proofs into Unentanglement}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {53:153:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17556},
URN = {urn:nbn:de:0030drops175564},
doi = {10.4230/LIPIcs.ITCS.2023.53},
annote = {Keywords: quantum complexity theory, Quantum Merlin Arthur (QMA), QMA(2), ground state connectivity (GSCON), quantum error correction}
}
Keywords: 

quantum complexity theory, Quantum Merlin Arthur (QMA), QMA(2), ground state connectivity (GSCON), quantum error correction 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 