pith. sign in

arxiv: 1907.00707 · v1 · pith:YFNQSPRGnew · submitted 2019-06-24 · 🪐 quant-ph · cs.NE

Quantum-Assisted Genetic Algorithm

James King , Masoud Mohseni , William Bernoudy , Alexandre Fr\'echette , Hossein Sadeghi , Sergei V. Isakov , Hartmut Neven , Mohammad H. Amin This is my paper

Pith reviewed 2026-05-25 17:44 UTC · model grok-4.3

classification 🪐 quant-ph cs.NE
keywords quantum annealinggenetic algorithmreverse annealingspin glassoptimizationNISQhybrid quantum-classicalmutation
0
0 comments X

The pith

Quantum-assisted genetic algorithms using reverse annealing find global optima on spin-glass inputs where standard quantum annealing does not.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops quantum-assisted genetic algorithms (QAGAs) that employ reverse quantum annealing to generate mutations while relying on classical mechanisms for crossovers. On a set of spin-glass optimization problems, standard forward quantum annealing rapidly identifies good solutions but fails to reach the global optima, whereas the QAGA succeeds in locating those global optima. A reader would care if this hybrid approach offers a practical way to leverage NISQ devices for solving discrete optimization tasks that challenge both pure quantum and pure classical methods.

Core claim

By incorporating reverse quantum annealing as a novel source of mutations in a genetic algorithm, the resulting QAGA achieves effective discovery of global optima on spin-glass problems, in contrast to standard quantum annealing which finds good but not necessarily optimal solutions quickly.

What carries the argument

Reverse quantum annealing, a class of quantum evolutions that perform quasi-local or quasi-nonlocal search starting from a classical state, serving as mutation operators.

If this is right

  • QAGAs can locate global optima on the tested spin-glass inputs.
  • The combination of quantum fluctuations for mutations and classical crossovers improves performance over standard forward annealing.
  • This interplay suggests a path for practical use of NISQ devices in heuristic optimization.
  • Standard quantum annealing struggles to escape local optima on these inputs despite finding good solutions fast.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Hybrid quantum-classical methods like this may scale to problems where pure classical genetic algorithms require more computational resources for equivalent mutation diversity.
  • Similar reverse-annealing mutations could be tested in other evolutionary algorithms beyond genetic algorithms.
  • The success on spin glasses raises the question of whether the quantum advantage persists when compared to classical algorithms tuned with equivalent mutation statistics.

Load-bearing premise

That mutations generated by the specific reverse-annealing schedules provide statistical properties of search moves that classical mutation operators cannot replicate at comparable computational cost.

What would settle it

Demonstrating that a classical genetic algorithm equipped with mutation operators whose move statistics match those of the reverse annealing achieves equivalent rates of finding global optima on the same spin-glass inputs.

Figures

Figures reproduced from arXiv: 1907.00707 by Alexandre Fr\'echette, Hartmut Neven, Hossein Sadeghi, James King, Masoud Mohseni, Mohammad H. Amin, Sergei V. Isakov, William Bernoudy.

Figure 1
Figure 1. Figure 1: FIG. 1. Sketch of the reverse annealing process. The anneal starts at a specified classical state (left), then performs [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Annealing schedules for canonical forward annealing (left) and reverse annealing (right). In this case the [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Example of recombination on a 2D lattice via isoenergetic cluster move. The two “parent” individuals (left) are [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Performance of QA, QAGA, SA, PT, and PT-ICM on the three input classes studied. Each plot is a swarm [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Head-to-head comparisons of QAGA versus other solvers. Comparisons against QA are in the left column [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript introduces Quantum-Assisted Genetic Algorithms (QAGAs) that employ reverse quantum annealing as a mutation operator within a genetic algorithm, combining it with classical crossover mechanisms. Experimental results on a D-Wave 2000Q processor for spin-glass instances show that the QAGA reaches global optima while standard forward quantum annealing does not.

Significance. If the performance difference is robust and specifically due to the quantum mutation operator rather than classical aspects of the search, the approach would illustrate a practical hybrid strategy for leveraging NISQ devices in heuristic optimization by interleaving quantum fluctuations with classical non-local moves.

major comments (2)
  1. [Abstract] Abstract: the claim that 'our QAGA proves effective at finding global optima for these inputs' while standard QA 'struggles to find global optima' supplies no counts of instances, success probabilities, statistical tests, or certification method for global optimality, leaving the central empirical comparison under-specified.
  2. [Abstract] Abstract: the attribution of the performance gain to 'quantum fluctuation for mutations' requires evidence that the statistical properties of the reverse-annealing trajectories cannot be reproduced by classical mutation operators at comparable computational cost; no such classical baseline (e.g., Monte-Carlo sampling of equivalent intermediate Hamiltonians) is presented.
minor comments (1)
  1. [Abstract] The abstract refers to 'a set of spin-glass inputs' without indicating the number or size of instances; adding this detail would improve reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on the abstract. We address each major comment below and will revise the manuscript to improve precision where appropriate.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that 'our QAGA proves effective at finding global optima for these inputs' while standard QA 'struggles to find global optima' supplies no counts of instances, success probabilities, statistical tests, or certification method for global optimality, leaving the central empirical comparison under-specified.

    Authors: We agree the abstract is concise and would benefit from added quantitative detail. The full manuscript reports results across multiple spin-glass instances with global optima certified via known ground states (for small instances) or established benchmarks, along with observed success rates for QAGA versus standard QA. We will revise the abstract to incorporate representative counts, success probabilities, and a brief note on certification. revision: yes

  2. Referee: [Abstract] Abstract: the attribution of the performance gain to 'quantum fluctuation for mutations' requires evidence that the statistical properties of the reverse-annealing trajectories cannot be reproduced by classical mutation operators at comparable computational cost; no such classical baseline (e.g., Monte-Carlo sampling of equivalent intermediate Hamiltonians) is presented.

    Authors: The performance gains are shown using reverse annealing executed on the D-Wave 2000Q quantum processor. We acknowledge that an explicit classical baseline (such as Monte-Carlo sampling of equivalent Hamiltonians) is not presented. We will add a short discussion in the revised manuscript noting this limitation and the non-trivial nature of constructing an exact classical analog, while emphasizing that the demonstrated hybrid quantum-classical search is the core contribution. revision: partial

Circularity Check

0 steps flagged

No derivation chain present; purely experimental performance comparison

full rationale

The manuscript reports experimental runs of a hybrid genetic algorithm on D-Wave 2000Q hardware, contrasting reverse-annealing mutations against forward annealing on a fixed set of spin-glass instances. No equations, fitted parameters, or first-principles derivations are advanced whose outputs are then re-used as inputs. The central claim is an empirical observation of solution quality on those instances; it does not reduce to any self-referential definition, fitted-input prediction, or self-citation load-bearing step. Self-citations, if present, are incidental and not invoked to establish uniqueness or to close a logical loop. The result is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the domain assumption that reverse annealing schedules can be engineered to act as useful mutation operators and on the experimental observation that the resulting hybrid outperforms standard annealing on the tested instances.

axioms (1)
  • domain assumption Reverse quantum annealing can generate families of quasi-local or quasi-nonlocal search trajectories starting from a classical state.
    Invoked when the abstract introduces reverse annealing as a source of mutations.
invented entities (1)
  • Reverse quantum annealing no independent evidence
    purpose: To supply tunable quantum-fluctuation mutations inside a genetic algorithm.
    Presented as a novel class of quantum evolutions; no independent falsifiable prediction outside the reported experiments is given.

pith-pipeline@v0.9.0 · 5728 in / 1198 out tokens · 31641 ms · 2026-05-25T17:44:06.371295+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms

    quant-ph 2026-05 unverdicted novelty 6.0

    Local degree-dependent controls in Rydberg adiabatic MIS algorithms accelerate convergence and reduce fidelity decay by 25% compared to global controls in numerical simulations.

  2. Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms

    quant-ph 2026-05 unverdicted novelty 6.0

    Engineered local Hamiltonian controls in Rydberg arrays accelerate adiabatic convergence to MIS solutions, raise success probabilities over global controls, and cut fidelity decay rate by 25% as graphs harden.

  3. How to Build a Quantum Supercomputer: Scaling from Hundreds to Millions of Qubits

    quant-ph 2024-11 accept novelty 4.0

    A comprehensive review of scaling paths for superconducting quantum computers, with resource and sensitivity analyses for utility-scale applications under realistic error distributions.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · cited by 2 Pith papers · 7 internal anchors

  1. [1]

    Kadowaki and H

    T. Kadowaki and H. Nishimori, Physical Review E58, 5355 (1998)

    work page 1998

  2. [2]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science220, 671 (1983)

    work page 1983

  3. [3]

    W. K. Wootters and W. H. Zurek, Nature299, 802 (1982)

    work page 1982

  4. [4]

    Quantum assisted optimization,

    V. S. Denchev, M. Mohseni, and H. Neven, “Quantum assisted optimization,” International Patent Application WO 2017/189052 Al (2017)

    work page 2017

  5. [5]

    D-Wave Systems,Reverse Quantum Annealing for Local Refinement of Solutions, Tech. Rep. 14-1018A-A (2017)

    work page 2017

  6. [6]

    Chancellor, New Journal of Physics19, 023024 (2017)

    N. Chancellor, New Journal of Physics19, 023024 (2017)

    work page 2017

  7. [7]

    Chancellor, arXiv:1609.05875 (2016)

    N. Chancellor, arXiv:1609.05875 (2016)

    work page arXiv 2016

  8. [8]

    Barahona, Journal of Physics A: Mathematical and General15, 3241 (1982)

    F. Barahona, Journal of Physics A: Mathematical and General15, 3241 (1982)

    work page 1982

  9. [9]

    Lucas, Frontiers in Physics2 (2014), 10.3389/fphy.2014.00005, arXiv:1302.5843

    A. Lucas, Frontiers in Physics2 (2014), 10.3389/fphy.2014.00005, arXiv:1302.5843

    work page doi:10.3389/fphy.2014.00005 2014

  10. [10]

    D-Wave QPU Architecture: Chimera,

    “D-Wave QPU Architecture: Chimera,”https://docs.dwavesys.com/docs/latest/c_gs_4.html, D-Wave Sys- tem Documentation

    work page

  11. [11]

    Houdayer, The European Physical Journal B-Condensed Matter and Complex Systems22, 479 (2001)

    J. Houdayer, The European Physical Journal B-Condensed Matter and Complex Systems22, 479 (2001)

    work page 2001

  12. [13]

    R. E. Smith, S. Forrest, and A. S. Perelson, Evolutionary Computation1, 127 (1993)

    work page 1993

  13. [14]

    Srinivas and L

    M. Srinivas and L. M. Patnaik, IEEE Transactions on Systems, Man, and Cybernetics24, 656 (1994)

    work page 1994

  14. [15]

    H. M. Pandey, A. Chaudhary, and D. Mehrotra, Applied Soft Computing24, 1047 (2014)

    work page 2014

  15. [16]

    Swendsen and J

    R. Swendsen and J. Wang, Phys. Rev. Lett.57, 2607 (1986)

    work page 1986

  16. [17]

    S. V. Isakov, I. Zintchenko, and M. Troyer, (2014), arXiv:1401.1084v1

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  17. [18]

    T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Science 345, 420 (2014), arXiv:1401.2910

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  18. [19]

    Efficient subgraph-based sampling of Ising-type models with frustration

    A. Selby, arXiv:1409.3934 (2014)

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  19. [20]

    A. D. King, E. Hoskinson, T. Lanting, E. Andriyash, and M. H. Amin, Phys. Rev. A93, 52320 (2016)

    work page 2016

  20. [21]

    J. King, S. Yarkoni, M. M. Nevisi, J. P. Hilton, and C. C. McGeoch, arXiv:1508.05087 (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  21. [22]

    D. S. Steiger, T. F. Rønnow, and M. Troyer, Physical Review Letters 115 (2015), 10.1103/Phys- RevLett.115.230501, arXiv:1504.07991

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/phys- 2015

  22. [23]

    H. G. Katzgraber, F. Hamze, and R. S. Andrist, Physical Review X4, 21008 (2014)

    work page 2014

  23. [24]

    Mandrà and H

    S. Mandrà and H. G. Katzgraber, Quantum Science and Technology3, 04LT01 (2018)

    work page 2018

  24. [25]

    J. King, S. Yarkoni, J. Raymond, I. Ozfidan, A. D. King, M. M. Nevisi, J. P. Hilton, and C. C. McGeoch, Journal of the Physical Society of Japan88, 61007 (2019)

    work page 2019

  25. [26]

    I. Hen, J. Job, T. Albash, T. F. Rønnow, M. Troyer, and D. A. Lidar, Physical Review A - Atomic, Molecular, and Optical Physics92, 1 (2015), arXiv:1502.01663v2

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  26. [27]

    A. D. King, T. Lanting, and R. Harris, arXiv:1502.02098 (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  27. [28]

    Konak, D

    A. Konak, D. W. Coit, and A. E. Smith, Reliability Engineering & System Safety91, 992 (2006). 11 Appendix A: Shared Ising Energy F unction Shared Ising energy.When using a high recombination rate, we use a form of implicit fitness sharing [13] to maintain population diversity. In implicit fitness sharing, each “reward” component of the fitness function is sh...

    work page 2006