Warm-starting Quantum Optimization
Thursday January 14, 2021 • 11:00 AM to 12:00 PM
There is an increasing interest in quantum algorithms for problems of combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best approximation ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. Considering that the Unique Games Conjecture is not valid when there are entangled provers, warm-starting quantum algorithms may allow for an improvement over classical algorithms. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
Join us to hear Dr. Daniel J. Egger present his findings from his work in the Quantum Technologies group at IBM Research in Zurich. His research focusses on the control of quantum computers and on the practical applications of quantum algorithms in finance. Dr. Egger joined IBM in 2016. From 2014 to 2016 he worked in the asset management industry as a risk manager. He earned a PhD in theoretical physics in 2014 for his work on quantum simulations and optimal control of quantum computers based on superconducting qubits.
For more information, contact:
Chelsea Donahue, Rethinc. Labs Assistant Director
Chelsea_Donahue@kenan-flagler.unc.edu
Speaker
Dr. Daniel J. Egger Quantum Technologies group at IBM Research in Zurich