Supervisor

Suitable for

Abstract

Prerequisites: 

Desirable: Courses in Quantum Information / Quantum Computation / Classical Complexity course. This is non-essential and can be picked up quickly.

Essential: Familiarity with the basics of Quantum Information and Computation as described in this short set of lecture notes (https://www.qi.damtp.cam.ac.uk/files/PartIIIQC/Part%20IIC%20QIC/PartIIC%20QIClectures%20Full.pdf)

 

Background

Constraint satisfaction problems serve as a foundational framework for understanding a wide variety of computational problems. Since it is impossible to solve many of those exactly in polynomial time (assuming P != NP), we turn to studying approximation algorithms. These algorithms often solve a relaxed version of the problem as a semi-definite program (SDP), which can be efficiently optimized. The SDP solution is then ‘rounded’ to a feasible configuration that maximizes the number of satisfied constraints. A landmark example is the Goemans-Williamson algorithm for Max-Cut [GW95], which uses hyperplane rounding to achieve an approximation ratio of 0.878. The PCP theorem establishes that finding a solution within a certain constant factor of the optimum is NP-hard. Furthermore, stronger assumptions like the Unique Games Conjecture suggest that SDP rounding approaches achieve provably optimal approximation ratios [KKMO07]."

The quantum counterpart to constraint satisfaction is the Local Hamiltonian Problem, which aims to find the minimum eigenvalue of a given local Hamiltonian. As the canonical QMA-complete problem, it also motivates the study of approximation algorithms. The challenge is even more intriguing because in the quantum setting one has to take into account the monogamy of entanglement – a fundamental quantum constraint on correlations between systems.

In the last 5 years there has been fascinating progress to achieve higher approximation ratio in the quantum case using diverse approaches. In 2020, authors in [AGM20] achieved approximation ratio of 0.53 in the worst case. This was followed by hardness results in 2022 by [HNPTW23]: it is Unique Games-hard to compute a (0.956 + epsilon)-approximation to the value of the best state. Shortly after, the achievable approximation ratio was improved to 0.582 by using techniques which involve rounding a semi-definite program relaxation to an entangled state. Further insights were obtained in [WCEHK24] by an extension of non-commutative Sum of Squares optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut and its subsequent refinement in [R23] with improved scaling in [HTPG24]. Another improvement to the achievable approximation of 0.595 in the worst case was obtained by [LP24] in 2024. Lastly, towards the end of 2024 authors in [KKZ24] introduced a Hamiltonian Quantum Approximate Optimization Algorithm. It builds on the well-known Quantum Approximate Optimization Algorithm which is a variational quantum approximation algorithm designed for classical combinatorial optimization problems on near-term hardware. The quest for higher achievable approximation ratio is still ongoing.

 

Focus

This project will review and analyse (a subset of) existing techniques and discuss their relative merits and limitations for partial and worse-case instances.

 

Method

A natural starting point is [K23]. Depending on a personal preference and/or familiarity with a particular technique, the project will review the ideas from the subset of references that correspond to the chosen technique(s) and study their limitations in special cases (e.g. on triangle-free graphs).

 

References

[AGM20] Anshu, A., Gosset, D., & Morenz, K. (2020). Beyond product state approximations for a quantum analogue of max cut. arXiv preprint arXiv:2003.14394. (In proceedings of 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020))

[HNPTW23] Hwang, Y., Neeman, J., Parekh, O., Thompson, K., & Wright, J. (2023). Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 1319-1384). Society for Industrial and Applied Mathematics

[K23] King, R. (2023). An improved approximation algorithm for quantum max-cut on triangle-free graphs. Quantum, 7, 1180.

[WCEHK24] Watts, A. B., Chowdhury, A., Epperly, A., Helton, J. W., & Klep, I. (2024). Relaxations and exact solutions to quantum Max Cut via the algebraic structure of swap operators. Quantum, 8, 1352.

[R23] Rao, S. (2023). Analysis of sum-of-squares relaxations for the quantum rotor model. arXiv preprint arXiv:2311.09010.

[LP24] Lee, E., & Parekh, O. (2024). An improved Quantum Max Cut approximation via matching. arXiv preprint arXiv:2401.03616.

[HTPG24] Huber, F., Thompson, K., Parekh, O., & Gharibian, S. (2024). Second order cone relaxations for quantum Max Cut.  arXiv:2411.04120.

[KKZ24] Kannan, I., King, R., & Zhou, L. (2024). A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems. arXiv preprint arXiv:2412.09221.