Pith. sign in

REVIEW 5 major objections 6 minor 22 references

Incorporating Quantum Advantage in Quantum Circuit Generation through Genetic Programming

T0 review · 5 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that adding a measure of quantum advantage to a genetic algorithm's fitness function makes circuit search converge faster and rediscover textbook quantum circuits.

desk verdict Two genuinely new fitness functions for GA-based quantum circuit design, and one evolved single-oracle-call search circuit is intriguing, but the convergence-speed claim is unsupported because the compared fitness curves are on different scales. read the letter →

arxiv 2501.09682 v1 pith:44J5DGA3 submitted 2025-01-16 quant-ph cs.AIcs.ETcs.NE

Christoph Stein , Michael Färber This is my paper · ORCID
classification quant-phcs.AIcs.ETcs.NE MSC 68T2081P68 PACS 03.67.Lx
keywords QuantumComputingGeneticProgrammingAlgorithmsCircuitGenerationAdvantageBernstein-VaziraniProblemUnstructuredDatabaseSearchFitnessFunction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether a genetic algorithm that explicitly rewards quantum advantage can discover efficient quantum circuits on its own. It proposes two fitness functions—one that minimizes the ratio of oracle gates to classical oracle calls, and one that penalizes circuits lacking superposition and entanglement gates—and tests them on the Bernstein-Vazirani problem and unstructured database search. The reported result is that both fitness functions converge faster than the baseline and produce circuits that are structurally equivalent to textbook solutions, including a circuit that closely mirrors the Grover diffusion operator. If this holds, automated circuit design could accelerate algorithm discovery by building advantage-seeking into the search itself.

What carries the argument

The central machinery is the fitness function itself, which shapes the search landscape. DirectQAFitness builds on the multi-component fitness of [19] and, once all test cases are passed, appends a penalty equal to the ratio of oracle gates in the circuit to the number of classical oracle calls, plus a small gate-count term ($\frac{\text{countGates}(\text{circuit})}{100000}$). IndirectQAFitness prepends a constraint layer: if the circuit lacks any superposition-capable gate or any controlled gate, it adds $\#TestCases+1$ to the fitness, forcing the search to prefer circuits with the raw ingredients of quantum advantage before optimizing correctness. These terms are what carry the argument that advantage can be incorporated into fitness.

What would settle it

Run the best circuits from DirectQAFitness on a simulator that counts actual oracle queries, and compare that count with the oracle-gate count the fitness function rewarded; if a circuit with many H and CNOT gates that never influence the output still earns a top fitness score, or if a circuit that solves the problem without any superposition gate outperforms the generated ones on a real device, the fitness proxy is broken.

Watch

Extended reading notes

Core claim

The authors claim that incorporating a measure of quantum advantage into the fitness function of a genetic algorithm improves both convergence speed and the quality of generated quantum circuits. DirectQAFitness, once all test cases pass, punishes a circuit with $\frac{\text{countOracleGates}(\text{circuit})}{\text{classicalOracleCalls}} + \frac{\text{countGates}(\text{circuit})}{100000}$, so circuits that solve the problem with fewer oracle queries score better. IndirectQAFitness adds a penalty of $\#TestCases+1$ to any circuit that contains no superposition-capable gate or no controlled gate, steering evolution toward circuits with the ingredients of quantum advantage before optimizing correctness. On the Bernstein-Vazirani and Unstructured Database Search problems, the proposed functions either match or outperform the baseline fitness of [19] in convergence, and the best generated circuits are equivalent to or structurally reminiscent of expert-designed circuits.

Load-bearing premise

The load-bearing premise is that a circuit's oracle-gate count and its possession of superposition and controlled gates faithfully measure real quantum advantage, so optimizing these proxies actually optimizes for advantage.

Editorial extensions

If this is right

  • A genetic algorithm can rediscover known quantum algorithms without prior knowledge of their structure, as seen in the Bernstein-Vazirani circuits and the Grover-like diffusion operator.
  • Adding an advantage proxy to the fitness function accelerates convergence, so good circuits appear in fewer generations than with the baseline fitness.
  • The constraint-based penalty can be attached to any correctness-based fitness to steer evolution toward quantum-feasible circuits.
  • The search can also find structurally novel but functionally valid alternatives, such as the step-wise entanglement circuits for unstructured search that differ from the textbook equal-superposition start.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because DirectQAFitness counts oracle gates in the circuit rather than actual oracle queries on a device, its success suggests gate-count proxies may suffice for steering evolution; a natural extension is to delete gates that do not affect the output and re-run the search to see if convergence changes.
  • The indirect penalty treats any superposition gate and any controlled gate as sufficient for quantum advantage, so a circuit containing useless H and CNOT gates would pass the constraint; a more refined penalty could weight gates by their effect on the final state or by the degree of entanglement produced.
  • The same pair of fitness functions should transfer to other black-box problems with a known classical-to-quantum query gap, such as the Deutsch-Jozsa or Simon problems, where the ratio of oracle calls is well defined.
  • The authors note that oracle cases are currently treated independently; their proposed well-formedness measure, if added, could be used to test whether the generated Grover-like circuit generalizes across oracle implementations rather than overfitting specific ones.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 6 minor

Summary. The paper proposes two fitness functions for genetic programming of quantum circuits, extending the Spector et al. baseline: DirectQAFitness (Algorithm 1), which adds a term based on the ratio of oracle gates to classical oracle calls once all test cases are passed, and IndirectQAFitness (Algorithm 2), which adds penalties when a circuit lacks any superposition-capable gate or any controlled gate. The methods are evaluated on the Bernstein-Vazirani problem and the unstructured database search problem with 12 runs per configuration. The authors report faster convergence for the quantum-advantage-aware fitness functions and present evolved circuits that are structurally similar to textbook solutions, including a Grover-like diffusion operator. The code is released on GitHub. The central claims are plausible, but the current evidence is weakened by incomparable fitness metrics, a weak success threshold, and the absence of statistical reporting.

Significance. If the convergence and circuit-quality claims are substantiated, this would be a modest but useful contribution to quantum architecture search, showing that query-complexity-inspired terms can shape evolutionary search. The idea of measuring quantum advantage inside the fitness function is a natural extension of prior work and is worth investigating. The paper is clearly written, provides pseudocode for both fitness functions, and releases its code, which are strengths. However, as presented, the experiments do not yet separate genuine improvements in solution quality from artifacts of the fitness definitions; the structural rediscovery of a Grover-like diffusion operator is an encouraging proof-of-concept but needs stronger supporting evidence.

major comments (5)
  1. [Sec. 4, Figs. 1 and 3] The headline claim that the proposed fitness functions 'improve the convergence speed' is not supported by the reported plots, because the three curves are values of different objective functions. In Algorithm 1, line 16, DirectQAFitness adds the term countOracleGates(circuit)/classicalOracleCalls to the baseline efficiency term, so its numerical scale is shifted relative to BaselineFitness; in Algorithm 2, lines 14-19, IndirectQAFitness adds penalties of #TestCases+1 that disappear as soon as the circuit contains any superposition-capable and any controlled gate. A decrease in IndirectQAFitness after those constraints are satisfied is therefore partly a consequence of the penalty structure rather than evidence that better circuits are being found. To substantiate the convergence claim, the authors should re-plot and compare all configurations using a common task-level metric, for example the fraction of runs that have found a circuit passing all test cases above a fixed probability threshold by a given generation, or the generation at which the success probability of the best circuit first exceeds a threshold.
  2. [Sec. 3.2, Algorithm 2] The indirect quantum-advantage constraint checks only for the existence of any gate capable of creating superposition and any controlled gate. This is a necessary but not sufficient condition for genuine quantum advantage, and it is easy to satisfy with gates that do not participate in the relevant computation or that do not reduce query complexity. The paper does not verify, for the evolved circuits, that the presence of these gates corresponds to an actual quantum speedup; the convergence improvements could therefore reflect optimization of the proxy rather than of quantum advantage. Please validate the circuits with an external measure, such as the number of oracle calls needed for a target success probability, or explicitly weaken the claim that these fitness functions incorporate quantum advantage.
  3. [Sec. 4, experimental setup] All conclusions are based on 12 runs per configuration, but the reported curves are only averages, with no error bars, confidence intervals, or significance tests. Terms in Sec. 4.2 such as 'slight outperformance' and Sec. 5 'faster and more effective convergence' are therefore unsupported by statistical evidence. Please add per-generation variance information and, for the common task-level metric, a significance test or effect size.
  4. [Sec. 4, Figs. 4-6] The success threshold of 0.52 used in Algorithms 1 and 2 (line 6) is weak, and the paper never reports the actual success probability of the best circuits for the Unstructured Database Search Problem. A circuit that passes every test case with probability just above 0.52 is not obviously 'comparable to expert-designed solutions' as stated in the abstract. For the claim to be credible, please report the measured success probabilities of the circuits in Figs. 4-6 and compare them with the success probabilities of the textbook Bernstein-Vazirani and Grover circuits on the same instances.
  5. [Sec. 4.1 and Sec. 4.2] The evidence for the circuit-quality claim is based on the single best circuit found across all runs for each configuration. This is a post-hoc selection and does not show that the proposed fitness functions reliably produce such circuits. Please report the success frequency, for example the number of runs out of 12 in which a circuit with the relevant structural property or success probability was found.
minor comments (6)
  1. [Sec. 3.1] The text contains several typos: 'irreverent' should be 'irrelevant', 'amount of a gates' should be 'number of gates', and 'Similarity' in Sec. 4.2 should be 'Similarly'.
  2. [Sec. 4] The value of classicalOracleCalls is never explicitly defined for the Bernstein-Vazirani experiment; please state it, for example n oracle calls for an n-bit secret.
  3. [Figs. 1 and 3] The y-axis labels should make explicit that the three plotted curves are values of different fitness functions and are not directly comparable on a common numerical scale.
  4. [Sec. 4.2, Fig. 6] The matrix in Fig. 6 is described as 'exactly equal to the diffusion operator' when it is actually equal up to the sign of two rows; this should be qualified in the text, even though the authors correctly note that the signs do not affect measurement probabilities when the operator is terminal.
  5. [Title and Sec. 4] The title and abstract use 'genetic programming', while the method is a genetic algorithm with fixed-length chromosomes and crossover and mutation; aligning this terminology would improve clarity.
  6. [Sec. 2.1] The 0.52 threshold is inherited from Spector et al. and described as accounting for rounding errors, but its sensitivity is not discussed; a sentence on how the threshold affects the results would help.

Circularity Check

1 steps flagged · score 4.0 of 10

Convergence-speed claim is partly definitional because the 'speed' is measured on the same fitness functions the algorithms optimize; the independently benchmarked circuit-quality results keep the paper only moderately circular.

  1. self definitional [Section 4.2, Figs. 1 and 3; Algorithm 2 lines 14-19]
    "While the IndirectQAFitness has a higher averaged mean fitness value during early generations, due to the punishment terms applied in the fitness value computation, this fitness function converges faster, although to a less beneficial value compared to the DirectQAFitness function."

    The convergence comparison is made on the algorithms' own fitness values, but the fitness functions are not on a common scale. IndirectQAFitness adds #TestCases+1 to the fitness whenever superposition or entanglement gates are absent (Algorithm 2, lines 14-19), so once those constraints are satisfied the fitness drops by a fixed mechanical amount. This penalty removal is part of the fitness definition itself, not an independent measure of solution quality. The reported 'converges faster' therefore reduces, by construction, to the arithmetic effect of removing the penalty terms, rather than demonstrating improved convergence on a task-level metric.

full rationale

The paper's circuit-quality claims are independently grounded: the evolved Bernstein-Vazirani circuits are compared structurally to the known textbook circuit, and the search-circuit unitary is compared directly to Grover's diffusion operator. These external comparisons do not depend on the proposed fitness scales, so the 'comparable to expert-designed solutions' claim is not circular. However, the headline 'improve the convergence speed' claim is supported primarily by plots of the algorithms' own fitness values across generations. BaselineFitness, DirectQAFitness, and IndirectQAFitness are different objectives with different penalties, offsets, and scales, so lower values under one are not commensurable with lower values under another. IndirectQAFitness in particular has a built-in step: a #TestCases+1 penalty disappears once superposition and entanglement gates are present, which mechanically creates a fast apparent drop. Additionally, the paper notes that minimum fitness values are monotonically decreasing due to elitism, a property of the selection mechanism rather than of the proposed fitness functions. Thus the convergence-speed result is partly self-referential and does not by itself establish faster discovery of better circuits. Since the structural comparisons to known quantum algorithms remain external and non-circular, the overall circularity burden is moderate rather than severe.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central method rests on hand-set hyperparameters and heuristic proxies rather than on new physical postulates. No new entities are introduced. The main domain assumptions are the standard oracle-complexity results for Bernstein-Vazirani and Grover, and the claim that counting oracle gates or checking for H and CNOT gates tracks quantum advantage.

free parameters (4)
  • Quantum advantage weight in DirectQAFitness (100000 gate-count scaling factor) = 100000
    Algorithm 1 line 16 divides by classicalOracleCalls + countGates/100000; the 100000 factor sets the relative weight of gate count versus oracle calls, and is chosen by hand. As written it makes extra gates slightly reduce fitness, opposite of the intended efficiency penalty.
  • Penalty value for missing superposition or entanglement gates = #TestCases + 1
    Algorithm 2 lines 14-19 adds #TestCases+1 per missing constraint. The authors state the absolute value does not matter, but it is a hand-set hyperparameter that shapes the early search.
  • Success probability threshold = 0.52
    Taken from Spector et al. [19]; any circuit with target-state probability at least 0.52 counts as a hit. This threshold, rather than 0.5 or a confidence bound, determines when the quantum advantage term activates.
  • Genetic algorithm hyperparameters = population 1000, crossover 0.4, swap 0.03, elitism 10%, chromosome lengths 15 and 30, generations 500 and 800
    Section 4 says the parameters were chosen based on experience and systematic trial and error ahead of the experiment runs, i.e., fitted to the benchmark problems.
assumptions (4)
  • domain assumption Oracle complexity of Bernstein-Vazirani and Grover search applies at the small instance sizes used.
    Section 3.1 uses the known classical and quantum oracle call counts as the reference for classicalOracleCalls. If the small-instance values differ, the fitness ratio is miscalibrated.
  • ad hoc to paper A circuit that contains any superposition-capable gate and any controlled gate has the potential for quantum advantage.
    Section 3.2 defines the IndirectQAFitness constraints this way. It is a heuristic proxy and is not an independently established measure of quantum advantage.
  • domain assumption Counting oracle gates in the evolved circuit is equivalent to counting oracle calls in query complexity.
    The direct fitness uses countOracleGates(circuit) as the numerator. This assumes the chosen oracle decomposition makes gate count a faithful proxy for query count.
  • domain assumption The circuit representation and gate set inherited from Spector et al. can express the target algorithms.
    The genetic algorithm's search space must contain circuits close to Bernstein-Vazirani and Grover. If the representation cannot express such circuits, the method cannot rediscover them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Incorporating Quantum Advantage in Quantum Circuit Generation through Genetic Programming." pith.science (2026). https://pith.science/paper/44J5DGA3

@misc{pith2026250109682,
  author       = {Pith},
  title        = {Pith review of: Incorporating Quantum Advantage in Quantum Circuit Generation through Genetic Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/44J5DGA3}},
  note         = {Machine review of arXiv:2501.09682}
}
read the original abstract

Designing efficient quantum circuits that leverage quantum advantage compared to classical computing has become increasingly critical. Genetic algorithms have shown potential in generating such circuits through artificial evolution. However, integrating quantum advantage into the fitness function of these algorithms remains unexplored. In this paper, we aim to enhance the efficiency of quantum circuit design by proposing two novel approaches for incorporating quantum advantage metrics into the fitness function of genetic algorithms.1 We evaluate our approaches based on the Bernstein-Vazirani Problem and the Unstructured Database Search Problem as test cases. The results demonstrate that our approaches not only improve the convergence speed of the genetic algorithm but also produce circuits comparable to expert-designed solutions. 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.

Figures

Figures reproduced from arXiv: 2501.09682 by the authors.

Figure 1
Figure 1. Averaged fitness values on the Bernstein-Vazirani Problem. [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Best performing circuits of each fitness function for the Bernstein-Vazirani Problem. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Averaged fitness values on the Unstructured Database Search Problem, grouped by fitness function. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Best performing circuit for BaselineFitness on the Unstructured Database Search Problem. 4.2 Results on the Unstructured Database Search Problem [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Best performing circuit for DirectQAFitness on the Unstructured Database Search Problem [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Best performing circuit for IndirectQAFitness on the Unstructured Database Search Problem. superposition at the beginning of the circuit, as the state of the art solution does, these circuits start by placing the system in a partial superposition state. The circuit ill…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 19 canonical work pages

  1. [1]

    Usama Ahsan et al. 2020. AutoQP: Genetic Programming for Quantum Programming. In 2020 17th International Bhurban Conference on Applied Sciences and Technology (IBCAST). IEEE, 378–382

    work page 2020

  2. [2]

    Andrei Bautu and Elena Bautu. 2007. Quantum circuit design by means of genetic programming. Romanian Physics 52, 5-7 (2007), 697–704

    work page 2007

  3. [3]

    Ethan Bernstein and Umesh Vazirani. 1993. Quantum complexity theory. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. 11–20

    work page 1993

  4. [4]

    Don Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv preprint quant-ph/0201067 (2002)

    arXiv 2002

  5. [5]

    Kalyanmoy Deb and Himanshu Jain. 2013. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE transactions on evolutionary computation 18, 4 (2013), 577–601

    work page 2013

  6. [6]

    David Deutsch. 1985. Quantum theory, the Church–Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400, 1818 (1985), 97–117

    work page 1985

  7. [7]

    Lukas Franken, Bogdan Georgiev, Sascha Mucke, Moritz Wolter, Raoul Heese, Christian Bauckhage, and Nico Piatkowski. 2022. Quantum Circuit Evolution on NISQ Devices. In 2022 IEEE Congress on Evolutionary Computation (CEC) . IEEE, 1–8

    work page 2022

  8. [8]

    Felix Günther Gemeinhardt, Stefan Klikovits, and Manuel Wimmer. 2023. Hybrid multi-objective genetic programming for parameterized quantum operator discovery. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation . 795–798

    work page 2023

Show all 22 references
  1. [9]

    Alessandro Giovagnoli, Volker Tresp, Yunpu Ma, and Matthias Schubert. 2023. Qneat: Natural evolution of variational quantum circuit architecture. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation . 647–650

    2023

  2. [10]

    Lov K Grover. 1996. A fast quantum mechanical algorithm for database search. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing . 212–219

    1996

  3. [11]

    En-Jui Kuo, Yao-Lung L Fang, and Samuel Yen-Chi Chen. 2021. Quantum architecture search via deep reinforcement learning. arXiv preprint arXiv:2104.07715 (2021)

    2021 arXiv

  4. [12]

    Paul Massey, John A Clark, and Susan Stepney. 2004. Evolving quantum circuits and programs through genetic programming. InGenetic and Evolutionary Computation–GECCO 2004: Genetic and Evolutionary Computation Conference, Seattle, W A, USA, June 26-30, 2004. Proceedings, Part II...

    2004

  5. [13]

    Paul Massey, John A Clark, and Susan Stepney. 2006. Human-competitive evolution of quantum computing artefacts by genetic programming. Evolutionary Computation 14, 1 (2006), 21–40

    2006

  6. [14]

    Keri A McKiernan, Erik Davis, M Sohaib Alam, and Chad Rigetti. 2019. Automated quantum programming via reinforcement learning for combinatorial optimization. arXiv preprint arXiv:1908.08054 (2019)

    2019 arXiv

  7. [15]

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. 2014. A variational eigenvalue solver on a photonic quantum processor. Nature communications 5, 1 (2014), 4213

    2014

  8. [16]

    Benjamin IP Rubinstein. 2001. Evolving quantum circuits using genetic programming. In Proceedings of the 2001 congress on evolutionary computation (IEEE Cat. No. 01TH8546) , Vol. 1. IEEE, 144–151

    2001

  9. [17]

    Peter W Shor. 1999. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review 41, 2 (1999), 303–332

    1999

  10. [18]

    Peter W Shor. 2003. Why haven’t more quantum algorithms been found? Journal of the ACM (JACM) 50, 1 (2003), 87–90

    2003

  11. [19]

    Lee Spector, Howard Barnum, Herbert J Bernstein, and Nikhil Swamy. 1998. Genetic programming for quantum computers. Genetic Programming (1998), 365–373

    1998

  12. [20]

    Daniel Tandeitnik and Thiago Guerreiro. 2022. Evolving quantum circuits. arXiv preprint arXiv:2210.05058 (2022)

    2022 arXiv

  13. [21]

    Sagar Uprety, Dimitris Gkoumas, and Dawei Song. 2020. A survey of quantum theory inspired approaches to information retrieval. ACM Computing Surveys (CSUR) 53, 5 (2020), 1–39

    2020

  14. [22]

    Colin P Williams and Alexander G Gray. 1998. Automated design of quantum circuits. In NASA International Conference on Quantum Computing and Quantum Communications . Springer, 113–125. Received [TO BE FILLED]; revised [TO BE FILLED]; accepted [TO BE FILLED] ACM Trans. Quantum ...

    1998

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.