An introduction to Quantum Computing
By this time, most people have heard of quantum computing and how it may change everything we know about computers. The problem is, similarly to other new technologies, it is sometimes introduced as something magical or miraculous, and by trying to exhibit it as something impressive, some basic concepts end up being ignored. So in this post I’ll try to give an introduction to Quantum Computing in a way that, by the end of the read, you will understand the basic concepts of the subject and feel confortable to look further into it.
First of all, let’s look at the “magic” of quantum computers. When talking about classical computers, we say that the information is stored in bits, which can assume the values 0 or 1, in such a way that every number, word and image we see on a computer can be described as a string of zeros and ones. Quantum computers, on the other hand, take advantage of some properties of quantum mechanics to store its information on something called qubits (short for quantum bits). This qubits have some interesting properties, and the most known one is the fact that, besides being able to be in the states 0 or 1 just like a regular bit, it can also assume both values simultaneously. This is called a superposition of this states, and the way it is usually presented is by the fact that, with n qubits, your computer can assume 2^n states at the same time. To put it into perspective, it is believed the visible universe has around 10⁸² atoms, which is around 2²⁷², so, with 272 qubits, it would be possible to have a computer with the number of possible states as large as the number of atoms in the visible universe. However, despite being able to assume all of this values, that does not mean you can see or use all of this possible states at once, so getting 2²⁷² outputs from some function at the same time, and seeing all of the outputs is still not doable. So, before explaining why this magic cannot just happen, let’s start by talking about the qubits themselves.
If you have ever looked at some material about quantum computing, it is likely that you came across a qubit being represented as: |Ψ> = α |0> + β |1>. This is the most common way of describing the state of a qubit, and, as one might guess, the fact that quantum computing is related to quantum mechanics means that a lot of the notation used here comes from physics. The previous representation of a qubit uses something called Dirac Notation (also called Bra-Ket notation). To explain it, I strongly believe it is useful to make an analogy to vectors and linear algebra, specially taking into account that a quantum state is simply a vector into the Hilbert Space, while the vectors you know are usually into the Euclidean Space.
This is called a Ket |Ψ>, and it is analogous to a column vector;
This is a Bra <Ψ|, and it is analogous to a row vector;
This is a Bra-Ket <Ψ|Φ>, and it is analogous to a dot product between two vectors. This operation results in a complex number. An interesting property is that, similarly to a dot product, when the Bra-Ket between two states is equal to 0, this means those states are orthogonal.
And this is a Ket-Bra, also called outer product|Ψ><Φ|. This operation results in a matrix, of which the elements are complex numbers. (Note: A lot of times you will see this operation written as |ΨXΦ|, but that is not an “X”, it is just “><”).
As shown above, a state can be described by a vector, called statevector, and the elements in this vector are complex numbers. This numbers are called amplitudes, and they are related to the probability of getting a certain outcome when measuring the qubits, in a way that the bigger the amplitude, the best are the odds of getting that outcome.
Now imagine you have more than one qubit. To represent the resulting state with both qubits as a single state, you just need to perform a tensor product between the single qubit states. An example can be seen below.
In the example above, it was clear that the state |01> had the biggest amplitude on the state |01>, so it seems like the operation was not really useful. However, when you have superpositions of multiple states, than this notation of multiqubit states is really useful.
With that said, it is time to talk about measurements.
Before introducing actual measurements, I’d like to show some important quantum states.
The reason these states are important is because they are used to form the two most important basis of quantum computing. The definition of a basis is the same as in linear algebra, i.e. a basis is formed by orthogonal states in a way that you can represent every other state as a linear combination of the basis states. In quantum computing, another reason for the relevance of basis is the fact that you must choose in which basis you will make a measurement, so the only possible outcome of a measurement is one of the states that form the basis. The two most important basis you will see are the Z-basis (also called the standard basis or the computational basis), which is formed by the |0> and |1> states (Z = {|0>, |1>}), and the X-basis, formed by the |+> and |-> states (X={|+>, |->}). One quick note here: I just said that every state can be described by a linear combination of the states of a certain basis, so looking back to the example state I showed before (|Ψ> = α |0> + β |1>), it is described as a linear combination of the states |0> and |1>, and if you want to make it sound cooler, you might say that this state is a superposition of the states |0> and |1>. What I mean by this is that a superposition can be understood as a linear combination of possible outcomes.
Going back to measurements, this is the moment the “magic” I presented at the beginning of the post is broken. Let’s suppose you have 270 qubits, and you put all of them in superposition in a way that you have a superposition of 2²⁷⁰ states. With this superposition state, you are able to work with all the possibilities at once, for example, you might use all of those values as input for a given function, and the output of the function would also be the superposition of the 2²⁷⁰ possible outputs. The problem is, despite those outputs existing all at once, at the moment you try to look at them, they will randomly collapse to a single value, so you can’t actually see every possibility. This is the problem with quantum measurement. No matter how many states you have in a superposition, they will always collapse to one when you measure it. So, how is it any useful?
To make it clear, despite the state collapsing to a random state, you are actually able to tell the probability of a measurement collapsing to any given state. Also, you can perform some operations on the circuit in order to maximize some of the amplitudes, so that the result you are looking for is more likely to happen.
In order to not get random results, it is important to know the probabilities of measurements. The probability of getting a certain outcome during a measurement operation is given by the Born’s rule:
Let’s say we are on the basis {|a>, |b>}, then the probability of a state Ψ collapsing to the state |a> is given by:
p(a)=|<a|Ψ>|² ; Notice <a|Ψ> is just a Bra-ket between states|a>and|Ψ>.
also, as we are talking about probabilities, ∑p(i)=1.
An example of a measurement is trying to measure the probabilities of the outcomes of the|+> state onto the Z basis:
To make things easier, most of the time we are measuring onto the Z-basis, so the probability of a certain state is simply the absolute value of it’s amplitude. So, for the example state|Ψ> = α |0> + β |1>, the probability of measuring |0> is p(0)=|α|², and p(1)=|β|². However, it is important to notice that, although we are only able to phisically measure onto the Z-basis, it is possible to mathematically calculate the probability of measurements in every possible basis.
Going back to qubit representations, now that the concept of basis is clear, we can proceed to the representation of a qubit as a bloch sphere. To understand this representation, let’s again look at the state |Ψ> = α |0> + β |1>. By Born’s rule, we know that |α|² + |β|² = 1, so instead of calling it α and β we can call them a sin and cos of a given angle. Also, let’s add a global phase e^iϕ to the sin term. The resulting state is |Ψ> = cos(θ/2) |0> + e^(iϕ) . sin(θ/2)|1>. Before we continue, some things must be made clear. First, the angle θ ∈ [0,π], and ϕ ∈ [0,2π]. Second, you must have noticed the angle is θ/2, not theta. This is because the angles in the bloch sphere are twice as big as in the Hilbert space. With that said, we can use the new state to describe points on a sphere, just like using spherical coordinates with r=1. The state is represented by the point on the sphere where the arrow points to.
As useful as it might be, the bloch sphere is still limited to the representation of single qubits, so the last representation I wanted to show is the Q-sphere, which can describe multiple qubits. This sphere has some points on its surface, and each of this points represent a basis state. So, in each point there is a node, and the size of this node is given by the probability of the measurement collapsing to that basis state. Along with it, each node also has a color representing its phase.
Despite the amount of concepts presented previously, I still have not introduced any use of quantum computing. So, in order to actually do something with it, we must build the so called quantum cirtuits. In fact, the algorithms you will come across are basically some circuits that can manipulate the qubits in a way that the result is some useful information. This circuits are built using a combination of qubits, classical bits (to store the measurements), and quantum gates. This gates are the most important blocks of the circuits, since they are responsible for making changes to existing states, such as creating superposition, entanglement, and other useful operations.
So we should start by talking about quantum gates. Before listing the most important ones, you should know some things about them:
- Quantum gates can be represented as square matrices, and the elements of those matrices are complex numbers.
- Quantum gates are called operators. Given that all of the implementations must follow the laws of physics, every quantum operation must be reversible, so every matrix used to represent a gate is a unitary matrix. Because of this, if you apply the same gate twice consecutively, it will be the same as doing nothing.
- A unitary matrix is a matrix such that its dagger is the same as its inverse. Let’s say we have matrix U, so U_dagger is the transpose conjugate of the matrix U. This means that a transpose operation is applied to the U matrix, and then each element is replaced by its complex conjugate. So, if U_dagger . U =I, “I” being the Identity matrix, then U is unitary. Note, the dagger is represented by a cross, so it would be something like U^+
- Some useful notation: Say you have an operator U, then U^n means that the operator U was applied n consecutive times to the same qubit. U^(⊗n) means the operator U was applied to n qubits at the same point of the circuit.
- To determine the effect of a sequence of multiple gates applied to a qubit, you can simply perform a matrix multiplication of the gates, and the resulting matrix will be applied to the qubit. However, it is important to notice that the sequence of the multiplication is important, so if you have the circuit H — X — Z — Y, then the resulting operator is given by the multiplication YZXH, since the last matrices are added to the left of the multiplication.
Now, to the quantum gates:
- Starting from the most basic one, the I gate (Identity): This gate simply keeps the state unchanged (it does nothing).
- X (not): This gate acts as a classical not, so X|0> = |1> and vice-versa. However, this state can be applied to a superposition of states |0> and |1>, so to understand its general effect, it is nice to look at the bloch sphere. This gate represents a rotation of π of a certain state on the X axis. Similar to this gate, we have the Z gate, which represents a rotationof of π on the Z axis, and the Y gate, which rotates a state by π on the Y axis. This three gates are called the Pauli gates, and are often written as δ_x, δ_y and δ_z. Along with the Identity gate, they form a basis of 2x2 matrices, so any other 2x2 matrix can be written as a combination of them.
- H (Hadamard): This gate is one of the most important gates for the algorithms, since it puts the input state into a superposition.
- CNOT (Controlled not). The controlled not operator is a gate that acts on 2 qubits at a time. We call one of this qubits the “controll” qubit and the other one the “target” qubit. If the controll qubit is in the state |1>, then a not operation is applied to the target qubit. Despite looking like a simple operation, this gate is really important as it allows the creation of entangled states. An entangled state is a state in which both qubits are connected in a way that, if you measure one of them, this measurement affects the measurement of the other qubit. This connection is instantaneous, and it can happen in really long distances.
- CCNOT (Controlled controlled not): Is similar to the CNOT, but it acts on three qubits, 2 controll qubits and one target, and the not is only applied when both controll qubits are in the state |1>.
- Measurement: Collapses a quantum state into a classical state, and saves this state in classical bits. The measurement is realised onto the Z-basis.
Combining these operators, you are able to build a wide range of algorithms, such as an adder circuit, or a circuit for teleporting the information of a quantum state.
The circuit above is a great example of how classical circuits can be implemented with quantum components.
Next I will present the circuit to perform a quantum teleportation, in which you send an unknown quantum state to someone else, by sending only two classical bits. Despite the name though, this is a teleportation of the information, not of the physical qubit itself, and all the information is transported through classical bits, so that means the teleportation follows every law of physics (a bit obvious). That means the transportation is slower than the speed of light, and because of the no-cloning theorem, when you send the information from one place to the other, the original information is destroyed (this is just another way of saying the original state will collapse).
By looking at the circuit above, you might be wondering how does it work, or how did someone come up with this. To figure out this circuits, a great understanding of maths and physics is necessary, and this is the reason you don’t see quantum algorithms being discovered everyday. Another quick note is that many quantum algorithms are not able to be implemented with today’s technology, so their advantages over classical algorithms are not seen in real life yet, but we know they are faster by analysing the complexity of the algorithms.
Now that you know the basics of quantum computing, you should be good to go and start learning some applications and algorithms, such as Grover’s algorithm, Shor’s algorithm and so on. Also, there are a lot of really interesting and slightly more advanced topics you might want to check out, such as the implementation of quantum computers and qubits, error correction, quantum machine learning, etc.
I know that a fraction of the text was dedicated to making quantum computing seem less “magical” and spectacular, but I hope that by showing some of the actual cool stuff quantum computing is able to do, your desire to look further into it just increased.