Quantum Genetic Algorithm with Individuals in Multiple Registers

• URL: http://arxiv.org/abs/2203.15039v1
• Date: Mon, 28 Mar 2022 19:05:03 GMT
• Title: Quantum Genetic Algorithm with Individuals in Multiple Registers
• Authors: Rub\'en Ibarrondo, Giancarlo Gatti, Mikel Sanz
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Genetic algorithms are heuristic optimization techniques inspired by Darwinian evolution, which are characterized by successfully finding robust solutions for optimization problems. Here, 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, i.e. population-based search with selection of many individuals, crossover, and mutation. Our subroutine-based construction permits us to consider several variants of the algorithm. For instance, we firstly analyze the performance of two different quantum cloning machines, a key component of the crossover subroutine. Indeed, we study two paradigmatic examples, namely, the biomimetic cloning of quantum observables and the Bu\v zek-Hillery universal quantum cloning machine, observing a faster average convergence of the former, but better final populations of the latter. Additionally, we analyzed the effect of introducing a mutation subroutine, concluding a minor impact on the average performance. Furthermore, we introduce a quantum channel analysis to prove the exponential convergence of our algorithm and even predict its convergence-ratio. This tool could be extended to formally prove results on the convergence of general non-unitary iteration-based algorithms.

Related papers

• Incorporating Quantum Advantage in Quantum Circuit Generation through Genetic Programming [10.573861741540853]
  We propose two novel approaches for incorporating quantum advantage metrics into the fitness function of genetic algorithms. We evaluate our approaches based on the Bernstein-Vazirani Problem and the Unstructured Database Search Problem as test cases. Our findings suggest that automated quantum circuit design using genetic algorithms that incorporate a measure of quantum advantage is a promising approach to accelerating the development of quantum algorithms.
  arXiv  Detail & Related papers  (2025-01-16T17:34:34Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach. On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Stochastic gradient descent estimation of generalized matrix factorization models with application to single-cell RNA sequencing data [41.94295877935867]
  Single-cell RNA sequencing allows the quantitation of gene expression at the individual cell level. Dimensionality reduction is a common preprocessing step to simplify the visualization, clustering, and phenotypic characterization of samples. We present a generalized matrix factorization model assuming a general exponential dispersion family distribution. We propose a scalable adaptive descent algorithm that allows us to estimate the model efficiently.
  arXiv  Detail & Related papers  (2024-12-29T16:02:15Z)
• 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)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• A Genetic Quantum Annealing Algorithm [0.0]
  A genetic algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. We present an algorithm which enhances the classical GA with input from quantum annealers.
  arXiv  Detail & Related papers  (2022-09-15T16:59:55Z)
• Variational quantum iterative power algorithms for global optimization [2.526320329485241]
  We introduce a family of variational quantum algorithms called quantum iterative power algorithms (QIPA) QIPA outperforms existing hybrid near-term quantum algorithms of the same kind. We anticipate large-scale implementation and adoption of the proposed algorithm across current major quantum hardware.
  arXiv  Detail & Related papers  (2022-08-22T17:45:14Z)
• Quantum vs classical genetic algorithms: A numerical comparison shows faster convergence [0.0]
  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.
  arXiv  Detail & Related papers  (2022-07-19T13:07:44Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Adaptive Random Quantum Eigensolver [0.0]
  We introduce a general method to parametrize and optimize the probability density function of a random number generator. Our optimization is based on two figures of merit: learning speed and learning accuracy.
  arXiv  Detail & Related papers  (2021-06-28T12:01:05Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)

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.