Why haven't quantum computers factored 21 yet?
10 days ago
- #shors-algorithm
- #quantum-computing
- #factoring
- Quantum computers factored 15 in 2001 but haven't factored 21 by 2025, not due to lack of progress but because factoring 21 is significantly more complex.
- The circuit for factoring 15 used 21 entangling gates, while the circuit for factoring 21 requires 2405 entangling gates—115 times more.
- Key reasons for the cost difference include: most multiplications in factoring 15 are by 1 (doing nothing), the first multiplication is nearly free, and remaining multiplications can be done with simple swaps.
- Factoring 21 involves no multiplications by 1, making it inherently more expensive, and the operations required are more complex (e.g., multiplying by 4 mod 21 requires 41 Toffoli gates).
- Additional factors like quantum error correction could make factoring 21 up to 10,000 times more expensive than factoring 15.
- Some papers claim to have factored 21 quantumly but often use optimizations that bypass the hard parts, making their results questionable.
- Quantum factoring isn't yet a good benchmark for progress; instead, focus on quantum error correction and scaling challenges.