Claude Designs Novel Quantum Circuits, Cutting Decoder Gate Counts by 12x

Anthropic researchers used Claude to optimize quantum circuit designs, demonstrating that AI can discover novel algorithms that significantly reduce resource usage compared to existing state-of-the-art methods. The study, involving collaboration with Harvard University and QuEra Computing, focused on the qubit count × gate count metric as a proxy for execution time.

Modular Inversion Breakthrough

For elliptic curve point addition, a critical step in solving discrete logarithm problems, Claude developed a new reversible algorithm for modular inversion. Traditional methods like divsteps require storing branch information, consuming massive amounts of qubits. Claude’s approach decodes branch information by inspecting number pairs after each iteration, eliminating the need to store branch history.

• Verification: The new algorithm was formally verified using Lean and large-scale numerical simulations.
• Performance: One design variant increased qubit usage by 12% but reduced gate counts by 17x, creating a new Pareto frontier for efficiency.

Optimizing Reed-Solomon Decoding

Claude also improved the Decoded Quantum Interferometry (DQI) algorithm, specifically targeting the Reed-Solomon decoder, which is the most expensive component. Previous implementations used the Extended Euclidean algorithm, which suffers from variable step counts incompatible with fixed quantum circuit structures.

• New Approach: Claude switched to Berlekamp-Massey decoding, which uses fixed rounds and uniform operations, better suited for quantum hardware.
• Memory Efficiency: By reconstructing temporary values from the current state rather than storing them, the design reduced the required qubits for the decoder's exception handling from a worst-case estimate of 665 (or 840 for a naive reversible version) to just 19 in typical cases.
• Result: The overall gate count decreased by 12x compared to Google’s previous configuration, making the DQI algorithm’s most costly stage approximately one order of magnitude cheaper.

Implications for Quantum Computing

The research suggests that AI-driven circuit design can accelerate the path to practical quantum computing. While the FeMoco simulation required 150,000x reduction over eight years of human effort, Claude achieved its elliptic curve design improvements in a single 53-hour run. The team noted that Claude tends to be conservative, preferring existing approaches, but prompting for diverse solutions unlocked these novel methodologies. Future work may involve joint optimization of algorithms, error correction codes, and hardware control.