How To Make Quantum Algorithms Cheaper | Craig Gidney on Magic-State Factories, Resource Estimates

Episode 50

0:00-2:03:47

How do you actually make quantum algorithms work on real hardware? Build your own quantum circuits in Crumble: https://algassert.com/crumble In this episode, we speak with Craig Gidney of Google Quantum AI, whose work focuses on the practical realities of building fault-tolerant quantum computers. Gidney explains how seemingly small implementation choices, like how you perform arithmetic, can dominate the cost of entire quantum algorithms. We explore why factoring small numbers like 15 in Shor's algorithm can be misleadingly easy, and why scaling to larger numbers requires dramatically more resources due to operations like modular multiplication. He breaks down how quantum circuits are often dominated by classical reversible logic, and why optimizing these routines is critical for making quantum computing viable. The conversation covers quantum error correction, including why T gates are especially expensive, how magic state factories works, and how different hardware architectures change what “cost” even means. Gidney also explains how resource estimates for breaking cryptography have dropped by orders of magnitude and what drove those improvements. We also dive into the tools he built, including Stim, Quirk, and Crumble, which help researchers simulate noise, visualize circuits, and track how errors propagate through complex systems.

Publisher

632nm

Link

share.transistor.fm/s/e45f1906

Published

March 27, 2026

Duration

2h 4m

Format

Podcast

Category

Issues · Science

Source

RSS feed

Host

Misha Shalaginov, Michael Dubrovsky, Xinghui Yin

6

632nm

@632nm

#quantumalgorithmscheaper #statefactories #resourceestimates #naturalsciences

The Nile