LLM Evolutionary Search Finds Cheaper Quantum Arithmetic Circuits

This episode examines a paper that uses an LLM-driven evolutionary search (OpenEvolve with Claude Mythos 5) to find quantum arithmetic circuits needing fewer Toffoli gates and fewer qubits than the best published designs across eight tasks. These tasks include decoders for decoded quantum interferometry, modular inversion, and chemistry and lattice-gauge workloads. It explains why quantum arithmetic is hard to write: coherent control flow forces every branch to run, reversibility requires uncomputation, and a stated failure budget can be traded for savings. It also covers how candidates are checked classically by tracking basis states and phases, so hallucinated circuits are rejected by an exact evaluator. The discussion places the work against FunSearch, AlphaEvolve and rewrite-based optimizers, and notes the trade-off that correctness is statistical rather than proved. It also flags the Anthropic affiliation and the simplification of equally weighting gate count and qubit count into one cost metric. Sources: 1. Discovering state-of-the-art quantum circuits with large language models — Andi Gu, Alek H. Kemeny, Susanne F. Yelin, Mikhail D. Lukin, 2026 http://arxiv.org/abs/2610.22367 2. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits — Craig Gidney, Martin Ekera, 2019 (Quantum 2021) https://scholar.google.com/scholar?q=How+to+factor+2048+bit+RSA+integers+in+8+hours+using+20+million+noisy+qubits 3. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity — Ryan Babbush, Craig Gidney, Dominic Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, Hartmut Neven, 2018 https://scholar.google.com/scholar?q=Encoding+Electronic+Spectra+in+Quantum+Circuits+with+Linear+T+Complexity 4. AlphaEvolve: A coding agent for scientific and algorithmic discovery (and the preceding FunSearch: Mathematical discoveries from program search with large language models) — Alexander Novikov, Ngan Vu, Marvin Eisenberger, et al. (Google DeepMind); FunSearch: Bernardino Romera-Paredes, Mohammadamin Barekatain, et al., 2025 (AlphaEvolve); 2023 (FunSearch, Nature 2024) https://scholar.google.com/scholar?q=AlphaEvolve%3A+A+coding+agent+for+scientific+and+algorithmic+discovery+%28and+the+preceding+FunSearch%3A+Mathematical+discoveries+from+program+search+with+large+language+models%29 5. Discovering faster matrix multiplication algorithms with reinforcement learning (AlphaTensor) and Quantum Circuit Optimization with AlphaTensor (AlphaTensor-Quantum) — Alhussein Fawzi et al.; Francisco J. R. Ruiz et al. (DeepMind), 2022 (AlphaTensor); 2024 (AlphaTensor-Quantum, Nature Machine Intelligence 2025) https://scholar.google.com/scholar?q=Discovering+faster+matrix+multiplication+algorithms+with+reinforcement+learning+%28AlphaTensor%29+and+Quantum+Circuit+Optimization+with+AlphaTensor+%28AlphaTensor-Quantum%29 6. Logical Reversibility of Computation — Charles H. Bennett, 1973 https://scholar.google.com/scholar?q=Logical+Reversibility+of+Computation 7. Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms — Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter, 2017 https://scholar.google.com/scholar?q=Quantum+Resource+Estimates+for+Computing+Elliptic+Curve+Discrete+Logarithms 8. Fast constant-time gcd computation and modular inversion — Daniel J. Bernstein, Bo-Yin Yang, 2019 https://scholar.google.com/scholar?q=Fast+constant-time+gcd+computation+and+modular+inversion 9. Reversible Residual Network: Backpropagation Without Storing Activations (RevNet) — Aidan N. Gomez, Mengye Ren, Raquel Urtasun, Roger B. Grosse, 2017 https://scholar.google.com/scholar?q=Reversible+Residual+Network%3A+Backpropagation+Without+Storing+Activations+%28RevNet%29 10. Mathematical discoveries from program search with large language models (FunSearch) — Romera-Paredes et al., 2023/2024 https://scholar.google.com/scholar?q=Mathematical+discoveries+from+program+search+with+large+language+models+%28FunSearch%29 11. AlphaEvolve: A coding agent for scientific and algorithmic discovery — Novikov et al. (Google DeepMind), 2025 https://scholar.google.com/scholar?q=AlphaEvolve%3A+A+coding+agent+for+scientific+and+algorithmic+discovery 12. Quartz / PyZX / TODD / T-par style circuit optimizers — Xu et al. (Quartz); Kissinger & van de Wetering (PyZX); Heyfron & Campbell (TODD); Amy, Maslov & Mosca (T-par), 2019-2022 https://scholar.google.com/scholar?q=Quartz+%2F+PyZX+%2F+TODD+%2F+T-par+style+circuit+optimizers 13. Faster quantum arithmetic / AlphaTensor-Quantum: Quantum circuit optimization with deep reinforcement learning — Ruiz et al. (DeepMind), 2024/2025 https://scholar.google.com/scholar?q=Faster+quantum+arithmetic+%2F+AlphaTensor-Quantum%3A+Quantum+circuit+optimization+with+deep+reinforcement+learning 14. Decoded Quantum Interferometry — Jordan et al., 2024 https://scholar.google.com/scholar?q=Decoded+Quantum+Interferometry 15. Compiling decoded quantum interferometry / reversible Reed-Solomon decoders for DQI (Khattar et al.) — Khattar et al., 2025 https://scholar.google.com/scholar?q=Compiling+decoded+quantum+interferometry+%2F+reversible+Reed-Solomon+decoders+for+DQI+%28Khattar+et+al.%29 16. Fast constant-time gcd computation and modular inversion (safegcd / divsteps) — Bernstein & Yang, 2019 https://scholar.google.com/scholar?q=Fast+constant-time+gcd+computation+and+modular+inversion+%28safegcd+%2F+divsteps%29 17. How to factor 2048 bit RSA integers with less than a million noisy qubits — Gidney, 2025 https://scholar.google.com/scholar?q=How+to+factor+2048+bit+RSA+integers+with+less+than+a+million+noisy+qubits 18. Halving the cost of quantum addition / Measurement-based uncomputation of quantum circuits — Gidney (2018); Berry et al. (2019), 2018/2019 https://scholar.google.com/scholar?q=Halving+the+cost+of+quantum+addition+%2F+Measurement-based+uncomputation+of+quantum+circuits 19. Coset representation of modular integers / approximate residue arithmetic — Zalka; Gidney, 2006/2019 https://scholar.google.com/scholar?q=Coset+representation+of+modular+integers+%2F+approximate+residue+arithmetic 20. Efficient implementations of reversible computation / Bennett pebble game space-time trade-offs — Bennett; Knill; Chan & Gidney, 1989/1995/2013 https://scholar.google.com/scholar?q=Efficient+implementations+of+reversible+computation+%2F+Bennett+pebble+game+space-time+trade-offs 21. The Reversible Residual Network: Backpropagation Without Storing Activations — Gomez et al., 2017 https://scholar.google.com/scholar?q=The+Reversible+Residual+Network%3A+Backpropagation+Without+Storing+Activations Interactive Visualization: LLM Evolutionary Search Finds Cheaper Quantum Arithmetic Circuits