Validation and benchmarking of quantum annealing technology

• URL: http://arxiv.org/abs/2312.03534v1
• Date: Wed, 6 Dec 2023 14:56:45 GMT
• Title: Validation and benchmarking of quantum annealing technology
• Authors: Konrad Ja{\l}owiecki
• Abstract summary: This thesis focuses on the problem of benchmarking and validating quantum annealers. We propose two algorithms for solving real-world problems and test how they perform on the current generation of quantum annealers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this thesis, we focus on the problem of validating and benchmarking quantum annealers. To this end, we propose two algorithms for solving real-world problems and test how they perform on the current generation of quantum annealers. The first algorithm allows for solving the dynamics of quantum systems (or, in fact, any dynamical systems). The second of the proposed algorithms is suitable for solving a particular family of railway dispatching problems. We assess the performance of those algorithms on the current generation of D-Wave quantum annealers with the assistance of two novel, classical strategies for solving an Ising model also presented in the thesis. The first, tensor network-based approach is a heuristic algorithm tailored for solving instances defined on Chimera-like graphs, thus making it ideal for providing a baseline with which the results from physical annealers can be compared. The other presented approach is a massively parallel implementation of the exhaustive (brute-force) search through the whole solution space. Although the brute-force approach is limited to moderate instance sizes, it has the advantage of being able to compute the low energy spectrum and certify the solutions. Our results suggest that present-day quantum annealers are able to solve a subset of the aforementioned problems. In particular, we show that the D-Wave annealers are capable of capturing the dynamics of a simple quantum system in a specific regime of parameters, and can be used to obtain good-quality solutions for instances of railway conflict management problems. Finally, our findings indicate that the current generation of D-Wave annealers is far from perfect. We discuss problem instances for which the annealers failed to find a good or even feasible solution. We also provide, where possible, a plausible explanation of why some of the presented problems might be hard for the annealers.

Related papers

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Formulation and evaluation of ocean dynamics problems as optimization problems for quantum annealing machines [0.0]
  Recent advancements in quantum computing suggest the potential to revolutionize computational algorithms across various scientific domains. Quantum computation is so different from classical computation that suitable frameworks to represent oceanic and atmospheric dynamics are yet to be explored.
  arXiv  Detail & Related papers  (2024-05-20T04:55:32Z)
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems [0.0]
  Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
  arXiv  Detail & Related papers  (2023-11-16T09:19:01Z)
• Hybrid quantum-classical and quantum-inspired classical algorithms for solving banded circulant linear systems [0.8192907805418583]
  We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems. By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$. We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
  arXiv  Detail & Related papers  (2023-09-20T16:27:16Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• 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)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• 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)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
  Linear constraints reduce the size of problems that can be represented in quantum annealers. We propose a method for solving a sparse QAP by applying a post-processing bit-flip algorithm to solutions obtained by the Ohzeki method. We successfully solved a QAP of size 19 with high accuracy for the first time using D-Wave Advantage.
  arXiv  Detail & Related papers  (2020-12-18T09:48:28Z)

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.