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

• URL: http://arxiv.org/abs/2206.05243v1
• Date: Fri, 10 Jun 2022 17:35:10 GMT
• Title: Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
• Authors: Sevag Gharibian and Dorian Rudolph
• Abstract summary: Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. We show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, 2012] (QMA(2)-complete for 1/poly promise gap)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
  We show that non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. We also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false.
  arXiv  Detail & Related papers  (2024-03-07T19:00:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Signal Processing with the one-dimensional quantum Ising model [0.0]
  Quantum Signal Processing (QSP) has emerged as a promising framework to manipulate and determine properties of quantum systems. We provide examples and applications of our approach in diverse fields ranging from space-time dual quantum circuits and quantum simulation, to quantum control.
  arXiv  Detail & Related papers  (2023-09-08T18:01:37Z)
• Space-bounded quantum state testing via space-efficient quantum singular value transformation [2.647089498084052]
  We present a novel complete characterization for space-bounded quantum computation. We consider settings with one-sided error (unitary coRQL) and two-sided error (BQL) Our results reveal that the space-bounded state testing problems all correspond to the same class.
  arXiv  Detail & Related papers  (2023-08-09T17:16:19Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• stateQIP = statePSPACE [0.15229257192293197]
  We study the relation between two such state classes:SDPPSPACE, and stateQIP. Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE. We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
  arXiv  Detail & Related papers  (2023-01-18T19:00:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.