Lightnews — Scholar-powered news

Craig Gidney @craiggidney.bsky.social · 5d

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

2

Craig Gidney @craiggidney.bsky.social · 10d

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

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 ...

arxiv.org

1 16

Craig Gidney @craiggidney.bsky.social · 10d

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.

2

Craig Gidney @craiggidney.bsky.social · 26d

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.

1 2

Craig Gidney @craiggidney.bsky.social · 26d

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.

1 1

Craig Gidney @craiggidney.bsky.social · 27d

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.

4 11 66

Craig Gidney @craiggidney.bsky.social · Sep 12

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.

1 3

Craig Gidney @craiggidney.bsky.social · Sep 12

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

1 1

Craig Gidney @craiggidney.bsky.social · Sep 12

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.

3

Craig Gidney @craiggidney.bsky.social · Sep 12

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.

2 5

Craig Gidney @craiggidney.bsky.social · Sep 8

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

1 3 29

Craig Gidney @craiggidney.bsky.social · Sep 4

// This is not a place of honor.

3

Craig Gidney @craiggidney.bsky.social · Sep 3

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.

1

Craig Gidney @craiggidney.bsky.social · Sep 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

4 9 130

Craig Gidney @craiggidney.bsky.social · Sep 3

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

Craig Gidney @craiggidney.bsky.social · Sep 2

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.

arxiv.org

2

Craig Gidney @craiggidney.bsky.social · Aug 31

Been awhile since I wrote a blog post.

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

algassert.com/post/2500

Why haven't quantum computers factored 21 yet?

Craig Gidney's computer science blog

algassert.com

5 13 65

Craig Gidney @craiggidney.bsky.social · Aug 27

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.

2

Craig Gidney @craiggidney.bsky.social · Aug 27

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++.

1

Craig Gidney @craiggidney.bsky.social · Aug 26

...what

1

Craig Gidney @craiggidney.bsky.social · Aug 23

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...

5

Craig Gidney @craiggidney.bsky.social · Aug 15

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

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

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...

docs.google.com

1 1 10

Craig Gidney @craiggidney.bsky.social · Aug 6

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

1

Craig Gidney @craiggidney.bsky.social · Aug 5

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

QIP2025

www.youtube.com

1 3

Craig Gidney @craiggidney.bsky.social · Aug 2

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.

3