Quantum annealing for nearest neighbour compliance problem.

Area of Science:

• Quantum Computing
• Computational Complexity
• Quantum Information Science

Background:

• Gate-based quantum computers have constraints where quantum gates must operate on adjacent qubits.
• The Nearest Neighbor Compliance (NNC) problem addresses these constraints by optimizing SWAP-gate insertions.
• Minimizing SWAP-gate count is crucial for efficient quantum computation.

Purpose of the Study:

• To explore the application of Quantum Annealing for solving the NNC problem.
• To propose and evaluate new Quadratic Unconstrained Optimization Problem formulations for NNC.
• To compare the performance of Quantum Annealing against existing methods for NNC.

Main Methods:

• Formulated two Quadratic Unconstrained Optimization Problems tailored for the NNC problem.
• Utilized a contemporary Quantum Annealer to test the proposed formulations.
• Benchmarked the Quantum Annealing approach against previous methods for NNC.

Main Results:

• Quantum Annealing demonstrates a promising potential for addressing the NNC problem.
• The proposed formulations were tested on current quantum annealing hardware.
• Performance comparison indicated the viability of the Quantum Annealing approach.

Conclusions:

• Quantum Annealing is a promising technique for tackling the Nearest Neighbor Compliance problem in quantum computing.
• The primary limitation to practical implementation is the current hardware's ability to find efficient embeddings.
• Further advancements in quantum hardware are needed to fully realize the benefits of Quantum Annealing for NNC.