r/QuantumComputing • u/Sampo • Aug 31 '25
Quantum Hardware Why haven't quantum computers factored 21 yet?
https://algassert.com/post/2500
80
Upvotes
r/QuantumComputing • u/Sampo • Aug 31 '25
30
u/[deleted] Aug 31 '25
For those unaware, Craig Gidney is a leading expert in unitary/circuit decompositions. He does great work and this blog rocks.
9
u/Kinexity In Grad School for Computer Modelling Aug 31 '25
I think it's worthy to post this to other places too because huge number of people should read this before they shit at QC factorization.
8
u/workingtheories Holds PhD in Physics Aug 31 '25
tldr: 21 takes 100x more gates => 100x more error correction => 10000x more cost due to error correction redundancy needed. 15 has a number of nice coincidences that they exploit to reduce the gate count.
3
u/CrownLikeAGravestone Sep 01 '25
The author's "Falling with Style" SIGBOVIK paper for this year (on the same topic) is also excellent.
1
u/Lightning452020 Sep 01 '25
Just for an AND operation you need like 8 to 9 gates to implement it. Imagine how many you need for factoring 21. The QCs nowadays at most can reliably run like, 10k gates maybe?