Originally Posted by

**Nordstern**
Quantum computing chips aren't really designed to solve these kinds of problems. Their problems are more like "analyze every surface of this mountain range simultaneously and tell me the highest peak and lowest valley" or "find the most likely result of this economic situation".

Might they be used in the future to do cryptographic analysis? Probably, but I haven't seen that yet.

Just FYI, that's a gross misunderstanding of how quantum computers work. Try

https://arxiv.org/pdf/quant-ph/9812037.pdf or the other quantum computing primers on

https://www.scottaaronson.com/blog/ (right sidebar, scroll down a ways).

They will be useful for certain cryptographic work: Shor's algorithm dramatically improves the performance of integer factorization and finding (elliptic curve) discrete logarithms. Grover's algorithm improves the performance for breaking symmetric algorithms like block ciphers and hash functions (EG the double SHA256 used in Bitcoin, though this is less direct[1]). Grover's algorithm effectively halves the number of bits of effective security, so a 256-bit cipher would be as effective as a 128-bit cipher is today. Hash functions require more bits for security than block cipher primitives, so Bitcoin will probably be breakable by quantum computers if they are actually possible.

The "if they are actually possible" bit is important: they work at very small scales but the difficulty of building a general-purpose quantum computer* grows exponentially with the number of qbits needed. The connections decohere faster and faster as more qbits are added, such that beyond 10-15 qbits (the current record is 10) the system decoheres (can't be used for computation) so quickly that we can't measure it. Going to the fastest measurement systems possible (femtosecond lasers) would only add 1-2 more qbits, even if those measurement systems were appropriate for the task at hand (they aren't). Several hundred are needed for any practical attacks. I'd estimate we're at least 50 years away from a practical general purpose quantum computer, and that's likely to be the perpetual 50 years away of Fusion power.

* D-wave's "quantum computer" is not general purpose. It only does simulated annealing, which isn't relevant to cryptography in any way.

[1] Not directly for SHA256, but likely applicable:

https://eprint.iacr.org/2017/864.pdf
## Bookmarks