On good encodings for quantum annealer and digital optimization solvers

Area of Science:

• Computational physics and operations research.
• Development of quantum-inspired optimization algorithms.

Background:

• Quantum annealing solvers are emerging for complex combinatorial optimization problems.
• These solvers address Ising models, equivalent to Quadratic Unconstrained Binary Optimization (QUBO), requiring effective constraint encoding.

Purpose of the Study:

• To experiment with different constraint encoding strategies for QUBO solvers.
• To evaluate quantum annealing hardware, probabilistic algorithms, and mathematical programming solvers on the cardinality constrained quadratic knapsack problem (CQKP).

Main Methods:

• Investigated various constraint penalization and variable encoding techniques for QUBO.
• Benchmarked three QUBO solvers: D-Wave Advantage (quantum annealing), probabilistic algorithms, and mathematical programming solvers.
• Analyzed resolution quality, time, and persistence values from quantum annealing.

Main Results:

• Linear penalization of the CQKP inequality demonstrated improved performance over current best practices.
• Persistence values from quantum hardware, using linear penalization, matched a specific CQKP metric from literature.
• Quantum annealing solvers showed effectiveness in general-purpose variable fixing for combinatorial optimization.

Conclusions:

• Linear penalization is an effective strategy for handling constraints in QUBO problems.
• Quantum hardware persistence values offer valuable information for optimization algorithms.
• Quantum annealing solvers are suitable for variable fixing in combinatorial optimization.