A quantum computer processes information using physical phenomena from quantum mechanics. Instead of ordinary bits, it uses qubits, which can occupy superpositions of 0 and 1. section 14.0 section 14.1.1
A simplified quantum computation follows this pattern:
- Prepare qubits in selected values or superposition. section 14.1.2
- Transform them with quantum gates, potentially creating entanglement. section 14.1.2
- Measure the qubits, collapsing their states into classical 0s and 1s. section 14.1.1 section 14.1.2
- Use a classical computer to interpret the result and complete a useful computation. section 14.1.2
Why cryptographers care
Shor’s algorithm can efficiently attack factorization and discrete-logarithm problems, threatening RSA, Diffie-Hellman, and elliptic-curve cryptography. Stored ciphertext could therefore become readable if sufficiently scalable quantum computers arrive. section 14.1.3 section 14.0
Quantum computers are not universally faster replacements for classical computers. Useful, scalable machines remain unrealized, with noise and error correction among the central obstacles. section 14.1.3 section 14.4
Google reported quantum supremacy in 2019 with a 53-qubit machine, completing a task in minutes that reportedly would have taken a classical computer thousands of years, though the task was not useful. section 14.1.2
