Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances
2405.01378
0
0
Abstract
Benchmarking Quantum Process Units (QPU) at an application level usually requires considering the whole programming stack of the quantum computer. One critical task is the minor-embedding (resp. transpilation) step, which involves space-time overheads for annealing-based (resp. gate-based) quantum computers. This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers (QA). This set of favorable mappings is used to generate a wide diversity of optimization problem instances. We use this method to benchmark QA on large instances of unconstrained and constrained optimization problems and compare the performance of the QPU with efficient classical solvers. The benchmark aims to evaluate and quantify the key characteristics of instances that could benefit from the use of a quantum computer. In this context, existing QA seem best suited for unconstrained problems on instances with densities less than $10%$. For constrained problems, the penalty terms used to encode the hard constraints restrict the performance of QA and suggest that these QPU will be less efficient on these problems of comparable size.
Create account to get full access
Overview
- This paper presents a benchmark for evaluating the performance of quantum annealers using near-optimal minor-embedded instances.
- The authors develop a set of benchmark problems based on the maximum cut (MAXCUT) and maximum independent set (MIS) problems, which are challenging optimization problems.
- They generate a set of problem instances that are close to the optimal solution, making them a rigorous test for quantum annealers.
- The goal is to provide a standardized way to compare the performance of different quantum annealing devices and track their improvements over time.
Plain English Explanation
Quantum annealers are a type of quantum computer that can be used to solve complex optimization problems. To benchmark the performance of these devices, the authors of this paper created a set of test problems that are very close to the optimal solution. These problems are based on the maximum cut (MAXCUT) and maximum independent set (MIS) problems, which are well-known optimization challenges.
By using instances that are near-optimal, the authors can put quantum annealers to the test and see how well they perform. This provides a standardized way to compare the capabilities of different quantum annealing devices and track their progress over time. The insights from this benchmark could help guide the development of more powerful quantum computers and their applications in fields like finance, industry, and beyond.
Technical Explanation
The paper introduces a benchmark suite for evaluating the performance of quantum annealers using near-optimal minor-embedded instances. The authors generate problem instances for the MAXCUT and MIS problems that are close to the optimal solution, making them a more rigorous test for quantum annealing devices.
To create these benchmark instances, the authors first generate random graphs and then use a classical optimization algorithm to find near-optimal solutions. They then embed these solutions into the hardware graph of the quantum annealer, a process known as minor embedding. This ensures that the problem instances can be directly executed on the quantum device.
By using instances that are close to the optimal solution, the authors can evaluate the ability of quantum annealers to find high-quality solutions, rather than just their ability to find any solution. This provides a more meaningful assessment of the devices' capabilities and allows for better comparisons between different quantum annealing systems.
Critical Analysis
The authors acknowledge that the benchmark instances they have created are still not as difficult as the hardest instances of the MAXCUT and MIS problems. There may be opportunities to further refine the benchmark suite to increase the challenge for quantum annealers, perhaps by generating instances that are even closer to the optimal solution.
Additionally, the paper does not address the potential impact of noise and errors in the quantum hardware on the performance of the devices. As quantum computers continue to scale up, these practical considerations will become increasingly important for benchmarking their real-world capabilities.
It would also be valuable to see how the performance of quantum annealers on these benchmark instances compares to the performance of classical optimization algorithms, to better understand the relative strengths and weaknesses of the two approaches.
Conclusion
This paper presents a new benchmark for evaluating the performance of quantum annealers using near-optimal minor-embedded instances. By creating challenging optimization problems that are close to the optimal solution, the authors have developed a rigorous test for these quantum devices.
The insights from this benchmark could help drive the development of more powerful quantum computers and enable their application in a wide range of fields, from finance to industry. As quantum technology continues to evolve, this type of standardized benchmarking will be crucial for tracking progress and guiding future research.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Towards Robust Benchmarking of Quantum Optimization Algorithms
David Bucher, Nico Kraus, Jonas Blenninger, Michael Lachner, Jonas Stein, Claudia Linnhoff-Popien
0
0
Benchmarking the performance of quantum optimization algorithms is crucial for identifying utility for industry-relevant use cases. Benchmarking processes vary between optimization applications and depend on user-specified goals. The heuristic nature of quantum algorithms poses challenges, especially when comparing to classical counterparts. A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches. This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks. We discuss (1) application-specific algorithm choice, ensuring every solver is provided with the most fitting mathematical formulation of a problem; (2) the selection of benchmark data, including hard instances and real-world samples; (3) the choice of a suitable holistic figure of merit, like time-to-solution or solution quality within time constraints; and (4) equitable hyperparameter training to eliminate bias towards a particular method. The proposed guidelines are tested across three benchmarking scenarios, utilizing the Max-Cut (MC) and Travelling Salesperson Problem (TSP). The benchmarks employ classical mathematical algorithms, such as Branch-and-Cut (BNC) solvers, classical heuristics, Quantum Annealing (QA), and the Quantum Approximate Optimization Algorithm (QAOA).
5/14/2024
Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All
Valentin Gilbert, St'ephane Louise
0
0
Quantum annealers (QA), such as D-Wave systems, become increasingly efficient and competitive at solving combinatorial optimization problems. However, solving problems that do not directly map the chip topology remains challenging for this type of quantum computer. The creation of logical qubits as sets of interconnected physical qubits overcomes limitations imposed by the sparsity of the chip at the expense of increasing the problem size and adding new parameters to optimize. This paper explores the advantages and drawbacks provided by the structure of the logical qubits and the impact of the rescaling of coupler strength on the minimum spectral gap of Ising models. We show that densely connected logical qubits require a lower chain strength to maintain the ferromagnetic coupling. We also analyze the optimal chain strength variations considering different minor embeddings of the same instance. This experimental study suggests that the chain strength can be optimized for each instance. We design a heuristic that optimizes the chain strength using a very low number of shots during the pre-processing step. This heuristic outperforms the default method used to initialize the chain strength on D-Wave systems, increasing the quality of the best solution by up to 17.2% for tested instances on the max-cut problem.
4/9/2024
🛠️
Dynamic Optimization on Quantum Hardware: Feasibility for a Process Industry Use Case
Dennis Michael Nenno, Adrian Caspari
0
0
The quest for real-time dynamic optimization solutions in the process industry represents a formidable computational challenge, particularly within the realm of applications like model-predictive control, where rapid and reliable computations are critical. Conventional methods can struggle to surmount the complexities of such tasks. Quantum computing and quantum annealing emerge as textit{avant-garde} contenders to transcend conventional computational constraints. We convert a dynamic optimization problem, {characterized by an optimization problem with a system of differential-algebraic equations embedded}, into a Quadratic Unconstrained Binary Optimization problem, enabling quantum computational approaches. The empirical findings synthesized from classical methods, simulated annealing, quantum annealing via D-Wave's quantum annealer, and hybrid solver methodologies, illuminate the intricate landscape of computational prowess essential for tackling complex and high-dimensional dynamic optimization problems. Our findings suggest that while quantum annealing is a maturing technology that currently does not outperform state-of-the-art classical solvers, continuous improvements could eventually aid in increasing efficiency within the chemical process industry.
4/29/2024
Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
Kyle Henke, Elijah Pelofske, Garrett Kenyon, Georg Hahn
0
0
We consider the problem of computing a sparse binary representation of an image. To be precise, given an image and an overcomplete, non-orthonormal basis, we aim to find a sparse binary vector indicating the minimal set of basis vectors that when added together best reconstruct the given input. We formulate this problem with an $L_2$ loss on the reconstruction error, and an $L_0$ (or, equivalently, an $L_1$) loss on the binary vector enforcing sparsity. This yields a quadratic binary optimization problem (QUBO), whose optimal solution(s) in general is NP-hard to find. The method of unsupervised and unnormalized dictionary feature learning for a desired sparsity level to best match the data is presented. Next, we solve the sparse representation QUBO by implementing it both on a D-Wave quantum annealer with Pegasus chip connectivity via minor embedding, as well as on the Intel Loihi 2 spiking neuromorphic processor. On the quantum annealer, we sample from the sparse representation QUBO using parallel quantum annealing combined with quantum evolution Monte Carlo, also known as iterated reverse annealing. On Loihi 2, we use a stochastic winner take all network of neurons. The solutions are benchmarked against simulated annealing, a classical heuristic, and the optimal solutions are computed using CPLEX. Iterated reverse quantum annealing performs similarly to simulated annealing, although simulated annealing is always able to sample the optimal solution whereas quantum annealing was not always able to. The Loihi 2 solutions that are sampled are on average more sparse than the solutions from any of the other methods. Loihi 2 outperforms a D-Wave quantum annealer standard linear-schedule anneal, while iterated reverse quantum annealing performs much better than both unmodified linear-schedule quantum annealing and iterated warm starting on Loihi 2.
6/3/2024