On the QUBO formulation of the Hamiltonian cycle problem

Area of Science:

• Quantum Computing
• Combinatorial Optimization
• Computational Complexity

Background:

• Combinatorial problems, particularly large-scale instances, present significant computational challenges.
• Quadratic Unconstrained Binary Optimization (QUBO) models are a key framework in quantum computing for addressing such problems.
• QUBO formulations require specialized approaches due to unique characteristics and quantum hardware constraints.

Purpose of the Study:

• To investigate and analyze QUBO formulations for the Hamiltonian Cycle Problem (HCP).
• To evaluate the effectiveness of different QUBO models, including those inspired by Lagrangian relaxation.
• To assess the impact of a preprocessing methodology on QUBO performance for HCP.

Main Methods:

• Developed and analyzed three QUBO formulations for the HCP.
• Incorporated Lagrangian relaxation techniques into two QUBO formulations.
• Introduced and applied a preprocessing methodology to the QUBO models.
• Evaluated QUBO formulations using D-Wave quantum annealers with fixed qubit topology and resource constraints.

Main Results:

• Experimental studies analyzed the performance of QUBO formulations with and without preprocessing.
• The mapping of QUBOs onto the D-Wave architecture highlighted the importance of efficient model design.
• Performance analysis demonstrated the impact of preprocessing on QUBO model effectiveness for HCP.

Conclusions:

• Efficient QUBO model design is crucial for mapping onto quantum hardware architectures like D-Wave.
• Preprocessing can enhance the performance of QUBO formulations for the Hamiltonian Cycle Problem.
• This research contributes to advancing QUBO applications in quantum computing for combinatorial optimization.