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

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. Gidney shares his unconventional path into the field, the role of intuition and tooling in discovery, and how software engineering shapes modern quantum research.

Whether you’re interested in quantum computing, error correction, cryptography, or the engineering challenges behind scalable quantum systems, this episode offers a clear and grounded look at what it really takes to turn quantum algorithms into reality.

Follow us for more technical interviews with the world’s greatest scientists:
Twitter: https://x.com/632nmPodcast
Instagram: https://www.instagram.com/632nmpodcast?utm_source=ig_web_button_share_sheet&igsh=ZDNlZDc0MzIxNw==
LinkedIn: https://www.linkedin.com/company/632nm/about/
Substack: https://632nmpodcast.substack.com/

Follow our hosts!
Mikhail Shalaginov: https://www.linkedin.com/in/mikhail-shalaginov/
Yudong Cao: https://www.linkedin.com/in/yudong-cao-25b6a929/

Subscribe:
Apple Podcasts: https://podcasts.apple.com/us/podcast/632nm/id1751170269
Spotify: https://open.spotify.com/show/4aVH9vT5qp5UUUvQ6Uf6OR
Website: https://www.632nm.com

Timestamps:
00:00 - Intro
01:22 - Shor’s Algorithm
04:02 - Why are Arithmetic Operations Important?
08:35 - Why are T-Gates Important for QEC?
13:47 - Motivations for Creating Crumble and STIM
18:40 - Can AI Code Quantum Simulators?
22:32 - Journey into Learning Quantum
26:50 - How to Enter the Field of Quantum Computing
31:16 - From Starcraft to Software Engineering
36:05 - Crumble Demo
53:18 - Quirk Demo
1:00:48 - Estimating Resources for Quantum Computation
1:08:58 - Optimizing Measurements for Computation
1:16:40 - How Many Qubits Do We Actually Need?
1:30:49 - Other Research Areas for Improving Fault Tolerance
1:41:23 - Elliptic Curve Discrete Logarithm Problem
1:46:55 - New Tools for Quantum Computing
1:50:23 - What Would Craig Do with Unlimited Funding?
1:52:28 - How Learning Has Changed for Craig with Experience
1:57:31 - Riding the Wave of Innovation vs Sticking to One Idea
1:59:53 - Advice for Young Scientists

#quantumcomputing #quantumphysics #computerscience #googleai #googlequantum