English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The quantum PCP (QPCP) conjecture states that all problems in QMA, thequantum analogue of NP, admit quantum verifiers that only act on a constantnumber of qubits of a polynomial size quantum proof and have a constant gapbetween completeness and soundness. Despite an impressive body of work tryingto prove or disprove the quantum PCP conjecture, it still remains widely open.The above-mentioned proof verification statement has also been shown equivalentto the QMA-completeness of the Local Hamiltonian problem with constant relativegap. Nevertheless, unlike in the classical case, no equivalent formulation inthe language of multi-prover games is known.  In this work, we propose a new type of quantum proof systems, the PointerQPCP, where a verifier first accesses a classical proof that he can use as apointer to which qubits from the quantum part of the proof to access. We definethe Pointer QPCP conjecture, that states that all problems in QMA admit quantumverifiers that first access a logarithmic number of bits from the classicalpart of a polynomial size proof, then act on a constant number of qubits fromthe quantum part of the proof, and have a constant gap between completeness andsoundness. We define a new QMA-complete problem, the Set Local Hamiltonianproblem, and a new restricted class of quantum multi-prover games, called CRESPgames. We use them to provide two other equivalent statements to the PointerQPCP conjecture: the Set Local Hamiltonian problem with constant relative gapis QMA-complete; and the approximation of the maximum acceptance probability ofCRESP games up to a constant additive factor is as hard as QMA. This is thefirst equivalence between a quantum PCP statement and the inapproximability ofquantum multi-prover games.

Pointer Quantum PCPs and Multi-Prover Games