Publications

Leibniz International Proceedings in Informatics, LIPIcs

Parekh, Ojas D.; Thompson, Kevin T.

The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.

Leibniz International Proceedings in Informatics, LIPIcs

Parekh, Ojas D.; Thompson, Kevin T.

The Lasserre Hierarchy, [18, 19], is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems [3, 7, 26]. There is a natural analogous quantum hierarchy [5, 8, 24], which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest [5, 6, 9]. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy [5]. Here we provide the first ever use of the level-2 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut [2, 9]. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-2 hierarchy satisfies many physically-motivated constraints that the level-1 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.

Thompson, Kevin T.

Abstract not provided.