Quantum Algorithms for Nonconvex Optimization: Theory and Implementation

dc.contributor.advisorWu, Xiaodi XWen_US
dc.contributor.authorLeng, Jiaqien_US
dc.contributor.departmentApplied Mathematics and Scientific Computationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2024-06-29T06:03:09Z
dc.date.available2024-06-29T06:03:09Z
dc.date.issued2024en_US
dc.description.abstractContinuous optimization problems arise in virtually all disciplines of quantitative research. While convex optimization has been well-studied in recent decades, large-scale nonconvex optimization problems remain intractable in both theory and practice. Quantum computers are expected to outperform classical computers in certain challenging computational problems. Some quantum algorithms for convex optimization have shown asymptotic speedups, while the quantum advantage for nonconvex optimization is yet to be fully understood. This thesis focuses on Quantum Hamiltonian Descent (QHD), a quantum algorithm for continuous optimization problems. A systematic study of Quantum Hamiltonian Descent is presented, including theoretical results concerning nonconvex optimization and efficient implementation techniques for quantum computers. Quantum Hamiltonian Descent is derived as the path integral of classical gradient descent algorithms. Due to the quantum interference of classical descent trajectories, Quantum Hamiltonian Descent exhibits drastically different behavior from classical gradient descent, especially for nonconvex problems. Under mild assumptions, we prove that Quantum Hamiltonian Descent can always find the global minimum of an unconstrained optimization problem given a sufficiently long runtime. Moreover, we demonstrate that Quantum Hamiltonian Descent can efficiently solve a family of nonconvex optimization problems with exponentially many local minima, which most commonly used classical optimizers require super-polynomial time to solve. Additionally, by using Quantum Hamiltonian Descent as an algorithmic primitive, we show a quadratic oracular separation between quantum and classical computing. We consider the implementation of Quantum Hamiltonian Descent for two important paradigms of quantum computing, namely digital (fault-tolerant) and analog quantum computers. Exploiting the product formula for quantum Hamiltonian simulation, we demonstrate that a digital quantum computer can implement Quantum Hamiltonian Descent with gate complexity nearly linear in problem dimension and evolution time. With a hardware-efficient sparse Hamiltonian simulation technique known as Hamiltonian embedding, we develop an analog implementation recipe for Quantum Hamiltonian Descent that addresses a broad class of nonlinear optimization problems, including nonconvex quadratic programming. This analog implementation approach is deployed on large-scale quantum spin-glass simulators, and the empirical results strongly suggest that Quantum Hamiltonian Descent has great potential for highly nonconvex and nonlinear optimization tasks.en_US
dc.identifierhttps://doi.org/10.13016/5vrh-y568
dc.identifier.urihttp://hdl.handle.net/1903/32939
dc.language.isoenen_US
dc.subject.pqcontrolledApplied mathematicsen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pqcontrolledOperations researchen_US
dc.subject.pquncontrolledmathematical optimizationen_US
dc.subject.pquncontrollednonconvex optimizationen_US
dc.subject.pquncontrolledquantum algorithmen_US
dc.subject.pquncontrolledquantum computingen_US
dc.titleQuantum Algorithms for Nonconvex Optimization: Theory and Implementationen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Leng_umd_0117E_24216.pdf
Size:
13.13 MB
Format:
Adobe Portable Document Format