Chapter 1
Introduction

1.1 Motivation

In 1935, Erwin Schrödinger, an Austrian physicist, proposed a thought experiment to illustrate the interpretation of uncertainty in quantum mechanics. This thought experiment later acquired the fond connotation of the "Schrödinger's Cat" experiment [1, 2]. In this treatise, we will refer to another thought experiment, namely the "Black Box Experiment." Let us assume that we have a black box with a coin spinning in it. It does not have to be a fair coin. Inside the box, we then start spinning the coin. We do not have any prior knowledge about the coin, namely whether the coin is fair or biased and we do not know whether it landed on the face or the tail side when it finally stopped spinning. At this moment, we may say that the coin inside the box is within a superposition of two states and has a certain probability for each of the two states. Let us continue the experiment by using several boxes. We may proceed by using two, three, or even an arbitrary number of boxes for this experiment. Similarly, we spin all the coins simultaneously and close the boxes. This situation may be viewed as having states, suggesting that we can increase the computational power exponentially in line with if we can exploit the above-mentioned superposition. Let us now continue the experiment with the following step. Up to this moment, all of the boxes are completely sealed and we have secured the states of the coins simultaneously. Now, we decide to open all of the boxes at once and observe all the coins. After observing the state of each coin in each box, we are now in the position to observe a single specific state from the full set of possible states. This illustrates that after lifting the lid of the boxes the quantum states suddenly collapse into a single deterministic classical state due to the action of "observation," which is also often termed in parlance as a "measurement." This property is exploited by quantum computers, which will create a powerful computational tool that is potentially capable of breaking conventional cryptography.

Consequently, while an -bit classical register can store only a single -bit value, an -qubit quantum register can store all the states concurrently. This allows the parallel evaluation of certain functions with regular global structure at a complexity cost that is equivalent to a single classical evaluation [3, 4], as illustrated in Figure 1.1. Therefore, as exemplified by Shor's factorization algorithm [5] and Grover's search algorithm [6], quantum-based computation is capable of solving certain complex problems at a substantially lower complexity than classical computing.

Figure 1.1 Quantum Parallelism: Given a function , which has a regular global structure such that , a classical system requires four evaluations to compute for all possible . By contrast, a two-qubit quantum register can be in a superposition of all the four possible states concurrently. This may be written as , where the operation distinguishes the quantum states. Therefore, quantum computing requires only a single classical evaluation/observation to yield the outcome, which is also in a superposition of all the four possibilities, i.e. . However, it is not possible to read all the four states, because the quantum register collapses to one of the four superimposed states upon measurement. Nevertheless, we may manipulate the resultant superposition of the four possible states before observing the quantum register for the sake of determining a desired property of the function.

Source: Adapted from [5-8].

In 1965, Gordon E. Moore released the general rule of thumb projecting the number of transistors on a single integrated circuit chip used in the semiconductor industry. This notable rule of thumb was later termed "Moore's Law," which dictates that the number of the transistors on an integrated circuit chip will be doubled every 18 months or two years [9]. This law has maintained its validity over the past few decades, as illustrated in Figure 1.2, but it has been hypothesized that the trend is expected to slow down [10]. As the transistor's size is reduced, we encounter new physical phenomena as we enter the nanoscale world, which can only be described using the postulates of quantum mechanics [11]. We encounter both pros and cons as we embark on this journey into the unknown. First, the ability to create the above-mentioned simultaneous states at any instant lends itself to high-power parallel computing by exploiting the quantum-domain superposition. Second, the collapse of quantum superposition into a classical state upon observation potentially allows us to conceive unbreachable communication schemes and detect eavesdropping, which is the main advantage of quantum communication.

Figure 1.2 The number of transistors on an integrated circuit has doubled every two years since 1971.

Source: [12]/Our World in Data/CC BY 4.0.

The field of theoretical quantum computing was established five decades after the Schrödinger Cat experiment by the renowned physicist Richard Feynman, who suggested how to simulate quantum phenomena using quantum computers [13]. Since then, diverse quantum-domain algorithms have been invented and indeed have shown that the laws of quantum mechanics can help us to speed up computations in some applications [4-7, 14-26]. In parallel to the quantum computing developments, attractive quantum-based solutions capable of providing absolute security have also been conceived [27-36].

Despite the above-mentioned advances, the physical implementation of quantum computers is still far from perfection. Substantial efforts have been invested in building a scalable and reliable quantum computer relying on different solutions. For instance, by using spin electron-based techniques [37, 38], photonic chips [39-41], superconducting qubits [42-44], and recently also by using silicon [45, 46] as well as microwave trapped-ion techniques have been conceived [47, 48]. In order to arrive at the best architecture for quantum computers, the physical implementations of quantum computation must satisfy the so-called "DiVincenzo's Criteria" [49] described below:

1. A scalable physical system with well-characterized qubits

   The elementary unit of information in classical computers is represented by binary digits or bits. Each bit can hold only a logical value of "0" or "1" at any instant, but not both. By contrast, the elementary unit of information in quantum computers is represented by a quantum bit or qubit. In quantum mechanics, the states of "0" and "1" are commonly represented using the Dirac notation, i.e. for state "0" and for state "1" [50]. Each qubit can hold a value of , , or the superposition of both states. The physical realization of a qubit should reliably distinguish the state and as well as the superposition of both states. For instance, we can have a two-level quantum system using the up/down spin states of a particle, or the ground and excited states of an atom, or the vertical and horizontal polarization of a single photon.

2. The ability to initialize the state of the qubits to a simple fiducial state

   One of the essential requirements in classical computing is to know the initial state of a register before starting the computations. Similar requirements are also applicable in the quantum domain. For instance, to initialize the process of quantum search and quantum factoring algorithms, the quantum registers must supply a certain number of fresh auxiliary qubits in the state . Similarly, operations such as quantum teleportation, quantum superdense coding, and quantum key distribution (QKD) also require the quantum registers to provide a continuous supply of fresh qubits in a certain superposition state.

3. Sufficiently long decoherence times, much longer than the gates' operation time

   In quantum computers, the qubits will be involved in a series of quantum-domain operations to carry out certain quantum computation or quantum communication tasks. Ideally, a quantum computing algorithm and similarly a quantum communication scheme should be designed by ensuring that the computational process or transmission finishes before the qubits are corrupted by the decoherence phenomenon caused by their undesired coupling with the surrounding environment. However, a long decoherence time does not necessarily mean that the qubits are more reliable. We primarily care about the number of operations that can be completed before the qubits decohere. Hence, we should take into account the gate operation time. The maximal number of reliable operations in quantum computers is defined by the ratio of the qubits' decoherence time to the per-gate operation duration. A quantum solution with a higher maximal number of reliable operations may be more preferable, because as we scale up the quantum computers, the number of gate operations will increase.

4. A universal set of quantum gates

   The power of quantum computers in speeding up some computations hinges on the availability of a universal set of quantum gates. More specifically, a universal set of quantum gates primarily entails the family of...