Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
arXiv:2412.04398 · doi:10.1088/2058-9565/adcae6
Abstract
Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.
18 pages, 6 figures; accepted version
References in corpus (36)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Theory of Quantum Annealing of an Ising Spin Glass
- Perspectives of quantum annealing: Methods and implementations
- Bounds for the adiabatic approximation with applications to quantum computation
- Anderson localization casts clouds over adiabatic quantum optimization
- Quantum annealing of the Traveling Salesman Problem
- Entanglement in a quantum annealing processor
- Quantum versus Classical Annealing of Ising Spin Glasses
- Consistency of the Adiabatic Theorem
- Quantum Annealing: An Overview
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
- Quantum annealing with antiferromagnetic fluctuations
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Analog Quantum Simulation of (1+1)D Lattice QED with Trapped Ions
- Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
- Universality of Entanglement and Quantum Computation Complexity
- Counterdiabatic Optimised Local Driving
- Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
- -body interactions between trapped ion qubits via spin-dependent squeezing
- Competing many-body interactions in systems of trapped ions
- Polymer Physics by Quantum Computing
- Approaching the theoretical limit in quantum gate decomposition
- Floquet engineering topological many-body localized systems
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
- Improved Error Bounds for the Adiabatic Approximation
- Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
- Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
- The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
- Encoding-Independent Optimization Problem Formulation for Quantum Computing
- Quantum Speed-Up at Zero Temperature via Coherent Catalysis
- Polynomial Reduction Methods and their Impact on QAOA Circuits
- The role of higher-order terms in trapped-ion quantum computing with magnetic gradient induced coupling