How does a Quantum Computer work?

This is the third post in a series on quantum computing, which began with the following:

By design, a quantum computer is a device that executes quantum computations. These quantum computations utilize quantum mechanical principles to encode and operate on inputs and outputs. There are two main types of quantum computers based on the data unit: discrete-based and continuous-based. Discrete-based quantum computers use a discrete unit of data with quantum properties; most use qubits on which operations are performed. In contrast, continuous-based quantum computers utilize observable quantities with continuous intervals to define the system’s state. We will focus on discrete/digital quantum systems as this is the most common model for which many algorithms have already been developed.

4-qubit Quantum Chip – Credit: Wikimedia

Like classical computers, the qubits in a quantum computer make up the memory on which computations are performed, but the similarities end there. For starters, data does not move between qubits as quantum states cannot be copied, so you can either change the state of a qubit or measure it. Furthermore, any operation on the quantum computer must preserve unitarity. In other words, no operation can destroy the quantum state of a qubit, so if there are three-qubit states as input, there will always be exactly three-qubit states as output.

Two actions can occur in a quantum computer: 1) an operation on a qubit or qubits according to some rule, or 2) a measurement. As before, a measurement destroys the superposition of a quantum state and makes it take a value. Meanwhile, operations on qubits can put them into superposition or entangle other qubits. We can encode and mutate data in a quantum computer with these operations.

The quantum state of a quantum computer

To understand these quantum operations in a quantum computer, let’s understand how these operations can work. Mathematically, we represent the quantum computer’s memory by its state, which is given by the joint state of all its qubits. Given the states of each qubit, we compute the tensor among all the qubit states to obtain the global state of the quantum computer,

$|\Psi\rangle = |\psi_1\rangle \otimes |\psi_2\rangle \otimes \dots \otimes |\psi_n\rangle$

The tensor intertwines all possible states in which the qubits might be, expressing the quantum computer’s state.

$|\Psi\rangle = |\psi_1\rangle \otimes |\psi_2\rangle$

Expanding this expression, we obtain:

Computationally, it is better to write it in vector form:

$|\Psi\rangle = \begin{bmatrix}ac\\ad\\bc\\bd\end{bmatrix}$

Notice that the global state contains a part of each possible classical combination of each qubit. Setting the first qubit to be in state $|0\rangle$ and the second to be in state $|1\rangle$ , is equivalent to setting $a=1,b=0,c=0,d=1$ which produces the global state $|\Psi\rangle = |01\rangle = \begin{bmatrix} 0\\1\\0\\0\end{bmatrix}$ which is what we expect.

As we add more qubits, we tensor the basis vectors to obtain the global state:

$= \begin{bmatrix} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h\end{bmatrix}$

Entanglement

One of the important things about the global state is that it can be obtained from the individual qubit states, but is this also true the other way around? Can we obtain the individual qubit states from the global state of the quantum computer?

Surprisingly, the answer is not always. Writing a specific tensor state that cannot be factored into tensors of individual states is possible.

For example, for a two-qubit quantum computer, the state $|\Psi\rangle = \frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ cannot be written as the product of single-qubit states $|\psi_1\rangle \otimes |\psi_2\rangle$ . For this simple example, you can prove it by using the previous expression from the tensor of two-qubit states: you must have two cross-terms that must be zero, which is only possible if two coefficients are zero, but then the other cross-terms will also be zero.

This strange phenomenon is called entanglement. To produce entanglement we require qubits to interact. These interactions between qubits must result from some kind of operation in the Quantum Computer, which is what Quantum gates do.

Quantum Gates as means of operations

Just as gates execute bit operations in classical computers, in quantum computers, gates are an abstract way to represent operations on qubits without their physical implementation. While fundamental classical gates execute classical boolean logic, quantum gates expand on that boolean logic.

Single Qubit Gates

The simplest gates are single qubit gates; the standard ones are the Identity, Pauli- $X$ , Pauli- $Y$ , Pauli- $Z$ , and $H$ /Hadamard gate. To understand what they do, we can take advantage of our mathematical representation: the equivalent of operations for vectors are matrices, so these gates can be represented as follows:

$I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$

$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$

$Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}$

$Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$

$H = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$

The Pauli- $X$ gate, also known as the NOT gate, is a rotation around the $x$ -axis by $\pi$ radians. It flips the qubit from its initial state to its opposite state, changing the probability amplitudes of $|0\rangle$ and $|1\rangle$ . Trivially, it changes a state $|0\rangle$ to $|1\rangle$ and vice-versa. However, it has a more interesting application: exchanging the probability amplitudes. For example, if you had the state $|\psi\rangle = 0.8|0\rangle + 0.6|1\rangle$ and applied the $X$ gate you would obtain:

$X|\psi\rangle = 0.6|0\rangle + 0.8|1\rangle$

This results in a state that not only has exchanged probability amplitudes, but also probabilities for measurement. Initially, there was $|0.6|^2=0.36$ for measuring $|0\rangle$ ; after applying the $X$ -gate it became $|0.6|^2=0.64$ .

The Pauli- $Y$ gate and Pauli- $Z$ gate represent rotations around the $y$ -axis, and $z$ -axis by $\pi$ radians, respectively. These two gates are less commonly used, but they represent a phase rotation (for the $Y$ there is also a flip). There is also a Phase gate whose unique purpose is causing a phase shift. Essentially, a phase shift is changing the value of the probability amplitude without changing the probability of the state. For example, when calculating the norm squared of $1, -1, i, -i$ all produce 1.

The Hadamard gate is a more interesting gate, it is a combination of rotations that places the state in another state of equal superposition. This effect can be clearly seen when applied to the basis states $|0\rangle$ and $|1\rangle$ :

$H|0\rangle = \frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} |1\rangle$

$H|1\rangle = \frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle$

In both cases, the resulting state becomes a combination of two states which have an equal probability of being measured. This becomes extremely important to take advantage of the quantum properties and, as we will see, of entanglement.

Finally, the identity gate does the same as the identity matrix, it leaves the state intact. We mention it here for the sake of completeness.

Something to note is that these gates are Unitary which means that they preserve the length of our vector. This is extremely important because quantum information cannot be destroyed. Furthermore, this also makes sense as we want to preserve the property that the probability can always be obtained from the probability amplitudes. In fact, all quantum gates are unitary. Unitary gates satisfy

$UU^\dag = I$

Where $\dag$ represents the complex conjugate of the transpose of a matrix.

The other interesting thing to note is that all these gates are also Hermitian, that is, when applied twice in a row they are equivalent to an identity matrix, so they return the state to its original value. This is not true for most gates, but it is a useful property to have. Hermitian gates satisfy:

$U=U^\dag$

Multi-Qubit Gates

All the previous gates only act on a single qubit, therefore, there is no interaction between qubits. However, we require interaction between the information of qubits to do complex logic. This is where we introduce multi-qubit gates. These gates execute an operation on two or more gates.

The most useful qubit gate is the Controlled-NOT gate, also known as the CNOT or CX gate. This gate executes an X gate operation on a target qubit if the control qubit is in the $|1\rangle$ , else it leaves the state unchanged. The control part of the gate work just like an if statement which most of the useful multiple qubit gates take advantage of to make qubits interact. This gate for a 2 qubit matrix with the control qubit being the first can be represented by the matrix:

$CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix}$

This truth table represents the behavior of this gate for each of the basis gates:

|\psi_1\rangle \otimes |\psi_2\rangle — “Truth Table” for a CNOT gate

CX |\psi_1\rangle \otimes |\psi_2\rangle — “Truth Table” for a CNOT gate

As you can see the control qubit is not modified, while the target qubit only changes when the control qubit is $|1\rangle$ .

With this gate, we can make qubits change in terms of the states of others. In fact, if we combine it with the Hadamard gate we can produce entanglement. The demo for entanglement works as follows:

Take 2 qubits in the $|0\rangle$ state and apply a Hadamard gate to one of them, this qubit will be the control qubit. What happens is that the Hadamard gate puts the target qubit into superposition, meanwhile, the other qubit stays the same. The change of the quantum computer’s state is the following:

$(H\otimes I)(|0\rangle \otimes |0\rangle) = \frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 & 1 & 1\\1 & 1 & 1 & 1\\ 1 & 1 & -1 & -1\\ 1 & 1 & -1 & -1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0\end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix}1 \\ 0 \\ 1 \\ 0\end{bmatrix}$

$= \frac{1}{\sqrt{2}} |0\rangle \otimes |0\rangle + \frac{1}{\sqrt{2}} |1\rangle \otimes |0\rangle$

Next apply a CNOT gate to the circuit. This results in the state:

$CNOT (\frac{1}{\sqrt{2}} |0\rangle \otimes |0\rangle + \frac{1}{\sqrt{2}} |1\rangle \otimes |0\rangle) = \begin{bmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}\frac{1}{\sqrt{2}} \\ 0 \\ \frac{1}{\sqrt{2}} \\ 0\end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix}1 \\ 0 \\ 0 \\ 1\end{bmatrix}$

$= \frac{1}{\sqrt{2}}|0\rangle \otimes |0\rangle + \frac{1}{\sqrt{2}} |1\rangle \otimes |1\rangle$

Measure the qubits: from the resulting state $\frac{1}{\sqrt{2}} |0\rangle \otimes |0\rangle + \frac{1}{\sqrt{2}} |1\rangle \otimes |1\rangle$ , there is 50% to measure $|00\rangle$ and 50% to measure $|11\rangle$ , while all other states have 0% of being measured. If you know the output of the first qubit, you know the value of the second qubit.

By applying the CNOT gate we basically execute an if statement with the control qubit as the argument; however, this control qubit has two possible states as it is in superposition. Because applying this gate does not measure the control qubit, the operation must be somehow done through both possibilities: one for which the control qubit is $|0\rangle$ which does not execute a NOT gate, and one for that is $|1\rangle$ which does execute the NOT gate. If the CNOT gate is applied, the target qubit will change from $|0\rangle$ to $|1\rangle$ . We know that for this arrangement then the only possible states are $|0\rangle \otimes |0\rangle$ and $|1\rangle \otimes |1\rangle$ as these are logically tied to each other. These states are entangled. Then, if we measure one of the qubits, we know what the other must be because of this logical connection.

If we measure the result of this experiment, we would get $|00\rangle$ and $|11\rangle$ each one with 50% chance. We just need one to know the other as we know there are no other possible combinations. This arrangement is called maximal entanglement as the measurement of one qubit gives us 100% certainty of the state of the other. The TL;DR is the Hadamard gate that provides multiple states while the CNOT gate forces the states to be logically linked. You can see how this experiment would be represented as Quantum Circuit.

Another useful control gate is the Controlled-Phase gate also known as the CPHASE. Just like the CNOT, it applies the operation of a phase rotation depending on the control qubit. It is mainly used in the Quantum Fourier Transform which we will discuss later.

With these two-qubit gates, it is possible to create other controlled gates such as the Controlled-Z, Controlled-Y, and Controlled-Hadamard gates. Apart from controlled gates, a SWAP gate is another result of combining fundamental two-qubit gates. Just as its name states, its purpose is to swap the state of two qubits. This is an essential operation to transfer data as the Quantum States cannot be copied. This fact is called the No-Cloning Theorem and hinders our ability to work with multiple copies of the same data, the best we can do is move the data of a qubit around by swapping their states.

Finally, we can combine everything to produce even bigger gates operating on many more qubits to produce complex quantum circuits.

Quantum Algorithms

To take full advantage of quantum computing and quantum circuits, we need to develop specific arrangements tailored to quantum properties to achieve the theoretical exponential speedup. For this reason, just like Classical Computers, people have developed Quantum Algorithms which execute specific tasks very efficiently. Unlike classical algorithms, the efficiency of quantum algorithms comes from the number of gates being used. Designing new algorithms is still a broad open research area, therefore, they are categorized depending on their purpose. Some of these are:

Quantum Fourier Transform-based Algorithms: these types of algorithms use the Quantum Fourier Transform algorithm and phase rotations to execute many tasks. Its use case is very broad, so we will expand a little bit on the Quantum Fourier Transform and its derivatives, as it is an essential algorithm in Quantum Computer that is easy to grasp.
Quantum Search Algorithms: these are used to search large databases more efficiently than classical algorithms. Generally, they can achieve this in $O(\sqrt{n})$ time. Among them, there is Grover’s algorithm which marks the state associated through an oracle and amplifies for measurement, and Quantum Counting which given an oracle, it tells you the numbers of states that satisfy the search constraints.

Optimization Algorithms: they are used to find the best solution to a problem from a large number of possible solutions, such as finding the optimal route for a delivery truck or optimizing the allocation of resources in a supply chain. Another use case for it is solving linear systems of equations and determining the ground state energy of a physical system. Some of these are the Variational Quantum Eigensolver (VQE), the Variational Quantum Linear Solver (VQLS), and the Quantum Approximate Optimization Algorithm (QAOA).
Quantum Simulation: they are designed to simulate complex quantum systems, such as molecules and materials, to enable the development of new drugs and materials. These algorithms have applications in fields such as quantum chemistry, where they can simulate complex molecules and materials; and in quantum physics, where complicated systems of quantum particles with complicated interactions are needed to be tested, for example, analyzing the behavior that Quantum Field Theory predicts for two particles.

Quantum Fourier Transform Algorithms

The Quantum Fourier Transform (QFT) is the equivalent of the quantum operation of a discrete Fourier transform, it changes the data representation from the computational basis to the Fourier basis. This is especially useful in a quantum computer as almost all operations are rotations on the qubit. For this reason, it is among the most used algorithms applied across different applications. Compared to the Fast Fourier Transform that has time complexity $O(N log N)$ , the QFT has $O(log N)$

Some of these applications are

Quantum Phase Estimation algorithm: approximates the eigenvalue of a unitary operator. This algorithm uses the inverse Quantum Fourier Transform (written as QFT $\dagger$ )
Period Finding: finds a multiple of the period for a generating function.

Shor’s factoring algorithm, arguably the most well-known quantum algorithm, also utilizes the power of the QFT. Shor’s algorithm is a quantum algorithm that solves the discrete logarithm ( $a^{sx_1 + x_2} \text{ mod } N = 1$ ) which allows integer factorization in polynomial time. Having the capability to execute this algorithm would have repercussions in the cryptographic system implemented on the internet (like RSA) opening the possibility of cryptographic attacks. However, to achieve this, current implementations require quantum computers that would at least contain tens of thousands of qubits to achieve it in a reasonable time scale, and even then, these would need to be highly accurate qubits (on the order of $1\times 10^{-12}$ error rate for each qubit of a quantum computer of around 10000 qubits).

While understanding how the Quantum Fourier Transform works is a much more complex topic that will require more than what we have explained so far, we can see visually what it essentially does. The Qiskit Textbook touches upon QFT in-depth and has the following comparison of the computational basis and Fourier basis:

Computational Basis Representation – Qiskit Textbook

Fourier Basis Representation – Qiskit Textbook

You can see here that while in the computational basis, a single state is a definite combination of $|0\rangle \text{ and } |1\rangle$ of each qubit, in the Fourier basis the state of the quantum computer is represented by different phase rotations of each qubit.

If you wish to know more about the logic involved in these algorithms, you can check the references for more information. I recommend looking at the Quantum Computation and Quantum Information book for the more theoretically invested first, and then looking at the Qiskit Textbook for implementation details.

Conclusion

Throughout this post, we delved deeper into the mathematical representation of the workings of a quantum computer and discussed combining multiple qubits and modifying them through gates to achieve a specific task. In addition, we touched upon the most important part of the philosophy of Quantum Computers which is the Quantum Algorithm, mentioned some of the most commonly used algorithms and their applications, and focused our attention on the Quantum Fourier Transform as a multi-purpose algorithm. Next time we will address the general idea of how these algorithms actually result in an exponential speedup in some applications, how they can be tested, and discuss what is the status quo of these applications in the real world.

References

Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667

A Modern Approach to Quantum Mechanics, John S. Townsend

Quantum Computer Transmon Chip Image. Wikimedia. By Jay M. Gambetta, Jerry M. Chow & Matthias Steffen – https://www.nature.com/articles/s41534-016-0004-0, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=61462110

Conservation of Quantum Information and the No-Hiding Theorem: Jharana Rani Samal, et al. “Experimental Test of the Quantum No-Hiding Theorem.” Physical Review Letters. 106, 080401 (2011). DOI: 10.1103/PhysRevLett.106.080401

Conservation of Quantum Information and the No-Hiding Theorem:

Jharana Rani Samal, et al. “Experimental Test of the Quantum No-Hiding Theorem.” Physical Review Letters. 106, 080401 (2011). DOI: 10.1103/PhysRevLett.106.080401

No Cloning Theorem: ”What is the no-cloning theorem in Quantum Computing?”. Ifrah Dar. Educative. (2023). https://www.educative.io/answers/what-is-the-no-cloning-theorem-in-quantum-computing

Quantum Attacks. Dan Goodin. Ars Technica. (2023). https://arstechnica.com/information-technology/2023/01/fear-not-rsa-encryption-wont-fall-to-quantum-computing-anytime-soon/#:~:text=Fujitsu%20researchers%2C%20the%20press%20release,would%20require%20about%20104%20days.

Qiskit Textbook. IBM & Jupyter Book Community.

https://qiskit.org/textbook/ch-gates/multiple-qubits-entangled-states.html

https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html

ArrayFire Quantum Simulator. https://github.com/arrayfire/afQuantumSim