Title | A quantum central path algorithm for linear optimization |

Publication Type | Journal Article |

Year of Publication | 2023 |

Authors | Augustino, B, Leng, J, Nannicini, G, Terlaky, T, Wu, X |

Date Published | 11/7/2023 |

Abstract | 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⋅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. |

URL | https://arxiv.org/abs/2311.03977 |