Feedback-Based Quantum Strategies for Constrained Combinatorial Optimization Problems

Abstract

Feedback-based quantum algorithms have recently emerged as potential methods for approximating the ground states of Hamiltonians. One such algorithm, the feedback-based algorithm for quantum optimization (FALQON), is specifically designed to solve quadratic unconstrained binary optimization problems. Its extension, the feedback-based algorithm for quantum optimization with constraints (FALQON-C), was introduced to handle constrained optimization problems with equality and inequality constraints. In this work, we extend the feedback-based quantum algorithms framework to address a broader class of constraints known as invalid configuration (IC) constraints, which explicitly prohibit specific configurations of decision variables. We first present a transformation technique that converts the constrained optimization problem with invalid configuration constraints into an equivalent unconstrained problem by incorporating a penalizing term into the cost function. Then, leaning upon control theory, we propose an alternative method tailored for feedback-based quantum algorithms that directly tackles IC constraints without requiring slack variables. Our approach introduces a new operator that encodes the optimal feasible solution of the constrained optimization problem as its ground state. Then, a controlled quantum system based on the Lyapunov control technique is designed to ensure convergence to the ground state of this operator. Two approaches are introduced in the design of this operator to address IC constraints: the folded spectrum approach and the deflation approach. These methods eliminate the need for slack variables, significantly reducing the quantum circuit depth and the number of qubits required. We show the effectiveness of our proposed algorithms through numerical simulations.

References in corpus (23)

• Variational Quantum Algorithms
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Perspectives of quantum annealing: Methods and implementations
• Variational Quantum Computation of Excited States
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices
• From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
• Rapid Lyapunov control of finite-dimensional quantum systems
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Feedback-based quantum optimization
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Constrained Optimization via Quantum Zeno Dynamics
• Digital quantum simulation of molecular dynamics and control
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Dynamical simulation via quantum machine learning with provable generalization
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Folded Spectrum VQE : A quantum computing method for the calculation of molecular excited states
• Overcoming the Coherence Time Barrier in Quantum Machine Learning on Temporal Data
• Variational quantum solutions to the Shortest Vector Problem
• Randomized adaptive quantum state preparation
• Scalable circuit depth reduction in feedback-based quantum optimization with a quadratic approximation