Session: Quantum Computing for combinatorial optimization
Chair: David Bernal Neira
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)
Talk 1: Super-Quadratic Speedups in Exact Combinatorial Optimization
Speaker: Shouvanik Chakrabarti
Abstract: Recent studies of error correction overheads for quantum algorithms have highlighted the need to identify large algorithmic speedups for industrial problems. In this talk, we describe some recent efforts to rigorously develop and prove these speedups. The focus will be on super-quadratic speedups over Markov Chain search (arXiv:2410.23270) arising from a generalization and extensions of the short path framework of Hastings, and its future refinements by Dalzell, Pancotti, Campbell, and Brandao.
Talk 2: Mixed-integer programming using a photonic quantum computer
Speaker: Farhad Khosravi
Abstract: We propose a scheme for solving mixed-integer programming problems in which the optimization problem is translated to a ground-state preparation problem on a set of bosonic quantum field modes (qumodes). We perform numerical demonstrations by simulating a circuit-based optical quantum computer with each individual qumode prepared in a Gaussian state. We simulate an adiabatic evolution from an initial mixing Hamiltonian, written in terms of the momentum operators of the qumodes, to a final Hamiltonian which is a polynomial of the position and boson number operators. In these demonstrations, we solve a variety of small non-convex optimization problems in integer programming, continuous non-convex optimization, and mixed-integer programming.
Talk 3: Quantum-Inspired Heuristic solvers for Binary Higher-Order and Mixed-Integer Constrained Problems
Speaker: Niraj Kumar
Abstract: Quantum-Inspired Heuristic solvers have recently emerged as techniques inspired from quantum annealing to solve hard optimization problems (arXiv: 2104.14096). While previous studies have primarily focused on graph-based problems with binary variables and quadratic unconstrained objective functions (e.g., MaxCUT), we numerically analyze the performance of these solvers for more complex problems such as Low-correlation Binary Sequence (binary quartic objective function), and mixed-integer problem formulation with inequality constraints. Our results indicate the promise these solvers towards industrially relevant problems, along with highlighting the outstanding unresolved questions.
