←Return to chapter

2.1. Foundations of quantum computing

The most widespread computational model in quantum computing – and arguably its simplest – is built on the qubit abstraction. As its name suggests, it is the quantum analogue of the classical bit, i.e., a value that can take the values 0 or 1.

We will stick to our promise of not delving into the details of the physical realisations of qubits in real-world architectures. Nonetheless, it is important to note one fundamental difference with classical systems. Classical bit values (the famous 0s and 1s of our computers) are typically encoded using two voltages; another way of saying this is that bit values, and hence data, correspond to electrical currents in the wires¹ of a chip. Gates, i.e. the lowest level of operations that can be applied to bits, then correspond to barriers that let the electrical current flow through to outgoing wires, or block it.

We can thus picture a classical gate as a black box with n input wires going into the box and m output wires leaving it. For any combination of on and off voltages on the input wires, the box will turn on some of the output wires. The vital point to take away from this classical state of affairs is that we can think of the carriers of input and output data (i.e. the input and output wires) as physically distinct objects that can exist and can be read simultaneously.

Quantum physics rules out such an implementations of qubits. In the case of matter-based qubits, such as ions in traps or Josephson junctions on superconductors, quantum gates are operations that modify – or “mutate”, to borrow a term from programming languages – the physical qubits themselves. An input qubit to a gate is thus submitted to physical interactions that change its internal state. After the gate execution is completed, the qubits that held the input states now contain the operation’s output.

Similarly, photonic systems encode qubits using modes of the electromagnetic field. A gate in this setting acts by transforming these modes – mixing them, shifting their phases, or entangling them with ancillary modes. It is never possible to modify qubit data coherently whilst keeping access to the original input data.

This has several profound implications for quantum computing. First and foremost, every quantum gate must have the same number of inputs as outputs. Most iconic classical gates (AND, OR, XOR, etc.) are thus impossible to implement on a quantum computer without some adjustments². This also means that the number of qubits must remain unchanged throughout the computation. A computation that starts with n qubits must also end in n qubits – and have n qubits at every point throughout the computation.

At this point, taking the preservation of qubits just described seriously, we should be asking how a quantum computation can even come to be at all, given that no qubit can be created out of thin air. In our attempt to remain blissfully ignorant of physical realities, we suggest adopting the following abstracted mental model of qubits: qubits can neither be created nor deleted³, they simply i) exist at all times, and ii) can be reset to the 0 state.

For our convenience, we can ignore qubits that are unimportant to us. If all we need are n qubits, then we will limit our considerations to these and pretend none other exists. Pushing further our myopic focus on qubits with a direct utility, we can also adjust the window of qubits of interest as we progress through the computation. If, for instance, a new qubit becomes useful halfway through our program execution, we can enlarge the set of qubits we are keeping track of and refer to this as “creating” a qubit. Conversely, qubits often become irrelevant, in which case we move them outside of our field of consideration and say that the qubits were discarded.

A final consequence of mutating qubits that we will highlight is that once a gate has been applied, the input states to the gate no longer exist! In other words, any state that we reach throughout our execution can only be used at most once. Here, your classical intuition might kick in:

Let us just maintain a copy of the original state before modifying it!

This would allow us to do more than one computation from a temporary value. However, copying is a big NO in quantum computing. It is a profound restriction (or property, depending on your point of view) with deep roots in the physics of quantum mechanics. This principle, the no-cloning theorem, is one of three fundamental properties of quantum physics that quantum computing builds upon.

The physical constraints of quantum computation #

No-cloning theorem #

The no-cloning principle Wootte., 1982W. K. Wootters and W. H. Zurek. 1982. A single quantum cannot be cloned. Nature 299, 5886 (October 1982, 802--803). doi: 10.1038/299802a0 provides a formal foundation for the vague statement “qubits live forever” we made earlier. It is a fundamental tenet of quantum information, deserving a more rigorous treatment than we are giving it here. We recommend that the curious reader refers themselves to more respectful references such as Nielsen, 2016Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press.

No-cloning theorem: it is impossible to copy an arbitrary unknown state onto another (possibly known) qubit, or to copy a (possibly known) qubit to a qubit with unknown arbitrary state.

If we use $\ket{\psi}$ to denote an arbitrary state and $\ket{0}$ to denote a known state, the principle can be restated as: there are no quantum computations mapping $\ket{\psi}\ket{0} \mapsto \ket{\psi}\ket{\psi}$, nor $\ket{\psi}\ket{0} \mapsto \ket{0}\ket{0}$. The consequences of this are profound.

A consequence of the first half is what we alluded to in the previous section: any qubit states can only be used once in a computation. This statement also justifies why every quantum gate implementation, no matter the hardware specifics, will mutate its input qubits to produce the output states.

The second half of the statement is often referred to as the “no delete” theorem. Indeed, if we view $\ket{\psi}$ as a state encoding some data, we can interpret it as some amount of information. The state $\ket{0}$, on the other hand, is a fixed state and thus cannot store any information. From the perspective of information theory, the map $\ket{\psi}\ket{0} \mapsto \ket{0}\ket{0}$ thus destroys information: it turns an information storing left-hand side into a product of $\ket{0}$ states, devoid of any information.

We can also revisit the first map $\ket{\psi}\ket{0} \mapsto \ket{\psi}\ket{\psi}$ and understand it from an information theoretic perspective as an attempt to create information out of thin air! Using this interpretation, the no-cloning theorem is thus the statement that quantum information is a preserved quantity in quantum computations: its amount will never increase or decrease.

Reversibility #

The fact that the amount of quantum information can never increase by transforming quantum states matches our intuition: if no new information is added from outside the system, then the total information encoded should not be increasing. Why, however, is it impossible to erase some information and thus reduce its total? The answer is reversibility of closed quantum systems: if we exclude the option of discarding parts of the physical system, every quantum of operation is undoable. In other words, a computation must have an inverse operation that recovers the input when applied to the output.

If a quantum operation were thus to erase any information, then an inverse operation would exist that creates information from nothing! The two halves of the no-cloning theorem, as we presented it, thus state the same principle once we consider that every operation must be reversible.

Universality #

Finally, a third distinguishing property of quantum computation is how arbitrarily large computations can be generated from single-qubit gates and pairwise entangling interactions between qubits (two-qubit gates) Barenco, 1995Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin and Harald Weinfurter. 1995. Elementary gates for quantum computation. Physical Review A 52, 5 (November 1995, 3457--3467). doi: 10.1103/PhysRevA.52.3457. It is furthermore the case that the choice of a fixed two-qubit gate, along with single-qubit gates, is sufficient to generate any arbitrary quantum computation. We call a set of gates that can be used to construct any arbitrary quantum computation a universal gate set.

This is a boon for hardware design, as manipulating single-qubit systems is often much more manageable than controlling physical interactions between multiple entities. This decomposition into single-qubit and (a fixed) two-qubit gates means that the architecture i) does not need to support interactions between $n > 2$ qubits, and ii) can be specialised and hand-tuned to execute the two-qubit interaction of choice as faithfully as possible. Having a two-qubit gate as the entangling operation is not the only choice. Some architectures, such as neutral atoms, choose instead to replace it with a global entangling operation that applies to many qubits simultaneously Evered, 2023Simon J. Evered, Dolev Bluvstein, Marcin Kalinowski, Sepehr Ebadi, Tom Manovitz, Hengyun Zhou, Sophie H. Li, Alexandra A. Geim, Tout T. Wang, Nishad Maskara, Harry Levine, Giulia Semeghini, Markus Greiner, Vladan Vuletić and Mikhail D. Lukin. 2023. High-fidelity parallel entangling gates on a neutral-atom quantum computer. Nature 622, 7982 (October 2023, 268--272). doi: 10.1038/s41586-023-06481-y, resulting in a universal gate set that is more convenient to implement experimentally in their system.

Gate set universality can be generalised further to approximate universality, which is at the centre of the development of error-correcting codes. Indeed, any quantum computations can be approximated to arbitrary precision using only discrete finite sets of one and two-qubit gates Kitaev, 2002Alexei Y. Kitaev, A. H. Shen and Mikhail N. Vyalyi. 2002. Classical and Quantum Computation. American Mathematical Society Dawson, 2006Christopher M. Dawson and Michael A. Nielsen. 2006. The Solovay-Kitaev algorithm. Quantum Information and Computation 6, 1 (January 2006, 81--95). doi: 10.26421/QIC6.1-6. This represents a significant simplification for error correction, as it removes the need for continuously parametrised gates and discretises the problem space.

Leveraging quantum properties for compilation #

We have introduced the universality, reversibility and no-cloning properties of quantum computations for a reason: these laws of physics that govern quantum computations and are absent from classical computer science are an excellent foundation for developing quantum-specific computation optimisations and compilation techniques in general.

As we have just discussed, the wide variety of universal gate sets are degrees of freedom that the compiler can use. Using universality to translate computations between universal gate sets, enabling programmers to seamlessly target different hardware, is one of quantum compiler’s first and most fundamental functions Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92.

Reversibility is also a source of flexibility when expressing quantum programs. Suppose the user wants to execute an operation $A$ but it is more convenient, or the hardware is only capable of executing a different gate $B$. Then, using the inverse $B^{-1}$ of $B$, it is always possible to rewrite the program as

where these diagrams should be read as operations to be executed from left to right. This is nothing but the mathematical trick of multiplying the left-hand side with the identity operation expressed as $B \circ B^{-1}$⁴.

Now, of course, this rewrite is only sensible if the operation $B^{-1} \circ A$ is reasonably cheap to perform. There are plenty of instances where this is indeed the case. Morally, the quantum compiler always has the freedom to execute any quantum operation – at the risk of producing very inefficient code – given that reversibility always guarantees that the operation can be reversed and the competition undone whenever necessary.

Finally, no-cloning is a very useful guarantee that the compiler can use to simplify reasoning about computations⁵. In chapter 4 we will see that it dramatically simplifies pattern matching, which helps identify all possible optimisations quickly. More generally, no-cloning restricts the set of programs that the compiler must consider, resulting in elegant graph transformation semantics – a topic we explore in chapter 3.

The quantum circuit representation #

We could not conclude our overview of the basics of quantum computing without mentioning the quantum circuit, a representation of quantum computation ubiquitous in the field. With the understanding that we have gained in this section, the two building blocks of the circuit model and the conventions around their graphical representation should be of no surprise to the reader:

1. Qubits are represented by straight, horizontal lines. Their evolution through time can be followed along the line from left to right: At the leftmost point on the line, the qubit is in its input state; when the qubit reaches its rightmost point, operations have mutated it into the output state of the circuit.
2. Gates on qubits are boxes placed vertically across one or multiple qubit lines. The qubits it is on represents the set that the gate may act on (and mutate), whereas the left-to-right ordering of the gates reflects their ordering in time.

A simple circuit composed of two qubits and three gates $A$, $B$ and $C$ could for instance look like this

The previous diagram was in fact also a circuit, in which each arrow pointing to the right was a segment of a qubit line. In this case, $A$ would be executed before $B$ and $C$; $A$ would act on both qubits, whereas $B$ and $C$ would only modify the first and second qubits, respectively. Note that there is no ordering specified between $B$ and $C$: because they act on disjoint sets of qubits, their relative ordering makes no difference. It is thus common to display them as acting at the same time. We could have equivalently chosen to draw them as:

All these circuits represent the same computation.

Certain quantum gates are particularly useful and appear very regularly in practice. These have standard names that are widely used in the field. The most common single qubit gates are arguably the Hadamard, represented in circuits by a $H$ box, and the $X$, $Y$ and $Z$-axis rotations, drawn as $R_x(\theta)$, $R_y(\theta)$ and $R_z(\theta)$ boxes respectively. Note that rotation gates are parametrised by an angle $0 \leqslant \theta < 4\pi$ that must be specified to execute the rotation.

There are also commonly used multi-qubit gates. For these, it becomes slightly awkward to draw them as boxes, as they may act on qubits that are not drawn next to each other in the circuit⁶ or might be applied to qubits in a specified order. As a solution, common gates were given representations that do not spell out their name but mark which qubit they are acting on and in what order. Here are the representations of three of the most famous ones, in order: the $\mathit{CX}$ (also known as CNOT) gate, the $\mathit{CZ}$ and the $\mathit{CCX}$ (also known as the three-qubit Toffoli):

You will probably notice that there seems to be a system to this graphical notation. There is, but unfortunately, explaining it would require us to discuss Pauli matrices and commutation relations and quickly lead us astray. The references in section 2.5 are a good starting point for further reading.

←Return to chapter