Quantum computers: how to navigate across Turing’s tapes, Schrödinger’s cat and Einstein’s dice.
«God doesn’t play dice with the universe» – Albert Einstein.
“Stop telling God what to do!” – Niels Bohr’s answer.
History so far has been on the dices’ side, but quantum computers are the present, and in few years they could revolutionize fields to the likes of cryptography, simulations and NP problems in general.
Last year Google announced they will soon provide access to their quantum computers via cloud services like IBM is already doing with IBM-Q since this past May. D-WAVE on its side has already been commercializing its D-WAVE ONE since 2011.
There is not much use for these types of service for the average Joe. They are especially oriented to research groups and scholars in general who wish to experiment with this kind of paradigm.
What’s so interesting about them? Well, the quantum nature of the process allows us to tackle very complex problems (e.g. cryptography or NP-hard problems), exploring and processing several paths at once.
Cryptography itself has been so far one of the most promising fields for quantum computers. Wikipedia even has an entry about post-quantum cryptography, that is, cryptographic algorithms that should be safe from quantum computers’ attacks.
Nowadays there is an enormous amount of information protected by algorithms like RSA: bank transactions, top-secret documents, blockchain etc. Quantum algorithms theoretically able to crack complex keys like RSA in reasonable time already exist, like Shor’s for example, and the thought of machines able to crack any cryptographic code is starting to cause panic to mount.
With these premises, we can say that the quantum race has begun.
How does a quantum computer work?
The science behind quantum computers is somewhat bizarre and weird, with properties very counterintuitive for our day-by-day experience
In order to attempt to explain what a quantum computer is, we have to start with analogies from traditional computers.
Traditional computers use bit (Binary digIT) as the fundamental unit of information, and these can be either 0 or 1; quantum computers, on the other hand, work with qubit (QUantum BIT), whose statuses are can also be 0 or 1.
But the analogies end here. While a bit can only be either 0 or 1, a qubit in superposition is all the values between 0 and 1 at once.
In simpler terms, a two-bit variable can be only one of the 4 possible values (e.g. 01), a two-qubit variable is simultaneously 00, 01, 10 and 11.
Superposition
Superposition is the ability of a particle to be in many states at once, that is until it gets measured.
You may think that the particle has always held that value, as a “hidden” value just waiting to be read. However, this is not the case: the particle really is in some kind of undetermined “limbo”. Strange as it may seem, the very act of reading it forces the particle to “decide” what value to be.
This oddness was proved with the “double slit experiment”, where the photons behaved as waves when not observed, and as particles when they were measured.
But there is more than superposition: two other important properties are the entanglement and tunneling effect. We have entanglement when two particles become tied each other so that they “interact” regardless of the distance (!). In some cases a particle can go through an obstacle as it was “teleporting”, and we call it tunneling effect.
All these properties can be leveraged to tackle complex problems like traveling salesman with quantum algorithms, finding solutions exponentially faster than traditional computers.
The main property of a particle is the “spin”, which is the angular momentum.
By convention we say that a particle’s state is “0” when it spins upward, and “1” when it spins downward. Using the vertical axis to represent the status is just a convention but it will serve us to work.
Entanglement
Entanglement is possibly even weirder than superposition: we say that two particles are entangled when their spin is tightly correlated. That is when one of the two flips, changing value, the other one instantaneously flips as well.
This means that when we observe one of the two, we can know precisely the value of the other one.
Entanglement is a key concept since the quantum gates can perform logic operations on the qubits because of it.
Traditional computers work with sets of logic gates. Logic gates are circuits performing simple operations on the bits in input, returning one bit in output.
Quantum gates
The figure shows logic gates, where A and B are the input bits, and Y is the output.
Instead, a quantum gate flips a superposition state of a qubit, and returns a different superposition in output.
Simplifying, a quantum circuit sets some qubits, applies quantum gates (therefore altering the probabilities), and ultimately measures the outcome. When the measurement is done, the qubit’s superposition collapses in a series of 0 and 1, which is the solution.
A world of Qubits
This means that all the possible combinations are processed at once, and the final result will be a single state, with a probability index. Basically, a quantum computer is a set of qubits arranged in a grid, so that they can talk each other.
Think of it like a small superconductive magnet, where the direction of the flow makes the spin.
The result of a computation executed by a quantum computer is just a probability. If we run it a few times, the result will be a list of probabilities, one for each combination. The possible combinations will be 2↑n, where n is the number of qubits.
Well, at least on paper. Practically speaking complex computations require quite a few qubits, and adding new ones becomes harder and harder as the number increases.
The reason for this is that the system rests on a very delicate balance: the qubits influence each other and even extremely small perturbations can produce errors quite difficult to correct. Also, in order to maintain the superconductive properties needed to perform these types of computations, quantum computers must be kept at an extremely low temperature, close to absolute zero.
Universal quantum computers: IBM and Google
Many of the most interesting abilities that make quantum computers so attractive are not yet possible with the current technology. For example, in order to break an RSA 2048, we would need several thousand qubits and a few million ports. As of today, the most advanced universal quantum computer has 17 qubits (IBM)1.
So, we aren’t there yet, but what is this “universal” about? We call a quantum computer “universal” when we can program it for different classes of problems. In short, it’s as close as to the “general purpose” concept we can get in quantum computing.
Universal quantum computers use what is called “Gate model”, that is a circuit made of a set of logic quantum gates (see fig. below) similarly to the transistor-based traditional ones.
Both IBM and Google have made public a set of API to help people learning the new paradigm…
Google’s Quantum Computing Playground is no more than a simulator. It has GPU accelerated hardware and a web interface which allows users to simulate quantum circuits with a scripting language named QScript.
IBM on its side made its IBM-Q architecture accessible through a Composer web app, where programmers can build quantum circuits by dragging and dropping quantum gates on its graphics interface (see below).
D-WAVE, an army of more than 2000 qubit
It might strike us as a bit odd to read about IBM and Google struggling with just a few tens of qubits when D-WAVE has recently commercialized the first quantum computer with more than 2000 (!) qubits. As a matter of fact, D-WAVE computers, even if they are already commercially used, with interesting use cases like validation of complex software systems in Lockheed Martin, are not universal.
In fact, D-WAVE’s computers are mostly optimizers, that is they look to the best solutions amongst the many possible. In other words, if we look at a graph of a function (below), we say we found a solution when we found the absolute minimum, that is the lowest energy point of the function, even if there can be other less optimal minima (local minima).
The main problem in this kind of computation (very common in machine learning), is that it’s very hard to determine if a certain point is the absolute minimum or just a local one.
D-Wave’s model is what is called “quantum annealing” (a special case of the adiabatic model).
The process works like this: the circuit starts from a high-energy state, which allows the qubits to “jump” over the thresholds of the local minima thanks to “quantum tunneling” (see below), where the particle can pass through the barrier, jumping straight to the next minimum.
This “operation” is repeated over and over, progressively cooling the state so to “amplify” the effect of the minima, until it reaches an energy level close to zero, where the particles no longer move from the minima they reached, and that represents the solution we were seeking.
Practical example to explain quantum annealing
This process, even if it cannot be considered universal, in Google’s estimates can be magnitudes faster than conventional computers for this specific kind of problems.
D-WAVE’s choice to specialize in quantum annealing has allowed them to minimize the number of connections between qubits, therefore making it possible to implement an extremely large number of qubits compared to the competition.
Microsoft’s version
Microsoft decided to pursue a different way and work on the topological model, that works with completely different principles than the others. In fact, the topological model uses the Braid theory as the mathematical base.
Instead of coding the information in the particle (like the spin), here it’s coded within the order the particles are swapped. As we swap the particles, the trail they leave behind somewhat resembles a braid (see figure).
At the end of the permutations, the particles are paired: some will annihilate each other, while others will not, and the combination of the particles that did not annihilate is the solution. The main advantage is that since the information is tied to the structure instead of the particles, it is far less sensitive to the oscillations, the noise and the loss of coherence (which leads to the loss of superposition).
The reason why this model has not been very successful in the past is that it strongly relies on the existence of an exotic quasiparticle, the “anyon”.
The very existence of the anyon has been in doubt for decades, therefore progress was limited until this past July 20th when a paper proving it experimentally was published in Science.
We are in the very early phase, but the race has begun.
This article was originally published on Spindox.it: Hitchhiker’s guide to quantum computers
Notes
1. Google has recently announced that a 50 qubits machine will be available soon.
Links
Artificial Intelligence and ethics: fears and controversy
Companies leader in the field
Google: Google Quantum A.I. Lab Team – About – Google+ in Mountain View, CA. They also have relations with a group at UC Santa Barbara, so they might have work going on there too.
IBM: Theory of quantum computing and information group, based at the Watson Research Center in NY.
Microsoft: Page on microsoft.com Station Q in Santa Barbara, California.
ID Quantique: ID Quantique, the home of Quantum-Safe Crypto based in Switzerland, sells commercial quantum cryptography systems.
MagiQ: Home based in Massachusetts also makes a commercial quantum cryptography system.
Articles
The quantum clock is ticking on encryption – and your data is under threat
Nature: Commercialize quantum technologies in five years
Top 3 Quantum myths and misconceptions
Topological Quantum Computer – Professor John Preskill, Caltech
why topological quantum computers cannot work -Gil Kalai
Israel gets spooky with national quantum lab
Overview of adiabatic quantum computation
Quantum Computers Compete for “Supremacy”
Inside Microsoft’s quest for a topological quantum computer
Google Quantum Computing Playground
Why Quantum Computers Might Not Break Cryptography
Google’s Quantum Computing Push Opens New Front in Cloud Battle
Andrea has been working in IT for almost 20 years, covering about everything, from development to business analysis, to project management.
Today we can tell he is a carefree gnome, passionate with Neurosciences, Artificial Intelligence, and photography
