Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems

Abstract

While variational quantum algorithms (VQAs) have demonstrated considerable success in unconstrained optimization, their application to constrained combinatorial problems face a trade-off. Penalty-based methods, despite their circuit simplicity, suffer from a fundamental limitation: inefficient sampling in vast infeasible regions. This often results in suboptimal solutions that violate constraints and impede convergence to high-quality results. In contrast, ansatz-based approaches enforce solution feasibility by design but require complex, problem-specific circuits that are challenging to implement on current noisy intermediate-scale quantum devices. To overcome these limitations, we introduce an alternative VQA whose core innovation lies in a strategically designed loss function. This function offers a dual advantage. First, it is provably guaranteed that its global minimum corresponds uniquely to the optimal feasible solution, as this is achieved by ensuring universally higher loss values for all infeasible solutions. Second, it furnishes distinct computational pathways for feasible versus infeasible regions, thus creating clear and non competing guidance for the optimizer. As a result of these combined features, the algorithm's overall performance is significantly enhanced. Regarding hardware overhead, our design requires adding only an efficient validation oracle module to the penalty-based circuit, resulting in a circuit complexity significantly lower than that of ansatz-based approaches with their custom mixers. To validate the practical efficiency of our method, we empirically demonstrate its effectiveness by solving minimum vertex cover and maximum independent set problems on random graphs of varying small-scale sizes.

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Annealing and Analog Quantum Computation
• Digitized adiabatic quantum computing with a superconducting circuit
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Digitized-counterdiabatic quantum approximate optimization algorithm
• MAXCUT QAOA performance guarantees for p >1
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Combinatorial optimisation via highly efficient quantum walks
• Approaches to Constrained Quantum Approximate Optimization
• A quantum-inspired tensor network method for constrained combinatorial optimization problems
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Resource-Efficient Hadamard Test Tailored Variational Framework for Nonlinear Dynamics on Quantum Computers