New algorithms beat existing methods for quantum circuits

Mark Webster, Stergios Koutsioumpas, and Dan E Browne University College London have developed new algorithms that reduce the number of two-qubit gates needed for quantum circuits.

The team benchmarked optimal, A*, and greedy algorithms against existing methods, and show that their approach results in circuits with lower two-qubit gate count. Their approach surpasses previous results achieved using reinforcement learning, even discovering a circuit for the 23-qubit Golay code with a lower two-qubit gate count than previously known. The algorithms are available as an open-source Python package for use by the classical and quantum computing community. Optimal Synthesis via Graph Isomorphism for Small Circuits The Golay code, an important component in quantum error correction, now benefits from a newly discovered circuit requiring fewer two-qubit gates than previously achieved. Researchers developed algorithms that outperformed existing reinforcement learning approaches, identifying a more efficient circuit for the 23-qubit Golay code, a significant step toward practical quantum computation. This improvement demonstrates the potential of graph isomorphism in optimizing quantum circuit design, a technique previously unexplored for this specific application. These algorithms operate on a tiered system, addressing circuits of varying complexity. For smaller circuits, a novel approach using graph isomorphism generates complete databases of optimal circuits, functioning orders of magnitude faster than prior optimal synthesis methods. This method maps the circuit synthesis problem onto a graph isomorphism problem, allowing for rapid identification of the most efficient configurations. Finally, for large circuits, a greedy algorithm, built upon a new vector heuristic, consistently surpasses publicly available alternatives in performance. Benchmarking against established methods like rustiq, tket, and qiskit was conducted. The two-qubit gate count, a key metric in evaluating circuit efficiency, is expressed as a percentage reduction from the Aaronson and Gottesman synthesis baseline; higher percentages indicate superior performance. This comparative analysis confirms the effectiveness of the new algorithms in minimizing circuit complexity, a critical factor in reducing the resources required for quantum computation.

The team’s work builds on previous research into linear reversible circuits, which have applications in both classical and quantum computing, and addresses a long-standing challenge in the field of quantum information processing. The algorithms’ efficiency stems from a focus on minimizing entangling two-qubit gates, essential for creating quantum entanglement, a fundamental resource in quantum computing. “Efficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms,” the researchers state in their published work, highlighting the broader implications of their findings. The development of these algorithms is not merely an academic exercise; it directly addresses the practical limitations of building and operating quantum computers, where minimizing gate count translates to reduced error rates and improved scalability. This accessibility is intended to encourage further research and development, allowing others to build upon their work and explore new avenues for quantum circuit optimization. The availability of this tool will likely accelerate progress in areas such as quantum cryptography, materials science, and drug discovery, all of which rely on efficient quantum computation. Further investigation into the underlying principles of graph isomorphism revealed its surprising applicability to circuit synthesis.

The team’s approach differs from previous methods that relied on heuristic searches or reinforcement learning, offering a more systematic and mathematically grounded solution. This systematic approach allows for a more thorough exploration of the solution space, leading to the discovery of circuits with demonstrably lower gate counts. The work also draws upon concepts from formal basis determination and cost minimization, integrating ideas from diverse areas of computer science and mathematics. The development of the greedy algorithm for large circuits was particularly challenging, requiring the creation of a new vector heuristic to guide the search process. This heuristic effectively prioritizes gate placements that minimize overall circuit complexity, enabling the algorithm to quickly converge on near-optimal solutions. The researchers tested this heuristic against a range of benchmark circuits, consistently demonstrating its superiority over existing methods. The A* search algorithm, used for intermediate-size circuits, combines the benefits of completeness and efficiency, guaranteeing that the optimal solution will be found within a reasonable timeframe.

The team’s work builds upon decades of research into reversible circuit synthesis, dating back to the early work on Gaussian elimination and greedy methods. However, their approach represents an advancement, using the power of graph isomorphism and advanced search algorithms to achieve a high level of optimization. A* Search and Vector Heuristics for Intermediate & Large Circuits This improvement stems from a tiered algorithmic approach, deploying different strategies based on circuit scale. The A* implementation prioritizes exploration of circuit configurations most likely to yield minimal two-qubit gate counts, effectively examining possible circuit arrangements. This approach differs from exhaustive searches, which become computationally intractable as circuit size increases, and from purely heuristic methods, which may settle for suboptimal solutions. For the largest and most complex circuits, the team developed a greedy algorithm guided by a new vector heuristic. The development of this greedy algorithm presented a significant challenge, demanding a heuristic capable of accurately assessing the quality of partial circuit constructions. The vector heuristic assesses potential gate placements based on their impact on the overall circuit structure, guiding the algorithm towards configurations that minimize entanglement and simplify the circuit’s topology. The algorithms are not limited to minimizing two-qubit gate count.

Golay Code Synthesis & Reduction of Two-Qubit Gate Count These algorithms not only surpass prior reinforcement learning approaches but also establish a new benchmark for efficient circuit construction within the field of quantum computation. This improvement is particularly significant given the disproportionate contribution of two-qubit gates to overall circuit error rates and the challenges associated with their reliable implementation in physical quantum systems. Intermediate-sized circuits are addressed with an A* search algorithm, a well-established pathfinding technique adapted to navigate the complex arrangements of possible gate arrangements and converge on near-optimal solutions. The vector heuristic guiding the greedy algorithm represents a key innovation, providing a more effective means of evaluating the potential of different gate choices during circuit construction. This heuristic prioritizes gate selections that minimize immediate gate count while also considering the potential for future optimization, effectively balancing short-term gains with long-term efficiency. The algorithms were tested against Aaronson and Gottesman synthesis, with results showing a percentage reduction in gate count. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community. Source: https://quantum-journal.org/papers/q-2026-09-21-2212/ More like thisQuantum AlgorithmsResearchers Bound Condition Number for Faster Parity LearningQuantum AlgorithmsResearchers Cut Overhead in Quantum Error AssessmentQuantum Error CorrectionResearchers Build Colour Codes with Polynomial Error CorrectionQuantum Error CorrectionResearchers Compute Evolution of ‘quantum Magic’ Using Renyi Entropy AnalysisStay currentSee today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals. Tags: