Description and objectives:
In this project we want to investigate quantum versions of constraint satisfaction problems such as K-sat. Suppose we have N quantum bits (spins 1/2) with M constraints that act on them. For quantum K-sat the constraints are given by rank-one projectors acting on K-uples (for K=2 pairs, for K=3 triples, …) of the N quantum bits chosen at random. The goal is to find N-qubit states that satisfy all constraints simultaneously, meaning that the state is a zero eigenstate of all projectors. The problem can be formulated in Hamiltonian language where the later is the sum of the M (non-commuting) rank one projectors. One then wants to find zero-energy ground states of the Hamiltonian. More precisely one wants to determine the phase diagram as a function of the constraint density alpha=M/N. While for K=2 the phase diagram is known to contain a PRODSAT phase of product state ground states for alpha< 1/2 and is UNSAT (no zero energy ground state) for alpha >1/2, the situation is still open for K greater equal to three. It is conjectured that an intermediate phase ENTSAT containing only entangled ground states might exist for greater K. After studying the basic literature (in particular https://arxiv.org/pdf/0910.2058.pdf ) the problem will be approached via various methods. We will in particular look at algorithmic ideas to construct the PRODSAT ground states.
Prerequisite:
None.
Lab and supervisor:
Nicolas Macris (for more information please contact me)
Number of students: one or two students