For some problems, quantum computers offer a polynomial speedup. The most well-known example of this is quantum database search, which can be solved by Grover's algorithm using quadratically fewer queries to the database than are required by classical algorithms. In this case the advantage is provable. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.
Consider a problem that has these four properties:
-The only way to solve it is to guess answers repeatedly and check them,
-The number of possible answers to check is the same as the number of inputs,
-Every possible answer takes the same amount of time to check, and
-There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.
An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length).
For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of the number of inputs. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as Triple DES and AES by attempting to guess the secret key.
This looks like exactly what someone bruteforcing SHA256 would need to do.
Aren't database search and keyspace search pretty similar?
Isn't "lucking out and coming across a private key" similar to "finding collisions to two-to-one functions"?
From SHA-256 page :
For a hash function for which L is the number of bits in the message digest, finding a message that corresponds to a given message digest can always be done using a brute force search in 2^L evaluations. This is called a preimage attack and may or may not be practical depending on L and the particular computing environment. The second criterion, finding two different messages that produce the same message digest, known as a collision, requires on average only 2^L/2 evaluations using a birthday attack.
Damn, so the fastest seems to be 2^128, 2^64 for a quantum computer...
Third time's a charm :
- Time complexity to find a collision for SHA256 using a classical computer : 2^128
- An Intel Core i7 Extreme Edition 3960X (Hex core) at 3.33 Ghz can do 178x10^9 instructions per second.
(Still assuming instructions=time complexity)
2x10^27 seconds or 60 billion billion years. Much less ridiculous, but still QUITE a lot!
Let's see for a quantum computer:
- Time complexity to find a collision for SHA256 using a quantum computer : 2^64 (assuming quadratic speedup)
That's still a LOT of operations, and if we could make a quantum computer manipulate qubits as fast as that i7 is manipulating bits, it would still need 10^8 seconds to execute that function, or about 120 days! (Or 6 days for a cluster of 20 of such computers and so on...)
So some day Bitcoin might have a problem with quantum computers, but it would require improvements in quantum computing greater than those which happened for classical computing since the time of the first mechanical computers! We're only able to manipulate a few qubits for now, even though that might change quickly with new breakthroughs :
http://newsroom.unsw.edu.au/news/technology/breakthrough-bid-create-first-quantum-computer(With this breakthrough we might not need for quantum computers to like go all the way from the first mechanical computers to current ones, but jump right in at the start of the "silicon age".)
