Originally published at www.amarchenkova.com on January 24, 2015.
Quantum mechanics is hard. No one is debating that. But there are a lot of bad facts out there just because the metaphors used were not explained well. Let’s debunk myths and explain some misconceptions.
“QUANTUM COMPUTERS ARE USEFUL BECAUSE THEY CAN CHECK ALL POSSIBILITIES AT ONCE”
No. That’s not how that works. Where did this explanation come from?
More than fifty quantum algorithms have been discovered. Each quantum algorithm works differently, but none of them work by checking all possibilities at once. If that was true, all quantum algorithms would be the same and quantum computers could speed up any problem, which is not true.
The most common time you will hear this myth is when breaking RSA encryption on a quantum computer is discussed. This is how it really works:
The quantum algorithm, Shor’s, run on a quantum computer doesn’t try checking each prime factor directly. There is one quantum step that makes finding the prime factors much easier; it concentrates on finding the period of a function which contains the RSA key and classically computes the greatest common divisor. (Interested in reading more? Here’s an article I wrote about how Shor’s algorithm is run on a quantum computer, in case you have one in your back pocket)
This is why doubling the size of the RSA key will not make cracking RSA encryption that much more difficult for a quantum computer to solve. It doesn’t need to test more primes, as it would if the algorithm was just testing more possibilities — it uses the same quantum Fourier transform to find the period of the function containing the RSA key.
“ENTANGLING TWO QUBITS TOGETHER ALLOWS FOR FASTER THAN THE SPEED OF LIGHT COMMUNICATION”
General scientific consensus is that no, that faster than the speed of light communication is not possible. This myth came around through this simple but misleading thought experiment explaining entanglement:
You have two lights. One can flash red, the other can flash blue. You put one in a box, and the other in another box. You send ONE of the boxes to Pluto. When you open your box on Earth and trigger the light and see that the light is flashing red, you KNOW that the box on Pluto has the blue light.
This implies “instantaneously” and “faster than the speed of light”.
Here’s the issue — no information is actually passed between the lights. The lights are ‘collapsed’ before the ‘measurement’ of opening the box. We were messing in the initial state preparation, by ‘knowing’ that one light will be red, and the other blue, and collapsing them before they are sent. We interfered in the original creation of the ‘entanglement’, saying that one light should be red, and the other should be blue.
We can apply this same metaphor to real qubits. Measuring one qubit and immediately knowing the state of the other implies we knew all along how they were entangled, just as we knew how the lights were entangled.
In quantum entanglement, while the qubits themselves exist in a superposition of 0 and 1, and only upon measurement, the qubit collapses into either a 0 or 1. They remain in that superposition until they are measured far apart. At first glance, this does seem to be information transfer.
However, if we don’t mess with the initial state preparation, we will receive the measurement information, but we won’t be able to interpret it. Are the qubits going to correlate and be both polarized up, both polarized down, or opposite polarizations (assuming our qubits here are photons)? You don’t know what the information means without the classical channel — which is limited by the speed of light.
Now you see the fallacy in the light experiment, where we know how the lights will be entangled beforehand. Since we interfered in the initial state of the lights, we get misled into believing there is faster than the speed of light information transfer, when actually we knew the entanglement all along.
“D-WAVE IS THE FIRST QUANTUM COMPUTER”
How do you define quantum computer? This is an interesting question because the race is on to build the first “quantum computer”. What kind of quantum computer? How many qubits? What application? The reliability?
D-Wave is a quantum annealer, which is very different from a universal quantum computer. It’s great for optimizing solutions to problems by quickly searching over a space and finding a minimum (or “solution”) by running adiabatic quantum algorithms. However, quantum annealing will never be able to run Shor’s algorithm, which breaks common forms of modern cryptography, like RSA and ECC.
A universal quantum computer is meant to be general purpose, where basic quantum circuit operations, similar to the classical circuit operations like AND and OR, can be put together to create any sequence. This includes Shor’s algorithm and Grover’s algorithm — and can be used for a larger set of problems than a quantum annealer.
Which type of quantum computer is a true quantum computer?
Which algorithm will convince us of quantum speedup? Shor’s seems to be ‘Schrodinger’s Killer App’ to ‘prove’ quantum computers are real. However, there are also a minimum amount of qubits required to run Shor’s algorithm but a thousand times more required to show a speedup.
How large a prime number must it break to be the ‘first’ quantum computer? In what amount of time?
What if you don’t care about factorization at all, and care about optimization?
I think we will have many ‘first’ quantum computers.
Follow me on www.amarchenkova.com to see these posts first! If you liked this post, please share. Quantum mechanics is a great late night bar topic!
I tweet about quantum tech a lot: