Chinmay Nirkhe

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-236

November 23, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-236.pdf

The quantum PCP conjecture is one of the central open questions in quantum complexity theory. It asserts that calculating even a rough approximation to the ground energy of a local Hamiltonian is intractable even for quantum devices. The widely believed separation between the complexity classes NP and QMA necessitates that polynomial length classical proofs do not exist for calculating the ground energy. This further implies that low-energy states of local Hamiltonians cannot be described by constant-depth quantum circuits. The "No low-energy trivial states (NLTS)" conjecture by Freedman and Hastings posited the existence of such Hamiltonians.

This thesis describes a line of research culminating in a proof of the NLTS conjecture, first presented by Anshu, Breuckmann, and Nirkhe. The construction is based on quantum error correction and the thesis elaborates on how error correction, local Hamiltonians, and low-depth quantum circuits are related.

Advisors: Umesh Vazirani

---

BibTeX citation:

@phdthesis{Nirkhe:EECS-2022-236,
    Author= {Nirkhe, Chinmay},
    Title= {Lower bounds on the complexity of quantum proofs},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {Nov},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-236.html},
    Number= {UCB/EECS-2022-236},
    Abstract= {The quantum PCP conjecture is one of the central open questions in quantum complexity theory. It asserts that calculating even a rough approximation to the ground energy of a local Hamiltonian is intractable even for quantum devices. The widely believed separation between the complexity classes NP and QMA necessitates that polynomial length classical proofs do not exist for calculating the ground energy. This further implies that low-energy states of local Hamiltonians cannot be described by constant-depth quantum circuits. The "No low-energy trivial states (NLTS)" conjecture by Freedman and Hastings posited the existence of such Hamiltonians.

This thesis describes a line of research culminating in a proof of the NLTS conjecture, first presented by Anshu, Breuckmann, and Nirkhe. The construction is based on quantum error correction and the thesis elaborates on how error correction, local Hamiltonians, and low-depth quantum circuits are related.},
}

EndNote citation:

%0 Thesis
%A Nirkhe, Chinmay 
%T Lower bounds on the complexity of quantum proofs
%I EECS Department, University of California, Berkeley
%D 2022
%8 November 23
%@ UCB/EECS-2022-236
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-236.html
%F Nirkhe:EECS-2022-236