Degeneracy Engineering for Classical and Quantum Annealing: A Case Study of Sparse Linear Regression in Collider Physics

Abstract

Classical and quantum annealing are computing paradigms that have been proposed to solve a wide range of optimization problems. In this paper, we aim to enhance the performance of annealing algorithms by introducing the technique of degeneracy engineering, through which the relative degeneracy of the ground state is increased by modifying a subset of terms in the objective Hamiltonian. We illustrate this novel approach by applying it to the example of ${\ell }_0$-norm regularization for sparse linear regression, which is in general an NP-hard optimization problem. Specifically, we show how to cast ${\ell }_0$-norm regularization as a quadratic unconstrained binary optimization (QUBO) problem, suitable for implementation on annealing platforms. As a case study, we apply this QUBO formulation to energy flow polynomials in high-energy collider physics, finding that degeneracy engineering substantially improves the annealing performance. Our results motivate the application of degeneracy engineering to a variety of regularized optimization problems.

arXiv comment22 pages, 7 figures, 1 table, v2: updated to match journal version

References in corpus (28)

• PYTHIA 6.4 Physics and Manual
• PYTHIA 6.2 Physics and Manual
• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Defining and detecting quantum speedup
• Tensor networks for complex quantum systems
• Perspectives of quantum annealing: Methods and implementations
• Energy Correlation Functions for Jet Substructure
• Jet Shapes and Jet Algorithms in SCET
• The Machine Learning Landscape of Top Taggers
• Gaining (Mutual) Information about Quark/Gluon Discrimination
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Adiabatic Quantum Simulation of Quantum Chemistry
• Probing for quantum speedup in spin glass problems with planted solutions
• Quark and Gluon Jet Substructure
• Interplay of quantum and thermal fluctuations in a frustrated magnet
• Energy flow polynomials: A complete linear basis for jet substructure
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Evaluating the noise resilience of variational quantum algorithms
• An operational definition of quark and gluon jets
• Universal Effectiveness of High-Depth Circuits in Variational Eigenproblems
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Quantum adiabatic machine learning with zooming
• Cutting Multiparticle Correlators Down to Size