A more efficient implementation of Shor's algorithm
6 hours ago
- #cryptography
- #zero-knowledge-proof
- #quantum-computing
- Shor's algorithm runs faster on quantum computers theoretically, but practical implementation is limited by memory constraints.
- A new paper reduces the memory needed for 256-bit elliptic-curve cryptography attacks by a factor of 20, though still impractical on current quantum computers.
- Researchers published a zero-knowledge proof instead of the actual quantum circuit, citing security concerns, a first in quantum computing papers.
- Quantum circuits require error correction and logical qubits; the new circuit uses <1,200 logical qubits and 90 million gates, needing ~500,000 physical qubits.
- Zero-knowledge proof uses SP1 and STARKs to verify circuit correctness without revealing details, compressed into a SNARK (Groth16) for efficiency.
- The proof relies on secure randomness from a 2019 multi-party computation, producing a 1.7MB verifiable file.
- This approach raises concerns about open mathematics, as the breakthrough isn't shared, hindering collaboration and further advancements.
- Unknown circuit details prevent assessing compatibility with other advances, like reducing physical qubits, keeping timelines for practical quantum computers uncertain.