Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems

Abstract

We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast to the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. Our study includes a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.

References in corpus (9)

• Surface codes: Towards practical large-scale quantum computation
• Suppressing quantum errors by scaling a surface code logical qubit
• Quantum error correction below the surface code threshold
• Mathematical Foundation of Quantum Annealing
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• The effects of mixedness and entanglement on the properties of the entropic uncertainty in Heisenberg model with Dzyaloshinski-Moriya interaction
• Quantum annealing with antiferromagnetic fluctuations
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Transit facility allocation: Hybrid quantum-classical optimization

Cited by in corpus (3)

• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
• Adiabatic Dynamics of Entanglement