Quantum proofs, the local Hamiltonian problem and applications

Abstract : In QMA, the quantum generalization of the complexity class NP, a quantum state is provided as a proof of a mathematical statement, and this quantum proof can be verified by a quantum algorithm. This complexity class has a very natural complete problem, the Local Hamiltonian problem. Inspired by Condensed Matters Physics, this problem concerns the groundstate energy of quantum systems. In this thesis, we study some problems related to QMA and to the Local Hamiltonian problem. First, we study the difference of power when classical or quantum proofs are provided to quantum verification algorithms. We propose an intermediate setting where the proof is a “simpler” quantum state, and we manage to prove that these simpler states are enough to solve all problems in QMA. From this result, we are able to present a new QMA-complete problem and we also study the one-sided error version of our new complexity class. Secondly, we propose the first relativistic verifiable delegation scheme for quantum computation. In this setting, a classical client delegates her quantumcomputation to two entangled servers who are allowed to communicate, but respecting the assumption that information cannot be propagated faster than speed of light. This protocol is achieved through a one-round two-prover game for the Local Hamiltonian problem where provers only need polynomial time quantum computation and access to copies of the groundstate of the Hamiltonian. Finally, we study the quantumPCP conjecture, which asks if all problems in QMA accept aproof systemwhere only a fewqubits of the proof are checked. Our result consists in proposing an extension of QPCP proof systems where the verifier is also provided an auxiliary classical proof. Based on this proof system, we propose a weaker version of QPCP conjecture. We then show that this new conjecture can be formulated as a Local Hamiltonian problem and also as a problem involving the maximum acceptance probability of multi-prover games. This is the first equivalence of a multi-prover game and some QPCP statement.
Document type :
Complete list of metadatas

Cited literature [120 references]  Display  Hide  Download

Contributor : Abes Star <>
Submitted on : Tuesday, June 11, 2019 - 1:34:31 PM
Last modification on : Thursday, June 13, 2019 - 1:17:59 AM


Version validated by the jury (STAR)


  • HAL Id : tel-02152364, version 1



Alex Bredariol Grilo. Quantum proofs, the local Hamiltonian problem and applications. Computer Arithmetic. Université Sorbonne Paris Cité, 2018. English. ⟨NNT : 2018USPCC051⟩. ⟨tel-02152364⟩



Record views


Files downloads