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 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 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$ , the 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 has exchanged probability amplitudes and probabilities for measurement. Initially, the probability for measuring $|0\rangle$ was $|0.6|^2=0.36$ ; after applying the $X$ -gate it became $|0.8|^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 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. A phase shift changes the probability amplitude value without changing the state’s probability. For example, calculating the norm squared of $1, -1, i, -i$ produces 1.

The Hadamard gate is more interesting; it combines rotations that place the state in another state of equal superposition. This effect can be 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 with 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, meaning they preserve our vector’s length. 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. All quantum gates are unitary. Unitary gates satisfy

$UU^\dag = I$

Where $\dag$ , called dagger, represents the complex conjugate of the transpose of a matrix: $U^\dag = (U^T)^*$ .

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

$U=U^\dag$

The interesting thing about the Hermitian gates is that applying the same gate twice returns leaves the state unchanged. Examples of these are the X, Y, Z, and H gates which are Hermitian.

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, the CNOT, or the 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 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. 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 in 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 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, 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 will get $|00\rangle$ and $|11\rangle$ each with a 50% chance. We need one to know the other, as 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, the CPHASE. 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 essential 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 must 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 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 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 is Grover’s algorithm, which marks the state associated through an oracle and amplifies for measurement, and Quantum Counting, which, given an oracle, tells you the number of states that satisfy the search constraints.

Optimization Algorithms: they are used to find the best solution to a problem from many 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 requiring more than we have explained, we can see visually what it 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, then 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. We discussed combining and modifying multiple qubits 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 result in an exponential speedup in some applications, how they can be tested, and discuss 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