



01354nas a2200157   4500008004100000245006100041210005900102260001400161520088700175100002301062700001601085700002301101700002001124700001501144856003701159       2023                        eng d00aA quantum central path algorithm for linear optimization0 aquantum central path algorithm for linear optimization  c11/7/20233 a<p>We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. Combining our approach with iterative refinement techniques, we obtain an exact solution to a linear optimization problem involving m constraints and n variables using at most O((m+n)nnz(A)κ(M)L&sdot;polylog(m,n,κ(M))) elementary gates and O(nnz(A)L) classical arithmetic operations, where nnz(A) is the total number of non-zero elements found in the constraint matrix, L denotes binary input length of the problem data, and κ(M) is a condition number that depends only on the problem data.</p>1 aAugustino, Brandon1 aLeng, Jiaqi1 aNannicini, Giacomo1 aTerlaky, Tamás1 aWu, Xiaodi  uhttps://arxiv.org/abs/2311.03977