One for All: A Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems
Lennart Binkowski, Tobias J. Osborne, Marvin Schwiering, René Schwonnek, Timo Ziegler · 2024
Read One for All: A Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems by Lennart Binkowski, Tobias J. Osborne, Marvin Schwiering, René Schwonnek, Timo Ziegler (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00435.txt.
Description
Abstract We present a unified quantum-classical framework for addressing NP-complete constrained combinatorial optimization problems, generalizing the recently proposed Quantum Conic Programming (QCP) approach. Accordingly, it inherits many favorable properties of the original proposal such as mitigation of the effects of barren plateaus and avoidance of NP-hard parameter optimization.
Catalog record
| CREATOR | Lennart Binkowski, Tobias J. Osborne, Marvin Schwiering, René Schwonnek, Timo Ziegler |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-00435
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
One for All: A Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems Lennart Binkowski, Tobias J. Osborne, Marvin Schwiering, René Schwonnek, Timo Ziegler Abstract We present a unified quantum-classical framework for addressing NP-complete constrained combinatorial optimization problems, generalizing the recently proposed Quantum Conic Programming (QCP) approach. Accordingly, it inherits many favorable properties of the original proposal such as mitigation of the effects of barren plateaus and avoidance of NP-hard parameter optimization. By collecting the entire classical feasibility structure in a single constraint, we enlarge QCP’s scope to arbitrary hard-constrained problems. Yet, we prove that the additional restriction is mild enough to still allow for an efficient parameter optimization via the formulation of a generalized eigenvalue problem (GEP) of adaptable dimension. Our rigorous proof further fills some apparent gaps in prior derivations of GEPs from parameter optimization problems. We further detail a measurement protocol for formulating the classical parameter optimization that does not require us to implement any (time evolution with a) problem-specific objective Hamiltonian or a quantum feasibility oracle. Lastly, we prove that, even under the influence of noise, QCP’s parameterized ansatz class always captures the optimum attainable within its generated subcone. All of our results hold true for arbitrarily-constrained combinatorial optimization problems. † † footnotetext: † † footnotetext: Corresponding electronic address: [email protected] I Introduction Optimization is a ubiquitous aspect of various disciplines, arising naturally in economics, society, and science. Decades of advancements in electrical engineering and algorithmic design have pushed the frontier of what is feasible to compute and solve, to the point where even minute improvements often lead to meaningful gains. One promising candidate for significant advancement is the development of quantum computers, where recent experimental milestones Google Quantum AI 2023 ; Evered et al. 2023 ; Bluvstein et al. 2024 ; Iqbal et al. 2024 ; da Silva et al. 2024 ; PsiQuantum Team 2024 are expected to ultimately pave the way from the current noisy intermediate-scale quantum (NISQ) Preskill 2018 devices to fault-tolerant, large-scale quantum processing units (QPUs). Seminal works by Grover 1997 , Kadowaki and Nishimori 1998 , and Farhi et al. 2000 have sparked lasting interest in quantum search and quantum optimization Abbas et al. 2024 , leading to the proposal of frameworks like quantum branch-and-bound Montanaro 2020 ; Ambainis and Kokainis 2017 ; Chakrabarti et al. 2022 , quantum dynamic programming Ambainis et al. 2019 , and quantum solvers for semidefinite programs (SDPs) Brandão and Svore 2017 ; van Apeldoorn et al. 2020 ; Brandão et al. 2019 . The framework most suited for the NISQ era is often deemed to be variational quantum algorithms (VQAs) Peruzzo et al. 2014 ; Farhi et al. 2014 ; Hadfield et al. 2019 ; Cerezo et al. 2021a , consisting of a parameterized quantum circuit (PQC) V_{L}(\theta_{L})\cdots V_{1}(\theta_{1}) dependent on a series of parameters \theta_{j} to be optimized by a classical optimization algorithm. The parameters are optimized in order to yield a high-quality approximation of a given target state, typically the ground state of a target Hamiltonian. However, significant hurdles remain for the widespread application to classical optimization problems: The design of PQCs that respect an optimization problem’s constraints is highly non-trivial and problem-specific Hadfield et al. 2019 , the parameter optimization problem handed to the classical optimizer is often at least as hard as the original problem Bittel and Kliesch 2021 , and VQAs often suffer from the barren plateau phenomenon McClean et al. 2018 ; Campos et al. 2021 ; Cerezo et al. 2021b ; Arrasmith et al. 2021 ; Ortiz Marrero et al. 2021 ; Wang et al. 2021 , where vanishing gradients slow or hinder convergence to an (even local) optimum. In order to address these and other issues, we propose a natural generalization of Quantum Conic Programming (QCP), as introduced in Binkowski et al. 2023 , by expanding QCP from a VQA subroutine for unconstrained optimization problems into a general framework for constrained combinatorial optimization problems. QCP and similar frameworks McClean et al. 2017 ; Huggins et al. 2020 ; Bharti et al. 2022 mitigate the effect of barren plateaus and avoid the overly complex parameter optimization tasks by utilizing non-unitary parameterized gates. These gates are implemented via linear combinations of unitaries (LCU) Childs and Wiebe 2012 ; Chakraborty 2023 , the classical optimization task involves solving a generalized eigenvalue problem (GEP) or, more generally, an SDP. In our generalization, we keep the fundamental design principles of QCP while extending its scope to constrained problems: We enforce feasibility preservation of an LCU step by introducing an additional constraint to the associated parameter optimization problem; yet, under minimal assumptions, we ensure that the resulting optimization problem can again be reduced to a GEP without incurring additional sampling overhead for the QPU. Moreover, we obtain a feasibility-preserving LCU operation even if the individual unitaries are not guaranteed to fully preserve feasibility, thus eliminating the need to handcraft problem-specific PQCs. After reviewing fundamental notions of constrained combinatorial optimization problems, VQAs — in particular, the Quantum Approximate Optimization Algorithm Farhi et al. 2014 and the Quantum Alternating Operator Ansatz (QAOA) Hadfield et al. 2019 —, and QCP in Section II , we present our general framework in Section III . Here, we first discuss the incorporation of hard-constraints into the parameter optimization problem of QCP before detailing how to formulate the optimization task for a classical computer with the aid of moment matrices. For the latter, we provide a specialized measurement protocol that fully utilizes the underlying classical structure manifested through, e.g., commutativity among all relevant observables. Subsequently, we rigorously reduce the original doubly-constrained parameter optimization problem to a GEP. Our detailed proof of Theorem 3 not only extends, but also completes earlier derivations of the singly-constrained case in terms of mathematical rigor and proper handling of degenerate cases. We further comment on the LCU implementation and its success probability, once the optimal parameters have been obtained, and we later re-establish the connection between QCP and QAOA with its well-established theory for feasibility-preserving PQCs. We conclude this section by revisiting the aforementioned steps from a density-operator perspective. In this framework, we show that even noisy input states require only a pure state preparation for LCU implementation. In Section IV , we discuss the implications and open questions raised by our work. We highlight our framework’s interplay with QAOA, as well as its conceptual independence from it. In particular, we conclude that generalized QCP restores out-of-the-box applicability for hard-constrained problems, a feature unfortunately missing in the extended QAOA framework. II Preliminaries II.1 Constrained combinatorial optimization problems Let \mathbbmss{b}\coloneqq\{0,1\} . A constrained combinatorial optimization problem (CCOP) is formally defined as a triple (n,c,S) , where n\in\mathbb{N} is the problem size, c:\mathbbmss{b}^{n}\rightarrow\mathbb{R} is the objective function, and S\subseteq\mathbbmss{b}^{n} is the feasible set. Given a CCOP, the task is to minimize c over all \bm{b}\in S . Prominent examples of CCOPs are the Job-Shop Scheduling problem Manne 1960 ; Jain and Meeran 1999 ; Zhang et al. 2019 , the Knapsack problem Martello and Toth 1990 ; Kellerer et al. 2004 , the Maximum Independent Set problem Tarjan and Trojanowski 1977 ; Boppana and Halldórsson 1992 ; Fomin et al. 2009 , the Minimum Spanning Tree problem