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
- 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 [8.240558902431976]
We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers.
We present LQC algorithms that solve in time the problem of maximum independent set and the problems in the classes of NP, co-NP, PH (polynomial hierarchy), PP (probabilistic-time), and $text Psharp textP$.
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) - Quantum state testing beyond the polarizing regime and quantum
triangular discrimination [0.0]
We introduce proper quantum analogs for time-bounded distribution testing problems with respect to triangular discrimination and the Jensen-Shannon divergence.
These new $mathsfQSZK$-complete problems improve $mathsfQSZK$ containments for QSDP beyond the polarizing regime.
We establish a simple $mathsfQSZK$-hardness for the quantum entropy difference problem.
arXiv Detail & Related papers (2023-03-03T14:25:18Z) - 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) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z)
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.