Quote from: enigmazr on June 10, 2013, 08:49:42 AM

Additionally, some believe that the device will also be inefficient at mining -- although I am inclined to think otherwise.

They aren't inefficient at mining they are completely incapable of mining. A quantum computer of insufficient size (in terms of qubits) to "model" the problem can't solve the problem even given an infinite amount of time. Even if a quantum computer of sufficient size (# of qubits) was built collision resistant hashing algorithms (like SHA) can't be solved using Shor's algorithm. The only known quantum algorithm is Grover's algorithm which doesn't provide the exponential reduction that Shor's algorithm does.

To brute force a symetric key or hash function requires 2^n operations (attempts) in classical computing. Grover's algorithm reduces that to 2^(n/2). There has been little work done in quantum resistant hashes because despite how great n/2 vs n looks one can compensate by simply doubling the hash size. For example if someday a quantum computer could break a 2^256 hash in reasonable amount of time one could go to 2^512 hash (which would require 2^256 operations or 2^128 times as long as that "reasonable amount of time"). We routinely extend hashes beyond what is necessary. Brute force of SHA-128 isn't even possible using classical computing and probably won't be in our lifetimes (barring some cryptographic break) but we hedge that by using 256 bit (or 512 bit) hashes instead.

For bitcoin mining the issue becomes more complex. The Grover's algorithm looks for a specific value (which is very difficult in a 2^256 keyspace) but Bitcoin mining isn't that hard. In Bitcoin mining where the miner is looking for ANY value that is less than the difficulty based on the target. In other words a miner's job is easier than a simple brute force attack because any hash meeting the difficulty target is "good". For current difficulty, the target is 0x0000000000000113370000000000000000000000000000000000000000000000 in hexadecimal and there are 1,797,329,777,810,040,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 potential hashes below that target.

For SHA-256 a QC running Grover's algorithm would require 2^128 attempts to break a specific hash. However a Bitcoin miner using classical computing can find (at current difficulty) one (of many) hash which is small enough in "only" ~2^56 attempts. 2^56 is still a smaller number of operations than 2^128 even if 2^128 is much smaller than 2^256.

A common misconception is that QC are "faster" in the sense that a single operation is completed faster which is incorrect. In actuality they are many many magnitudes slower due to need for retesting to compensate for quantum noise (errors). They are "faster" because they need to perform less operations. It would be more accurate to say they operate more efficiently. An analogy might help. Imagine you have a task which requires 1 second per attempt and on average takes 3,600 attempts to find a solution. It would take you on average 1 hour to complete. On the other hand if you could complete the task in such a way that it took 10 seconds per attempt but on average only took six attempts the time to a solution is now only a minute. Although the individual attempt takes 10x as long the fact that the new algorithm is so much more efficient means the solution is found faster. This is how quantum computers gain significant "speed" increases. They are "fast" because they exploit quantum properties to reduce the number of attempts not because each attempt is any faster.

2^128 quantum operations is still greater than 2^56 classical operations even if both systems could complete a single operation in the same amount of time. At the current time quantum computers are much slower per operation but that will likely decrease with time. Satoshi did well using a 256 bit hash although SHA-128 for example is essentially unbreakable even with classical computing. Had he done so 2^64 is pretty close to 2^56 and when difficulty is 20 billion a quantum computer would require less operations than a classical one. Even then it is unclear if quantum mining would be faster.