The computational model behind quantum algorithms
If you are familiar with the topic of quantum computing, you have probably heard about qubits, the basic support of information in quantum computers. The qubit is the core element of quantum computation and its properties are at the root of the efficiency of quantum algorithms to solve specific problems.
In this post we are going to describe how qubits are actually modeled and manipulated in order to design quantum algorithms. When addressing the question of qubit description, there are two distinct approaches : model the qubit as a physical object (e.g an electron, a photon,…) or as an abstract mathematical object provided with specific properties. The main benefit of treating qubits as abstract mathematical objects is that it allows to build a general theory of quantum computation which is totally independent of the underlying physical nature of the qubit. This is especially relevant in the current context where there is no major standard for creating qubits and multiple physical systems with similar properties can be used. It also appears that the agreement over of a standard computational abstract model for the qubit is also of extreme use for the design of quantum algorithms.
One qubit
The transition from classical bits to quantum bits symbolizes a shift from a deterministic to a probabilistic world. As you probably know, the qubit can take values 0 and 1, as can the classical bit, but can also exist in a superposition of those values in variable proportions. The qubit thus appear to be an entity richer in information than the bit and the convention is to model the qubit as a 2-dimensional vector. To do so, we introduce a vector space V along with the following states that form the computational basis of this vector space :
A quantum state can be any linear combination of those two basic states. More precisely, a state |ψ 〉 is represented as :
with α and β complex numbers, meaning we can think of qubits as vectors in a 2-dimensional complex vector space. We say that the state |ψ 〉 is in a superposition of |0 〉 and |1 〉 with amplitudes α and β.
The ‘|〉’ notation for vectors is called the Dirac notation and is the one commonly used as the standard. There are different notations to describe quantum states :
The vector represented with the “bra” notation is called the dual vector of its “ket” equivalent.
In general, a quantum state of n qubits is described by a vector of 2ⁿ complex numbers. Such a state can contain a huge amount of information, yet it is crucial to understand that this information is only available at the quantum level, meaning at atomic and subatomic dimensions. The single act of measuring the quantum state in order to bring the information to a more classical level forces the quantum state to collapse in only one state following a probabilistic model dictated by the different amplitudes. To be more precise, we need to introduce Born’s rule, a fundamental concept of quantum mechanic.
The rule postulates that for a state |ψ 〉 = α |0 〉 + β |1 〉, the output of the measurement will be |0 〉 with probability |α|² and |1 〉 with probability |β|². Putting it differently, the probability of measuring the qubit on a given state is equal to the square of the magnitude of the amplitude at that point.
For any complex number z, the magnitude |z| is computed as :
Born’s rule implies that the sum |α|² + |β|² must always be equal to 1, since probabilities must always add up to 1. That’s for this rule that qubit ’s states are generally normalized.
There is another way to describe the norm of a quantum state : the inner product with itself. We said previously that quantum states are vectors in a complex vector space, but this definition is not as precise as it should be. Actually, quantum states are vectors in a Hilbert space, which is characterized by the same properties as vectors spaces with additionally a definition of an inner product, written 〈φ|ψ〉, respecting some specific properties.
More concretely, the inner product is defined as follows :
In other words, using the inner product it is possible to take any pair of vectors from the Hilbert space and associate them with a well-defined complex number. Based on the definition of the inner product of the Hilbert space, it is possible to define the norm of a vector as the square root of the inner product with its dual vector :
We can check that this definition of the norm gives the same result as the previous formula. Let’s take an example :
So what’s the norm of |ψ 〉 ?
In conclusion, we find as expected that :
Bloch Sphere
The mathematical model of the qubit is commonly embodied by the famous Bloch sphere, which provides a geometric representation of quantum states as vectors spanning from the origin of the sphere to a point on its surface.
Each vector on the Bloch sphere is identified with the value of two angles : θ the angle from the vertical axis Z and φ the angle from the X axis on the equator. Given those two real values, it is possible to write the state :
with
One can see the Bloch sphere as a generalization of the representation of complex numbers with norm 1 on the unit circle in the complex plan. More details and proofs by calculus can be found here.
The quantum state |ψ 〉 is represented on the Bloch sphere with its Bloch vector r⃗, such that |r⃗| = 1 and :
An important property to emphasize is that the value of the angle between the Bloch vector and the Z-axis is twice as big as the same angle in the Hilbert space. This appears when we look at the coordinates of the Bloch vector which is based on the angle θ while the same vector in the Hilbert space is based on the angle θ/2. This property can also be seen by looking at the two vectors of the computational basis |0 〉 and |1 〉 which are orthogonal in the Hilbert space and opposed in the Bloch sphere.
When the qubit is measured, the state collapses to either |0 〉 or | 1 〉, meaning it is projected to the computational basis {|0 〉, |1 〉} : this is called a Z-measurement. It is possible to define the probabilities of measurement of a state |ψ 〉 as follows :
We can illustrate with an example on the following state :
We can measure the probability of measuring |0 〉 as
and the probability of measuring |1 〉 as
When peeking the amplitudes of quantum states in the Bloch sphere, it is possible to notice that the probability of measurement only depends upon the angle θ and not the angle φ. Indeed, with some calculation we find :
If we try to visualize this property, it means that all the states belonging to the same horizontal plan in the Bloch sphere have the same probabilities of measurement. They have the same angle θ but differ by a relative phase φ. The more compelling example to illustrate it is to consider the following states, called |+ 〉 and |- 〉.
For both states, the probability of measuring |0 〉 or |1 〉 is always ½. However the former has amplitude 1/√(2) for the state |1 〉 while the latter has amplitude -1/√(2). We generally say that two amplitudes α and β differ by a relative phase when it exists a real θ such that
Therefore in this example, both amplitudes differ by a relative phase of π. Indeed, using Euler’s formula we find that
Graphically, we see that both states |+ 〉 and |- 〉 belong to the same horizontal plan, which is in this case the equator of the Bloch sphere. A cross section of the sphere on the equator gives :
Basically, a relative phase between |0 〉 and |1 〉 is a rotation around a horizontal cross-section of the Bloch sphere. This property is at the origin of quantum interference.
From a physical point of view, states that differ by a relative phase are different quantum systems evolving in different ways in accordance with the Schrödinger equation. In spite of this difference they appear identical when measured. To put it in one sentence, relative phases have a strong physical meaning, they are at the core of quantum computing.
The term “phase” can also be employed when considering global phases. In contrast to relative phases, global phases are pure mathematical artefacts without any physical meaning. Generally we say that two states |ψ 〉 and |φ 〉 are equal up to a global phase if there exist a real γ such that :
States that are equals up to a global phase γ are the same physical systems. It means that for any value of γ :
Though very powerful and intuitive to represent one qubit, the model of the Bloch sphere remains limited since there is no equivalent to visualize multiple qubits.
Multiple qubits
As we said earlier, a quantum state with n qubits is described by a vector in a 2ⁿ - dimensional complex Hilbert space :
with the constraint on the amplitudes
To describe the state of a quantum system with multiple qubits, it is primordial to introduce the concept of tensor product, noted ⊗. To outline how this operator works, let’s consider an example with two qubits in respective quantum states |ψ 〉 and |φ 〉 :
The overall system is therefore in a state :
With a matrix representation :
More formally, if the first particle is defined by a complex vector space V of dimension n and the second particle is defined by a complex vector space W of dimension m, then the system made of those two particles is represented by a new complex vector space V ⊗ W of dimension m × n.
Coming back to the example, it is possible to notice that the state |ψ 〉 ⊗|φ 〉 respects the property :
However this property may not be respected by some special quantum states. For instance, consider the state :
It stands clearly that the above states cannot be split into two independent 1-particle states since the previous condition is not respected. This state is one of the four Bell states which are the simplest states to highlight the following property :
A quantum state of multiple particles is entangled if it cannot be described as the tensor product of the state of each particle.
Bell states are known to be maximally entangled.
It is interesting to point out the fact that the measurement of a quantum system with more than one particle can be carried out on a subset of the qubits. In the case where the number of qubits is 2, if we measure the first qubit alone, the overall quantum states collapses to a superposition of all the different states where the first qubit has the measured value. In the previous state |ψ 〉 ⊗|φ 〉, the measuring of the first qubit alone gives |0 〉 with probability |α|² + |β|² and |1 〉 with probability |γ|² + |δ|². In both cases, the quantum state left after the measurement must be re-normalized to ensure that the constraint on the amplitudes remains respected. Indeed, if the first qubit is measured |0 〉, the the post measurement state is
It works the same way if the first qubit is measured |1 〉.
When applying this property on the Bell states, it gives place to interesting insights about how quantum mechanic works. Considering any of the Bell states described above, measuring the first qubit allows one to “guess” the value of the second qubit with certainty. Considering for example the state |Φ⁺〉, the measurement of the first qubit gives either |0 〉 (leaving the state in |00 〉) or |1 〉 (leaving the state in |11 〉) with the same probability ½. In this position, the second qubit always takes the same value as the first one, the outcomes of the two measurements are therefore correlated.
These correlations that we can observe in quantum computation are stronger than any one that could exist in classical computation and give an edge to quantum computers that make the most of those properties.
Quantum gates
So far, we have talked about how qubits are depicted and the impact of measurement. Now we shift our focus to the other way of interacting with a qubit which is by by transforming it . A transformation aims at modifying the values of the amplitudes α and β keeping the constraint |α|² + |β|² = 1. Those modifications are possible with quantum gates.
From a mathematical point of view, quantum gates are matrices. To be more precise, those matrices have to be unitary in order to preserve the normalization condition. We say that a matrix U is unitary if :
Unitary matrices have the property of preserving the norm of the quantum state they are applied to. Does this mean that any unitary matrix is a valid quantum gate ? Yes, exactly. However, there are still some common gates at disposal when we start building quantum circuits, some are applied to single qubits while other combine multiple qubits. The most basic single qubit gate is the NOT gate. In a classical model, the NOT gate basically inverts the value of the input bit, 0 becomes 1 and vice versa. The question is now how to adapt this definition to qubits. The point is that a definition that maps |0 〉 to |1 〉 and |1 〉 to |0 〉 is insufficient since it does not tell us how to apply the gate to states in superposition. In practice, the NOT gate is represented by a matrix X which interchanges amplitudes of the state.
In top of the NOT gate, there are other major one-qubit gates :
- The Hadamard gate : this gate turns |0 〉 to |+ 〉 and |1 〉 to |- 〉. It is used to create an equal superposition of |0 〉 and |1 〉. This operation is embodied by the matrix :
Please note that applying the Hadamard gate twice on the same qubit has no effect since
- The Z gate : The Z gate just flips the sign of |1 〉 and leaves |0 〉 unchanged.
Remember when we spoke about relative phases, we mentioned that states |+ 〉 and |- 〉 differ by a relative phase of π. Performing this transformation is the role of the Z gate.
- Phase shift gate : This is a generalization of the Z gate. This time the angle of rotation is not fixed to π but can take any real value θ.
In the category multiple-qubits gates , I just want to talk about the CNOT gate. You may know that in classical computation, any gate (AND, OR, XOR, …) can be re-written as a composition of NAND gates. In classical circuits the NAND is the universal gate. The quantum counterpart of the NAND is the CNOT. It takes two qubits as input and flips the value of the second (the target) only if the first (the control) has value |1 〉. Overall the CNOT transformation is
and its matrix representation is
Some other resources
- The book “Quantum Computation and Quantum Information”, from Chuang and Nielsen
- Lectures from Scott AAronson : https://www.scottaaronson.com/qclec/
- The online Qiskit course from IBM, “Introduction to Quantum computing and Quantum hardware” : https://www.youtube.com/playlist?list=PLOFEBzvs-VvrXTMy5Y2IqmSaUjfnhvBHR
