The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

• URL: http://arxiv.org/abs/2402.18790v1
• Date: Thu, 29 Feb 2024 01:35:46 GMT
• Title: The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
• Authors: Fernando Granha Jeronimo and Pei Wu
• Abstract summary: 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.
• Score: 55.90795112399611
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum entanglement is a fundamental property of quantum mechanics and plays a crucial role in quantum computation and information. We study entanglement via the lens of computational complexity by considering quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is a longstanding open problem, and only the trivial bounds QMA $\subseteq$ QMA(2) $\subseteq$ NEXP are known. In this work, we study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $\text{QMA}^+(2)$. In this setting, we are able to design proof verification protocols for problems both using logarithmic size quantum proofs and having a constant probability gap in distinguishing yes from no instances. In particular, we design global protocols for small set expansion, unique games, and PCP verification. As a consequence, we obtain NP $\subseteq \text{QMA}^+_{\log}(2)$ with a constant gap. By virtue of the new constant gap, we are able to ``scale up'' this result to $\text{QMA}^+(2)$, obtaining the full characterization $\text{QMA}^+(2)$=NEXP by establishing stronger explicitness properties of the PCP for NEXP. One key novelty of these protocols is the manipulation of quantum proofs in a global and coherent way yielding constant gaps. Previous protocols (only available for general amplitudes) are either local having vanishingly small gaps or treat the quantum proofs as classical probability distributions requiring polynomially many proofs thereby not implying non-trivial bounds on QMA(2). Finally, we show that QMA(2) is equal to $\text{QMA}^+(2)$ provided the gap of the latter is a sufficiently large constant. In particular, if $\text{QMA}^+(2)$ admits gap amplification, then QMA(2)=NEXP.

Related papers

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  We study the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework. We focus on complexity classes p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states. We apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or
  arXiv  Detail & Related papers  (2024-11-06T07:29:52Z)
• 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)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18: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)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  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)
  arXiv  Detail & Related papers  (2022-06-10T17:35:10Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• 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)
• Quantum Proofs of Proximity [6.160793572747927]
  We show that QMA proofs of proximity can be exponentially stronger than classical proofs of proximity and quantum testers. Our results include an algorithmic framework that enables quantum speedups for testing an expressive class of properties. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family.
  arXiv  Detail & Related papers  (2021-05-08T13:15:30Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.