Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances
- URL: http://arxiv.org/abs/2405.01378v2
- Date: Thu, 1 Aug 2024 11:01:47 GMT
- Title: Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances
- Authors: Valentin Gilbert, Julien Rodriguez, Stéphane Louise,
- Abstract summary: This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers.
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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.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.
Related papers
- Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization.
We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
arXiv Detail & Related papers (2024-07-08T22:02:39Z) - Unlocking Quantum Optimization: A Use Case Study on NISQ Systems [0.0]
This paper considers two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes.
Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.
arXiv Detail & Related papers (2024-04-10T17:08:07Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Accelerating variational quantum algorithms with multiple quantum
processors [78.36566711543476]
Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages.
Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data.
Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
arXiv Detail & Related papers (2021-06-24T08:18:42Z) - QPack: Quantum Approximate Optimization Algorithms as universal
benchmark for quantum computers [1.1602089225841632]
We present QPack, a universal benchmark for Noisy Intermediate-Scale Quantum (NISQ) computers.
QPack evaluates the maximum problem size a quantum computer can solve, the required runtime, as well as the achieved accuracy.
arXiv Detail & Related papers (2021-03-31T16:20:51Z) - Benchmarking quantum co-processors in an application-centric,
hardware-agnostic and scalable way [0.0]
We introduce a new benchmark, dubbed Atos Q-score (TM)
The Q-score measures the maximum number of qubits that can be used effectively to solve the MaxCut optimization problem.
We provide an open-source implementation of Q-score that makes it easy to compute the Q-score of any quantum hardware.
arXiv Detail & Related papers (2021-02-25T16:26:23Z) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
We propose a resource and runtime efficient scheme termed quantum architecture search (QAS)
QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates.
We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
arXiv Detail & Related papers (2020-10-20T12:06:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.