Lightnews — Scholar-powered news

Craig Gidney @craiggidney.bsky.social · 5h

The dialog takes >2n qubits of storage because we don't know any way to sift out the classically-known modulus (so annoying!). Still beats prior work.

There's some waste from GCDs taking so many steps, but the Bernstein-Yang GCD is close to the 2n qubit floor.

Craig Gidney @craiggidney.bsky.social · 5h

Because dialogs are built from linear operations, applying the dialog for x mod N to an initial state of (y, 0) instead of (x, 0) will produce (y/x, 0) instead of (1, 0). So y /= x is performed by:
1. convert x into dialog rep (i.e. do a GCD)
2. apply the dialog's steps to y
3. uncompute the dialog

1

Craig Gidney @craiggidney.bsky.social · 5h

My contribution to arxiv.org/abs/2510.10967 is a space-efficient strategy for modular division under superposition. It's based on recording the branches taken during a GCD, to decompose a number+modulus into their "dialog representation", which unlike binary is entirely linear.

1 12

Craig Gidney @craiggidney.bsky.social · 12h

I'll be speaking at the Simons Institute this Thursday: simons.berkeley.edu/events/quant... (Hopefully my flight doesn't get cancelled this time.)

Talk Title: Optimizing the Annoying Stuff: Reducing Costs Obscured by the Abstract Circuit Model

Abstract: attached as image

9

Craig Gidney @craiggidney.bsky.social · 7d

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 · 12d

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 · 12d

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 · 28d

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 · 28d

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 · 29d

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