Session: Optimization problems arising in quantum computing and physics
Chair: Ojas Parekh
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)
Talk 1: The quantum nature of classical problems in topological data analysis
Speaker: Sankara Sai Chaithanya Rayudu
Abstract: Recent work has exposed unexpected connections between the complexity of problems in topological data analysis (TDA) and quantum local Hamiltonian problems. We show that a natural TDA problem, gapped homology in independence complexes, is QMA-complete, where QMA is a quantum version of the complexity class NP. We accomplish this by introducing a related new quantum (fermionic) local Hamiltonian version of the classical independent set problem.
Talk 2: Second order cone relaxations for Quantum Max Cut
Speaker: Felix Huber
Abstract: Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-1 of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of 0.526 to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.
Talk 3: Generalized Quantum State Discrimination Tasks
Speaker: Jamie Sikora
Abstract: Quantum state discrimination is a central task in many quantum computing settings where one wishes to identify what quantum state they are holding. We introduce a framework that generalizes many of its variants and present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. Using this, optimal bounds for antidistinguishability will also be presented. This talk is based on arXiv:2312.04023 and arxiv:2311.17047.
