Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians

• URL: http://arxiv.org/abs/2403.04841v1
• Date: Thu, 7 Mar 2024 19:00:06 GMT
• Title: Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
• Authors: Harry Buhrman, Jonas Helsen, Jordi Weggemans
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: (i) Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply uniformly at random from a subset of all possible index combinations, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). (ii) If the $q$-local Hamiltonian problem with constant promise gap can be solved in $\mathsf{QCMA}$, then $\mathsf{QPCP}[q] \subseteq \mathsf{QCMA}$ for any $q \in O(1)$. (iii) If $\mathsf{QMA}(k)$ has a quantum PCP for any $k \leq \text{poly}(n)$, then $\mathsf{QMA}(2) = \mathsf{QMA}$, connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.

Related papers

• Extending Quantum Perceptrons: Rydberg Devices, Multi-Class Classification, and Error Tolerance [67.77677387243135]
  Quantum Neuromorphic Computing (QNC) merges quantum computation with neural computation to create scalable, noise-resilient algorithms for quantum machine learning (QML) At the core of QNC is the quantum perceptron (QP), which leverages the analog dynamics of interacting qubits to enable universal quantum computation.
  arXiv  Detail & Related papers  (2024-11-13T23:56:20Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  We generalize quantum-classical PCPs to allow for $q$ quantum queries to a classical proof. Surprisingly, this shows that we can amplify the promise gap from inverse to constant for constant query quantum-classicals. Even though we can achieve promise gap, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $mathsfQCMA$.
  arXiv  Detail & Related papers  (2024-11-01T18:00:56Z)
• The status of the quantum PCP conjecture (games version) [0.6144680854063939]
  We show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick.
  arXiv  Detail & Related papers  (2024-03-19T18:30:32Z)
• The Power of Lorentz Quantum Computer [6.9754404995027794]
  We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class $text Psharp textP$, demonstrating its equivalence to the complexity class $text Psharp textP$. We show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.
  arXiv  Detail & Related papers  (2024-03-07T03:00:09Z)
• 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)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem. These problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We show that guidable local Hamiltonian problems for both classes of guiding states are $mathsfQCMA$-complete in the inverse-polynomial precision setting.
  arXiv  Detail & Related papers  (2023-02-22T19:00:00Z)
• 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)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• 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.