Quantum computing has been projected as a sort of messiah to the technological plateau that humanity is experiencing. The general prevailing belief is that with the advent of QC, we will be able to do the impossible — break cryptographic codes, solve problems that have eluded computer scientists for years, and even occupy interstellar space.
This is what everyone has to offer when asked what quantum computing is: “Well, these computers can tackle multiple problems at once. It’s because classical computers can only be in one state at a time — 0 or 1 — while quantum computers can be in both states at the same instant of time!”
The only problem with this explanation is that it is wrong, and misleading to say the very least.
No, quantum computers are NOT in the same state at the same time. At least not technically, and although we might be able to break cryptographic codes faster, we won’t be able to solve puzzles miraculously.
Justin Trudeau was asked to summarize[1] quantum computing and he summed it up better than any layman explanation would:
“Very simply…normal computers work, either there’s power going through a wire or not— a one, or a zero. They’re binary systems … What quantum states allow for is much more complex information to be encoded into a single bit…a quantum state can be much more complex than that, because as we know, things can be both particle and wave at the same time.”
He was careful not to use the term “can be in both states at the same time,” which is commendable because that is where the problem lies. It turns out that staying in two states is physically impossible. Rather, quantum computers fundamentally take advantage of the superposition principle in quantum mechanics which states that any particle can be assumed to be in all states until and unless observed. Upon observation, the particle randomly takes one of the states. In other words, quantum computers form entangled states[2] of 0 or 1, and stay in those states, which is vastly different from staying in two states at the same time. A geometric way to think about it is to think of 0 and 1 as only the poles of a sphere, and a “qubit” as any point on that sphere. Due to a multitude of these points, data of many orders of magnitude[3] more can be stored using the same number of qubits and classical bits.
While we may still be able to crack conventional cryptographic techniques much faster, it is because of this enormous capability to store more data and not because of duality of states. The class of problems known as non deterministic polynomial complexity or NP — problems that don’t seem to have polynomial time solution-getting algorithms — will unfortunately still remain unsolved, because quantum computers don’t so much mathematically model a problem as physically model it; in theory, we let nature do the math for us, and just watch where the final state ends up. The newfound capability to break crypto sequences wouldn’t be a problem in the long run either, because there are ways to make it even more secure using quantum cryptography. In fact, Google has already begun testing[4] such techniques. Even current state of the art research cannot guarantee that the “speed-up” on computational problems we expect from quantum computing will happen for all problems. Recently, Ewin Tang from the University of Texas at Austin proved that one of the major advances in quantum computing was redundant[5] and can be achieved by classical computing, which set back the quantum industry by decades. Add to that to the fact that we are at least a decade away from the world’s first meaningful quantum computer, and we’ve been that way for more than a decade, the picture is not so rosy anymore.
But there’s more reason to be optimistic than dismal. Intel has already created 49 and 17 qubit processor chips[6] that offer a glimpse into the enormous potential of quantum computing. They demonstrably prove that most traditional solvable problems will be solved in milliseconds, compared to minutes in the traditional way. The only major hurdle for stable quantum computing remains to achieve absolute zero-like temperatures. Qubits require temperatures 250 times colder than outer space to sustain their wave-like behavior. Attempts to recreate those environments in today’s laptops have yielded little fruit, however, the news that major companies have already started preparing for a quantum future is reason enough to be optimistic. And while we may not have quantum computers in our pocket anytime soon, watch out for each quantum of progress they make.
References
Morris, David Z (April 17, 2016). “Justin Trudeau Explains Quantum Computing, And the Crowd Goes Wild”. Fortune Magazine. http://fortune.com/2016/04/17/justin-trudeau-quantum-computing/
Beall, Abigail and Reynolds, Matt (February 16, 2018). “What are quantum computers and how do they work?”. Wired. https://www.wired.co.uk/article/quantum-computing-explained
Aaronson, Scott (2008). “The Limits of Quantum” https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
Greenberg, Andy (July 7, 2016). “Google Tests New Crypto to Fend Off Quantum Attacks”. Wired. https://www.wired.com/2016/07/google-tests-new-crypto-chrome-fend-off-quantum-attacks/
Hartnett, Kevin (July 31, 2018).“Major Quantum Computing Advance Made Obsolete by Teenager”. Scientific American. https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/
Greenemeier, Larry (May 30, 2018). “How Close Are We—Really—to Building a Quantum Computer?” https://www.scientificamerican.com/article/how-close-are-we-really-to-building-a-quantum-computer/