I should start by saying that my background is software engineering. While I’ve read a couple of books on quantum mechanics, I don’t have formal training as a physicist, but that didn’t deter me from playing with quantum computing simulators and learning the generalities.
About a week ago, IBM launched the Quantum Experience. The cornerstone of this initiative is to make a real, working quantum computer available for anyone. They can build a program using a Composer, dig through an excellently written tutorial, and either simulate or execute the quantum algorithm through the cloud. I can’t overstate how important this move is: a few universities and institutions are working on quantum computers, but this is the first time everyone can use it, free of charge (actually, there’s a “currency” you spend for prioritization, but you don’t pay for it).
This blog will discuss the topic, give the basics while trying to dwell as little as possible on algebra or physics and, at the end, we’ll build a simple algorithm and discuss the results. This is just an engineer’s perspective, and you should definitely check the manual.
Up until now, the only way people could interact with quantum computers is through simulators. In a theoretical sense, you can simulate full quantum computers with a classical computer. What we gain from actually executing it in a real one is great theoretical speedup in some applications. The simplest example is the Deutsch-Jozsa problem. Let’s say we have a function that’s either constant, in that it always outputs the same value for any input or balanced, in that it returns a value for half of its inputs and another value for the other half.
A classical computer, in the worst case, would need to check this function for half of the input plus 1 to be sure. A quantum computer only needs to use this function once.
Other popular algorithms includes Grover’s algorithm, which searches an unsorted database faster than anything else, and Shor’s algorithm, which factorizes numbers and poses a security risk to the widely used RSA cryptography scheme.
Classical algorithms with randomness
People in general know about quantum mechanics at different degrees. Maybe the best way to introduce the subject is not through it, but through random results in classical algorithms. For that, we’ll turn to a primitive tool: the ruler.
Everyone who has children (or was a child themselves) should be familiar with this: You have two papers of different lengths and you want a third one to be as large as the two of them combined. There are various ways to do it, with either marked or unmarked rulers. Let’s say it’s the former and the algorithm for adding those two distances is:
- First, measure both distances (say 34 mm and 46 mm).
- Add those numbers together (80 mm).
- Use a marker on the third piece of paper with that distance.
- Finally, cut at that place.
If you compare your result at the end with our two original papers, you’ll see you get it right most of the time, but sometimes you’ll get it a millimeter wrong to either side. Maybe you draw too big of a mark, maybe you grabbed the scissor with your less-skillful hand. The most likely cause, though, is that the distances were 34.3 and 46.4 and those little errors we ignored added up. Let’s think this in probability terms: We have this procedure for adding up distances (or numbers in general) and it produces results randomly. In a function, this is how we could describe this situation (remember 0.95 is 95%).
In the digital world, a bit is either on or off and a 5 in binary is the same as any other 5 in binary; in the analog world, a lamp has various degrees of “on” — each of them almost impossible to replicate with exact precision. In a sense, quantum computing is a return to the infinite-precision variables from the analog world, with a twist.
Introduction to quantum
Let’s start by remembering the bit: It has two states, on or off, 1 and 0. This bit can be negated into its opposite and operated with other bits with AND and OR. These three operations are enough to build any operation over bits that produce the desired results, e.g. a summation or product.
A quantum computer features a similar building block: the qubit. A qubit is an object that, when observed, can be in two possible states, just like the bit. Those states are named
|1>. The best possible way to show a qubit’s state is by putting coordinates in a unit circle.
Here, we have two qubits. Each axis corresponds to each state a qubit can take, so each qubit has two components. The blue qubit is in the pure state
|0> and the red qubit is in the pure state
|1>. Measuring them will yield that state. Now, things get interesting: before being measured, the qubit can also be somewhere else on the unit circle, in a mixed state (a,b), being both
|1> at the same time. You can see it in the following qubit.
When a qubit is measured, it will stop being in this mixed state and randomly become either
|1>, with the probability rule.
This is also known as Born Rule.
So, in this third qubit, we have a state: (0.5, 0.866…). This means that the probability of observing a
0.5*0.5 = 0.25 and
0.866… * 0.866… = 0.75 of observing a
|1> (remember that 0.25 means 25%). For real numbers, the unit circle maps nicely because we can see Pythagoras theorem directly: probabilities (absolute value of components squared) add up to 1. Note that numbers can be negative and the probability will be the same. Finally, quantum mechanics also allow complex numbers as components. The unit circle can’t easily show complex numbers, but you can see them using a Bloch sphere instead. I won’t show the Bloch sphere or deal with complex numbers in this blog, but you can consult Wikipedia.
Now that we know what’s a qubit, we are ready to deal with quantum algorithms. A digital computer works by manipulating the state of a set of bits; a quantum computer works by manipulating a set of qubits’ states in a way that maximizes the probability of observing a desired output. The way we modify those states is through gates.
Quantum algorithms for IBM’s quantum computer are built using the Composer. Here’s an example:
Each line or wire is a qubit. They all start in the
|0> pure state and you insert operations (also called gates) on that line to modify that state. When you are done, you can either measure the qubit or get a Bloch sphere representation.
Gates are usually their own inverse, otherwise their complex conjugate is (denoted by
†) . This means that you can reverse the state back by putting two in a row.
IBM offers around a dozen basic ones, but we’ll focus on the Hadamard gate, X and CNOT gates here, so you’ll get the hang of it.
The Hadamard gate is a 1-qubit operation. For real numbers, it amounts to a reflection as shown in the following graphic.
Here, (1,0) turns into (0.707… , 0.707…) and (0,1) turns into (0.707… , -0.707…). See that this gate can turn pure states into an equal-probability mixed-states and vice versa. See also that mixed states are also affected.
This gate is usually at the beginning of all qubits in quantum algorithms because it makes every possible measurement equally probable. Many popular quantum algorithms start by doing this. You also use this to test an algorithm, checking that the final states are as likely to happen as you expected.
You can already build a quantum algorithm right now: a quantum coin-flip, virtually impossible to tamper with. Just put in a single qubit a H-gate and measure it.
X, or bit-flip, is another simple gate. It will flip the components for
|1> (exchanging their probabilities). In a unit circle, it would be a reflection like this.
This gate is also useful at the beginning if you want to turn a qubit’s initial pure state of
|1>. That way, you can test the algorithm when it starts in a specific pure state.
Two qubits and CNOT (or Controlled NOT)
Of course, while manipulating single qubits can be of some use, when they start interacting with each other is when great effects appear. A multi-qubit system is nothing to worry about, we just put each qubit in order: the pure state
|01> means measuring a
|0> in the first qubit and a
|1> in the second. Born’s rule still applies, and adding all components squared still add up to one. Finally, states grow exponentially:
- Measuring 1 qubit yields either
- Measuring 2 qubits yields one of 4 different states:
|11>. We represent it with four components, as in (a,b,c,d).
- 3 qubits allow 8 states
- n qubits allow 2 to the power of n states.
We’ll see the simplest, basic two-qubit gate: the Controlled-NOT, or CNOT. One qubit is the control (the one with a dot), and the other is the target (the one with a plus sign).
What this gate does is:
- If the controlling qubit is in the
|0>pure state, nothing happens.
- If the controlling qubit is in the
|1>pure state, the target gate will bit-flip.
- In general, this gate flips the components for
|11>(therefore, swapping the probabilities for those states).
For graduating on the topic, let’s see what happens with this quantum algorithm.
- First, both qubits are
|0>, so the state is (1,0,0,0) and the prob. is 100% that we’d observe
|00>and 0% for the rest.
- After the H-gate, the first qubit has equal probability for each pure state, the state is (0.707…, 0, 0.707…, 0) and the prob. is both 50% for
- After the CNOT, we exchange components, the state is (0.707…, 0, 0, 0.707…) and the probability is both 50% for
|11>. This is also known as the Bell state, and guarantees that we’ll observe two qubits with the same value, even if that value is random.
With (some more) single qubit-operations and this gate, you can achieve any state you want, for any number of qubits. It’s the equivalent to the NOT, AND and OR gates, but in a quantum computer.
A simple, two qubit summation
For closing up this tutorial, we’ll do the equivalent to a two-qubit summation. We’ll have two qubits with our input and two qubits for the output (4 qubits total) and we want to maximize the probability that these transitions occur:
- |0000> ==> |0000>
- |0100> ==> |0101>
- |1000> ==> |1001>
- |1100> ==> |1110>
Q0 and Q1 will be our input, while Q2 and Q3 will be our output (this is just for convenience, as there aren’t input or output qubits). What we need to do now is:
- Put an H-gate at the beginning of the 1st and 2nd qubit to test every possibility at once.
- The 3rd qubit is the result of a sort-of “AND”. We can use a composite gate, the quantum Toffoli gate, to get this result. It contains gates we haven’t seen, but it isn’t required to know what they do to follow this example. You can copy it from the manual.
- The 4th is a sort-of “XOR”. Two CNOTs are all we need for doing that.
Before we write our algorithm, IBM’s quantum computer has a restriction: it can only handle CNOTs with the middle qubit (named Q2) as the target. So, we need to know two more things:
To reverse the direction of a CNOT gate, you can use this trick:
In order to swap states between qubits, you can use this other arrangement:
Now that we know this, here’s the algorithm.
We can simulate it in ideal conditions, which will yield our desired probabilities in equal measure. After that, we can either simulate it in real conditions or run it. These are the results we get for the theoretical simulation.
These are the results for the realistic simulation.
Ouch. At least for the inputs, the expected state at measurement was the most likely, and the expected input/output has the highest values. Even though it’s a simulation, you start to feel the noise. The code is large and there’s a lot of qubits. We’ve reached the end of the road, now. We ran a total of 8192 times this algorithm in the quantum computer and the result, in all its glory, is here:
The expected results are quite interesting. We had a great result for everything but the last case, which failed to even dispute against the rest.
So, what can we do to improve this? First of all, there are quantum error correction/detection algorithms in the manual. We can also rewrite this algorithm using less gates or just three qubits, removing sources of error. RSA can sleep safe, though: we still can’t factorize big numbers without succumbing to noise.
We barely scraped the surface of quantum computing in this tutorial, but I hope you started thinking in quantum states and how these machines operate. I wish you to join me in learning more about this topic and expect to see you sharing your algorithms.