Quantum vs classical genetic algorithms: A numerical comparison shows faster convergence

• URL: http://arxiv.org/abs/2207.09251v2
• Date: Fri, 30 Sep 2022 11:56:27 GMT
• Title: Quantum vs classical genetic algorithms: A numerical comparison shows faster convergence
• Authors: Rub\'en Ibarrondo, Giancarlo Gatti, Mikel Sanz
• Abstract summary: We show that some quantum variants outperform all classical ones in convergence speed towards a near-to-optimal result. If this advantage holds for larger systems, quantum genetic algorithms would provide a new tool to address optimization problems with quantum computers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Genetic algorithms are heuristic optimization techniques inspired by Darwinian evolution. Quantum computation is a new computational paradigm which exploits quantum resources to speed up information processing tasks. Therefore, it is sensible to explore the potential enhancement in the performance of genetic algorithms by introducing quantum degrees of freedom. Along this line, a modular quantum genetic algorithm has recently been proposed, with individuals encoded in independent registers comprising exchangeable quantum subroutines [arXiv:2203.15039], which leads to different variants. Here, we address the numerical benchmarking of these algorithms against classical genetic algorithms, a comparison missing from previous literature. To overcome the severe limitations of simulating quantum algorithms, our approach focuses on measuring the effect of quantum resources on the performance. In order to isolate the effect of the quantum resources in the performance, the classical variants have been selected to resemble the fundamental characteristics of the quantum genetic algorithms. Under these conditions, we encode an optimization problem in a two-qubit Hamiltonian and face the problem of finding its ground state. A numerical analysis based on a sample of 200 random cases shows that some quantum variants outperform all classical ones in convergence speed towards a near-to-optimal result. Additionally, we have considered a diagonal Hamiltonian and the Hamiltonian of the hydrogen molecule to complete the analysis with two relevant use-cases. If this advantage holds for larger systems, quantum genetic algorithms would provide a new tool to address optimization problems with quantum computers.

Related papers

• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32: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)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  We introduce an iterative quantum optimization algorithm to solve optimization problems. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement.
  arXiv  Detail & Related papers  (2023-03-09T18:59:37Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum Genetic Algorithm with Individuals in Multiple Registers [0.0]
  We propose a subroutine-based quantum genetic algorithm with individuals codified in independent registers. This distinctive codification allows our proposal to depict all the fundamental elements characterizing genetic algorithms. We study two paradigmatic examples, namely, the biomimetic cloning of quantum observables and the Buv zek-Hillery universal quantum cloning machine.
  arXiv  Detail & Related papers  (2022-03-28T19:05:03Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing [1.7077661158850292]
  We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems. We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer. Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
  arXiv  Detail & Related papers  (2021-07-22T08:12:49Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Resource-efficient encoding algorithm for variational bosonic quantum simulations [0.0]
  In the Noisy Intermediate Scale Quantum (NISQ) era of quantum computing, quantum resources are limited. We present a resource-efficient quantum algorithm for bosonic ground and excited state computations.
  arXiv  Detail & Related papers  (2021-02-23T19:00:05Z)

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.