Hybrid Classical-Quantum Branch-and-Bound Algorithm for Solving Integer Linear Problems.

Area of Science:

• Quantum computing
• Computational optimization
• Logistics

Background:

• Quantum annealers solve Quadratic Unconstrained Binary Optimization (QUBO) problems.
• Large-scale QUBO problems suffer from reduced solution optimality due to thermal noise and other quantum hardware limitations.

Purpose of the Study:

• To propose a hybrid quantum-classical approach to mitigate limitations in quantum annealer performance.
• To enhance the practical applicability of quantum annealers for complex optimization tasks.

Main Methods:

• Implementation of a classical branch-and-bound algorithm to decompose large QUBO problems into smaller sub-problems.
• Analysis of the hybrid approach's performance on the knapsack and traveling salesman problems.
• Utilizing the D-Wave Advantage quantum hardware for experimental validation.

Main Results:

• The branch-and-bound method effectively reduces the qubit requirements for sub-problems.
• Demonstrated a trade-off between the number of computational steps and the acceptable error in quantum solutions.
• Achieved practical results on a commercially available quantum annealer.

Conclusions:

• The proposed hybrid algorithm offers a viable strategy for improving quantum annealer performance on logistic optimization.
• This approach provides a practical framework for balancing computational resources and solution accuracy in quantum computing.