Iterative Algorithm Improves Problem Mapping on Existing Quantum Hardware

Quantum computers promise to revolutionise computation, but current machines face limitations in how their basic units, qubits, connect to each other. Marcel Seelbach Benkner, Zorah Lähner, and colleagues at the Universität Siegen, along with collaborators at the MPI Informatik and Hamburg University of Technology, present a new approach to overcome these connectivity restrictions without needing to add more qubits. Their research introduces an algorithm that cleverly utilises existing connections, iteratively reconfiguring the problem to fit the hardware, and avoids the computationally difficult process of finding optimal qubit arrangements. This method, demonstrated both in simulations and on a D-Wave Advantage quantum annealer, offers a potentially significant step towards harnessing the full power of near-term quantum devices by making more efficient use of available resources.

Mapping Problems to Limited Quantum Connectivity

Quantum annealing represents a promising new approach to optimization, potentially outperforming traditional methods when tackling complex energy landscapes. However, current quantum annealing experiments face significant limitations in connectivity, as not every qubit can directly interact with every other qubit. This restriction hinders the size and complexity of problems that can be solved, even with increasingly powerful quantum annealing hardware. To overcome this connectivity constraint, researchers typically combine multiple physical qubits into a single “logical” qubit, effectively creating a more versatile, though reduced, system.

This process, known as minor embedding, involves mapping the problem’s connections onto the limited physical connections of the quantum annealer. However, finding an effective minor embedding is computationally difficult, and adds overhead, limiting the size of solvable problems. Researchers have developed a novel algorithm that avoids the need for minor embedding altogether. Instead of combining qubits, their method intelligently utilizes the existing connections on the quantum annealer, focusing on a subset of the problem’s connections in each step. By strategically selecting which connections to prioritize, and then rotating this focus through a random permutation, the algorithm efficiently explores the problem space without requiring additional qubits or complex pre-processing. This iterative approach includes a “damping term” to build upon previous calculations, offering a potential advantage for larger, highly connected problems. The team has validated their method through simulations and experiments on actual D-Wave quantum annealing hardware, demonstrating its practical feasibility.

Connectivity Improves Quantum Annealer Performance

Researchers have developed a new optimization method that significantly improves the performance of quantum annealers, particularly when solving complex problems with limited connectivity between qubits. Current quantum annealers face challenges because not every qubit can directly interact with every other qubit, restricting the types of problems they can efficiently address. Traditional approaches often involve converting a problem into a form that fits the hardware’s limitations, a process known as minor embedding, which can be computationally expensive and limit the size of solvable problems. This new method avoids the need for additional qubits or complex embedding procedures.

Instead, it intelligently utilizes the existing connections within the quantum annealer, iteratively refining the solution by focusing on different parts of the problem in each step. The technique is based on principles similar to those used in classical optimization, specifically proximal gradient descent, but adapted for the unique characteristics of quantum annealing. This allows the method to efficiently navigate the problem landscape and find improved solutions without being hampered by the hardware’s connectivity constraints. Experiments demonstrate that this iterative approach outperforms both standard minor embedding techniques and other local search algorithms, especially when dealing with problems that are difficult to embed.

In tests on the D-Wave Advantage quantum annealer, the new method consistently achieved better results, indicating its practical viability and potential for real-world applications. Notably, the method excels at solving problems with diverse connectivity patterns, including fully connected problems where traditional embedding methods struggle. The researchers highlight that their method is not limited by the specific connectivity structure of the problem instance, offering a significant advantage over approaches that rely on pre-computed embeddings or tailored solutions. This flexibility, combined with its ability to handle larger and more complex problems, positions the new method as a promising advancement in the field of quantum optimization, potentially unlocking the full potential of quantum annealers for a wider range of applications.

Iterative QUBO Solving Without Extra Qubits

This research introduces a novel iterative algorithm for solving complex optimization problems represented as Quadratic Unconstrained Binary Optimization (QUBO) models, particularly when faced with limitations in qubit connectivity. The method avoids the need for additional qubits by strategically utilising existing connections to progressively address different parts of the problem, demonstrating a theoretically proven, though not always strictly maintained, monotonic improvement. The team confirmed the practicality of their approach through experiments on the D-Wave Advantage quantum annealer, achieving promising results on Max-Cut problems with simple +1 and -1 coefficients. While the algorithm struggled with instances containing float-valued weights, it performed well when restricted to binary coefficients, suggesting a sensitivity to problem characteristics and the precision of the QUBO matrix. The authors acknowledge that determining which problem types will benefit most from this splitting method requires further investigation, and that the choice between this iterative approach and traditional minor embedding remains problem-dependent.