Craig Gidney

I see loopholes

- CNOTs can't lower bound cost of computation because you can compile CNOTs away (e.g. Game of Surface Codes)
- What matters is amortized cost of doing many gates, not cost of isolated gates
- They speak of codes, not circuits, which is how Baspin+ missed the loophole in their bound

Low Depth Color Code Circuits with CXSWAP gate We present two new types of syndrome extraction circuits for the color code. Our first construction, which after [M. McEwen, D. Bacon, and C. Gidney, Quantum 7, 1172 (2023)] we call the semi-wiggling ...

For their student researcher-ship, Satoshi Yoshida extended our work on dynamic surface code circuits to color codes. They built and simulated iswap color code circuits and wiggling color code circuits. The iswap circuits use fewer entangling layers than CX circuits!

arxiv.org/abs/2510.00370

This HSBC paper reminds me of www.youtube.com/watch?v=EbfJ...

In the clip at 38:10, a speaker relays Pons being told a light water control had excess heat. Instead of "oh no", Pons replies "That's the most exciting thing, we see it too!". The audience bursts into laughter at the clear self-fooling.

Someone pointed out they're saying "not entangled" in the abstract via the word "independent". I made a correction to the post.

I still think it's a silly assumption, and if I'd been writing the paper I'd have yelled it, but with hindsight I no longer think they hid it in the supplement.

I was careful to avoid saying it isn't in the paper. It isn't in the abstract/title/intro/conclusion/body of the paper; it's in the supplement of the paper.

I do think it's misleading to put this in the supplement. A paper isn't supposed to have tricksy fine print. Leave that to the lawyers.

Blog post: "Actually, you can't test if quantum uses complex numbers" algassert.com/post/2501

I doom the concept of that 2021 Nature paper by showing how to compile any distributed quantum protocol into real-only gates while preserving locality.

This is tricky because any quantum algorithm, even one using imaginary values, can be encoded into the reals-only gates. They're BQP-complete. However, the simplest encodings add an ancilla that all encoded gates touch, and so fail to work in spacelike-separated tests that require locality.

Those papers misunderstand the goal. They avoid the word "complex" by using pairs of real numbers. But that's just complex with extra steps.

The real goal is to distinguish quantum computers limited to a reals-only gateset like

H, CCX, M, Z

from ones using a universal gateset like

H, CCX, M, ∜Z

This is the moral equivalent of running Bell tests without spacelike separation. It's better than nothing, but it's just fundamentally not nearly as convincing. There is a very clear avenue towards spoofing the test, and you would be blindly trusting that nature isn't doing it.

Remember the Nature paper constructing an experiment to distinguish real-number-only QM from complex-number-using QM?

In the supplementary material, they admit it doesn't work if pre-shared entanglement is present. Which there's no way to test for. So the experiment doesn't actually do the thing.

Apparently September 5th is "cultivate with fold-transversal S" day:

arxiv.org/abs/2509.05232

arxiv.org/abs/2502.017...

arxiv.org/abs/2509.05212

// This is not a place of honor.

Shor's algorithm is a great example of asymptotic analysis giving pretty bad intuition.

Case in point: you said O(n^2), implying fancy multipliers, but for cryptographically relevant sizes you'd (probably) still be using schoolbook multiplication. So the "relevant" scaling is more like n^3.

I used to write TODOs in my code. Now I write DIDNTDOs. Because let's be honest... these are apologies, not promises.

// DIDNTDO: handle negative values

It's not written as an identity in the 1992 Deutsch-Josza paper, but I'd consider that algorithm as clearly *using* the identity.

No, they used period-aware precompilation. Figure 2a arxiv.org/pdf/1111.414... is a dead giveaway. The accumulator is 3 qubits instead of 5 qubits, so it can't store intermediate values mod 21. And they stop after two steps despite (g^2)^2 mod 21 not being 1 for most choices of g.

Been awhile since I wrote a blog post.

Anyways... why haven't quantum computers factored 21 yet?

algassert.com/post/2500

Upon further investigation, it appears to be an inlining issue, where the compiler stopped inlining after the method reached some size threshold. Manually inlining it allowed adding the extra debug info at no runtime cost.

Was wondering why my code suddenly got HALF AS FAST.

I traced it to extra error info.. in a switch default that never even runs! I think the compiler was unconditionally constructing a location for the temporary string or something?? 🤮

Clear example why people trust C more than C++.

...what

Been experimenting with generating circuit-specialized simulation code, to reduce branch mispredictions.

Generating a 1M line NASM file has gone far better than a 1M line C++ file. nasm finishes in a few seconds on inputs of that size (gcc was taking hours). But still unnecessarily slow...

Yoked surface codes - QEC2025 Hello everyone my name is Craig and I'm going to be talking about techniques for reducing the spatial overhead of surface codes without asking for anything more from hardware Yoked surface codes Craig...

The recording of my talk on denser planar storage, at QEC2025: yale.hosted.panopto.com/Panopto/Page...

And the slides: docs.google.com/presentation...

What made you choose the floquet color code, instead of the floquet surface code (the honeycomb code)?

QIP2025

Something about that URL screams ephemeral. I remember thinking the site wouldn't be around for long, when I was attending.

The internet archive claims to have snapshots but for me they currently come up blank: web.archive.org/web/20250219...

But the talks are online at www.youtube.com/@QIP2025

An identity that'd be great... if it did 2 things instead of 3.

If one of the two CCZs on the right wasn't there, it'd yield an n-qubit incrementer with ̶4̶n̶→3n T gates.

If the CCCZ wasn't there, it'd yield n single-shared-control Toffolis to be done with ̶4̶n̶→3n T gates.

The key idea is to just eagerly delete inconvenient qubits using X basis measurements, and fix the resulting phase shifts later.

The first novel thing I did in quantum computing was find a way add +1 to a register using O(1) space and O(n) gates. For 10 years I've wanted to know how to generalize that from x+=1 to x+=C... and I finally figured out a way to do it!

arxiv.org/abs/2507.23079

When their preprint came out, it was overshadowed by Regev's paper. I found it disconcerting: space is the key near-term cost and Regev was paying space while this paper was saving space, but then Quanta and Scott Aaronson mentioned Regev but not Chevignard+. Glad they're getting recognition now.

YouTube video by QIP2025 Clémence Chevignard: "Reducing the Number of Qubits in Quantum Factoring" (QIP 2025)

Chevignard's QIP2025 talk on reducing the space cost of quantum factoring:

www.youtube.com/watch?v=R3yM...

And her co-author Schrottenloher's talk at the Simons Summer Cluster on Quantum Computing:

www.youtube.com/watch?v=0pnX...

YouTube video by QIP2025 Craig Gidney: "Magic state cultivation: growing T states as cheap as CNOT gates" (QIP 2025)

My QIP2025 talk on magic state cultivation:

www.youtube.com/watch?v=bbR0...

A later longer version of the talk, given at the Simons quantum colloquium:

www.youtube.com/watch?v=gxzt...