Constrained Optimization via Quantum Zeno Dynamics

Abstract

Constrained optimization problems are ubiquitous in science and industry. Quantum algorithms have shown promise in solving optimization problems, yet none of the current algorithms can effectively handle arbitrary constraints. We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer via repeated projective measurements, requiring only a small number of auxiliary qubits and no post-selection. Our technique has broad applicability, which we demonstrate by incorporating it into the quantum approximate optimization algorithm (QAOA) and variational quantum circuits for optimization. We evaluate our method numerically on portfolio optimization problems with multiple realistic constraints and observe better solution quality and higher in-constraint probability than state-of-the-art techniques. We implement a proof-of-concept demonstration of our method on the Quantinuum H1-2 quantum processor.

References in corpus (12)

• Quantum Zeno dynamics: mathematical and physical aspects
• Quantum computing for finance
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum Simulations of Classical Annealing Processes
• Efficient synthesis of universal Repeat-Until-Success circuits
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Short-Depth Circuits for Dicke State Preparation
• Quantum Image Segmentation Based on Grayscale Morphology
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm

Cited by in corpus (24)

• Quantum computing for finance
• Challenges and Opportunities in Quantum Optimization
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Tight-binding model subject to conditional resets at random times
• Grover Speedup from Many Forms of the Zeno Effect
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum control for the Zeno effect with noise
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Inequality constraints in variational quantum circuits with qudits
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Motion from Measurement: The Role of Symmetry of Quantum Measurements
• Feedback-Based Quantum Strategies for Constrained Combinatorial Optimization Problems
• A Quantum Model for Constrained Markowitz Modern Portfolio Using Slack Variables to Process Mixed-Binary Optimization under QAOA
• Free dilations of families of ${\mathcal{C}}_0$-semigroups and applications to evolution families
• Feedback-Based Quantum Algorithm for Constrained Optimization Problems
• Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Constrained Search in Imaginary Time
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems