Comparing the Digital Annealer with Classical Evolutionary Algorithm

• URL: http://arxiv.org/abs/2205.13586v1
• Date: Thu, 26 May 2022 19:04:20 GMT
• Title: Comparing the Digital Annealer with Classical Evolutionary Algorithm
• Authors: Mayowa Ayodele
• Abstract summary: Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA)
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In more recent years, there has been increasing research interest in exploiting the use of application specific hardware for solving optimisation problems. Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA). These solvers have been developed to optimise problems faster than traditional meta-heuristics implemented on general purpose machines. Previous research has shown that these solvers (can optimise many problems much quicker than exact solvers such as GUROBI and CPLEX. Such conclusions have not been made when comparing hardware solvers with classical evolutionary algorithms. Making a fair comparison between traditional evolutionary algorithms, such as Genetic Algorithm (GA), and the DA (or other similar solvers) is challenging because the later benefits from the use of application specific hardware while evolutionary algorithms are often implemented on generation purpose machines. Moreover, quantum or quantum-inspired solvers are limited to solving problems in a specific format. A common formulation used is Quadratic Unconstrained Binary Optimisation (QUBO). Many optimisation problems are however constrained and have natural representations that are non-binary. Converting such problems to QUBO can lead to more problem difficulty and/or larger search space. The question addressed in this paper is whether quantum or quantum-inspired solvers can optimise QUBO transformations of combinatorial optimisation problems faster than classical evolutionary algorithms applied to the same problems in their natural representations. We show that the DA often presents better average objective function values than GA on Travelling Salesman, Quadratic Assignment and Multi-dimensional Knapsack Problem instances.

Related papers

• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04: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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems. However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made.
  arXiv  Detail & Related papers  (2022-10-20T14:54:37Z)
• 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)
• Training variational quantum algorithms is NP-hard [0.7614628596146599]
  We show that the corresponding classical optimization problems are NP-hard. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard.
  arXiv  Detail & Related papers  (2021-01-18T19:00:01Z)
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles [0.0]
  We present a case study for two industrial NP-Hard problems drawn from the strongly developing field of smart-charging of electric vehicles. Quantum algorithms exhibit the same approximation ratios than conventional approximation algorithms, or improve them. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.
  arXiv  Detail & Related papers  (2020-12-29T17:10:31Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Warm-starting quantum optimization [6.832341432995627]
  We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem. This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
  arXiv  Detail & Related papers  (2020-09-21T18:00:09Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17: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.