Quantum optimization with linear Ising penalty functions for customer data science

Abstract

Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behaviour of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective.

16 pages, 11 figures. Published in Physical Review Research with minor differences

References in corpus (22)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Array Programming with NumPy
• Quantum Computing in the NISQ era and beyond
• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum computing for finance: overview and prospects
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Expanding the horizon of automated metamaterials discovery via quantum annealing
• Support vector machines on the D-Wave quantum annealer
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Quantum Annealing for Constrained Optimization
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Driver Hamiltonians for constrained optimization in quantum annealing
• Item Listing Optimization for E-commerce Websites based on Diversity
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• An energetic perspective on rapid quenches in quantum annealing
• Understanding domain-wall encoding theoretically and experimentally
• Parity Quantum Optimization: Encoding Constraints
• Experimental demonstration of improved quantum optimization with linear Ising penalties

Cited by in corpus (4)

• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Structural Comparison of Error Mitigation Methods for Ising Machines: Penalty-Spin Model versus Stacked Model
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems