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 (54)

• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Dynamical suppression of decoherence in two-state quantum systems
• Evaluating analytic gradients on quantum hardware
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Zeno subspaces
• A Theory of Trotter Error
• Semiclassical Fourier Transform for Quantum Computation
• Quantum Zeno dynamics: mathematical and physical aspects
• Unification of Dynamical Decoupling and the Quantum Zeno Effect
• General parameter-shift rules for quantum gradients
• Quantum computing for finance
• Halving the cost of quantum addition
• Novel constructions for the fault-tolerant Toffoli gate
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum Simulations of Classical Annealing Processes
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum Zeno Dynamics
• Fundamental limits of quantum error mitigation
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Efficient synthesis of universal Repeat-Until-Success circuits
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Measurement quantum mechanics and experiments on quantum Zeno effect
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Quantum search by measurement
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Driver Hamiltonians for constrained optimization in quantum annealing
• Quantum walk-based portfolio optimisation
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Stabilizing lattice gauge theories through simplified local pseudo generators
• Combinatorial optimisation via highly efficient quantum walks
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Low depth mechanisms for quantum optimization
• Quantum Zeno Dynamics from General Quantum Operations
• Short-Depth Circuits for Dicke State Preparation
• Enhancing disorder-free localization through dynamically emergent local symmetries
• Quantum arithmetic operations based on quantum Fourier transform on signed integers
• Quantum Image Segmentation Based on Grayscale Morphology
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Threshold-Based Quantum Optimization
• Modular Parity Quantum Approximate Optimization
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Characterizing Error Mitigation by Symmetry Verification in QAOA

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