Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

S. Gharibian, D. Rudolph, ArXiv:2206.05243 (2022).

Download
No fulltext has been uploaded.
Preprint | English
Author
Gharibian, SevagLibreCat ; Rudolph, Dorian
Abstract
Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), where an exponentially long classical proof is streamed to a poly-space quantum verifier. Besides two main results, we also show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. For completeness, we introduce Streaming-QMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE=QMA_EXP (quantum analogue of NEXP). Our first main result shows, in 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 quantum error-correcting 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 multi-prover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof.
Publishing Year
Journal Title
arXiv:2206.05243
LibreCat-ID

Cite this

Gharibian S, Rudolph D. Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement. arXiv:220605243. Published online 2022.
Gharibian, S., & Rudolph, D. (2022). Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement. In arXiv:2206.05243.
@article{Gharibian_Rudolph_2022, title={Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement}, journal={arXiv:2206.05243}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022} }
Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover  Interactive Proofs into Unentanglement.” ArXiv:2206.05243, 2022.
S. Gharibian and D. Rudolph, “Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement,” arXiv:2206.05243. 2022.
Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover  Interactive Proofs into Unentanglement.” ArXiv:2206.05243, 2022.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 2206.05243

Search this title in

Google Scholar