Session: Quantum Linear Algebra and Optimization (Part 2)
Chair: Mohammadhossein Mohammadisiahroudi
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)
Talk 1: Quantum Linear Algebra for Interior Point Methods
Speaker: Mohammadhossein Mohammadisiahroudi
Abstract: Quantum computing has recently emerged as a promising avenue for accelerating large-scale optimization. One notable direction is the use of quantum linear system algorithms to enhance the efficiency of Interior Point Methods. However, a key challenge in Quantum Interior Point Methods (QIPMs) lies in the tomography process, which extracts a classical representation of the Newton system solution from a quantum state. In this talk, we introduce a novel hybrid iterative approach that significantly improves the precision of Newton system solutions, achieving exponential accuracy gains. Additionally, we explore the integration of advanced quantum linear algebra techniques, such as quantum matrix-vector and matrix-matrix multiplications, to further accelerate QIPMs and enhance their practical feasibility.
Talk 2: Quantum Multiplicative Weights SOCP Solver
Speaker: Maria Isabel Franco Garrido
Abstract: Second-order cone programming (SOCP) is a key optimization framework that extends linear and quadratic programming and can be seen as a subset of semidefinite programming (SDP). Its wide applicability in fields such as machine learning, portfolio optimization, robotics, engineering design, and power systems underscores the critical need for faster and scalable solvers. State-of-the-art methods, such as interior-point methods (IPMs), are efficient and widely used in modern solvers; however, as these problems are large-scale, the development of more optimized solvers remains an important area of interest. In this work, we explore multiplicative weights (MW)-based methods as an alternative approach for solving SOCPs, addressing a gap in the classical optimization literature while also investigating quantum speedups. Although MW methods have been successfully applied to linear and semidefinite programs, their potential for SOCPs has remained largely unexplored. We analyze the complexity of our proposed algorithms in terms of query complexity, assuming oracle access to problem data. Our results demonstrate a quadratic quantum speed-up over classical implementations, contingent on the availability of quantum random access memory (QRAM), a common assumption in prior asymptotic analyses.
Talk 3: Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation
Speaker: Sophia Simon
Abstract: In this talk, we present several quantum algorithms for continuous optimization that do not require any gradient estimation. Instead, we encode the optimization problem into the dynamics of a physical system and then leverage existing Hamiltonian simulation algorithms to efficiently simulate the time evolution in a coherent manner. This allows us, in certain cases, to obtain exponentially better query upper bounds relative to the best known upper bounds for optimization schemes based on gradient descent which utilize the quantum computer only for estimating gradients of the objective function.
