The Quantum Series
Part II — Achieving quantum speedup
In our first article, we walked through the history of quantum physics and provided and intuition for the main postulates behind this theory. We also introduced a mathematical framework that allows us to represent bits and logic gates through vectors and matrices.
In this article, we’ll apply these tools to a new unit of information: the qubit. As we start performing operations on qubits through quantum gates, we’ll discover ways in which we can use quantum properties to our advantage.
Quantum computing
The idea of a quantum computer was first introduced by Richard Feynman, who envisioned the possibility of using quantum properties such as superposition and entanglement in order to perform computations with an outstanding speed. The idea behind this is that should we have a set of particles in a superposition of states, we could perform transformations (computations) over those particles simultaneously over every state, since they are in superposition, so that we can finally measure and collapse these to the state we are looking for. In other words, using the laws of physics as our computer.
We’ll come back to this concept later on. For the time being, we’ll take baby steps towards the goal of performing quantum computations.
The qubit
In the previous article we defined a traditional bit as a unit of information that can have two possible values: 0 or 1. In quantum computers, we’ll define a new unit of information, the qubit, which can be in any superposition of these two states. As predicted by the Copenhagen interpretation, once we measure this qubit it will collapse either to the zero or to the one state.
Please note that, in consequence, classical bits are a particular case of qubits in which there is no superposition of states 0 and 1, so we can safely conclude two things:
- Quantum computers can perform, at least, the same computations as classical computers.
- In order to take advantage of quantum computing, we need to use qubits in a superposition of states. Otherwise it makes no sense to go quantum.
We’ll formally define a qubit as vector:
The qubit ψ from this definition is in a superposition of states zero and one, which is represented by amplitudes a and b, which are complex numbers. For the purposes of this series, we’ll make all examples using real numbers only. However, it is important to know that we have another dimension at our disposition (the imaginary axis).
The probability that our qubit ψ will collapse to states zero or one upon measurement is given by:
Since, as we stated, a qubit can only collapse to any of these two possible states, the sum of these two probabilities must add up to one. This is important because one could tend to think that the use of qubits will speed up communications by allowing us to transfer information from one point to the other in a superposition of states. Since a and b are complex numbers, they would be enough to encode any amount of information we need to transfer within a single qubit. This is, of course, wrong, since there is no way to determine the values of a and b once we receive the qubit. We can only measure it and get one of two possible values, zero or one, same as with classical bits.
Using Dirac notation, the previous definition of a qubit can also be represented as:
Some examples of valid qubits are:
These both have a probability of 1 of collapsing to their corresponding state.
Both these qubits have a 50/50 probability of collapsing to 0 or to 1. Hence, it is possible to have two qubits with different amplitudes and equivalent probabilities (this property will be used later on).
Quantum gates
As with the case of the classical logic gates we used in part I, we’ll represent quantum gates as matrices that can be applied to qubits through traditional matrix multiplication. All gates we defined previously (identity, negation, set 0, set 1, OR, CNot) could be applied to qubits yielding valid qubits as a result.
However, there is a caveat: quantum gates must be reversible. In other words, given the output of a gate, we need to be able to determine the input that generated it. This means that, from our previous list, identity, negation and CNot are valid quantum gates, while set 0, set 1 and OR aren’t valid quantum gates.
This is a restriction of quantum physics that can be understood through the following intuition: If we are computing over a superposition of states, it is as to say that we’re trying all states at once. If one of those computations were not reversible, it wouldn’t be possible to perform it without affecting the other possible results, hence providing an invalid state.
Another, more mathematical way of seeing this, is that all quantum gates must be represented by unitary matrices. These are matrices that satisfy this property:
In other words, the conjugate transpose of the matrix is the inverse of the matrix itself. The reason behind this is that unitary matrices are the only matrices that can keep the magnitude of all vectors after being applied to these. This is imperative, because we need all qubits to have a magnitude of 1, otherwise they wouldn’t satisfy the definition we stated earlier that they must either collapse to 0 or 1 with probability 1. Quantum gates must be unitary in order to take valid qubits as an input and produce valid qubits as an output.
There is a third, much more complex explanation behind this that has to do with entropy and its relation to time (entropy is sometimes called the “arrow of time”). Since non-reversible gates produce an increase in entropy, this would imply the system moved forward in a direction of time that cannot maintain the previous quantum superposition state.
Whatever explanation suits the reader better, the fact is that quantum gates need to be reversible in order to produce valid qubits.
The Hadamard gate
Let’s introduce our first purely quantum gate, the Hadamard gate:
If we apply this gate to the 0 and 1 qubits, we get:
As we can see, the Hadamard gate takes the zero or one qubits and transform them into the uniform superposition of both states. It can be seen as the “flip a coin” gate.
Note that the output of the Hadamard gate applied to qubit one, while having the same probability of collapsing to the zero or one states, is different from the one corresponding to the zero state since the amplitude of the second component is negated. This is necessary for the gate to be valid. Otherwise, if they both yielded the same qubit as a result, it wouldn’t be a reversible gate.
If we were to apply the Hadamard gate to our output qubits again, it can be easily seen that we would get our input qubits as a result (this matrix is its own inverse). Hence, we can apply it once to get into uniform superposition and then apply it again to get back to non-superposed states.
As we stated at the beginning of this article, it doesn’t make sense to use a quantum computer, if we’re not using qubits in a superposition of states. Otherwise, we’ll find no gain compared to classical computing. Hence, the Hadamard gate will play a very important role in our computations since it allows us to put our qubits in a uniform superposition before starting to operate on them.
I hope with this the reader can start to unveil the potential of quantum computing. Suppose we have two qubits in state zero as an input and apply a Hadamard gate to both of them. Both qubits are now in a uniform superposition of states zero and one. This means that they are in all states 00, 01, 10 and 11 simultaneously with a probability of one quarter of collapsing to each of these combinations upon measurement. When we perform calculations on these qubits, we are doing so on the four states at once.
If instead of two, we had three qubits, the uniform superposition would yield eight possible states upon measurement: 000, 001, 010, 011, 100, 101, 110 and 111. We would be making calculations on all 8 possible states at once.
In general, if we had n qubits in the uniform superposition, we would be calculating on 2 to the power of n possible states. This is the real breakthrough of quantum computing, the sought “quantum speedup”, and later on we’ll see how we can use this to perform calculations on all states at once, producing the result we’re looking for through quantum algorithms.
Finally, as we can see, quantum computers aren’t merely faster computers that we approach in the same way we do classical computers. They are a new kind of computer that uses a different computational model. In order to take advantage of quantum computers, we need to rethink our programs in a way that can make the most out of qubits and quantum gates.
Universal logic gates
In classical computing, universal logic gates are those gates that can be used in order to compose any other possible gates. They are the basic building blocks that can be put together to build additional gates.
It can be shown that the NAND and NOR gate are both universal in classical computing. By connecting NAND gates in different ways, we’re able to produce AND, OR, NOR, XOR, NOT, and all other logic gates. The same applies for the NOR gate.
Another gate that is also universal in classical computing is the Toffoli gate (or CCNot gate). This is a CNot gate as the one we introduced in the first article that has two control bits instead of one. Despite not being a very popular gate in classical computing, this gate satisfies a very important property in the quantum world: apart from being universal, it is reversible (unlike the NAND and NOR gates).
The Toffoli gate by itself is not universal in quantum computing, since it cannot switch non-superposed input qubits into a superposed output. This can be done by combining the Toffoli gate together with the Hadamard gate, hence achieving a universal set of quantum gates.
Quantum algorithms
By combining qubits and the quantum gates we have previously defined in order, we can start to produce quantum algorithms: quantum computer programs that allow us to solve specific problems.
We’ll introduce one quantum algorithm that takes advantage of superposition in order to gain a quantum speedup over classical computing on a very simple problem.
The Deutsch oracle
Let’s suppose we are given a black box that we know performs one of the four possible one-bit operations: Set 0, Set 1, Identity or Negation.
Hoy many measurements do we need to make in order to determine which operation the black box performs in classical computing? The answer is 2, we measure the outputs with zero and one and follow the table:
What if we were working with a quantum computer? How many measurements do we need to make? Sadly, the answer is still two. This is easy to understand, because it is an information theory, not quantum theory problem. If there is only one measurement, then we have one output qubit to determine one of four possible states. However, as we stated earlier, a qubit when measured can collapse to either state 0 or state 1, implying that with only one qubit we can only identify two possible answers, not four. Hence, we still need two measurements in order to identify the operation.
Now let’s change the question and try to identify if the black box yields a constant result (set 0 or set 1) or variable result (identity or negation). In other words, we’ll determine whether the input influences the output. In classical computing, it would still take two measurements in order to determine this, as shown in the following table after one measurement:
In quantum computing, however, we can do this with only one measurement. But first, we need to modify our set 0 and set 1 gates so that they become reversible, yielding valid quantum logic gates. One simple hack that allows us to do this, is by placing an additional output qubit that is wired to the input qubit.
The following diagrams illustrate how our black box is modified adding the input and output qubit:
As we can see in the diagram, after the modification we have:
- An input qubit that is kept in one output.
- An input qubit that always starts with state zero and is set to the result of the operation in the second output.
Since we have the input qubit in the output, we can, given an output, reverse the gate in order to tell what its input was.
Now that we have a generic reversible black box for our four operations, let’s see what each of these would look like internally.
Set 0
The set 0 gate consists just of two wires. Whatever the input, the output will be set to zero, while keeping the input in the second output.
Set 1
The set 1 gate is just like the set 0 gate, only it negates the output with the X (Not) gate.
Identity
Here we’re using the CNot gate we introduced in the previous post. In the representation shown above, the input (solid circle) is the control bit, while de output is the target bit. If the input is set to zero, the target bit is unaffected, yielding a zero on the output. If the input is set to one, the target bit is negated, yielding a one on the output, hence producing the identity gate.
Negation
Finally, the negation gate is produced by negating the output on the identity gate.
Proposed circuit
Now that we have identified the four possible gates our black box could have, we’ll design a circuit that will allow us to solve the Deutsch oracle problem in only one measurement. We’ll then do the maths behind this circuit and show this to be true.
Basically, our algorithm has the following steps:
- Apply a not gate followed by a Hadamard gate to our inputs.
- Perform the black box computation.
- Apply a Hadamard gate to our outputs.
- Measure the value of the outputs.
If the black box were the set 0 gate, the result would be the following:
In the case of the set 1 gate, the result would be:
The identity gate produces:
Finally, the not gate produces:
As we could prove in our previous calculations, whenever we have a constant operation, the result of our algorithm will be |11> and whenever we have a variable operation, the result will be |01>.
Therefore, by just looking at the first output bit after one measurement we can tell whether the black box operation is constant or variable.
Wrapping up
We did it! We have designed our first quantum algorithm that provides a quantum speedup over classical computing. In this case, the efficiency gain may not seem that important, but quantum algorithms can build upon each other to produce significant performance gains, as will be the case with this one.
The Deutsch-Jozsa algorithm is a generalization of this basic case, which allows us to determine if our black box function produces a constant or balanced output when given a size n input. In a classical approach, it would take one plus two to the power of n-1 (half plus one possible values) evaluations in order to determine if the function output is constant or balanced.
However, in the quantum approach, we can do it with a single evaluation, hence producing an exponential speedup!
In the following posts, we’ll introduce the entanglement of qubits and how quantum teleportation can be produced. We’ll also see further quantum algorithms that are both more complex and interesting (because of their practical applications) than the Deutsch oracle, provide some examples in code and wrap up with the state of the art and practical applications of quantum computing.
Email us at us@urudata.com for any comments or questions!
Our purpose in Urudata Software is making our customers more efficient through technology.
We develop BPM (Workflow) and Document Management solutions and implement these with our experienced team, which analyzes our customers’ business processes looking for efficiency gains and automation opportunities. These projects allow for the generation of cost efficiencies, improved quality and predictability, better customer experience and availability of data for analytics.
