Jorquera, Z. (CSE) – Quantum Entanglement Bounds and the Approximation Algorithms That Use Them
One of the central challenges in quantum computing is finding or approximating the ground-state energy of a local Hamiltonian, a quantum analogue of classical constraint satisfaction problems (CSPs). Among these, the Quantum Max-Cut problem serves as a canonical example, paralleling the classical Max-Cut problem. Despite its foundational importance in both theoretical computer science and condensed matter physics, our understanding of approximation algorithms for Quantum Max-Cut and related local Hamiltonian problems remains limited, primarily due to the difficulty of representing and optimizing over entangled quantum states.
In this advancement talk, we introduce the quantum information background needed to contextualize the results and the significance of the proposed future work by drawing an analogy to classical optimization. We then investigate approximation algorithms for 2-local Hamiltonians beyond qubit systems, focusing on higher-dimensional qudit analogues, such as Quantum Max-d-Cut and a new problem we introduce: the Maximal Entanglement problem. We establish new entanglement upper bounds for these problems based on the star bound, a key tool for analyzing entanglement monogamy in Hamiltonian optimization. For the Maximal Entanglement problem, we show that these bounds can be efficiently certified via semidefinite programs (SDPs) and that they directly admit a (1/d + O(1/D))-approximation algorithm (where D is the degree of the interaction graph), which beats random assignment. For Quantum Max-d-Cut, the star bound gives a more complicated notion of entanglement, for which we show that the basic SDP can verify this bound for all reduced marginals on up to five vertices when d=3, but likely fails for larger subgraphs. We further propose that b-matchings, with b = d-1, capture the appropriate notion of entanglement for these higher-dimensional Quantum Max-d-Cut systems, analogous to matchings in the qubit/Quantum Max-Cut case. Leveraging this insight, we design a novel 2-matching-based algorithm that outperforms existing approaches for Quantum Max-3-Cut, giving an approximation ratio of 0.555.
The present work advances the theoretical framework for understanding approximations in qudit Hamiltonians and highlights open directions for certifying quantum upper bounds as well as finding lower bounds via approximation algorithms.
Event Host: Zack Jorquera, Ph.D. Student, Computer Science and Engineering
Advisor: Alexandra Kolla
Zoom- https://ucsc.zoom.us/j/98034235739?pwd=k260nd9labWT8xoQ9Cv3m2TATGw7VB.1
