QuEnG Seminar, Computer Science - Stoquastic PCP vs. Randomness

on the October 9, 2019

At 2:00pm
As part of the QuEnG Seminar - Computer Science, we are pleased to welcome Dr Alex Bredariol Grilo from CWI and QuSoft who is interested in Quantum computing, Interactive proof systems and PCPs, Complexity theory, Cryptography.

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the MA-completeness of the problem of deciding whether the groundenergy of a uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show that the gapped version of this problem, i.e. deciding if a given uniform stoquastic local Hamiltonian is frustration-free or has energy at least some constant ?, is in NP. Thus, if there exists a gap-amplification procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap amplification procedure for constraint satisfaction problems in the original PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap amplification procedure exhibits some additional (natural) properties, then P = RP. We feel this work opens up a rich set of new directions to explore, which might lead to progress on both quantum PCP and derandomization. As a small side result, we also show that deciding if commuting stoquastic Hamiltonian is frustration free is in NP. 


Richard EAST will be waiting at the entrance to let people up, any late comers should contact him at rdp.east@gmail.com which he will be monitoring.

Published on September 12, 2019

Practical informations


Laboratoire d'informatique de Grenoble (LIG)
Bâtiment IMAG, 4th Floor - Room 406
700 Avenue Centrale, 38401 Saint-Martin-d'Hères