We discuss an effective paradigm of utilizing AI agents to better compile quantum circuits when one can constrain bottleneck subroutines to have some form of classically verifiable structure. For example, when critical subroutines are composed exclusively of reversible classical logic, phasing operations, and measurement based uncomputation, one can efficiently simulate execution for classical inputs. This property facilitates efficient certification of approximate circuit synthesis via a form of fuzz testing, provided suitable assumptions on the input distribution. While this pattern was recently exploited to improve quantum cryptanalysis circuits, here we highlight the flexibility of the broader approach by discussing three important applications. (1) The computation of $1/\sqrt{x}$ that bottlenecks real space simulations of the Coulomb operator such as those important for modeling inertial confinement fusion reactors. (2) The decoding of Reed-Solomon codes which bottlenecks the decoded quantum interferometry algorithm when used to approximately solve the optimal polynomial intersection problem. And (3) the quantum look-up tables and controlled application of Givens rotations that bottleneck the most performant quantum algorithms for simulating chemistry in second quantization. We discuss reference implementations of these algorithms and how they can be constrained and verified in the interest of seeding a Kaggle competition designed to accelerate AI-based research into the optimization of their compilation.
AI Summary
The paper addresses how AI coding agents can optimize costly fault-tolerant subroutines while candidate circuits remain classically testable. It extends a previously used workflow to three benchmarks: inverse-square-root phasing for Coulomb simulation, Reed–Solomon decoding for decoded quantum interferometry (DQI), and angle lookup/factorization for chemistry block encodings.
It releases `kickmix`, a C++20/Python package within Qualtran for circuits comprising reversible classical logic, diagonal phases, and measurement-based uncomputation. Bit-packed basis-state trajectories track outputs and phases; reported performance includes constructing an 86-million-gate DQI circuit in under five seconds and checking 102,400 decoder shots in 150 seconds on one CPU core. Verification uses circuit-hash-derived randomness, with a private competition salt against seed grinding. Under an injectivity assumption on each measurement-conditioned map, testing inputs drawn from the algorithm’s computational-basis probability distribution gives an output trace-distance bound of $2\sqrt{\varepsilon}$ for failure probability $\varepsilon$. Binomial confidence bounds quantify sampling uncertainty.
Reference circuits and scoring rules seed a Kaggle competition. The inverse-square-root baseline uses 260 qubits and 7,988 Toffoli-equivalent gates, with worst-case relative error $2.84\times10^{-8}$; the DQI decoder uses 1,893 qubits and 5,725,461 Toffolis. Claimed internal AI improvements are hash-committed but withheld until competition completion.
The approach excludes subroutines with general internal interference and tests fixed-size circuits rather than parameterized constructions. Chemistry scoring includes heuristic costs for unverified components; its coefficient-error checks do not certify a 20 mHa many-electron energy error. Logical resource scores also omit architecture-specific fault-tolerance costs.
Some signs of AI-generated textAI use disclosedIncrementalMissing comparisonStrong assumptions
In our own runs with AI coding agents, we have found significant improvements over the previously published baselines, and we expect further improvements remain to be discovered.
Error found: The coherent-error certification theorem assumes injectivity of each measurement-record map on supported inputs, but the permitted submission format and sampled verification checks do not independently guarantee that assumption.
The stated fidelity lower bound (1−2ε)² is false for general ε>1/2 and must be replaced by max(0,1−2ε)² or explicitly restricted to ε≤1/2.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We discuss an effective paradigm of utilizing AI agents to better compile quantum circuits when one can constrain bottleneck subroutines to have some form of classically verifiable structure. For example, when critical subroutines are composed exclusively of reversible classical logic, phasing operations, and measurement based uncomputation, one can efficiently simulate execution for classical inputs. This property facilitates efficient certification of approximate circuit synthesis via a form of fuzz testing, provided suitable assumptions on the input distribution. While this pattern was recently exploited to improve quantum cryptanalysis circuits, here we highlight the flexibility of the broader approach by discussing three important applications. (1) The computation of 1/x that bottlenecks real space simulations of the Coulomb operator such as those important for modeling inertial confinement fusion reactors. (2) The decoding of Reed-Solomon codes which bottlenecks the decoded quantum interferometry algorithm when used to approximately solve the optimal polynomial intersection problem. And (3) the quantum look-up tables and controlled application of Givens rotations that bottleneck the most performant quantum algorithms for simulating chemistry in second quantization. We discuss reference implementations of these algorithms and how they can be constrained and verified in the interest of seeding a Kaggle competition designed to accelerate AI-based research into the optimization of their compilation.
The paper addresses how AI coding agents can optimize costly fault-tolerant subroutines while candidate circuits remain classically testable. It extends a previously used workflow to three benchmarks: inverse-square-root phasing for Coulomb simulation, Reed–Solomon decoding for decoded quantum interferometry (DQI), and angle lookup/factorization for chemistry block encodings.
It releases kickmix, a C++20/Python package within Qualtran for circuits comprising reversible classical logic, diagonal phases, and measurement-based uncomputation. Bit-packed basis-state trajectories track outputs and phases; reported performance includes constructing an 86-million-gate DQI circuit in under five seconds and checking 102,400 decoder shots in 150 seconds on one CPU core. Verification uses circuit-hash-derived randomness, with a private competition salt against seed grinding. Under an injectivity assumption on each measurement-conditioned map, testing inputs drawn from the algorithm’s computational-basis probability distribution gives an output trace-distance bound of 2ε for failure probability ε. Binomial confidence bounds quantify sampling uncertainty.
Reference circuits and scoring rules seed a Kaggle competition. The inverse-square-root baseline uses 260 qubits and 7,988 Toffoli-equivalent gates, with worst-case relative error 2.84×10−8; the DQI decoder uses 1,893 qubits and 5,725,461 Toffolis. Claimed internal AI improvements are hash-committed but withheld until competition completion.
The approach excludes subroutines with general internal interference and tests fixed-size circuits rather than parameterized constructions. Chemistry scoring includes heuristic costs for unverified components; its coefficient-error checks do not certify a 20 mHa many-electron energy error. Logical resource scores also omit architecture-specific fault-tolerance costs.
Compiling quantum algorithms for real devices involves hard optimization problems that can decide whether an algorithm runs at scale. We present a general method for solving such problems with AI agents, with every result certified. It builds on autoresearch loops, in which agents iteratively improve programs against a fixed evaluator and which have recently improved quantum cryptanalysis circuits, and adds two elements: a frozen, exact verifier certifies every result, and this verifier, together with the challenge around it, is built by an agent that formulates the problem with a researcher and validates the verifier against a solved case, deliberately broken solutions and published results before any solution exists. The method applies to any optimization problem whose solutions can be verified exactly and efficiently. We apply it to three compilation problems in quantum simulation, namely fermion-to-qubit encoding, Hamiltonian layout and unitary synthesis. In each, the agents improved substantially on published or standard constructions, reducing the cost being optimized by up to 73% at the largest sizes tested and outperforming a state-of-the-art optimizer for fermion-to-qubit encodings. Every submission is a program accompanied by its agent's notes, so the ideas behind each improvement are recorded in human-readable form; later agents built on them, and we describe them here. These results open the way to automated, certified discovery across quantum circuit design and beyond.
Quantum computing is a potential paradigm to overcome the current computational bottlenecks. The increasing maturity of quantum processors provides more possibilities for the development and implementation of quantum algorithms. As the crucial stages for quantum algorithm implementation, the logic circuit design and quantum compiling have also received significant attention, which covers key technologies, e.g., quantum logic circuit synthesis (especially quantum architecture search for parameterized quantum circuits) and optimization, as well as qubit mapping and routing. Recent studies suggest that the scale and precision of related algorithms are steadily increasing, especially with the integration of artificial intelligence methods. In this survey, we systematically review and summarize a vast body of literature, exploring the feasibility of an integrated design and optimization scheme that spans from the algorithmic level to quantum hardware, combining the steps of logic circuit design and compilation optimization. Leveraging the exceptional cognitive and learning capabilities of AI algorithms, it becomes more possible to reduce manual design costs, enhance the precision and efficiency of execution, and facilitate the implementation and validation of the superiority of quantum algorithms on hardware.
Cloud platforms have made quantum hardware accessible for research, while autonomous agents powered by large language models are increasingly used to generate code. When such an agent receives a computational problem, however, it often cannot determine whether quantum computing offers a real benefit or whether the problem is better suited to classical hardware. To address this gap, this article proposes a three-stage decision framework. The first stage extracts structural features from the problem description: problem type, search space size, and the presence of a verification oracle. The second stage assigns a quantum advantage classification from established properties of algorithms suited to noisy intermediate-scale quantum devices. The third stage verifies whether the resulting circuit can be executed on real hardware. Circuit generation is implemented for Grover’s search, the quantum approximate optimization algorithm, and the variational quantum eigensolver, and evaluated on a simulator under six noise channels. An ablation study compares three classifiers on a benchmark of 15 standard and 12 adversarial descriptions: the deterministic framework, a feedforward network trained by back-propagation, and a standalone language model. Their aggregate accuracy is within sampling variation, yet they fail on categorically different problems, and the learned classifier never succeeds where reasoning about problem scale is required. The feasibility gate is further validated against circuits compiled for the coupling map and native gates of a 127-qubit device, showing the accuracy of analytic resource estimates to be strongly algorithm dependent. The implementation is validated with 119 automated tests at 96% code coverage and demonstrated through integration with an autonomous agent platform.
Quantum circuit compilation is a critical step in realizing quantum algorithms on real quantum hardware. Traditional compilation methods often employ static optimization strategies, neglecting the unique constraints and characteristics of the target quantum device. This paper introduces a novel adaptive quantum circuit compilation framework designed to dynamically adjust circuit designs based on hardware-specific information, aiming to minimize gate count and, consequently, error rates. The core of the framework lies in integrating a hardware simulator directly within the compilation process. This allows the compiler to evaluate the performance of various circuit designs—considering factors like qubit connectivity, gate fidelity, and decoherence models—before committing to a final layout. The proposed approach represents a shift from static to adaptive optimization, providing a more nuanced and effective strategy for translating quantum algorithms into executable code on diverse quantum hardware platforms. This research demonstrates a significant potential improvement in quantum circuit efficiency and fidelity, addressing a key bottleneck in the advancement of quantum computing.
The timeline by which quantum computers can solve breakthrough problems in science depends on improved quantum algorithms as much as on better hardware. Such algorithmic advances are typically achieved through many years of expert human collaboration. In mathematics and computer science, large language models have accelerated progress through automated discovery loops. However, quantum algorithms can only be evaluated by classical computers on restricted or small instances. Here we demonstrate automated discovery of quantum programs beyond these regimes including order-of-magnitude improvements on scientific applications. To achieve this, we build a quantum program library in the Lean theorem prover in which Gemini 4 agents synthesize novel programs against formal problem specifications and verify their correctness and cost. Agent teams collaborate, sharing results and knowledge through wikis and discussing ideas at organized conferences. Our results improve on prior baselines for parallel search (up to 2.55x), quantum arithmetic (290x), and simulations relevant to fusion, photochemistry and drug-metabolism by 11x, 8x and 2.5x respectively. Combining human and artificial intelligence at scale, under the rigor of mathematical proof, lets researchers design algorithms that today's classical and quantum computers cannot test, shortening the path to practical quantum computation.
In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.