The main goal of this PhD project is to study the problems that lie in the intersection of quatum Hamiltonian complexity and (classical) derandomization. These are two important topics in the field of Computational Complexity theory of independent interest.

On the one hand, the derandomization problem asks if randomness increases the computational power of polynomial-time computation. More specifically, we are interested in the non- deterministic version of the derandomization conjecture, which roughly says that every problem whose solution can be verified by randomized algorithms can also be verified by deterministic ones. In technical terms, this is stated as NP = MA, where NP is the class of problems with efficient deterministic verification and MA is its randomized analog. It is widely believed that derandomization is possible,and this is supported by plausible assumptions (e.g. the existence of pseudorandom generators, etc.), but proving even weaker versions of this conjecture has been an active area of research.

On the other hand, Hamiltonian complexity lies in the heart of quantum complexity theory due to its relevance for physics and computer science. The central problem here is the following: given as input a local Hamiltonian H that describes the evolution of an n-particle quantum system, find an approximation of the ground-energy of H, which is the value of energy corresponding to the ground- state of H. The importance of this problem was put in evidence by Kitaev, who showed in 1999 that the approximation of the ground-energy of a Hamiltonian, up to an inverse polynomial additive error, is QMA-complete, where QMA is the quantum analog of NP. The quantum PCP conjecture states that approximating the ground-energy of a Hamiltonian up to a constant additive error remains QMA-complete. This conjecture has important consequences to complexity theory and condensed matter physics, e.g. it implies the existence of families of quantum systems with highly entangled states even at « room temperature ».

The surprising relation between derandomization and Hamitlonian complexity was proved by Aharonov and Grilo – one of the co-advisors in this project – (FOCS’19). More concretly, they show that proving the quantum PCP conjecture for a restricted family of quantum Hamiltonians, named Stoquastic Hamiltonians, is actually equivalent to the MA vs. NP questions. For the best of our knowledge, this is the very first approach to prove derandomization statements from results in quantum computing.

It is worthy to mention that stoquastic Hamiltonians arise naturally in quantum physics, and since they do not suffer of what is called the sign problem, they are more amenable to be tackled by classical techniques. Moreover, stoquastic Hamiltonians have practical importance, since, for example, they describe some non-universal quantum computers that were developed in practice, like D-Wave devices.

PhD project

The goal is to strengthen the connection between derandomization and Hamiltonian complexity that was initiated by Grilo and Aharonov.

More concretely, our plan is to try tackle intermediate steps towards a quantum PCP theorem for stoquastic Hamiltoanians. Attacking these « simpler » problems would not only provide valuable insights towards the stoquastic PCP conjecture, but it could also elucidate critical difficulties for the general version of these problems, which remain open.

We now describe some specific problems that could be explore by the PhD candidate:

Low-energy state generation: An important question in Hamiltonian complexity is the efficiency of creating low-energy states of Hamiltonians. Notice that there is always an efficient circuit that constructs the ground-state of classical Hamiltonians (but, finding such a circuit is a hard task since the problem is NP-complete). Quantumly, it is not expected that the ground-state of local Hamiltonians can be efficiently created since this contradicts some believed complexity theoretical assumptions, namely QCMA being different of QMA. However, it is unclear if this (conditional) impossibility also holds for low-energy states of the Hamiltonian. In this context, the No Low-energy Trivial States conjecture (NLTS) was proposed to study « toy » versions of this question. NLTS states that there is a family of Hamiltonians for which constant-depth quantum circuits cannot construct states with low energy. While this statement is reasonable, being even implied by the quantum PCP conjecture, it has been answered only partially and in restricted settings. In this project, we want to study the NLTS conjecture but restricted to stoquastic Hamiltonians. In particular, our goal is to use tools developed in Aharonov and Grilo, together with techniques related to Markov chains, quantum walks, and derandomization, to possibly disprove a stoquastic version of the NLTS conjecture.

Classical simulation of the evolution of stoquastic Hamiltonians. Adiabatic quantum computation is a computational model described by the evolution of quantum systems. Formally, it is defined by two Hamiltonians: the first one has an easy-to-prepare ground-state, whereas the second one encodes the computational problem that we want to solve. The computation is performed by slowly transitioning from the ground-state of the initial Hamiltonian into the ground-state of the final one, which would give us the answer for our computational problem. This model of computation was proposed hoping that it would lead to faster algorithms for combinatorial optimization problems and for this purpose it was used in the (non-universal) D-Wave’s machine. In particular, D-Wave’s devices implement the adiabatic evolution of stoquastic Hamiltonians. Bravyi and Terhal (SICOMP 2009) proved an efficient classical simulation of the adiabatic evolution of a natural subfamily of stoquastic Hamiltonians, namely frustration-free ones. On the other hand, in a recent results by Gilyén, Hastings and Vazirani (STOC 2021) gives some indication that the adiabatic evolution of stoquastic Hamiltonians is strictly more powerful than classical computation, by proving an oracle separation between them. In this project, we want to explore some of the graph-theoretical tools from Aharonov and Grilo, together with new combinatorial techniques from Hodge theory and derandomization to find larger families of Hamiltonians that can be classically simulated. This could be used to achieve further advances on the question « how quantum is the D-Wave machine? ». Moreover, another question in this direction is extending the oracle separation of Hasting to the non-deterministic setting, clarifying the landscape of the complexity of stoquastic Hamiltonians. Pertinence of the project

This PhD project has the potential to achieve important advances in our understanding of the computational power of sub-families of quantum Hamiltonians, which clearly lies in the scope of QICS.

Contact to submit your application :
Damian Markham, damian.markham@lip6.fr
Alex Bredariol Grilo, Alex.Bredariol-Grilo@lip6.fr

We list now some publications from the supervisors that are relevant for this proposal:

Antonio, Markham, Anders, Trade-off between computation time and Hamiltonian degree in adiabatic graph state quantum computation, NJP 16, 113070 (2014)

Aharonov, Grilo, and Liu. StoqMA vs. MA: the power of error reduction. Under submission. Aharonov and Grilo. Two Combinatorial MA-Complete Problems. ITCS 2021
Aharonov and Grilo. Stoquastic PCP vs. Randomness. FOCS 2019 and plenary talk at QIP 2020.