The objective of this project is to check D-Wave’s evolution in one year based on previous research project [1] [2]. In order to evaluate this state-of-the-art, the three current D-Wave’s QPU topologies have been used for performance comparison. The aspects that have been studied are time performance, the correctness of results and stability of minor embedding into each type of quantum architecture. The problem that has been used as a test for this performance comparison has been the well-known Travelling Salesman Problem (TSP) with a soft constraint which is Sequential Ordering Problem (SOP). The different setups that have executed each approach are the following: - D-Wave’s Exact solver (using CPU exclusively). - Pure QPU implementation using D-Wave’s Dimod solver. - GPU adapted parallelization of Classical Brute-force algorithm with NVIDIA CUDA API. - D-Wave’s Hybrid solver (which combines QPU together with classical techniques). The results of this project reveal that current quantum resources have some limitations on their own. Using a pure QPU approach achieves no better results than current classical computation (CPU and GPU). However, its importance lies in the simultaneous usage of both quantum and classical resources to leverage the complexity burden and compensate for each other’s weaknesses. This is the quantum hybrid approach, which has proved to achieve nice results. These results took an execution time that is unfeasible for classical computing due to O(N!) complexity of Brute-force algorithms required to solve NP-hard problems like TSP. Regarding topologies, the use of a Zephyr prototype with many fewer qubits than Pegasus and Chimera devices has proven that Zephyr is a much better architecture due to the high connectivity of the qubits lattice that enables better minor-embedding, shorter execution times and more stability in the results obtained.
The objective of this project is to check D-Wave’s evolution in one year based on previous research project [1] [2]. In order to evaluate this state-of-the-art, the three current D-Wave’s QPU topologies have been used for performance comparison. The aspects that have been studied are time performance, the correctness of results and stability of minor embedding into each type of quantum architecture. The problem that has been used as a test for this performance comparison has been the well-known Travelling Salesman Problem (TSP) with a soft constraint which is Sequential Ordering Problem (SOP). The different setups that have executed each approach are the following: - D-Wave’s Exact solver (using CPU exclusively). - Pure QPU implementation using D-Wave’s Dimod solver. - GPU adapted parallelization of Classical Brute-force algorithm with NVIDIA CUDA API. - D-Wave’s Hybrid solver (which combines QPU together with classical techniques). The results of this project reveal that current quantum resources have some limitations on their own. Using a pure QPU approach achieves no better results than current classical computation (CPU and GPU). However, its importance lies in the simultaneous usage of both quantum and classical resources to leverage the complexity burden and compensate for each other’s weaknesses. This is the quantum hybrid approach, which has proved to achieve nice results. These results took an execution time that is unfeasible for classical computing due to O(N!) complexity of Brute-force algorithms required to solve NP-hard problems like TSP. Regarding topologies, the use of a Zephyr prototype with many fewer qubits than Pegasus and Chimera devices has proven that Zephyr is a much better architecture due to the high connectivity of the qubits lattice that enables better minor-embedding, shorter execution times and more stability in the results obtained.
Abstract Quantum annealing (QA) is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. QA in the transverse Ising model, implemented on D-Wave quantum processing units, are available as cloud computing resources. In this study we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-hard discrete combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently quadratic unconstrained binary optimization, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly variable, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size 52, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid-search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples, chain break proportions, and time-to-solution for the maximum clique problem instances. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.
Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem P via QA involves a hardware-aware circuit compilation which requires representing P as a graph GP and embedding it into the hardware connectivity graph GQ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU).
Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of GP -- the logical variables of P -- to a chain of adjacent nodes in GQ by means of one of its minors, so that the arcs of GP are preserved as physical connections among qubits in GQ.
The static topology of hardwired qubits can clearly lead to inefficient compilations because GQ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology GQ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise.
We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map GP into a minor of GQ.
Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of GP, exhibiting smoother scaling of the largest embeddable GP as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.
The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.
Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer.
In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.