CHAPTER: WEEK 1: A BRIEF HISTORY OF COMPUTERS

§ WHAT IS COMPUTING

The term “computing" often brings to mind the image of computers, machines that we typically associate with performing computational tasks <cit.>. However, computing encompasses far more than just the operations carried out by electronic devices. In essence, computing is a fundamental aspect of numerous processes and activities in the world. Our brain, for instance, can be considered one of the earliest computing tools, constantly engaged in computational processes. Everyday activities like arithmetic calculations, strategizing in chess, or decision-making in games like mah-jongg are all instances where our brain naturally engages in abstraction and computation.

When we consider the computational ability of a computer, we are referring to its capacity for mathematical induction and transformation. This ability involves transforming abstract and complex mathematical expressions or numbers into forms that are comprehensible to us, using various mathematical methods. In this sense, computing is not just about the hardware (computers) but also about the fundamental process of transforming and understanding information, a process that is central to both artificial machines and the human mind.

Computers are renowned for their capability to perform a wide array of tasks at speeds far surpassing human capabilities. This efficiency and speed in processing complex calculations and managing vast amounts of data is one of the primary reasons for their ubiquitous presence in modern life.

Historically, humans have always sought tools to aid in computation. From the abacus, an ancient tool for arithmetic, to the concepts of binary logic, and eventually to the Analytical Engine conceptualized by Charles Babbage, the journey of computational tools has been long and transformative.

Looking ahead, it becomes increasingly clear that both individuals and societies, in the context of countries, science, or everyday life, will continue to rely heavily on data and computing. Data has emerged as a cornerstone of competitiveness in numerous fields, making the ability to process and understand this data a critical skill. This is evident in technologies such as intelligent identification systems, as illustrated in Figure <ref>, and the ubiquitous use of smartphones, as shown in Figure <ref>. These are prime examples of data processing capabilities in action. The demand for computing power is a constant in an ever-evolving technological landscape, indicating that there will always be a need for more advanced and efficient computational tools.

[Intelligent identification]

[Mobile phone]

(a) An illustration of a futuristic intelligent identification system, showcasing advanced technology with a sleek, high-tech design. This system is depicted scanning and identifying cartoon-style human figures, demonstrating the process of data analysis and recognition in a sophisticated yet approachable manner.(b)A depiction of global connectivity, represented by a stylized world map in the background, with a modern smartphone in the foreground showcasing advanced computing features. This image symbolizes the widespread use of smartphones across the globe, highlighting their capabilities in data processing, communication, and multimedia, and emphasizing their role in a globally connected world.

§ BINARY NUMBERS AND BOOLEAN LOGIC

The foundation of modern computing lies in binary arithmetic. Therefore, it is essential to understand binary numbers <cit.>.

A binary number is a number expressed in the base-2 numeral system, which uses only two digits, 0 and 1. All numbers can be represented in binary form.

There are two primary methods for converting between binary and decimal systems. The first method is converting from decimal to binary. This is achieved using the “division by 2" method, which involves dividing the decimal number by 2 to get a quotient and a remainder. This process is repeated, using the quotient for subsequent divisions, until the quotient becomes 0. The binary number is then formed by arranging the remainders in reverse order, starting from the last remainder obtained (the least significant bit) to the first (the most significant bit).

The second method is converting from binary to decimal. In this method, each digit of the binary number is multiplied by the corresponding power of 2, starting from the rightmost digit. The sum of these products gives the decimal equivalent of the binary number.

Table <ref> illustrates the conversion of binary numbers from 0 to 8, providing a clear reference for understanding this fundamental concept in computing.

Decimal number     0     1     2     3     4     5     6     7     8

Binary number     0     1     10     11     100     101     110     111     1000

The convert of binary and decimal from 0 to 8

Next, we explore the conversion of decimal fractions to binary. This process involves two main parts: converting the integer part and converting the fractional part of a decimal number to binary.

Converting the Integer Part of a Decimal to Binary:
The conversion of the integer part is relatively straightforward and can be done using the division-by-2 method. The steps include:

* Divide the integer part of the decimal number by 2 and write down the remainder. This remainder is the least significant bit of the binary representation.

* Continue dividing the quotient by 2 and write down the remainder as the next higher bit in the binary number.

* Repeat the process until the quotient becomes 0.

Converting the Fractional Part of a Decimal to Binary:
The conversion of the fractional part employs the multiplication-by-2 method. The steps are:

* Multiply the fractional part of the decimal number by 2. The integer part of the result is the most significant bit of the binary fraction.

* Use the fractional part of the result for the next multiplication by 2 and record the integer part as the next binary digit.

* Continue this process until the fractional part becomes 0 or reaches a repeating pattern.

Converting Decimal Fractions to Binary:
To convert a decimal fraction to binary, convert the numerator and denominator into binary separately. Then, represent the binary fraction with the binary numerator and denominator separated by the fraction line.

Table <ref> shows the binary conversion and approximation of fractions, including the approximation of infinite recurring decimals using geometric series. In the series, “a" represents the first term, and “r" is the common ratio. The sum of an infinite geometric series is given by:

\begin{equation}
\sum_{k=0}^{\infty}ar^{k} = \frac{a}{1-r}
\end{equation}

This mathematical principle helps in understanding the approximation of recurring decimals in binary representation.

Fraction     Decimal     Binary     Fraction Approximation

$1/1$     $1$ or $0.999...$     $1$ or $0.111...$     $1/2+1/4+1/8$

$1/2$     $0.5$ or $0.4999...$     $0.11$ or $0.0111...$     $1/4+1/8+1/16$

$1/3$     $0.333$ or $0.010101$     $1$ or $0.111...$     $1/4+1/16+1/64$

Binary conversion and approximation of fractions

conversion Between Decimal and Binary:

According to the example of convent decimal and binary, fill in the correct result of binary conversion in the blank in table <ref>

Decimal     Binary     Decimal     Binary

0     0     8     1000

1     1     9

2     10     10

3     11     11

4     100     12

5     101     13

6     110     16

7     111     15

16            99

Exercise 1 conversion Between Decimal and Binary

Now let's learn binary arithmetic, including addition, subtraction, multiplication, and division:

Binary Addition:
The rules for binary addition are as follows:

\begin{align*}
0 + 0 &\to 0 \\
0 + 1 &\to 1 \\
1 + 0 &\to 1 \\
1 + 1 &\to 0 \text{ (carry 1)}
\end{align*}

Addition of two binary numbers:

0     1     1     0     1

+     1     0     1     1     1

=      1     0     0     1     0     0     = 36

Binary Subtraction:
The rules for binary subtraction are as follows:

\begin{align*}
0 - 0 &\to 0 \\
0 - 1 &\to 1 \text{ (borrow 1)} \\
1 - 0 &\to 1 \\
1 - 1 &\to 0
\end{align*}

Subtraction of two binary numbers:

1     1     0     1     1     1     0

-                 1     0     1     1     1

=      1     0     1     0     1     1     1

Binary Multiplication:

Multiplication of two binary numbers:

1     0     1     1

x     1     0     1     0

0     0     0     0

+                1     0     1     1

+          0     0     0     0

+    1     0     1     1

=    1     1     0     1     1     1     0

Binary Division:

Division of two binary numbers:
& 101 \\
101 & \overline{)11011} \\
& \underline{-101} \\
& 111 \\
& \underline{-101}\\
& 010
\end{array}$

Four operations in binary.
Please calculate and fill in the correct result in the blank of the following vertical operations:

(1) Binary Addition

1     1     0     1     1     1     0

+     1     1     0     0

(2) Binary Subtraction

1     1     0     1     1     1     0

-     1     1     0     0

(3) Binary Multiplication

1     1     0     1

1     0     1

(4) Binary Division
1101 & \overline{)1101110} \\
\end{array}$

Boolean logic is a fundamental concept in computer science and mathematics, involving set algebra and various basic operators to symbolize and algebraize logical processes. Set algebra, a branch of mathematics, focuses on operations involving sets. The primary operations defined in set algebra include:

Union: The union of two sets \(A\) and \(B\), denoted by \(A \cup B\), is the set of elements that are in \(A\), in \(B\), or in both \(A\) and \(B\). For example, if \(A = \{1, 2\}\) and \(B = \{2, 3\}\), then \(A \cup B = \{1, 2, 3\}\).

Intersection: The intersection of two sets \(A\) and \(B\), denoted by \(A \cap B\), is the set of elements that are in both \(A\) and \(B\). For instance, if \(A = \{1, 2\}\) and \(B = \{2, 3\}\), then \(A \cap B = \{2\}\).

Complement: The complement of a set \(A\), denoted by \(A'\), is the set of elements not in \(A\) but present in the universal set \(U\) (the set containing all possible elements). For example, if \(A = \{1, 2\}\) and \(U = \{1, 2, 3, 4\}\), then \(A' = \{3, 4\}\).

A Venn Diagram <cit.> is a visual tool used to represent sets and their relationships. It employs overlapping circles or other shapes to illustrate the logical relationships between two or more sets. Each circle represents a set, and the areas where the circles overlap indicate the intersection of these sets.

The aforementioned operations, along with their corresponding Venn diagrams, are illustrated in Figure <ref>, demonstrating the principles of set algebra in Boolean logic.

Set algebra in this figure we show the union, intersection and complement

Boolean algebra <cit.>, also known as logical algebra, involves variables that represent the states of “True" and “False”, typically denoted as “1" for True and “0" for False. This form of algebra is foundational in computer science and digital circuit design. There are three basic operational logics in Boolean algebra:

AND: Symbolized as \(\land\). For \(x \land y\), the output is 1 (True) if and only if both \(x = 1\) and \(y = 1\); otherwise, \(x \land y = 0\) (False).

OR: Symbolized as \(\vee\). For \(x \vee y\), the output is 0 (False) if and only if both \(x = 0\) and \(y = 0\); in all other cases, \(x \vee y = 1\) (True).

NOT: Symbolized as \(\neg\). For \(\neg x\), if \(x = 1\), then \(\neg x = 0\) (False), and if \(x = 0\), then \(\neg x = 1\) (True).

The truth tables for the “AND", “OR" and “NOT" operations are shown in Table <ref>:

\(x\)     \(y\)     \(x \land y\)     \(x \vee y\)

0     0     0     0

0     1     0     1

1     0     0     1

1     1     1     1

\(x\)     \(\neg x\)

0     1

1     0

The truth table of the three basic operational logics: “AND", “OR", “NOT"

The logical operations “AND", “OR" and “NOT" in Boolean algebra can be effectively illustrated using Venn diagrams. Venn diagrams provide a visual representation of these operations by showing the relationship between different sets.

In a Venn diagram:

* The “AND" operation (\(\land\)) is represented by the intersection of sets, highlighting the common elements.

* The “OR" operation (\(\vee\)) is depicted by the union of sets, encompassing all elements that belong to either set.

* The “NOT" operation (\(\neg\)) is visualized by showing the complement of a set, which includes all elements not in the set within a given universal context.

These representations help in understanding how Boolean operations combine and manipulate sets, reflecting their applications in logical processes and digital circuits. The Venn diagrams corresponding to the “AND", “OR" and “NOT" operations are presented in Figure <ref>.

Venn Graph of “AND", “OR", “NOT"

Boolean operations can be used to construct various other logical operations. For example:

\begin{align}
x \to y &= \neg x \vee y\\
x \oplus y &= (x \vee y) \land (\neg x \vee \neg y) = (x \land \neg y) \vee (\neg x \land y)\\
x \equiv y &= (x \land y) \vee (\neg x \land \neg y)
\end{align}

The truth tables for these operations are shown in Table <ref>:

$x$     $y$     $x \to y$     $x \oplus y$     $x \equiv y$

0     0     1     0     1

0     1     1     1     0

1     0     0     1     0

1     1     1     0     1

The truth table for “AND", “OR", and “NOT"

De Morgan's theorem is another crucial concept in Boolean algebra:

\begin{align}
x \land y &= \neg(\neg x \vee \neg y)\\
x \vee y &= \neg(\neg x \land \neg y)
\end{align}

Truth table of De Morgan's Law:

Using the theorem formula, please calculate and fill in the correct result in the blank of the following truth tables in Tables <ref> and  <ref>:

Formula one: \(x \land y = \neg(\neg x \vee \neg y)\)

$x$     $y$     $x \land y$     $\neg x$     $\neg y$     $\neg x \vee \neg y$     $\neg(\neg x \vee \neg y)$

0     0     0     1     1     1     0

0     1     0     1     0     1     0

1     0     0     0     1     1     0

1     1     1     0     0     0     1

The truth table for De Morgan's Law (Formula one)

Formula two: \(x \vee y = \neg(\neg x \land \neg y)\)

$x$     $y$     $x \vee y$     $\neg x$     $\neg y$     $\neg x \land \neg y$     $\neg(\neg x \land \neg y)$

0     0     0     1     1     1     0

0     1     1     1     0     0     1

1     0     1     0     1     0     1

1     1     1     0     0     0     1

The truth table for De Morgan's Law (Formula two)

A Boolean function <cit.> is defined as a logical calculation that takes Boolean inputs to produce a Boolean output. Essentially, a Boolean function can only return True (1) or False (0). For a Boolean function with $k$ inputs, it is defined as:

\begin{equation}
f:\{0, 1\}^{k} \to \{0, 1\}
\end{equation}

In cases where a Boolean function has multiple outputs, $k$ represents the number of inputs and $m$ the number of outputs:

\begin{equation}
f:\{0, 1\}^{k} \to \{0, 1\}^{m}
\end{equation}

For a Boolean function $f$ with $k=2$ (input of two numbers) and $m=1$:

If $f$ represents the “OR" operation, then:

\begin{align*}
f(00) &= 0, \\
f(01) &= 1, \\
f(10) &= 1, \\
f(11) &= 1
\end{align*}

For a Boolean function $f$ with $k=3$ (input of three numbers) and $m=3$:

$f$ can be defined as:

\begin{align*}
f(000) &= 000, \\
f(011) &= 011, \\
f(110) &= 111, \\
f(111) &= 110
\end{align*}

The basic unit of computer operation is the logic circuit <cit.>, which typically contains “AND", “OR" and “NOT" gates. These gates function as Boolean operations.

Consider the “Parity" Boolean function, represented by the following truth table (Table <ref>):
For a variable $x$, it can be written as:

\begin{equation}
x = x_{2}x_{1}x_{0} , \text{ where } x_{2}, x_{1}, x_{0} \in \{ 0, 1 \}
\end{equation}

x     000     001     010     011     100     101     110     111

$f$     0       1       1       0       1       0       0       1

Truth table of the “Parity" Boolean function

The Boolean function $f$ in terms of Boolean logic can be expressed as:

\begin{equation}
f = (\neg x_{2} \land \neg x_{1} \land x_{0}) \vee (\neg x_{2} \land x_{1} \land \neg x_{0}) \vee (x_{2} \land \neg x_{1} \land \neg x_{0}) \vee (x_{2} \land x_{1} \land x_{0})
\end{equation}

Alternatively, it can be simplified as:

\begin{equation}
f = x_{2} \oplus x_{1} \oplus x_{0}
\end{equation}

§ COMPUTER ARCHITECTURE AND LOGIC CIRCUITS

Human computing tools have a history spanning thousands of years  <cit.>. From primitive tools like fingers to ancient calculators such as the abacus, and later to mechanical computers, the evolution of these tools has been remarkable. Early tools like the abacus were based on the Decimal system, while modern computers operate on Binary logic. For instance, Figure <ref> illustrates a tool based on Binary.

Decimal: Historically, the Decimal system has been pivotal in mathematical computing. Although the human brain is a powerful computing tool, we have always needed auxiliary tools to enhance and accelerate the computing process.

Binary: A significant advancement was the invention of binary logic around 1702, which laid the technical groundwork for the development of modern computers.

Charles Babbage invented an analysis engine based on Binary, the figure is from <https://commons.wikimedia.org/wiki/File:Babbages_Analytical_Engine,_1834-1871._(9660574685).jpg>.

Before modern computer was invented, the word “computer" is already exist, it represented a person who perform computing. Until 1946, when the first general digital computer was invented, the word “Computer” refer to the machine which perform computing tasks.

Before the invention of modern computers, the term “computer” referred to a person who performed calculations. This definition changed in 1946 with the invention of the first general digital computer, after which “computer" came to denote the machine itself.

The Turing Machine is a pivotal mathematical model of computation, defining an abstract machine that manipulates symbols on a strip of tape according to a table of rules <cit.>. As a general representation of a CPU, the Turing Machine controls all data manipulation in a computer, using sequential memory for data storage. Despite its simplicity, a Turing Machine can simulate the logic of any computer algorithm.

With an understanding of computation models, the next question is: how were computers built?

From 1937 to 1960, the digital computer was developed, heralding the birth of computer science. The earliest electronic computers were built using vacuum tubes, with high and low levels representing binary digits (1 and 0, respectively). These tubes facilitated the implementation of binary operation rules. Figure <ref> shows various vacuum tubes.

A vacuum tube, electron tube. The figure is from

In 1946, the world's first electronic computer based on binary logic, the ENIAC, was introduced. Figure <ref> shows the ENIAC.

The world's first electronic computer was based on Binary called ENIAC. The figure is from  <https://commons.wikimedia.org/wiki/File:Glen_Beck_and_Betty_Snyder_program_the_ENIAC_in_building_328_at_the_Ballistic_Research_Laboratory.jpg>.

IBM constructed the first commercial computer, the IBM 701, in 1952. Figure <ref> showcases this pioneering machine.

The first commercial electronic computer was made by IBM :IBM 701 (1952 year). The figure is from <https://commons.wikimedia.org/wiki/File:IBM_701console.jpg>.

Modern computers, products of the third industrial revolution, include PCs, mobile phones, laptops, and other devices typically built using semiconductor technology. These computers are based on the "Von Neumann Architecture".

Von Neumann Architecture: Despite significant changes in the manufacturing process, size, and shape of electronic computers, their fundamental architecture has remained consistent. This architecture encompasses input, output, control unit, computing unit, and storage unit. Figure <ref> illustrates the Von Neumann Architecture.

Von Neumann Architecture. The figure is from

The basic unit of computer operation is the logic circuit. The basic logic circuit contains “AND", “OR", “NOT" 3 gates. “AND", “OR", “NOT" are also the basic operations of Boolean algebra <cit.>.

In the “AND" gate, the output $Q=A\land B$. In the “OR" gate, the output $Q=A\vee B$. In the “NOT" gate, the output $Q=\neg A$. The “AND" gate, “OR" gate, “NOR" gate shown in Figure <ref>, Figure <ref> and Figure <ref>.

The “AND" gate, $Q=A\land B$

The “OR" gate, $Q=A\vee B$

The “NOT" gate, $Q=\neg A$

The truth table of “AND" gate, “OR" gate, “NOT" gate in table <ref>:

x     y     $x\land y$     $x\vee y$

0     0     0              0

1     0     0              1

0     1     0              1

1     1     1              1

2|c|x     2|c|$\neg x$

2|c|0     2|c|1

2|c|1     2|c|0

The truth table of “AND" gate, “OR" gate, “NOT" gate

Other operations “NAND", “NOR", “XOR", “XNOR" also is common logic circuits. In the “NAND" gate, the output $Q= \neg(A\land B)$. In the “XOR" gate, the output $Q=(A\land\neg B)\vee(\neg A\land B)=A\oplus B$. In the “NOR" gate, the output $Q=\neg(A\vee B)$. In the “XNOR" gate the output $Q=\neg(A\oplus B)$. The gate “NAND", “NOR", “XOR", “XNOR" are show in Figure <ref>, Figure <ref>, Figure <ref> and Figure <ref>.

“NAND" gate $Q= \neg(A\land B)$

“XOR" gate $Q=(A\land\neg B)\vee(\neg A\land B)=A\oplus B$

“NOR"gate $Q=\neg(A\vee B)$

“XNOR"gate $Q=\neg(A\oplus B)$

Truth table of Logic Gate

According to the logic gate formula provided, please calculate and fill the correct result in the following truth table the truth table are in table <ref> and table <ref>.

1. “XOR" gate $Q=(A\land\neg B)\vee(\neg A\land B)=A\oplus B$

A     B     $A\land\neg B$     $\neg A\land B$     $A\oplus B$

0     0

0     1

1     0

1     1

“XOR" gate $Q=(A\land\neg B)\vee(\neg A\land B)=A\oplus B$

2. “XNOR"gate $Q=\neg(A\oplus B)$

A     B     $A\oplus B$     $\neg(A\oplus B)$

0     0

0     1

1     0

1     1

“XOR" gate $Q=(A\land\neg B)\vee(\neg A\land B)=A\oplus B$

Now we look at some examples of logic circuits.

Half adder:

All computing algorithms can be implemented using logic circuits. The basic units in arithmetic circuits are half adders and full adders. A half adder has two inputs and two outputs, the inputs can be identified as A, B, and the outputs are usually identified as Sum (Sum) and Carry (Carry). The input is S after the XOR operation AND C after the and operation. The half adder has two binary inputs, which add the input values and output the result to Sum and Carry. Although the half adder can produce carry values, the half adder itself cannot process carry values. The Figure <ref> show the half adder.

The half adder only calculates the sum of the base bits, and does not consider the carry from the lower bits, so it is called a half adder.

The truth table of half adder in table <ref>. Based on the logic circuit shown in Figure <ref>, calculate and fill in the correct result in the blanks of the truth table.

A     B     Sum of Half add "S"     Carry Number "C"

0     0

1     0

0     1

1     1

The truth table of half adder

Full adder:

The English name of the full adder is full-adder, which is a combination line that uses a gate circuit to add two binary numbers and find the sum, called a full adder. The one-bit full adder can handle the low carry and output the standard add carry. Multiple one-bit full adders can be cascaded to obtain a multi-bit full adder. All computing algorithms can be implemented using logic circuits. The basic units in arithmetic circuits are half adders and full adders. There is an example of full adder in Figure <ref>

Logic circuits example : Full adder

Truth table Full adder

Based on the logic circuit shown in Figure <ref>, calculate and fill in the correct result in the blanks of the truth table. The truth table of full adder in table <ref>

A     B     low-order carry     Sum S     Carry number

0     0     0

0     0     1

0     1     0

0     1     1

1     0     0

1     0     1

1     1     0

1     1     1

The truth table of half adder

The summary of Logical circuit truth table shown in Figure <ref> :

Logical operator “And": $A\land B$ can be write as: $A\cdot B$. “OR": $A\vee B$ can be write as: $A+B$. “NOT": $\neg A$ can be write as: $\bar{A}$.

The summary of Logical circuit truth table are as follows

“NAND" gates alone (or alternatively “NOR" gates alone) can be used to reproduce the functions of all the other logic gates.

So NAND is “universal” to compute any Boolean function. “NAND" or “NOR" can form all logic gates independently (Charles Sanders Peirce,during 1880–1881).
Therefore, the “NAND"  gate is a complete logic gate.

In the Figure <ref> the six gate(“AND" gate, “OR" gate, “NOT" gate, “NAND", “XOR", “XNOR")
are use “NAND" gate to build.

Use the “NAND" gate to build the six gate(“AND" gate, “OR" gate, “NOR" gate, “NOT" gate, “XOR" gate, “XNOR" gate). The order is left to right, top to bottom.

§ COMPUTERS WITH INTEGRATED CIRCUITS

The earliest electronic computers utilized vacuum tubes in their logic circuits. However, with the invention of the transistor in 1947, these circuits began incorporating transistors in the 1950s. A significant milestone was the invention of the integrated circuit in 1959, which revolutionized logic circuit manufacturing, with transistors being the core component. Integrated circuit technology has advanced dramatically, allowing for an increasing number of transistors to be integrated per unit area, thereby significantly enhancing chip computing power. In 1965, Gordon Moore forecasted that the number of transistors on a chip would double approximately every 18 months, a prediction known as Moore's Law <cit.>. This trend continued until around 2020, when the diminishing scale of semiconductor processes approached the quantum limit (1 nanometer), causing Moore's Law to reach its threshold.

From 1945 to 2020, computing power witnessed an astonishing increase of four thousand billion times. However, this exponential growth faces inevitable limits as transistors near atomic sizes and quantum effects at microscopic levels pose new challenges.

While Moore's Law <cit.> has primarily focused on hardware developments to enhance computing power, reaching its limit could shift the focus to software improvements, such as cloud computing. This approach involves dividing a task into numerous parts and executing them simultaneously, vastly improving efficiency. For example, a task that would take 1000 hours for one person can be completed in an hour by 1000 people, as seen in Bitcoin mining pools. However, the energy consumption of traditional electronic computers is increasing, leading to projections that by 2040, global computer electricity consumption might equal the current global power generation.

The evolution of software that has improved computing power includes:

1950s: Machine language and programming languages like Fortran.

1950s: Finite state machines and formal languages.
1960s: Computational complexity.

1970s: Computational time and circuit complexity; VLSI models; algorithms and data structures.

1980s and 1990s: Parallel computing; distributed computing; cryptography.

2000s and beyond: Cloud computing and machine learning.

Artificial Neural Networks (ANNs) <cit.> have been a focal point in artificial intelligence research since the 1980s. The development and structure of ANNs are depicted in Figures <ref>,  <ref>, and  <ref>, illustrating the progression and architecture of these networks.

The brief history of neural networks. The figure is from <https://qbi.uq.edu.au/files/40697/The-Brain-Intelligent-Machines-AI-timeline.jpg>.

The brief history of neural networks. The figure is from <https://medium.com/analytics-vidhya/brief-history-of-neural-networks-44c2bf72eec>.

A neural network has three layer structure. The artificial neural networks structure is shown in the Figure <ref>.

Artificial neural network with layer coloring. The figure is from <https://commons.wikimedia.org/wiki/File:Colored_neural_network.svg>.

§ REVERSIBLE COMPUTATION

Reversible computing <cit.> is a model of computation where the computational process to some extent is time-reversible. In a model that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the mapping from states to their successors must be one-to-one. Reversible computing is a form of unconventional computing. Due to the unitarity of quantum mechanics, quantum circuits are usually reversible.

For a computational process to be physically reversible, it must also be logically reversible.

Landauer’s principle <cit.> is the rigorously valid observation that the oblivious erasure of \( n \) bits of known information must always incur a cost of \( nkT\) in thermodynamic entropy, where \( k \) is the Boltzmann constant and \( T \) is the temperature. A discrete, deterministic computational process is logically reversible if its transition function, mapping old computational states to new ones, is a one-to-one function. This means the output logical states uniquely determine the input logical states of the computational operation.

According to the principles of informatics, modern computing processes based on “AND" and “OR" gates must consume energy. Both “AND" and “OR" gates, having two inputs and one output, necessitate the erasure of one bit of information during operation. This process consumes energy, resulting in an increase in entropy. Figures <ref> and <ref> show the “AND" and “OR" gates, respectively.

TThe “AND" gate

The “OR" gate

If a reversible computing process can be constructed, then, from the informatics perspective, the computing process can potentially consume no energy. For a computational process to be physically realizable as reversible, it must also be logically reversible (Randall, 1962, IBM).

An example of reversible computing is illustrated in Figure <ref>, which shows the reversible XOR gate. Figure <ref> demonstrates the relationship between the inputs (\( A \) and \( B \)) and the outputs (\( P \) and \( Q \)). If we take the outputs \( P \) and \( Q \) as new inputs and pass them through the reversible XOR gate again, we find that the new outputs are \( P' = A \) and \( Q' = B \), thereby demonstrating the reversibility of the process.

Example:reversible XOR gate

The relationship of input and output.

Now we consider some examples of reversible computing gates.

Control-NOT(XOR) gate:

Now lei's see the example of reversible: The Control-NOT(XOR) gate. This gate is a universal reversible logic gate it's contains 2 input qubits and 2 output qubits, the first input qubit are called control qubit, and the second qubit is called the controlled qubit. When and only control qubits are both 1, the controlled qubit performs a “NO" operation, otherwise, the state of the controlled qubit remains unchanged. The Control-NOT(XOR) gate are shown in Figure <ref>.

\[ \Qcircuit @!C @!R{
&\lstick{a} &\ctrl{1}&\rstick{a^{'}=a}\qw\\
&\lstick{b} &\targ&\rstick{b^{'}=a\oplus b}\qw}\]

The reversible computation gate CNOT gate

Toffoli gate:

The Toffoli gate is a universal reversible logic gate it's contains 3 input qubits and 3 output qubits, the first two input qubits are called control qubits, and the third qubit is called the controlled qubit. When and only two control qubits are both 1, the controlled qubit performs a “NO" operation, otherwise, the state of the controlled qubit remains unchanged. The Toffoli gate is a complete general logic gate. The Figure <ref> show a Toffoli gate.

Toffoli gate

Reversible Computation: Any classical logic gate can be converted into a reversible logic gate. The Figure <ref> shown that any classical logic gate can be converted into a reversible logic gate. For example in the reversible AND gate if we let the output A, B and C as a new input pass the reversible AND gate then the new output and input are the same. reversible OR gate is the same as reversible AND gate.

Any classical logic gate can be converted into a reversible logic gate

Implementing a half adder with reversible computational logic gates. The classical half adder in Figure <ref>.

Classical half adder

The half adder implemented with reversible logic gates shown in Figure <ref>.

Half adder implemented with reversible logic gates

CHAPTER: WEEK 2: A BRIEF INTRODUCTION TO QUANTUM COMPUTING

§ REVERSIBLE COMPUTING AND QUANTUM COMPUTING

The early history of quantum computing <cit.> is a fascinating tale of theoretical exploration and groundbreaking ideas, particularly centered around the concepts of reversible computing and the pioneering work of figures like Richard Feynman and David Deutsch.

Reversible computing <cit.>, a cornerstone concept in quantum computing, emerged from Rolf Landauer's principle <cit.> formulated in 1961. Landauer, an IBM researcher, postulated that information erasure is inherently irreversible and that computation could, in theory, be energy-efficient if it were reversible. This principle set the stage for Charles Bennett, also of IBM, to demonstrate in the 1970s that reversible computing is not just a theoretical possibility but can be practically implemented. Bennett's work showed that any computation could be made reversible, thereby reducing the energy requirements of computational processes.

While reversible computing <cit.> was developing, Richard Feynman, a renowned physicist, brought a new perspective in the early 1980s. At the First Conference on the Physics of Computation at MIT in 1981, Feynman proposed the idea of a quantum computer. He argued that classical computers were inadequate for simulating quantum phenomena. Feynman's insight was that a computer based on quantum mechanical principles would be more adept at such tasks, highlighting the need for quantum computers to accurately simulate the natural world.

In 1985, David Deutsch, a physicist at the University of Oxford, built upon Feynman's ideas. Deutsch proposed the theoretical framework for a universal quantum computer, suggesting that such machines, operating on the principles of quantum mechanics, would possess remarkable capabilities beyond the reach of classical Turing machines. His work was instrumental in establishing the field of quantum complexity theory, exploring the potential of quantum computers to solve problems intractably complex for classical computers.

Paul Benioff's work in the early 1980s also played a crucial role. He proposed a quantum mechanical model of the Turing machine, bridging the gap between reversible computing and quantum computing. Benioff's model showed that a computing machine could operate in a quantum mechanical fashion, utilizing the principles of superposition and entanglement inherent to quantum computing.

The early history of quantum computing is thus marked by a series of theoretical developments, from Landauer's and Bennett's work on reversible computing to Feynman's and Deutsch's foundational contributions to the concept and theory of quantum computing. These advancements laid the groundwork for the subsequent development and realization of quantum computing technologies, marking the beginning of a new era in computational capability and understanding.

§ QUANTUM GATES

To understand how a qubit transitions from a state of \(\ket{0}\) or \(\ket{1}\) to a state of superposition, we use quantum gates. The Hadamard gate, denoted as \(H\), is particularly significant in this process. The Hadamard gate transforms a qubit's state from a definite state (\(\ket{0}\) or \(\ket{1}\)) to a superposition of states <cit.>.

When the Hadamard gate is applied to a qubit in the state \(\ket{0}\), it results in the qubit transitioning to a state which can be described as \(\ket{0} + \ket{1}\). Similarly, applying the Hadamard gate to a qubit in the state \(\ket{1}\) transforms it to \(\ket{0} - \ket{1}\). For simplicity, in this explanation (and throughout Week 2), we are omitting the normalization factor of \(\sqrt{2}\) that is typically included in these expressions.

The operation can be represented mathematically as:

\[ H\ket{0} \to \ket{0} + \ket{1}, \]

\[ H\ket{1} \to \ket{0} - \ket{1}. \]

The action of the Hadamard gate can be visualized using quantum circuit diagrams. In these diagrams, the Hadamard gate is represented by the symbol \(H\), applied to the initial qubit state, leading to the resultant superposition state.

\[
\Qcircuit @C=1em @R=.7em {
& \lstick{\ket{0}} & \gate{H} & \rstick{\ket{0} + \ket{1}} \qw    }
\]

\[
\Qcircuit @C=1em @R=.7em {
& \lstick{\ket{1}} & \gate{H} & \rstick{\ket{0} - \ket{1}} \qw    }
\]

Sample diagram of the \(H\) gate operation.

From Figure <ref>, we understand the action of the Hadamard gate \(H\) on the basis states \(\ket{0}\) and \(\ket{1}\):

\begin{align}
H\ket{0} = \ket{0} + \ket{1}, \\
H\ket{1} = \ket{0} - \ket{1}.
\end{align}

Now, let's verify the effect of applying the Hadamard gate twice on these basis states:

\begin{align}
H(H\ket{0}) = H(\ket{0} + \ket{1}) = \ket{0}, \\
H(H\ket{1}) = H(\ket{0} - \ket{1}) = \ket{1}.
\end{align}

This demonstrates the interesting property of the Hadamard gate where applying it twice returns the qubit to its original state.

Using two Hadamard gates, we can generate a superposition of two qubits, representing four states simultaneously. Figure <ref> shows how passing two qubits through \(H\) gates results in a system with four states. In contrast, Figure <ref> illustrates that when only the first qubit passes through an \(H\) gate, the system represents two states.

\[ \Qcircuit @C=1em @R=.7em {
& \lstick{\mid0\rangle} & \gate{H} & \qw \\
& \lstick{\mid0\rangle} & \gate{H} & \qw & }\]

Two qubit pass by $H$ gate there will be 4 states

\[ \Qcircuit @C=1em @R=.7em {
& \lstick{\mid0\rangle} & \gate{H} & \qw \\
& \lstick{\mid0\rangle} & \qw & \qw & }\]

Only first qubit pass by $H$ gate there will be 2 states

In Figure <ref> we ignore the other two states $\mid01\rangle$ and $\mid11\rangle$, which probabilities are 0.

Using \(n\) Hadamard gates (\(H\)), we can construct a superposition of \(n\) qubits. This superposition state can represent \(2^{n}\) different states simultaneously. These states correspond to all the possible combinations of the \(n\) qubits, ranging from \(\ket{0}\) to \(\ket{2^{n} - 1}\), where each qubit can be either in the state \(\ket{0}\) or \(\ket{1}\). The states are often labeled using decimal numbers for simplicity.

For instance, with \(n\) qubits in superposition, the states they represent can be enumerated as \(\ket{0}\), \(\ket{1}\), \(\ket{2}\), ..., \(\ket{2^{n}-1}\). As illustrated in Figure <ref>, a quantum system with multiple qubits in superposition can be represented in two ways: the more explicit left representation showing each qubit's contribution, and the simplified right representation using a single ket notation to denote the entire superposed state.

\[ \Qcircuit @C=1em @R=.7em {
&\lstick{\mid0\rangle} &\qw &\gate{H} &\qw &\qw \\
&\lstick{\mid0\rangle} &\qw &\gate{H} &\qw &\qw \\
\\
&\lstick{\mid0\rangle} &\qw &\gate{H} &\qw &\qw\\
& &\push{\downarrow}& & & \\
&\lstick{{\mid0\rangle}^n} &{/}\qw &\gate{H} &\qw&\qw &\rstick{\sum_{x}\mid x\rangle}}\]

Use $n$ H gates to build the superposition of $n$ qubits

§ BELL STATES

Bell states <cit.> are a fundamental concept in quantum information theory, describing the four maximally entangled states of a two-qubit system. In a system that is in one of the Bell states, measuring the state of one qubit immediately determines the state of the other qubit .

The Bell states are defined as follows (omitting the normalization factor of \(\sqrt{2}\) for simplicity):

\begin{equation}
\ket{\beta_{00}} = \ket{00} + \ket{11}
\end{equation}

\begin{equation}
\ket{\beta_{10}} = \ket{00} - \ket{11}
\end{equation}

\begin{equation}
\ket{\beta_{01}} = \ket{01} + \ket{10}
\end{equation}

\begin{equation}
\ket{\beta_{11}} = \ket{01} - \ket{10}
\end{equation}

To generate Bell states, we can use a combination of Hadamard (H) and Controlled-NOT (CNOT) gates. For instance, to create the Bell state \(\ket{\beta_{00}} = \ket{00} + \ket{11}\), a specific sequence of H and CNOT gates is applied. This process is illustrated in Figure <ref>, where we demonstrate how to use the H gate and CNOT gate to construct the Bell state \(\ket{\beta_{00}}\).

\[ \Qcircuit @C=1em @R=.7em {
& \lstick{\mid0\rangle} & \gate{H} & \qw & \qw & \qw &\qw & \qw & \ctrl{2} &\qw &\qw &\qw \\
& \lstick{\mid0\rangle} & \qw & \qw & \qw & \qw & \qw & \qw & \targ & \qw &\qw &\qw \\
&\lstick{\mid00\rangle}& & & &\push{\mid00\rangle+\mid10\rangle} & & & & & &\push{\mid00\rangle+\mid11\rangle}}\]

use $H$ gate and CNOT gate to build Bell states: $\mid\beta_{00}\rangle={\mid00\rangle+\mid11\rangle}$

In quantum circuits, the Hadamard ($H$) gate is often used to create superposition states <cit.>. However, the introduction of an arbitrary controlled operation, denoted as \( f \), adds another layer of complexity and utility to the circuit. Figure <ref> presents an example of such a configuration.

In Figure <ref>, we introduce a function \( f \), treated as a black box operation, within a two-qubit quantum circuit. This setup allows us to observe the effects of applying \( f \) in conjunction with other quantum gates. After the operation of the circuit and upon measurement, the state of the first qubit remains as \(\ket{x}\), indicating that it is unaffected by \( f \). However, the state of the second qubit evolves to \( f(x) \), demonstrating the application of the function \( f \) to the input state. This configuration exemplifies how quantum circuits can implement complex operations and how the state of one qubit can be manipulated based on the state of another qubit, a fundamental aspect of quantum computation.

\[ \Qcircuit @C=1em @R=.7em{
&\lstick{\mid x\rangle} & \multigate{1}{f} &\qw &\rstick{\mid x \rangle} \\
&\lstick{\mid 0\rangle} & \ghost{f}        &\qw &\rstick{\mid f(x)\rangle}}\]

A quantum circuit with function $f$.

Now, let's explore the effect of adding the \( H \) gate to our quantum circuit.

In Figure <ref>, which builds upon the setup in Figure <ref>, we initialize all the qubits to the \(\ket{0}\) state. Then, we apply the \( H \) gate to the first qubit. This addition of the \( H \) gate is crucial for generating superposition. After this operation and subsequent measurement, the resulting state of the system can be represented as a superimposed state \(\sum_{x} \ket{x, f(x)}\). This notation implies that for each possible value of \( x \) (generated by the \( H \) gate's action on the first qubit), the circuit outputs a corresponding \( f(x) \) on the second qubit. Hence, the entire quantum system is in a superposition of all possible inputs \( x \) and their corresponding outputs \( f(x) \) from the function.

\[ \Qcircuit @C=1em @R=.7em{
&\lstick{{\mid0\rangle}^n}&\qw {/^n}\qw &\gate{H^n} &\multigate{2}{f}&\qw\\
&&&&&\rstick{\sum_{x}\mid x,f(x)\rangle}\\
&\lstick{{\mid0\rangle}^n}&\qw {/^n}\qw &\qw        &\ghost{f} &\qw}\]

Add the quantum dot path after the H gate.

In quantum circuits, the \( H \) gate, also known as the Hadamard gate, continues to play a pivotal role in building superposition states. The Quantum Processing Unit (QPU) leverages this capability of the \( H \) gate to perform calculations utilizing quantum superposition. This feature is integral to the power of quantum computing, allowing the QPU to process and represent multiple states simultaneously through superposition, which is a fundamental aspect of quantum mechanics.

§ QUANTUM CIRCUIT MODEL

Single Qubit Gates

In quantum computing, qubits
are the fundamental units of information. Unlike classical bits which are either \( \ket{0} \) or \( \ket{1} \), qubits can exist in a superposition of these states, represented as <cit.>:

\begin{equation}
\ket{\phi} = a\ket{0} + b\ket{1}
\end{equation}

Understanding this quantum superposition principle is key to grasping the behavior of qubits. Now, what about quantum “gates"? Quantum gates are reversible operations that transform the states of qubits. They are analogous to logic gates in classical computing but operate under the principles of quantum mechanics. Here are some examples of single qubit gates <cit.>:

The “NOT" gate, denoted by $X$, flips the state of a qubit:

\begin{equation}
\begin{cases}
X\ket{0} = \ket{1}, \\
X\ket{1} = \ket{0}.
\end{cases}
\end{equation}

The “Hadamard" gate, denoted by $H$, creates superpositions:

\begin{equation}
\begin{cases}
H\ket{0} = \ket{0} + \ket{1}, \\
H\ket{1} = \ket{0} - \ket{1}.
\end{cases}
\end{equation}

The “Phase" gate, denoted by $Z$, applies a phase shift:

\begin{equation}
\begin{cases}
Z\ket{0} = \ket{0}, \\
Z\ket{1} = -\ket{1}.
\end{cases}
\end{equation}

Interestingly, quantum gates <cit.> can be combined to build other gates. For instance, the Phase gate can be constructed using the Hadamard gate and the NOT gate, and vice versa. Figure <ref> illustrates this concept:

\[ \Qcircuit @C=1em @R=.7em {
& \gate{H} & \gate{Z} & \gate{H} & \qw & \push{=} &  & \gate{X} & \qw \\
& \gate{H} & \gate{X} & \gate{H} & \qw & \push{=} &  & \gate{Z} & \qw

Construction of Phase gate and NOT gate using combinations of quantum gates.

Two-Qubit Gates

Let's explore some examples of two-qubit gates in quantum computing.

Figure <ref> illustrates the Reversible XOR, also an example of Reversible Computation.

Reversible XOR

The Reversible XOR, also known as the “Controlled-NOT (CNOT)", is a fundamental two-qubit gate. It has two input qubits: a control qubit and a target qubit. As shown on the left of Figure <ref>, the top \(\ket{x}\) is the control qubit and the bottom \(\ket{y}\) is the target qubit.

Figure <ref> presents two examples of the CNOT gate.

CNOT with the first qubit as the control:

\begin{equation}
\ket{x} \otimes \ket{y} \to \ket{x} \otimes \ket{y \oplus x}
\end{equation}

Similarly, a CNOT gate with the second qubit as the control:

\begin{equation}
\ket{x} \otimes \ket{y} \to \ket{x \oplus y} \otimes \ket{y}
\end{equation}

\[\Qcircuit @!C @!R{
&\lstick{\ket{x}} &\ctrl{1}&\rstick{\ket{x}}\qw \\
&\lstick{\ket{y}} &\targ&\rstick{\ket{y\oplus x}}\qw

\[\Qcircuit @!C @!R{
&\lstick{\ket{x}} &\targ&\rstick{\ket{x\oplus y}}\qw\\
&\lstick{\ket{y}} &\ctrl{-1}&\rstick{\ket{y}}\qw

CNOT gate

Controlled-Z (CZ) transforms input states as follows:

\begin{align}
\ket{00} &\to \ket{00}\\
\ket{01} &\to \ket{01}\\
\ket{10} &\to \ket{10}\\
\ket{11} &\to -\ket{11}.
\end{align}

Since the CZ operation is symmetric between the two qubits, there's no need to specify control and target qubits. Figure <ref> shows the circuit for the CZ gate.

\[\Qcircuit @!C @!R {
\lstick{\ket{x}} &\ctrl{1}&\rstick{\ket{x}}\qw \\
\lstick{\ket{y}} &\control\qw&\rstick{(-1)^{xy}\ket{y}}\qw

CZ operation

Let \( U \) be any single-qubit unitary operation. Then, the controlled-\( U \) operation is a two-qubit operation. Figure <ref> illustrates the controlled-\( U \) gate.

\[\Qcircuit @!C @!R {
&\lstick{\ket{x}} &\ctrl{1}&\rstick{\ket{x}}\qw \\
&\lstick{\ket{y}} &\gate{U}&\rstick{U^{x}\ket{y}}\qw

The CNOT is effectively a controlled-\(X\). Figure <ref> depicts this operation.

\[\Qcircuit @!C @!R {
&\lstick{\ket{x}} &\ctrl{1}&\rstick{\ket{x}}\qw \\
&\lstick{\ket{y}} &\gate{X}&\rstick{X^{x}\ket{y}}\qw

Lastly, Figure <ref> presents the controlled-\(Z\) gate.

\[\Qcircuit @!C @!R {
&\lstick{\ket{x}} &\ctrl{1}&\rstick{\ket{x}}\qw \\
&\lstick{\ket{y}} &\gate{Z}&\rstick{Z^{x}\ket{y}}\qw

Multi-qubit gate(three-qubit gate)

Now, let's expand from a two-qubit gate to a three-qubit gate. For example the Toffoli gate <cit.> is an example of three qubit like Figure <ref> and Figure <ref>

Toffoli gate: when the first two qubits (control qubits) are both 1, flips the third qubit (target qubit). The Figure <ref> shown that.

\[\Qcircuit @!C @!R {
&\lstick{\mid x\rangle} &\ctrl{2}&\rstick{\mid x\rangle}\qw \\
&\lstick{\mid y\rangle} &\ctrl{1}&\rstick{\mid y\rangle}\qw \\
&\lstick{\mid z\rangle} &\targ   &\rstick{\mid z\oplus(x\land y)\rangle}\qw}\]

A Toffoli gate

A complex circuit consisting of a toffoli gate is shown in Figure <ref>.

\[\Qcircuit @!C @!R {
&\lstick{\mid x\rangle} &\ctrl{2} &\qw &\ctrl{2}&\rstick{\mid x\rangle}\qw \\
&\lstick{\mid y\rangle} &\ctrl{1} &\qw &\ctrl{1}&\rstick{\mid y\rangle}\qw \\
&\lstick{\mid 0\rangle} &\targ    &\ctrl{2} &\targ&\rstick{\mid 0\rangle}\qw\\
&\lstick{\mid z\rangle} &\qw      &\ctrl{1} &\qw  &\rstick{\mid z\rangle}\qw\\
&\lstick{\mid w\rangle} &\qw      &\targ    &\qw  &\rstick{\mid w\oplus(x\land y\land z)\rangle}\qw}\]

A complex circuit

Toffoli gate is universal for example in the Figure <ref>.

\[\Qcircuit @!C @!R {
&\lstick{\mid x\rangle} &\ctrl{2}&\rstick{\mid x\rangle}\qw \\
&\lstick{\mid y\rangle} &\ctrl{1}&\rstick{\mid y\rangle}\qw \\
&\lstick{\mid 0\rangle} &\targ   &\rstick{\mid x\land y\rangle}\qw}\]

\[\Qcircuit @!C @!R {
&\lstick{\mid 1\rangle} &\ctrl{2}&\rstick{\mid 1\rangle}\qw \\
&\lstick{\mid 1\rangle} &\ctrl{1}&\rstick{\mid 1\rangle}\qw \\
&\lstick{\mid z\rangle} &\targ   &\rstick{\mid\neg z\rangle}\qw}\]

\[\Qcircuit @!C @!R {
&\lstick{\mid 1\rangle} &\ctrl{2}&\rstick{\mid 1\rangle}\qw \\
&\lstick{\mid y\rangle} &\ctrl{1}&\rstick{\mid y\rangle}\qw \\
&\lstick{\mid 0\rangle} &\targ   &\rstick{\mid y\rangle}\qw}\]

Universal gate

The Fredkin gate <cit.> also is a kind of three-qubit gate. The circuit of Fredkin gate shown in Figure <ref>.

\[\Qcircuit @!C @!R{

The circuit of Fredkin gate

In Fredkin gate <cit.> when $a=0$, the output $w=a, x=b, y=c$, when $a=1$, $b,c$ perform the exchange operation the output $w=a, x=c, y=b$. In other word, when input $a=1$, $b,c$ exchange as output $x=c,y=b$, when $a=0$, $b=x,c=y$ as output.

For $\mid\psi\rangle = \sum\alpha_{x}\mid x\rangle$ , measure in the basis of {$\mid x\rangle$} returns $\mid x\rangle$ with probability $p_{x} = \mid\alpha_{x}\mid^{2}$. The Figure <ref> shown this.

\[\Qcircuit @C=1em @R=.7em {
&\lstick{\mid\phi\rangle}&=&\push{\sum{\alpha_{x}\mid x\rangle}} &{/}\qw &\meter&=&\rstick{\mid x\rangle}}\]

Measurements $\mid\psi\rangle = \sum\alpha_{x}\mid x\rangle$

For $\mid\psi\rangle = \sum\alpha_{x}\mid x\rangle\mid\phi_{x}\rangle$ , measure the first register in the basis of $\{\mid x\rangle\}$ returns $\mid x\rangle_{n}\mid\psi x\rangle$ with probability $p_{x} = \mid\alpha_{x}\mid^{2}$ Figure<ref> shown that.

\[\Qcircuit @C=1em @R=.7em {
&&&&{/}\qw&\meter&\cw&\rstick{\mid x\rangle}\\
&\push{\mid\psi\rangle=\sum\alpha_{x}\mid x
\rangle\mid\phi\rangle}&&\\

Measurements $\mid\psi\rangle = \sum\alpha_{x}\mid x\rangle\mid\phi_{x}\rangle$

Find the output state $\mid\phi\rangle$ of the following circuit:

\[\Qcircuit @!C @!R {
&\lstick{} &\ctrl{1} &\qw &\qw &\meter &\rstick{|0\rangle}\cw\\
&\lstick{\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)} &\ctrl{1} &\gate{H} &\targ &\meter &\rstick{|1\rangle}\cw\\
&\lstick{} &\targ &\qw &\ctrl{-1} &\qw &\rstick{|\phi\rangle}\qw

The example of quantum circuit

The circuit Figure <ref> operation process is shown below:

\begin{align}
\frac{1}{\sqrt{2}}(|000\rangle + |111\rangle&\stackrel{\text{Toffoli}}{\longrightarrow}\frac{1}{\sqrt{2}}(|000\rangle + |110\rangle)\nonumber\\
&\stackrel{\text{H}_2}{\longrightarrow}\frac{1}{\sqrt{2}}[|0\rangle\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)+|1\rangle\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)|0\rangle]\nonumber\\ &\qquad  =\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle)\nonumber\\
&\stackrel{\text{CNOT}_{32}}{\longrightarrow}\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle) \to |\phi\rangle=|0\rangle.
\end{align}

DiVincenzo Criteria

David DiVincenzo, a prominent figure in quantum computing, proposed a set of requirements essential for the realization of a quantum computer. Known as the DiVincenzo criteria <cit.>, these guidelines outline the foundational aspects necessary for the construction and operation of a quantum computer. The five specific criteria are:

* A scalable physical system with well-characterized qubits, allowing for the construction of larger quantum systems while maintaining control over individual qubits.

* The ability to initialize the state of the qubits to a simple fiducial state, which is crucial for setting a known starting point for quantum computations.

* Long relative decoherence times, significantly longer than the gate-operation time, to ensure that quantum states maintain coherence throughout the computation process.

* A universal set of quantum gates, enabling the performance of any quantum computation through a combination of these fundamental operations.

* Qubit-specific measurement capability, allowing for the extraction of information from individual qubits without disturbing the entire quantum system.

Meeting these criteria is essential for any physical system to be considered a viable quantum computer, as they address the key challenges in harnessing and manipulating quantum mechanics for computational purposes.

§ DEUTSCH'S ALGORITHM

Deutsch's algorithm <cit.>, proposed by British scientist David Deutsch in 1985, holds a significant place in the field of quantum computing. It is celebrated for demonstrating the potential of quantum computing to outperform classical computing in specific scenarios. Deutsch's algorithm is often considered one of the most fundamental quantum algorithms, known for its ability to determine properties of functions at a quantum speedup.

The algorithm utilizes a combination of quantum gates, namely the X, H (Hadamard), and CNOT gates, to solve a specific type of problem. This problem involves determining the nature of a given function, showcasing how quantum algorithms can achieve tasks more efficiently compared to their classical counterparts.

Deutsch's problem can be formulated as follows:

Consider a binary function \( f \) defined as:

\begin{equation}
f: \{0, 1\} \to \{0, 1\}
\end{equation}

The function \( f \) has four possible configurations, each representing different scenarios. These scenarios are illustrated in Figure <ref> and include cases where the function outputs are both equal to $0$, invariant under input change, flipped based on the input, or both equal to $1$.

The kind of case of the function $f: \{0, 1\} \to \{0, 1\}$

Based on the input and output results, the four possible configurations of the function \( f \) can be divided into two categories:

* The function \( f \) is balanced if \( f(0) \neq f(1) \). This category includes the “invariant" and “flipped" cases, where the output changes with the input.

* The function \( f \) is constant if \( f(0) = f(1) \). This category encompasses the cases where the output is “both equal to 0" or “both equal to 1", indicating the output remains the same regardless of the input.

Now, consider the function \( f: \{0, 1\} \to \{0, 1\} \) provided as a black box. In this scenario, one can evaluate the function for a given input but cannot inspect the internal mechanism defining \( f \). The challenge is to determine whether \( f \) is balanced or constant using the least number of evaluations. Figure <ref> illustrates the function \( f \) as a black box.

\[\Qcircuit @!C @!R{

Function \( f: \{0, 1\} \to \{0, 1\} \) as a black box.

If the function \( f \) is reversible, we can represent its operation in a quantum circuit as depicted in Figure <ref>. In the context of a quantum computer, consider an initial state \(\ket{x, y}\). The goal is to transform this state using \( f \) in a way that the second part of the state, \( y \), becomes \( y \oplus f(x) \). This operation is a quantum representation of the function \( f \).

To achieve this, we define a unitary operation \( U_{f} \) that maps the initial state \(\ket{x, y}\) to the transformed state \(\ket{x, y \oplus f(x)}\). The mapping is expressed as:

\begin{equation}
U_{f} : \ket{x, y} \to \ket{x, y \oplus f(x)}
\end{equation}

This quantum operation \( U_{f} \) effectively encodes the classical function \( f \) into a quantum circuit, allowing for the superposition and interference properties of quantum mechanics to be harnessed in evaluating the nature of \( f \).

\[\Qcircuit @!C @!R{

\[\Qcircuit @!C @!R{
&\lstick{\mid x\rangle}&\multigate{1}{U_{f}}&\rstick{x}\qw \\
&\lstick{\mid y\rangle}&\ghost{U_{f}}&\rstick{\mid y\oplus f(x)\rangle}\qw}\]

The reversible function convert the initial state to $\mid x,y\oplus f(x)\rangle$.

Next, let's consider the quantum circuit depicted in Figure <ref>. In this setup, we add an \( H \) gate to the first qubit and then apply the operation \( U_{f} \). As a result, the state of the system after these operations, ignoring the factor of \(\sqrt{2}\) for simplicity, will be:

\begin{equation}
\ket{\phi_{2}} = \ket{0, f(0)} + \ket{1, f(1)}
\end{equation}

This equation represents the output state of the circuit, where the first qubit is in a superposition of \(\ket{0}\) and \(\ket{1}\), and the second qubit is transformed based on the function \( f \) applied to the corresponding state of the first qubit.

\[\Qcircuit @!C @!R{
&\lstick{\mid 0\rangle}&\qw&\gate{H}&\qw&\multigate{1}{U_{f}}&\qw&\qw\\
&\lstick{\mid 0\rangle}&\qw&\qw     &\qw&\ghost{U_{f}}       &\qw&\meter\\
&                      &\dstick{\mid\phi_{0}\rangle}& &\dstick{\mid\phi_{1}\rangle}& &\dstick{\mid\phi_{2}\rangle}&&

The circuit.

The process of the Deutsch's algorithm in the quantum circuit can be described step-by-step as follows, ignoring the normalization factor of \(\sqrt{2}\):

\begin{equation}
\ket{\phi_{0}} = \ket{0, 0}
\end{equation}

This is the initial state of the two qubits in the system.

\begin{equation}
\ket{\phi_{1}} = (\ket{0} + \ket{1})\ket{0}
\end{equation}

Here, the first qubit is put into a superposition of \(\ket{0}\) and \(\ket{1}\) using the \( H \) gate, while the second qubit remains in the state \(\ket{0}\).

\begin{equation}
\ket{\phi_{2}} = \ket{0, f(0)} + \ket{1, f(1)}
\end{equation}

In this step, the \( U_{f} \) operation is applied, resulting in the transformation of the second qubit based on the function \( f \) evaluated at the state of the first qubit.

Now, consider the first qubit \(\ket{x}\) and the second qubit \(\ket{1}\). Apply the \( H \) gate to the second qubit, followed by the \( U_{f} \) operation, and then measure the second qubit to obtain the state \(\ket{\phi}\). The circuit for this process is depicted in Figure <ref>.

\[\Qcircuit @!C @!R{
&\lstick{\mid x\rangle}&\qw&\qw&\qw&\multigate{1}{U_{f}}&\qw&\qw\\
&\lstick{\mid 1\rangle}&\qw&\gate{H}     &\qw&\ghost{U_{f}}       &\qw&\meter\\
&                      &\dstick{\mid\phi_{0}\rangle}& &\dstick{\mid\phi_{1}\rangle}& &\dstick{\mid\phi_{2}\rangle}&&

The circuit of $\mid\phi_{0}\rangle=\mid x,1\rangle$.

The process can be further described as follows:

\begin{equation}
\ket{\phi_{0}} = \ket{x, 1}
\end{equation}

This represents the initial state of the system where the first qubit is \(\ket{x}\) and the second qubit is \(\ket{1}\).

\begin{equation}
\ket{\phi_{1}} = \ket{x} (\ket{0} - \ket{1}) = \ket{x, 0} - \ket{x, 1}
\end{equation}

After applying the \( H \) gate to the second qubit, the second qubit is in a superposition of \(\ket{0}\) and \(\ket{1}\) states.

\begin{align}
\ket{\phi_{2}} &= \ket{x, 0 \oplus f(x)} - \ket{x, 1 \oplus f(x)} \nonumber \\
&= \ket{x, f(x)} - \ket{x, \bar{f(x)}} \nonumber \\
&= \ket{x} (\ket{f(x)} - \ket{\bar{f(x)}}).
\end{align}

Here, the \( U_{f} \) operation is applied, affecting the second qubit based on the value of \( f(x) \).

\begin{equation}
\ket{\phi_{2}} =
\begin{cases}
\ket{x} (\ket{0} - \ket{1}), & \text{if } f(x) = 0, \\
\ket{x} (\ket{1} - \ket{0}), & \text{if } f(x) = 1.
\end{cases}
\end{equation}

This equation illustrates the state of the system after applying \( U_{f} \), depending on the function \( f \).

\begin{equation}
\ket{\phi_{2}} = (-1)^{f(x)} \ket{x} (\ket{0} - \ket{1})
\end{equation}

This final form shows the quantum state right before measurement, indicating how the function \( f \) influences the state.

By making slight modifications to the circuit shown in Figure <ref>, we can derive a quantum circuit that implements Deutsch's algorithm. The quantum circuit implementation of Deutsch's algorithm is depicted in Figure <ref>.

\[\Qcircuit @!C @!R{
&\lstick{\mid 0\rangle}&\qw&\gate{H}&\qw&\multigate{1}{U_{f}}&\qw&\gate{H}&\qw&\meter\\
&\lstick{\mid 1\rangle}&\qw&\gate{H}&\qw&\ghost{U_{f}}&\qw&\qw&\qw&\qw\\
&                      &\dstick{\mid\phi_{0}\rangle}& &\dstick{\mid\phi_{1}\rangle}& &\dstick{\mid\phi_{2}\rangle}&&\dstick{\mid\phi_{3}\rangle}

The quantum circuit implementation of Deutsch's algorithm.

In the quantum circuit implementation of Deutsch's algorithm, the process unfolds as follows:

\begin{equation}
\ket{\phi_{0}} = \ket{0, 1}
\end{equation}

This is the initial state with the first qubit in \(\ket{0}\) and the second qubit in \(\ket{1}\).

\begin{equation}
\ket{\phi_{1}} = (\ket{0} + \ket{1})(\ket{0} - \ket{1}) = \ket{0, 0} - \ket{0, 1} + \ket{1, 0} - \ket{1, 1}
\end{equation}

After applying the \( H \) gate to both qubits, we get the first qubit in a superposition of \(\ket{0}\) and \(\ket{1}\), and the second qubit in a superposition of \(\ket{0}\) and \(\ket{1}\), but with a negative sign on \(\ket{1}\).

\begin{align}
\ket{\phi_{2}} &= \ket{0, f(0)} - \ket{0, \bar{f(0)}} + \ket{1, f(1)} - \ket{1, \bar{f(1)}} \nonumber \\
&= (-1)^{f(0)}\ket{0}(\ket{0} - \ket{1}) + (-1)^{f(1)}\ket{1}(\ket{0} - \ket{1}) \nonumber \\
&= [(-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}](\ket{0} - \ket{1}).
\end{align}

After applying the \( U_{f} \) operation, the state reflects the outcome of the function \( f \) applied to both possible inputs.

\begin{equation}
\ket{\phi_{2}} = \begin{cases}
(\pm1)(\ket{0} + \ket{1})(\ket{0} - \ket{1}), & \text{when } f(0) = f(1), \\
(\pm1)(\ket{0} - \ket{1})(\ket{0} - \ket{1}), & \text{when } f(0) \neq f(1).
\end{cases}
\end{equation}

This state indicates whether \( f \) is balanced or constant.

\begin{equation}
\ket{\phi_{3}} = \begin{cases}
(\pm1)\ket{0}(\ket{0} - \ket{1}), & \text{when } f(0) = f(1), \\
(\pm1)\ket{1}(\ket{0} - \ket{1}), & \text{when } f(0) \neq f(1).
\end{cases}
\end{equation}

By measuring the first qubit, we can determine the relationship between \( f(0) \) and \( f(1) \). This quantum circuit can determine if \( f(x) \) is balanced or constant by evaluating \( f(x) \) only once, showcasing an advantage over classical methods.

The Deutsch algorithm only needs to calculate \( f(x) \) once to determine whether \( f(0) = f(1) \).

The key to the Deutsch algorithm's efficiency is the ability to set qubits to a superposition state \(\ket{0} + \ket{1}\) in quantum computing. Thus, \( f(\ket{0}) \) and \( f(\ket{1}) \) can be calculated simultaneously.

While the Deutsch algorithm can determine whether \( f(0) = f(1) \), it does not output the specific values of \( f(0) \) and \( f(1) \). To know these specific values, we must calculate \( f(x) \) twice, aligning with classical computation.

The Deutsch algorithm is seminal in demonstrating the potential superiority of quantum computing. Its extension, the Deutsch-Jozsa algorithm, further explores these concepts. Further study of these algorithms can offer deeper insights into quantum computation.

Brief Summary:

The Deutsch algorithm marks a pivotal point in demonstrating the advantages of quantum computing. It can perform two classical computations simultaneously in a single operation. The algorithm underscores the significance of quantum superposition in computational processes.

§ EXPERIMENT

Now let's do some experiment of the quantum computer. The experiments in this section are all basic experiments, aiming to give students an introductory understanding of quantum computing.(The experiments are all completed on real quantum computers. Due to the influence of noise, there will be a difference between real data and analog data.)

The experiment of reversible logic

Reversible logic <cit.> plays a crucial role in quantum computing due to its fundamental alignment with the principles of quantum mechanics. In this context, let's delve into an experiment demonstrating reversible logic.

Consider two inputs, A and B. These inputs are fed into a quantum circuit, resulting in two outputs, P and Q. To test the reversibility of the logic, we then use P and Q as new inputs and pass them back through the circuit. The outputs obtained from this second pass are denoted as \( P' \) and \( Q' \).

The experiment is considered successful in demonstrating reversible logic if the outputs \( P' \) and \( Q' \) are identical to the original inputs A and B, respectively. This means that \( A = P' \) and \( B = Q' \), indicating that the process is indeed reversible. Figure <ref> illustrates this reversible logic process.

\[\Qcircuit@!C @!R{
&\lstick{B}&\qw     &\gate{X}&\rstick{Q}\qw&\lstick{Q}&\gate{X}&\qw   &\rstick{Q^{'}}\qw}\]

If $A=P^{'}, B=Q^{'}$ we finish the reversible logic experiment.

Now let's see an exmaple of reversible logic(XOR also called CNOT gate).

The XOR gate as Figure <ref>. The gate of U is XOR(CNOT) gate.

\[\Qcircuit @C=1em @R=.7em{
&\lstick{B}&\push{\to}&\ghost{U}&\qw&\push{\to}&\rstick{Q=A\oplus B}}\]

The example of XOR gate.

Thus, it is feasible to construct and implement reversible logic circuits on an actual quantum computer. As depicted in Figure <ref>, we have designed and executed a reversible logic circuit on a real quantum computing platform. This practical execution allows us to observe and verify the principles of reversible logic in a real-world quantum computing environment, thereby concretely demonstrating the concept. The successful completion of this experiment on a quantum computer not only validates the theoretical aspects of reversible logic but also showcases the practical capabilities and potential of quantum computing technology in processing complex computations.

Build with reversible logic ircuit

The experiment of Single qubit gates ($X$, $H$ and $Z$)

In quantum computing the gates $X$, $H$ and $Z$ are three important gates.

First let's build a quantum circuit of gates $X$, $H$ and $Z$. We shown the circuit in Figure <ref>. We set $\mid0\rangle$ as input.

\[\Qcircuit @!C @!R {

\[\Qcircuit @!C @!R {

\[\Qcircuit @!C @!R {

The circuit of gate H, Z and X

Second we build the $H$ and $X$ circuit on a real quantum computer in Figure <ref> we build $H$ gate, in Figure <ref> we build $X$ gate.

Build with $H$ gate circuit in quantum circuit.

Build with $X$ gate circuit in quantum circuit.

Now, let's consider the question: How can we construct a circuit incorporating the \( Z \) gate on an actual quantum computer? To provide a hint, remember that we can convert the state \(\ket{0}\) to \(\ket{1}\) using the \( X \) gate. This conversion is key to demonstrating the effect of the \( Z \) gate, as its impact is more pronounced when applied to the \(\ket{1}\) state.

Figure <ref> illustrates the process of building and implementing a circuit with the \( Z \) gate on a real quantum computer. This example helps to understand how the \( Z \) gate operates within a quantum circuit and how its effects can be observed and analyzed in an actual quantum computing setup.

Build with Z gate circuit in quantum circuit.

Finally we make a measurement. In this way we have completed the gates of $H$, $X$ and $Z$ experiments.

The experiment of Two-qubit gates (CNOT)

The Controlled-NOT (CNOT) gate
is a fundamental element in quantum computing, playing a pivotal role in the manipulation and entanglement of qubits.

To explore the functionalities and implications of the CNOT gate, we will conduct an experiment contrasting it with the classical XOR gate. The first step in this process is to construct a quantum circuit that incorporates the CNOT gate.

Figure <ref> illustrates the designed circuit that integrates the CNOT gate.

\[\Qcircuit @!C @!R{
&\lstick{\mid x\rangle}&\ctrl{1}&\rstick{\mid x\rangle}\qw\\
&\lstick{\mid y\rangle}&\targ&\rstick{\mid x\oplus y\rangle}\qw}\]

The CNOT gate circuit

Second we build with CNOT gate circuit on a real quantum computer shown in Figure <ref>.

The CNOT gate circuit on a real quantum computer

Finally we make a measurement. In this way we have completed the CNOT gate experiment.

The Experiment of Bell states

The Figure<ref> shown the SpinQ experiments for Bell states <cit.>. With SpinQ we can achieve the Bell states

The SpinQ experiments for Bell states.

The Experiment of Deutsch's Algorithm

Deutsch's Algorithm <cit.> is a pivotal algorithm in the field of quantum computing, known for demonstrating the potential of quantum algorithms to outperform classical ones in specific scenarios.

To explore the practical implementation and effectiveness of Deutsch's Algorithm, we will conduct an experiment by constructing and executing its quantum circuit. This experiment aims to demonstrate the algorithm's ability to determine properties of functions more efficiently than classical computing methods.

The first step in this experiment is to build the quantum circuit that represents Deutsch's Algorithm. The design of this circuit, which is crucial for the experiment, is depicted in Figure <ref>. This circuit serves as the foundation for demonstrating the algorithm's functionality and showcases how quantum superposition and interference are harnessed to achieve computational advantages in quantum computing.

\[\Qcircuit @!C @!R{
&\lstick{\mid 0\rangle}&\qw&\gate{H}&\qw&\multigate{1}{U_{f}}&\qw&\gate{H}&\qw&\meter\\
&\lstick{\mid 1\rangle}&\qw&\gate{H}&\qw&\ghost{U_{f}}&\qw&\qw&\qw&\qw\\
&                      &\push{\mid\phi_{0}\rangle}& &\push{\mid\phi_{1}\rangle}& &\push{\mid\phi_{2}\rangle}&&\push{\mid\phi_{3}\rangle}

The quantum circuit implementation of Deutsch's algorithm.

Next, we proceed to implement this circuit on an actual quantum computer. This step involves interacting with the quantum computer's interface. Specifically, we select the "Case" option on the right side of the interface, choose the appropriate algorithm category, and then select "Deutsch's Algorithm" from the list. Once selected, we initiate the simulation to observe the algorithm in action.

This process is illustrated in Figure <ref>, which shows how the circuit for Deutsch's Algorithm is set up and run on a quantum computing platform. Running this simulation on a real quantum computer allows us to observe firsthand the workings of Deutsch's Algorithm and its ability to efficiently determine properties of functions, thereby reinforcing its significance in the realm of quantum computation.

The case of Deutsch algorithm circuit on a real quantum computer

Once the simulation of Deutsch's Algorithm is run on the quantum computer, the next step is to observe and record the projection probabilities of the four quantum states \(\ket{00}\), \(\ket{01}\), \(\ket{10}\), and \(\ket{11}\). These probabilities provide crucial insights into the behavior of the algorithm.

The recorded probabilities are displayed in Figure <ref>. By analyzing these results, we can discern the relationship between \(f(0)\) and \(f(1)\). This analysis is pivotal in determining whether the quantum circuit correctly implements Deutsch's Algorithm. Specifically, the relative probabilities of these four states indicate whether the function \(f\) used in the experiment is balanced or constant, thus validating the algorithm's performance.

The Deutsh algorithm experiment result

From the observed results, if the first qubit consistently outputs \(1\), it indicates that the function \(f\) is balanced, meaning \(f(1) \neq f(0)\). This conclusion is drawn from the principle that Deutsch's Algorithm determines whether the function \(f\) applied to the qubits is constant (the same output for both inputs) or balanced (different outputs for each input). Therefore, the outcome where the first qubit is in the state \(1\) directly reflects the nature of \(f\) as a balanced function.

CHAPTER: WEEK 3: MATRIX REPRESENTATION OF QUANTUM GATES

Last week, we dipped our toes into the intriguing world of quantum computing with a brief look at Deutsch's algorithm, exploring it through the lens of counting rather than delving into matrices. This week, we're ready to take a step further. We'll begin by introducing two key concepts: vectors, which we'll use to describe quantum states, and matrices, serving as the tools to manipulate these states. Think of this as learning the alphabet and grammar of the quantum computing language. As we grow more comfortable with these ideas, we'll expand our exploration to multi-qubit systems, where the real magic of quantum computing begins to unfold. This journey will lay the groundwork for understanding how quantum computers can perform complex tasks that are currently beyond the capabilities of classical computers. By the end of this chapter, you’ll have a foundational understanding of quantum states and operations, setting you up perfectly for the exciting world of quantum algorithms.

§ VECTORS AND MATRICES

Bits and vectors

In our previous discussions, we saw how classical bits are the simplest units in computing, representing either 0 or 1. In quantum computing, we use something similar but more powerful: qubits <cit.>. Let's see how we can represent both classical bits and qubits using vectors, which are just lists of numbers arranged in a certain way.

In the world of classical computing, we can represent a bit using a 2D column vector <cit.>. A bit with a value of 0 is shown as $\begin{bmatrix} 1\\0 \end{bmatrix}$, and a bit with a value of 1 is shown as $\begin{bmatrix} 0\\1 \end{bmatrix}$.

Quantum bits, or qubits, have a similar representation <cit.>. The quantum state $|0\rangle$, which is analogous to the classical 0 bit, is represented as $\begin{bmatrix} 1\\0 \end{bmatrix}$. Similarly, the quantum state $|1\rangle$, like the classical 1 bit, is represented as $\begin{bmatrix} 0\\1 \end{bmatrix}$.

But there's something unique about qubits: they can be in a state called superposition <cit.>, which means they can be a bit of both 0 and 1 at the same time! We can express a general qubit state $|\varphi\rangle$ as a combination (or superposition) of $|0\rangle$ and $|1\rangle$, which looks like this: $|\varphi\rangle=a|0\rangle+b|1\rangle$. When we use the vector representation, this becomes:

\begin{equation}
|\varphi\rangle=a|0\rangle+b|1\rangle = a\begin{bmatrix} 1  \\ 0 \end{bmatrix}+b\begin{bmatrix} 0  \\ 1 \end{bmatrix}=\begin{bmatrix} a  \\ b \end{bmatrix}.
\end{equation}

In this vector, $a$ and $b$ are numbers that tell us how much of $|0\rangle$ and $|1\rangle$ are in the superposition. For example, if we have an equal mix of $|0\rangle$ and $|1\rangle$, it looks like this:

\begin{equation}
|\varphi\rangle=\frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle \to \begin{bmatrix} \frac{1}{\sqrt{2}}  \\ \frac{1}{\sqrt{2}} \end{bmatrix}.
\end{equation}

Gates and matrices

Now, let's talk about how we can use matrices to represent operations in quantum computing, similar to how we use commands in a computer program. In classical computing, there's a simple operation called the NOT gate, which flips a bit <cit.>. If the bit is 0, it turns it to 1, and if it's 1, it turns it to 0. We already know that bits can be represented as vectors: 0 as $\begin{bmatrix} 1\\0 \end{bmatrix}$ and 1 as $\begin{bmatrix} 0\\1 \end{bmatrix}$. The NOT gate's function, which inverts a bit, can be represented using a matrix. The matrix for a NOT gate looks like this <cit.>:

\begin{equation}
\begin{bmatrix}
\end{bmatrix}.\nonumber
\end{equation}

In this matrix, the first row tells us what happens when the input is 0, and the second row tells us what happens when the input is 1. Basically, the matrix captures the entire function of the NOT gate.

When we apply this matrix to a bit, it's like giving a command to the bit. For example, let's apply the NOT matrix to the bit 0 (represented as $\begin{bmatrix} 1\\0 \end{bmatrix}$):

\begin{equation}
\text{NOT} \times \begin{bmatrix} 1\\0 \end{bmatrix} =
\begin{bmatrix}
\end{bmatrix} \times \begin{bmatrix}
\end{bmatrix} =\begin{bmatrix}
\end{bmatrix},
\end{equation}

which is the vector representation of 1, showing that the input 0 has been flipped to 1. Similarly, if we apply the NOT gate to 1 (represented as $\begin{bmatrix} 0\\1 \end{bmatrix}$), it will flip it to 0. This way, matrices provide us with a neat and powerful way to represent and understand the operations of gates in quantum computing.

The rule of matrix arithmetic

In this section, we'll look at some basic rules for doing math with matrices. A matrix is like a big box filled with numbers, arranged in rows and columns. These numbers can be simple numbers (like the ones we use every day) or more complex ones.

Let's consider a matrix called A:

\begin{equation}
\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{bmatrix}.
\end{equation}

Here, each number in the matrix is called an element. The element in row $j$ and column $k$ is denoted as $a_{jk}$, where $j$ is the number of rows and $k$ is the number of columns.

Now, consider another matrix B, also with dimensions $m \times n$. We can define arithmetic operations between these matrices <cit.>:

* Addition: $(A + B)[j,k] = A[j,k] + B[j,k]$

* Scalar Multiplication: $(c \cdot A)[j,k] = c \times A[j,k]$

* Inverse: $(-A)[j,k] = -(A[j,k])$

* Matrix Multiplication:

Consider two matrices: A (dimensions $m \times n$) and B (dimensions $n \times s$). Their matrix product AB will be a new matrix with dimensions $m \times s$.

The multiplication rule is:

\begin{equation}
(AB)[j,k] = \sum_{h=0}^{n-1} (A[j,h] \times B[h,k]).
\end{equation}

Where we sum the products of entries from row $j$ of A and column $k$ of B.

\begin{equation}
\begin{bmatrix} 0 & 1\\1 & 0 \end{bmatrix}
\times \begin{bmatrix} 1\\0 \end{bmatrix} =
\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 0 & 1\\1 & 0 \end{bmatrix}
\times \begin{bmatrix} 0\\1 \end{bmatrix} =
\begin{bmatrix} 1\\0 \end{bmatrix}.
\end{equation}

Here's an important thing to remember: In matrix multiplication, the order matters! Unlike regular numbers, where \(2 \times 3\) is the same as \(3 \times 2\), with matrices, A multiplied by B (\({A}{B}\)) can be different from B multiplied by A (\({B}{A}\)) <cit.>. Generally:

\begin{equation}
AB \neq BA.
\end{equation}

Let's see this with a simple example. Consider two matrices:

\begin{equation}
{A} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad {B} = \begin{bmatrix} 2 & 0 \\ 1 & 2 \end{bmatrix}.
\end{equation}

Now, if we multiply A by B, we get:

\begin{equation}
AB = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \times \begin{bmatrix} 2 & 0 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 1\cdot2 + 2\cdot1 & 1\cdot0 + 2\cdot2 \\ 3\cdot2 + 4\cdot1 & 3\cdot0 + 4\cdot2 \end{bmatrix} = \begin{bmatrix} 4 & 4 \\ 10 & 8 \end{bmatrix}.
\end{equation}

But, if we flip the order and multiply B by A, we get a different result:

\begin{equation}
BA = \begin{bmatrix} 2 & 0 \\ 1 & 2 \end{bmatrix} \times \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} = \begin{bmatrix} 2\cdot1 + 0\cdot3 & 2\cdot2 + 0\cdot4 \\ 1\cdot1 + 2\cdot3 & 1\cdot2 + 2\cdot4 \end{bmatrix} = \begin{bmatrix} 2 & 4 \\ 7 & 10 \end{bmatrix}.
\end{equation}

So, in this case, \(AB \neq BA\).

This rule is important in quantum computing, as the order of operations can change the outcome of a computation!

Matrix multiplication isn't just a cool math trick; it's super useful, especially in quantum computing. To make these calculations easier, we can use software like Matlab <cit.> and Octave <cit.>. These tools are like calculators for matrices, helping us multiply and manipulate them without getting lost in all the numbers.

When we get the hang of multiplying matrices, we can start to represent a bunch of operations all together in a really neat and tidy way. It's like having a recipe where each step is clearly laid out, but instead of cooking, we're doing quantum computing!

The rules for working with matrices are pretty straightforward. Once we understand them, we can mix and match matrices to represent complex processes or rules in a simple and clear manner. It's a bit like putting together LEGO bricks to build something big and intricate – each brick (or matrix) has its place and role.

Mastering matrix arithmetic is a key step in unlocking the full potential of matrix computation. It's not just about doing math; it's about gaining a powerful tool to understand and analyze complex operations in quantum computing and beyond. So, diving into the world of matrices is definitely worth the effort!

§ ONE BIT/QUBIT VECTOR AND GATES

Representations of the NOT Gate

In the world of digital circuits, logic gates are like the basic building blocks. One of these is the NOT gate, which is pretty straightforward but super important. In Figure <ref>, we have a classic diagram of a NOT gate. It might look simple, but there are different ways to understand what it does <cit.>:

Classic NOT-gate logic diagram.

* Functional View: Think of the NOT gate as a function, which we'll call $f(x)$. This function has a simple job: if it gets a 0, it gives back a 1, and if it gets a 1, it gives back a 0. So, $f(0) = 1$ and $f(1) = 0$.

* Truth Table: To see this in a more organized way, we use a truth table. This table is like a quick reference guide that shows what the output will be for each possible input:

Input     Output

0     1

1     0

* Matrix Representation: Now, let's talk matrices. We can represent the NOT gate as a matrix too! The matrix for a NOT gate looks like this <cit.>:

\begin{equation}
\mathrm{NOT} =
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix}.
\end{equation}

When we apply this matrix to the vectors $\begin{bmatrix}1\end{bmatrix}$ and $\begin{bmatrix}0\end{bmatrix}$ (which represent the bits 0 and 1), it flips them, just like the NOT function does <cit.>:

\begin{equation}
\mathrm{NOT} \times \begin{bmatrix}1\end{bmatrix} = \begin{bmatrix}0\end{bmatrix},
\mathrm{NOT} \times \begin{bmatrix}0\end{bmatrix} = \begin{bmatrix}1\end{bmatrix}.
\end{equation}

These three ways of looking at the NOT gate help us understand it from different angles. Whether it's through a function, a table, or a matrix, each perspective adds to our understanding of how we can use logic gates to control and manipulate information.

Single qubit gates and matrices

In the quantum computing world, we encounter fascinating tools known as quantum gates. These gates are fundamental in building quantum circuits, where they manipulate the states of qubits in specific ways. One such gate is the NOT gate, known in quantum computing as the $X$ gate. This gate is crucial for flipping the state of a qubit <cit.>:

\begin{align}
X|0\rangle = |1\rangle,\nonumber\\
X|1\rangle = |0\rangle.
\end{align}

Transformations like these are essential in quantum computations, enabling unique processing and manipulation of information.

Each quantum gate corresponds to a specific matrix. For the $X$ gate, the matrix representation is:

\begin{equation}
X =
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix}.
\end{equation}

When this matrix multiplies a qubit state vector, it executes the NOT operation:

\begin{equation}
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix} \times \begin{bmatrix}
1\\ 0
\end{bmatrix}=\begin{bmatrix}
0\\ 1
\end{bmatrix},
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix} \times \begin{bmatrix}
0\\ 1
\end{bmatrix}=\begin{bmatrix}
1\\ 0
\end{bmatrix}.
\end{equation}

The $X$ gate, however, is just one member of a diverse family of quantum gates. For instance, the Hadamard gate, represented as $H$, is notable for creating superpositions of $|0\rangle$ and $|1\rangle$. The matrix for $H$ is <cit.>:

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

Applying $H$ to $|0\rangle$ results in $\frac{(|0\rangle+|1\rangle)}{\sqrt{2}}$, and applying it to $|1\rangle$ yields $\frac{(|0\rangle-|1\rangle)}{\sqrt{2}}$.

Another vital gate in single-qubit operations is the Phase Gate, denoted as $Z$. The $Z$ gate is unique in that it doesn't change the $|0\rangle$ state but flips the sign of the $|1\rangle$ state:

\begin{align}
Z|0\rangle &= |0\rangle,\nonumber\\
Z|1\rangle &= -|1\rangle.
\end{align}

The matrix for $Z$ is:

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

When applied, the $Z$ gate leaves the $|0\rangle$ state unchanged, while it flips the sign of the amplitude for the $|1\rangle$ state:

\begin{equation}
\begin{bmatrix}
1&0 \\0&-1\end{bmatrix} \times \begin{bmatrix}
1\\0\end{bmatrix} = \begin{bmatrix}
1&0 \\0&-1\end{bmatrix} \times \begin{bmatrix}
0\\1\end{bmatrix} = -\begin{bmatrix}
\end{equation}

Gates like $X$, $H$, and $Z$ are crucial in quantum computing, enabling control and manipulation of qubit states <cit.>. Understanding their matrix representations allows us to analyze and simulate quantum circuits and algorithms, demonstrating the transformative potential of quantum computing for solving complex problems.

In quantum computing, we can construct some quantum gates by cleverly combining other gates. A fascinating example is how we can create the phase gate $Z$ using the NOT gate $X$ and the Hadamard gate $H$ <cit.>:

\begin{align}
HZH = X,\nonumber\\
HXH = Z.
\end{align}

To see how this works, let's examine their matrix representations. The matrix for the Hadamard gate $H$ is defined as:

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

By performing the matrix multiplication, we can validate the relationships:

\begin{equation}
HZH=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\times\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\times\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}=X.
\end{equation}

Similarly, for $HXH = Z$:

\begin{equation}
HXH=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\times\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\times\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}=\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}=Z.
\end{equation}

These calculations show that the Hadamard gate $H$ can transform between the $X$ and $Z$ gates. This example illustrates the power of combining elementary quantum gates to create more complex operations on qubits, a fundamental aspect of quantum computing.

§ TWO BITS/QUBITS VECTORS AND GATES

Bits and vectors

In quantum computing, it's fascinating how we can represent bitstrings, or sequences of bits, as vectors. This method becomes particularly handy when dealing with more complex systems, like those with two bits or qubits. Let's dive into how this works for a two-bit system.

Consider all the possible combinations in a two-bit system: $00$, $01$, $10$, and $11$. Each of these bitstrings can be represented as a unique vector, with the position of the `1' in the vector indicating the value of the bitstring. Here's how we can depict each bitstring as a vector <cit.>:

$00 \to \begin{bmatrix} 1 \\0 \\0\\0\end{bmatrix},\quad 01 \to \begin{bmatrix} 0 \\1 \\0\\0\end{bmatrix},\quad 10 \to \begin{bmatrix} 0 \\0 \\1\\0\end{bmatrix},\quad 11 \to \begin{bmatrix} 0 \\0 \\0\\1\end{bmatrix}$.

In these representations, the position of the `1' in each vector corresponds to the specific bitstring it represents. For instance, the vector $\begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}$ represents the bitstring `10' because the `1' is in the third position, corresponding to the third possibility in our two-bit system.

This vector representation becomes even more powerful in quantum computing. In quantum systems, the elements of these vectors (known as amplitudes) can represent superpositions of multiple states. This means a quantum state can be a combination of several different bitstrings at the same time, unlike in classical computing where a bit is definitely either 0 or 1. Understanding this concept is key to grasping the fundamentals of quantum computing and how it differs from classical computing.

Gates and matrices

In both classical and quantum computing, representing bitstrings as vectors provides a consistent mathematical framework for mapping bitstrings onto states. Operations on bitstrings, such as AND, OR, NAND gates, correspond to specific manipulations of these state vectors.

Consider the AND gate, as shown in Figure <ref>. This gate performs a logical AND operation on two input bits <cit.>.

Classic AND-gate logic diagram.

Functionally, the AND gate outputs 1 only if both its input bits are 1. This can be expressed as:

\begin{equation}
f(00) = 0, f(01) = 0, f(10) = 0, f(11) = 1. \nonumber
\end{equation}

The truth table for the AND gate is:

$00 \to 0$

$01 \to 0$

$10 \to 0$

$11 \to 1$.

We can represent the AND operation using a matrix:

\begin{equation}
\text{AND} = \begin{bmatrix}
\end{bmatrix}.
\end{equation}

This matrix, when multiplied by an input vector, performs the AND operation on the bits. For example, applying the AND gate to the input $00$:

\begin{equation}
\text{AND}(00) = 0.
\end{equation}

The multiplication of the AND matrix with the vector representation of $00$ is:

\begin{equation}
\text{AND} = \begin{bmatrix}
\end{bmatrix}, 00=\begin{bmatrix}
\end{bmatrix}.
\end{equation}

This results in:

\begin{equation}
\begin{bmatrix}
\end{bmatrix} \times \begin{bmatrix}
\end{bmatrix}  =\begin{bmatrix}
\end{bmatrix}= 0.
\end{equation}

Hence, the AND gate maps the input $00$ to the state vector corresponding to 0, as expected. In general, multiplying the AND matrix with any input vector performs the AND logic operation on the bit values.

As depicted in Figure <ref>, we see a classic OR-gate logic diagram. The OR gate is another fundamental component in digital logic <cit.>.

Classic OR-gate logic diagram.

Now, let's examine the operation of the OR gate when it acts on the input $00$:

\begin{equation}
\text{OR}(00) = 0.
\end{equation}

To understand this operation in terms of matrix multiplication, we represent the OR operation as a matrix and multiply it with the vector representation of $00$ <cit.>:

\begin{equation}
\text{OR} = \begin{bmatrix}
\end{bmatrix}, \quad 00=\begin{bmatrix}
\end{bmatrix}.
\end{equation}

The result of this multiplication is:

\begin{equation}
\begin{bmatrix}
\end{bmatrix} \times \begin{bmatrix}
\end{bmatrix}  =\begin{bmatrix}
\end{bmatrix}= 0.
\end{equation}

As anticipated, the OR gate maps the input $00$ to the state vector corresponding to 0.

More generally, when we multiply the OR matrix with any input vector, it effectively carries out the logical OR operation on the bit values. Just like the AND gate, this matrix formulation allows us to conceptualize the OR operation as a linear transformation applied to bit vectors. This approach will be extended to understanding how quantum gates operate on qubit state vectors in quantum computing.

The NAND gate performs a NOT-AND operation on two bits. Figure <ref> illustrates a classic NAND-gate logic diagram.

Classic NAND-gate logic diagram.

Functionally, the NAND gate can be described as <cit.>:

\begin{equation}
f(00) = 1, f(01) = 1, f(10) = 1, f(11) = 0.\nonumber
\end{equation}

It essentially inverts the output of an AND gate. The truth table for NAND is:

$00 \to 1$

$01 \to  1$

$10 \to  1$

$11 \to  0 $

The matrix representation of NAND is:

\begin{equation}
\text{NAND} = \begin{bmatrix}
\end{bmatrix}.
\end{equation}

When this matrix multiplies input vectors, it effectively flips the output of an AND operation.

The NAND gate demonstrates how basic logic gates can be combined to create more complex operations. The matrix formulation provides a systematic way to manipulate these composite gates <cit.>.

Figure <ref> shows the construction of a NAND gate from AND and NOT gates:

\begin{equation}
\text{NAND} = \text{NOT} \times \text{AND}.
\end{equation}

NAND-gate construction.

The matrix for the NOT gate is:

\begin{equation}
\text{NOT} = \begin{bmatrix}
\end{bmatrix}.
\end{equation}

And the matrix for the AND gate is:

\begin{equation}
\text{AND} = \begin{bmatrix}
\end{bmatrix}.
\end{equation}

Multiplying these matrices gives:

\begin{equation}
\text{NOT} \times \text{AND} = \begin{bmatrix}
\end{bmatrix} \times \begin{bmatrix}
\end{bmatrix}=\begin{bmatrix}
\end{bmatrix}.
\end{equation}

This results in the NAND matrix, illustrating how we can construct complex gates like NAND from simpler gates such as AND and NOT using matrix operations. This approach is extendable to the construction of complex quantum operations from basic quantum gates.

Two-qubit gates

An important two-qubit gate is the controlled-NOT (CNOT) gate. This flips the second qubit if the first qubit is $|1\rangle$:

\begin{equation}
|x\rangle \otimes |y\rangle \to  |x\rangle \otimes |y \oplus x\rangle.
\end{equation}

Where $\oplus$ is addition modulo 2.

In the computational basis ${|00\rangle, |01\rangle, |10\rangle, |11\rangle}$, the CNOT matrix is <cit.>:

\begin{equation}
\text{CNOT} = \begin{pmatrix}1 &0& 0& 0\\
0 &1 &0 &0\\0& 0& 0 &1\\
0& 0& 1 &0
\end{pmatrix}.
\end{equation}

We can also construct a CNOT with the second qubit as control, taking $|x\rangle \otimes |y\rangle$ to $|x\oplus y\rangle \otimes|y\rangle$. As shown in Figure <ref>. In the left diagram of Figure <ref>, flips $|y\rangle$ if $|x\rangle = |1\rangle$. In the right diagram of Figure <ref>, flips $|x\rangle$ if $|y\rangle = |1\rangle$.

\[\Qcircuit @!C @!R {
&\lstick{|x\rangle} &\ctrl{1}  & \rstick{|x\rangle}\qw  & &  &\lstick{|x\rangle} &\targ    & \rstick{|x \oplus y\rangle}\qw \\
&\lstick{|y\rangle} &\targ    & \rstick{|y \oplus x\rangle}\qw &   & & \lstick{|y\rangle} &\ctrl{-1}  & \rstick{|y\rangle}\qw

A CNOT with the second qubit as control.

CNOT allows qubit-qubit interactions and entanglement in multi-qubit systems.

Another two-qubit gate is the controlled-Z (CZ) gate. This applies a phase flip to the second qubit if the first qubit is $|1\rangle$:

$|00\rangle \to |00\rangle$

$|01\rangle \to |01\rangle$

$|10\rangle \to |10\rangle$

$\quad|11\rangle \to -|11\rangle$.

The CZ gate is symmetric so the control/target roles are interchangeable. In the computational basis, the CZ matrix is <cit.>:

\begin{equation}
CZ =  \begin{pmatrix}
1& 0 &0 &0\\
0 &1& 0& 0\\
0& 0& 1 &0\\
0 &0 &0& -1
\end{pmatrix}.
\end{equation}

Figure <ref> depicts the graphical representation of the CZ gate.

\[\Qcircuit @!C @!R {
&\lstick{|x\rangle} &\ctrl{1}  & \rstick{|x\rangle}\qw \\
&\lstick{|y\rangle} &\control\qw & \rstick{(-1)^{xy}|y\rangle }\qw}\]

Circuit representation of the CZ gate.

Applies phase $(-1)^{xy}$ to $|y\rangle$ if $|x\rangle = |1\rangle$.

CZ creates entanglement between the two qubits. Multi-qubit gates like CZ and CNOT are key to quantum algorithms.

§ TENSOR PRODUCTS

In quantum computing, single-qubit states $|0\rangle$ and $|1\rangle$ can be expressed as vectors
1\\ 0
\end{bmatrix}$
0\\ 1
\end{bmatrix}$, respectively. Similarly, two-qubit states like $|00\rangle$, $|01\rangle$, $|10\rangle$, and $|11\rangle$ can be expressed as the vectors
1\\ 0\\ 0\\ 0
\end{bmatrix}$,
0\\ 1\\ 0\\ 0
\end{bmatrix}$,
0\\ 0\\ 1\\ 0
\end{bmatrix}$,
0\\ 0\\ 0\\ 1
\end{bmatrix}$.

To combine two single qubits into a two-qubit system, we use a mathematical operation known as the tensor product. The tensor product, denoted by $\otimes$, allows us to calculate the vector representation of the combined state.

Calculate the tensor product of $|1\rangle \otimes |1\rangle$.

To find the tensor product of $|1\rangle \otimes |1\rangle$, we first express each qubit as its vector representation:
$|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$.

The tensor product is calculated by multiplying each element of the first vector by the entire second vector:

\begin{align*}
|1\rangle \otimes |1\rangle & = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \otimes \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\
& = \begin{bmatrix} 0 \times \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ 1 \times \begin{bmatrix} 0 \\ 1 \end{bmatrix} \end{bmatrix} \\
& = \begin{bmatrix} 0 \times 0 \\ 0 \times 1 \\ 1 \times 0 \\ 1 \times 1 \end{bmatrix} \\
& = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}.
\end{align*}

Thus, the tensor product of $|1\rangle \otimes |1\rangle$ results in the vector representation of the two-qubit state $|11\rangle$, which is $\begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$.

This process of using tensor products is fundamental in building multi-qubit systems from single-qubit states in quantum computing.

The symbol for the tensor product in mathematics and quantum computing is $\otimes$. This operation is particularly important in quantum computing for combining states. For example, the tensor product of two vectors is expressed as follows <cit.>:
a_0\\ a_1\\ a_2\\ a_3
\end{bmatrix}$ $\otimes$
b_0\\ b_1
\end{bmatrix}$.

The rules for the tensor product of vectors are as follows:

* If vector A has $m$ elements and vector B has $n$ elements, their tensor product results in a new vector with $m \times n$ elements.

* The $i$th element of vector A is multiplied by the $j$th element of vector B to form the $(i \times n + j)$th element of the new vector.

For example, the tensor product of two vectors A and B is calculated as:

\begin{equation}
\begin{bmatrix}
a_0\\ a_1\\ a_2\\ a_3
\end{bmatrix} \otimes
\begin{bmatrix}
b_0\\ b_1
\end{bmatrix} =
\begin{bmatrix}
a_0b_0\\ a_0b_1\\a_1b_0\\a_1b_1\\a_2b_0\\a_2b_1\\a_3b_0\\a_3b_1
\end{bmatrix},
\end{equation}

and the general formula can be expressed as:

\begin{equation}
\begin{bmatrix}
a_0\\ a_1\\ \vdots\\ a_{m-1}
\end{bmatrix} \otimes
\begin{bmatrix}
b_0\\ b_1\\ \vdots \\b_{n-1}
\end{bmatrix} =
\begin{bmatrix}
a_0b_0\\ \vdots\\ a_0b_{n-1}\\a_1b_0\\ \vdots\\ a_1b_{n-1}\\ \vdots\\a_{m-1}b_{n-1}
\end{bmatrix}.
\end{equation}

For a qubit, the tensor product can be expressed as:

\begin{equation}
|0\rangle \otimes |0\rangle \otimes |0\rangle
= \begin{bmatrix} 1\\ 0 \end{bmatrix} \otimes \begin{bmatrix} 1\\ 0 \end{bmatrix} \otimes \begin{bmatrix} 1\\ 0 \end{bmatrix}
= \begin{bmatrix} 1\\ 0 \\0 \\0 \end{bmatrix} \otimes \begin{bmatrix} 1\\ 0 \end{bmatrix}
= \begin{bmatrix} 1\\ 0 \\0 \\0 \\0 \\0 \\0 \\0 \end{bmatrix} = |000\rangle.
\end{equation}

Similarly, calculate the tensor product of $|010\rangle$.

The tensor product is a fundamental operation in quantum computing with several important properties <cit.>:

1. A tensor product of a vector A with \( m \) elements and a vector B with \( n \) elements results in a new vector C with \( m \times n \) elements. However, a vector with \( m \times n \) elements is not necessarily the result of a tensor product of two vectors with \( m \) and \( n \) elements. It can also be a sum of tensor products of several vectors.

Consider the vector

\begin{equation}
\begin{bmatrix} 1\\ 0\\ 0\\1 \end{bmatrix} \neq \begin{bmatrix} x\\ y \end{bmatrix} \otimes \begin{bmatrix} a\\ b \end{bmatrix} = \begin{bmatrix} xa\\ xb\\ya \\yb \end{bmatrix},
\end{equation}

\begin{equation}
\begin{bmatrix} 1\\ 0\\ 0\\1 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix} \otimes \begin{bmatrix} 1\\ 0 \end{bmatrix} + \begin{bmatrix} 0\\ 1 \end{bmatrix} \otimes \begin{bmatrix} 0\\ 1 \end{bmatrix}.
\end{equation}

2. The tensor product does not satisfy the commutative law, meaning \( A \otimes B \neq B \otimes A \).

For instance:

\begin{equation}
\begin{bmatrix} 1\\ 0 \end{bmatrix} \otimes \begin{bmatrix} 0\\ 1 \end{bmatrix} \neq \begin{bmatrix} 0\\ 1 \end{bmatrix} \otimes \begin{bmatrix} 1\\ 0 \end{bmatrix},
\begin{bmatrix} 0\\ 1 \end{bmatrix} \otimes \begin{bmatrix} 8\\ 0 \\0 \end{bmatrix} \neq \begin{bmatrix} 8\\ 0 \\0 \end{bmatrix} \otimes \begin{bmatrix} 0\\ 1 \end{bmatrix}.
\end{equation}

3. The tensor product operation satisfies the associative law, such that \((A \otimes B) \otimes C = A \otimes (B \otimes C)\).

Here is an example:

\begin{equation}
\left(
\begin{bmatrix} a_0\\ a_1 \end{bmatrix} \otimes \begin{bmatrix} b_0\\ b_1  \end{bmatrix}\right) \otimes \begin{bmatrix} c_0\\ c_1 \end{bmatrix}  =
\begin{bmatrix} a_0b_0c_0\\ a_0b_0c_1\\a_0b_1c_0\\a_0b_1c_1\\a_1b_0c_0\\a_1b_0c_1\\a_1b_1c_0\\a_1b_1c_1 \end{bmatrix} = \begin{bmatrix} a_0\\ a_1 \end{bmatrix} \otimes \left(
\begin{bmatrix} b_0\\ b_1 \end{bmatrix} \otimes \begin{bmatrix} c_0\\ c_1  \end{bmatrix}\right).
\end{equation}

4. Expressing a 3-bit string (e.g., 101) or 3 qubits (e.g., \( |1 \rangle \otimes |0 \rangle \otimes |1\rangle \)) results in a vector with \( 2^3 = 8 \) elements. Generally, expressing \( n \) qubits yields a vector with \( 2^n \) elements.

For instance:

\begin{equation}
|1\rangle \otimes |0\rangle \otimes |1\rangle
= \begin{bmatrix} 0\\ 1 \end{bmatrix} \otimes \begin{bmatrix} 1\\ 0 \end{bmatrix} \otimes \begin{bmatrix} 0\\ 1 \end{bmatrix}
= \begin{bmatrix} 0\\ 0 \\1 \\0 \end{bmatrix} \otimes \begin{bmatrix} 0\\ 1 \end{bmatrix}
= \begin{bmatrix} 0\\ 0 \\0 \\0 \\0 \\1 \\0 \\0 \end{bmatrix} = |101\rangle.
\end{equation}

The tensor product is an essential operation in quantum computing, particularly useful for constructing larger matrices from smaller ones. Let's consider two sample matrices $A$ and $B$, where $A$ is a $2\times 2$ matrix and $B$ is a $3\times 3$ matrix. The tensor product $A\otimes B$ involves multiplying each element of $A$ by the entire matrix $B$. This process results in a new $6\times 6$ matrix.

Let's define matrices $A$ and $B$ as follows:

\begin{align}
A = \begin{bmatrix}
a_{00} & a_{01}\\
a_{10} & a_{11}
\end{bmatrix},
B = \begin{bmatrix}
b_{00} & b_{01} & b_{02}\\
b_{10} & b_{11} & b_{12}\\
b_{20} & b_{21} & b_{22}
\end{bmatrix}.
\end{align}

Then, the tensor product $A \otimes B$ is calculated as:

\begin{align}
A \otimes B = \begin{bmatrix}
a_{00}B & a_{01}B\\
a_{10}B & a_{11}B
\end{bmatrix}
= \begin{bmatrix}
b_{00} & b_{01} & b_{02}\\
b_{10} & b_{11} & b_{12}\\
b_{20} & b_{21} & b_{22}
\end{bmatrix} &  a_{01}\begin{bmatrix}
b_{00} & b_{01} & b_{02}\\
b_{10} & b_{11} & b_{12}\\
b_{20} & b_{21} & b_{22}
\end{bmatrix} \\
b_{00} & b_{01} & b_{02}\\
b_{10} & b_{11} & b_{12}\\
b_{20} & b_{21} & b_{22}
\end{bmatrix} &  a_{11}\begin{bmatrix}
b_{00} & b_{01} & b_{02}\\
b_{10} & b_{11} & b_{12}\\
b_{20} & b_{21} & b_{22}
\end{bmatrix} \end{bmatrix}.
\end{align}

This result showcases the new $6\times 6$ matrix generated from the tensor product of $A$ and $B$. Each block of this matrix is a scaled version of $B$, with the scaling factor being the corresponding element from matrix $A$.

Calculate the tensor product of
0 & 1\\
1 & 0
\end{bmatrix}$
1 & 1 \\
1 & -1
\end{bmatrix}$.

First, let's define the matrices as $A$ and $B$:
$A = \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}$,
$B = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$.

The tensor product $A \otimes B$ is calculated by multiplying each element of $A$ by the entire matrix $B$. This results in a $4 \times 4$ matrix, obtained as follows:

\begin{align*}
A \otimes B &= \begin{bmatrix}
0B & 1B\\
1B & 0B
\end{bmatrix} \\
&= \begin{bmatrix}
0 \cdot \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} & 1 \cdot \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \\
1 \cdot \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} & 0 \cdot \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}
\end{bmatrix} \\
&= \begin{bmatrix}
\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} & \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \\
\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} & \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}
\end{bmatrix} \\
&= \begin{bmatrix}
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\
1 & 1 & 0 & 0 \\
1 & -1 & 0 & 0
\end{bmatrix}.
\end{align*}

Therefore, the tensor product of the matrices $A$ and $B$ is a $4 \times 4$ matrix:
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\
1 & 1 & 0 & 0 \\
1 & -1 & 0 & 0
\end{bmatrix}$.

The tensor product is a vital operation in quantum computing, especially for combining matrices. However, it behaves differently from standard matrix multiplication. Here are some key properties of the tensor product <cit.>:

1. Non-Commutative Property: The tensor product does not satisfy the commutative law. This means the order of the matrices is important. Generally, for two matrices \( A \) and \( B \), \( A \otimes B \neq B \otimes A \).

2.  Associative Property: The tensor product is associative. This has a couple of implications:

2.1. When taking tensor products of three or more matrices, the grouping of matrices does not affect the result: \( (A \otimes B) \otimes C = A \otimes (B \otimes C) \).

2.2. For matrices that satisfy the conditions for matrix multiplication, the tensor product of products is the product of tensor products: \( (A \times A')\otimes(B \times B') = (A\otimes B) \times (A' \otimes B') \).

2.3. If matrices \( A \), \( B \) and vectors \( V \), \( V' \) satisfy the conditions for matrix multiplication, then \( (A \otimes B) \times (V \otimes V') = (A \times V) \otimes (B \times V') \).

These properties illustrate how the tensor product, while similar to regular matrix multiplication in some respects, has unique characteristics that are crucial for operations in quantum computing.

\begin{align}
A = \begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix},
B = \begin{pmatrix}
0 & 1\\
1 & 0
\end{pmatrix},
C = \begin{pmatrix}
1 & 0\\
0 & -1
\end{pmatrix},
V = \begin{pmatrix}
\end{pmatrix},
V' = \begin{pmatrix}
\end{pmatrix},
\end{align}

\[ (A \otimes B) \otimes C,\]

\[(A \times V) \otimes (B \times V'). \]

CHAPTER: WEEK 4: QUANTUM CIRCUITS AND SEARCH ALGORITHM

§ QUANTUM CIRCUITS

Building on our exploration of matrix representation in Week 3, this week, we delve into the realm of quantum circuits. A quantum circuit is a schematic that effectively illustrates how quantum gates are arranged to execute complex computational operations. There are chiefly two methodologies for arranging these gates: sequential and parallel. In a sequential arrangement, gates are applied consecutively, and this process equates to performing a series of matrix multiplications. Here, each quantum gate is depicted by its corresponding matrix, and the cumulative effect of the circuit is determined by the sequential multiplication of these matrices, mirroring the order of gate application <cit.>. Conversely, a parallel arrangement entails the simultaneous application of gates to distinct qubits. This type of arrangement is quantified mathematically through the tensor product of the matrices representing the individual gates <cit.>. Grasping these two key arrangements—sequential and parallel—is essential for a comprehensive understanding of how quantum circuits manipulate and process information at the quantum level.

Sequential Quantum Circuits

In quantum computing, understanding the sequential arrangement of circuits is crucial, especially when dealing with single qubit operations. Consider single qubit circuits with $2 \times 2$ matrices A and B. The sequence in which these matrices are applied is pivotal. For instance, if matrix A represents the first gate acting on a qubit, it appears on the left in the matrix multiplication. Therefore, if gate A acts first, followed by gate B, the corresponding matrix operation is $B \times A$, as depicted in Figure <ref>.

\[\Qcircuit @!C @!R {
&\gate{A}  & \gate{B} &\qw}\]

Sequential gate application in a single-qubit circuit.

When considering multiple qubits, the operations are represented by tensor products <cit.> of the matrices. In an m-qubit circuit, the dimensionality of matrices A and B increases to $2^m \times 2^m$, as illustrated in Figure <ref>.

\[\Qcircuit @C=2em @R=0.25em {
& & & & & &\qw& \multigate{4}{A}  & \multigate{4}{B} &\qw&\qw\\
& &  &  & & &\qw& \ghost{A} & \ghost{B}&\qw&\qw\\
&{/^{m}}\qw&\gate{A}  & \gate{B} &\qw & &\qw& \ghost{A} & \ghost{B}&\qw &\qw\\
& &   &  & & &\cdots& \nghost{A} & \nghost{B}&\cdots & \\
& & & & & & \qw&\ghost{A} &\ghost{B}&\qw&\qw

Sequential gate application in an m-qubit circuit.

Consider the circuit shown in Figure <ref>. It can be expressed as:

\begin{align}
G &= HXH \nonumber\\
&= \frac{1}{\sqrt{2}} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix}
\frac{1}{\sqrt{2}} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}\nonumber\\
&= \frac{1}{2} \begin{bmatrix}
1 & 1\\
-1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}\nonumber\\
&= \frac{1}{2} \begin{bmatrix}
2 & 0\\
0 & -2
\end{bmatrix}
1 & 0\\
0 & -1
\end{bmatrix}
= Z.
\end{align}

\[\Qcircuit @!C @!R {
&\gate{H}  & \gate{X} & \gate{H} &\qw}\]

Matrix representation of operations in a quantum circuit.

Using the principles discussed, calculate the resultant matrix for the operation $G = HZH$.

Parallel Quantum Circuits

Quantum circuits often involve operations occurring simultaneously on different qubits, known as parallel operations. To represent these parallel operations mathematically, we employ the tensor product, denoted as $A \otimes B$. This concept is illustrated in Figure <ref> for a circuit comprising $m$ qubits in the top wire and $n$ qubits in the bottom wire, with corresponding matrices $A$ (of size $2^m \times 2^m$) and $B$ (of size $2^n \times 2^n$).

\[\Qcircuit @!C @!R {
&\gate{A}&\qw   &  &{/^{m}}\qw&\gate{A} &\qw\\
&\gate{B}&\qw    &  &{/^{n}}\qw&\gate{B} &\qw}\]

The gate sequence representation on the multi-qubit  circuit.

Here are some examples:

As shown on the left in Figure <ref> can be expressed as:

\begin{align}
G &= H \otimes H
= \frac{1}{\sqrt{2}} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}
\otimes
\frac{1}{\sqrt{2}} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}
= \frac{1}{2}\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & -1 & 1 & -1\\
1 & 1 & -1 & -1\\
-1 & -1 & -1 & 1
\end{bmatrix}.
\end{align}

\[\Qcircuit @!C @!R {
&\gate{H}&\qw   &  &\gate{H} &\qw\\
&\gate{H}&\qw    &  &\qw  &\qw}\]

Calculation methods of different combinations of gates.

As shown on the right in Figure <ref>, if a circuit is empty, it will automatically fill the $``I"$ gate , and it can be expressed as:

\begin{align}
G &= H \otimes I
= \frac{\sqrt{2}}{2} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}
\otimes
\begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}
= \frac{\sqrt{2}}{2}\begin{bmatrix}
1 & 0 & 1 & 0\\
0 & 1 & 0 & 1\\
1 & 0 & -1 & 0\\
0 & 1 & 0 & -1
\end{bmatrix}.
\end{align}

In Figure <ref> can be expressed as:

\begin{align}
G &= CNOT \times (H \otimes I)\nonumber\\
&= \begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{bmatrix}
\left( \frac{\sqrt{2}}{2} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \right)\nonumber\\
&= \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix} \times \frac{\sqrt{2}}{2}  \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & -1 & 0\\ 0 & 1 & 0 & -1 \end{bmatrix}\nonumber\\
&= \frac{\sqrt{2}}{2} \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & -1\\ 1 & 0 & -1 & 0 \end{bmatrix}.
\end{align}

\[\Qcircuit @C=1.5em @R=1em {
&\lstick{}&\gate{H} &\ctrl{2} &\qw & & &\multigate{2}{G} &\qw\\
&\lstick{}& & & &= & & &  & & &\\
&\lstick{}&\qw &\targ &\qw& & &\ghost{G} &\qw

The circuit diagram on the left of the equal sign can be combined from H gate and CNOT gate.

In Figure <ref> can be expressed as:

\begin{align}
G &= (I \otimes H) \times  CZ \times (I \otimes H)\nonumber\\
&= \left( \begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}
\otimes
\frac{\sqrt{2}}{2} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix} \right)
\times  \begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & -1
\end{bmatrix} \times  \left( \begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}
\otimes
\frac{\sqrt{2}}{2} \begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix} \right)\nonumber\\
&= \frac{\sqrt{2}}{2}\begin{bmatrix}
1 & 1 & 0 & 0\\
1 & -1 & 0 & 0\\
0 & 0 & 1 & 1\\
0 & 0 & 1 & -1
\end{bmatrix} \times
\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & -1
\end{bmatrix}
\times \frac{\sqrt{2}}{2}\begin{bmatrix}
1 & 1 & 0 & 0\\
1 & -1 & 0 & 0\\
0 & 0 & 1 & 1\\
0 & 0 & 1 & -1
\end{bmatrix}\nonumber\\
&= \begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{bmatrix}
= \text{CNOT}
\end{align}

\[\Qcircuit @C=1.5em @R=1em {
&\lstick{}& \qw &\ctrl{2} &\qw &\qw & & &\multigate{2}{G} &\qw\\
& &  & & & & =& & & \\
&\lstick{}& \gate{H} & \control\qw &\gate{H} &\qw & & &\ghost{G} &\qw

The circuit diagram on the left of the equal sign can be combined from two H gates and CZ gate.

Reversible Circuits

Quantum gates differ from traditional logic gates in a critical aspect: reversibility. They have the unique ability to “undo" their operations, allowing them to revert to their original state. This property of reversibility is crucial for constructing quantum circuits that can maintain the delicate superposition states of qubits.

One of the most versatile reversible gates in quantum computing is the controlled-NOT (CNOT) gate. The CNOT gate, depicted in Figure <ref>, takes two qubit inputs: a control qubit and a target qubit <cit.>. When the control qubit is set to 1, the CNOT gate flips the state of the target qubit. However, if the control qubit is 0, the target qubit remains unchanged.

\[\Qcircuit @C=3em @R=2.5em {
&\lstick{x} &\ctrl{1}  & \rstick{x}\qw \\
&\lstick{y} &\gate{X}  & \rstick{y \oplus x}\qw}\]

CNOT gate circuit.

Another significant reversible gate is the Toffoli gate, also known as the CCNOT gate <cit.>. Illustrated in Figure <ref>, the Toffoli gate operates on three qubits - two control qubits and one target qubit. The target qubit flips its state only when both control qubits are set to 1.

\[\Qcircuit @!C @!R {
&\lstick{|x\rangle} &\ctrl{1}  & \rstick{|x\rangle}\qw \\
&\lstick{|y\rangle} &\ctrl{1}  & \rstick{|y\rangle}\qw \\
&\lstick{|z\rangle} &\targ \qw & \rstick{|z\oplus x\wedge y)\rangle }\qw}\]

Toffoli gate circuit.

The controlled-Z (CZ) gate is another vital component in quantum circuits <cit.>. It can be constructed using a CNOT gate combined with two Hadamard gates, as shown in Figure <ref>. The Hadamard gates change the basis states of the qubits ($H|0/1\rangle = \frac{1}{\sqrt{2}}(0 \pm 1)$), effectively transforming X operations into Z operations and vice versa. This transformation allows the CNOT gate to simulate the functionality of a CZ gate.

\[\Qcircuit @C=1.5em @R=1em {
&\ctrl{2} &\qw &  &\lstick{}& \qw &\ctrl{2} &\qw &\qw\\
& & &= & &  & & &\\
&\control\qw &\qw &  &\lstick{}& \gate{H} & \targ &\gate{H} &\qw

Constructing a CZ gate from a CNOT gate.

These multi-qubit reversible gates are the foundational elements for constructing more complex quantum circuits and algorithms, enabling conditional flipping, phase flipping, or entangling of qubits.

Summary of Quantum Circuits

Quantum circuits form the core framework of quantum computing, enabling the manipulation and processing of quantum information. This summary encapsulates the essence of quantum circuits, delving into their building blocks, the arrangement of these blocks, and the vital role of measurement. Below are the key elements that define quantum circuits:

* Building Blocks: The fundamental components of quantum circuits are quantum gates <cit.>. Distinct from classical logic gates, quantum gates are reversible and can operate on qubits in superposition states. Essential examples include single-qubit gates such as the Hadamard (H) and Pauli (X, Y, Z) gates, along with multi-qubit gates like the Controlled-NOT (CNOT), Toffoli, and Controlled-Z (CZ) gates. These gates manipulate qubit states to facilitate quantum computations.

* Arranging Quantum Gates: In quantum circuits, gates can be arranged sequentially or in parallel. Sequential arrangements involve gates applied in succession, with their operations equating to matrix multiplications. The sequence of gates is crucial, as it affects the qubits' final state. Parallel arrangements involve simultaneous operations of gates on different qubits, represented mathematically by the tensor product of the gates' matrices, enabling intricate multi-qubit operations <cit.>.

* Measurement: Measurement <cit.> is the process of deriving classical information from quantum states in a quantum circuit. It causes the quantum state to collapse into one of its basis states, yielding a specific outcome. Measurements, usually conducted at the circuit's end, are integral for acquiring the results of quantum computations. The probabilistic nature of quantum measurement leads to varied outcomes based on the qubit's state before measurement.

* Integration of Elements: Quantum circuits integrate quantum gates, their arrangements, and measurements to execute complex computational tasks <cit.>. The selection and configuration of gates define the functionality of the algorithm, while measurement delivers the results. Through thoughtful design of these circuits, the principles of quantum mechanics are harnessed for computational applications.

In the following we provide an example that brings together these elements, forming a comprehensive quantum circuit and illustrating the concepts discussed in this section.

Find the output state $|\phi\rangle$ of the circuit shown in Figure <ref>:

\[\Qcircuit @!C @!R {
&\lstick{} &\ctrl{1} &\qw &\qw &\meter &\rstick{|0\rangle}\cw\\
&\lstick{\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)} &\ctrl{1} &\gate{H} &\targ &\meter &\rstick{|1\rangle}\cw\\
&\lstick{} &\targ &\qw &\ctrl{-1} &\qw &\rstick{|\phi\rangle}\qw

An example of how quantum gates work on qubits in a quantum circuit.

It starts with three qubits in the state $\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)$. A Toffoli gate is applied, which flips the third qubit if both the first two are 1. This results in the state $\frac{1}{\sqrt{2}}(|000\rangle + |110\rangle)$.

Next, a Hadamard gate H is applied to the second qubit. This puts the qubit into a superposition of 0 and 1. The state becomes $\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle)$.

Finally, a CNOT gate with qubit 3 as control and qubit 2 as target is applied. This flips qubit 2 if qubit 3 is $|1\rangle$. The final state is $\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle)$.

The specific process is as follows:

\begin{align}
\frac{1}{\sqrt{2}}(|000\rangle + |111\rangle&\stackrel{\text{Toffoli}}{\longrightarrow}\frac{1}{\sqrt{2}}(|000\rangle + |110\rangle)\nonumber\\
&\stackrel{\text{H}_2}{\longrightarrow}\frac{1}{\sqrt{2}}[|0\rangle\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)+|1\rangle\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)|0\rangle]\nonumber \\ & \qquad=\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle)\nonumber\\
&\stackrel{\text{CNOT}_{32}}{\longrightarrow}\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle) \to |\phi\rangle=|0\rangle.
\end{align}

Note: $H_2$ means to perform $H$ gate operation on the second qubit; $CNOT_{32}$ means that the third qubit is the control qubit and the second qubit is the controlled qubit.

The matrix representation of this circuit can be written as:

\begin{align}
G &= (I \otimes CNOT_{32}) \times (I \otimes H_2 \otimes I) \times Toffoli  \nonumber \\
\left( \begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix} \otimes
\begin{bmatrix}
1 & 0 & 0 & 0\\
0& 0& 0 & 1 \\
0& 0& 1& 0\\
0& 1& 0& 0
\end{bmatrix} \right) \times
\left( \begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix} \otimes
\frac{\sqrt{2}}{2}
\begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix} \otimes
\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix} \right) \nonumber \\& \qquad \times
\begin{bmatrix}
1& 0 &0 &0 &0 &0 &0 &0 \\
0& 1 &0 &0 &0 &0 &0 &0 \\
0& 0 &1 &0 &0 &0 &0 &0 \\
0& 0 &0 &1 &0 &0 &0 &0 \\
0& 0 &0 &0 &1 &0 &0 &0 \\
0& 0 &0 &0 &0 &1 &0 &0 \\
0& 0 &0 &0 &0 &0 &0 &1 \\
0& 0 &0 &0 &0 &0 &1 &0
\end{bmatrix} \nonumber \\
&= \frac{\sqrt{2}}{2}
\begin{bmatrix}
1& 0& 1& 0& 0& 0& 0& 0\\
0& 1& 0& -1& 0& 0& 0& 0\\
1& 0& -1& 0& 0& 0& 0& 0\\
0& 1& 0& 1& 0& 0& 0& 0\\
0& 0& 0& 0& 1& 0& 0& 1\\
0& 0& 0& 0& 0& 1& -1& 0\\
0& 0& 0& 0& 1& 0& 0& -1\\
0& 0& 0& 0& 0& 1& 1& 0
\end{bmatrix}.
\end{align}

For the initial quantum state can be written as:

\begin{align}
\frac{1}{\sqrt{2}}(|000\rangle + |111\rangle = \frac{1}{\sqrt{2}} \times
\begin{bmatrix}
\end{bmatrix}.
\end{align}

Therefore, the final state obtained after the initial quantum state passes through the circuit G is:

\begin{align}
\frac{1}{2} \times
\begin{bmatrix}
\end{bmatrix},
\end{align}

The quantum state represented by this vector is: $\frac{1}{2}(|000\rangle + |010\rangle + |100\rangle - |110\rangle)$.

It is worth noting that for the operations of these matrices, we can fully utilize MATLAB for calculations, and there will be specific examples in the later courses.

§ GROVER’S ALGORITHM

Grover's Algorithm: Background

Grover's algorithm is designed to efficiently solve a specific type of search problem: locating a target element in a large, unstructured search space. A typical example of this problem is searching through a database. Imagine a database containing \( N = 2^n \) entries, among which only one entry (e.g., a red ball) satisfies our search criteria. We define a function \( f \): \( \{0, 1\}^n \rightarrow \{0, 1\} \), where \( n \) is a positive integer. This function \( f \) checks whether each entry is the target red ball \( x_0 \) <cit.>:

\begin{equation}
f(x) = \begin{cases}
1, & \text{if } x = x_0, \\
0, & \text{otherwise}.
\end{cases}
\end{equation}

The objective is to find this specific red ball \( x_0 \), meaning we need to locate the unique input \( x_0 \) for which \( f(x) \) maps to 1.

Consider an example with \( n = 2 \). There exists a function \( f \) such that:

\begin{equation}
f(00) = 0, \ f(01) = 0, \ f(10) = 0, \ f(11) = 1.
\end{equation}

Here, \( x_0 = 11 \) is the particular string we are trying to find.

On a classical computer, the typical approach is to search through all \( N \) entries linearly, requiring, on average, about \( \frac{N}{2} \) queries to find the red ball. However, Grover's algorithm on a quantum computer provides a significant advantage <cit.>. It offers a quadratic speedup for this kind of unstructured database search, needing only approximately \( \sqrt{N} \) queries to locate \( x_0 \), as illustrated in Figure <ref>.

[classical solution]

[quantum solution]

Comparative illustration of solving an unstructured database search problem.

Grover’s Algorithm: Separation of phase

In the field of quantum computing, phase separation <cit.> is a key concept that plays a central role in understanding and implementing quantum algorithms. Phase separation involves the phase changes of a quantum system's state after undergoing a series of operations, which is crucial for revealing the workings of quantum algorithms.

Let us examine this concept through two steps. As shown in Figure <ref>.

\[\Qcircuit @!C @!R{
&\lstick{\mid 0\rangle}&{/^{n}}\qw&\gate{H^{\otimes n}}\qw&{/^{n}}\qw&\multigate{1}{U_{f}}&{/^{n}}\qw &\meter\\
&\lstick{\mid 0\rangle}&\qw    &\qw     &\qw    &\ghost{U_{f}}       &\qw&\qw\\
&                      &\dstick{\mid\phi_{0}\rangle}& &\dstick{\mid\phi_{1}\rangle}& &\dstick{\mid\phi_{2}\rangle}&&

Quantum phase separation evolution circuit diagram.

First, imagine an initial state composed of two qubits, each initialized to $\ket{0}$, so that the entire system's state can be represented as $\ket{\phi_0} = \ket{00}$. Next, by performing a Hadamard transform on the first qubit, we put it into a superposition state, producing a new state $\ket{\phi_1}$ that contains a superposition of all possible $n$-bit strings $x$, which can be represented as :

\[
\ket{\phi_1} = \left( \sum_{x \in \{0,1\}^n} \ket{x} \right) \ket{0},
\]

this superposition state demonstrates the powerful capability of quantum computing, as it allows us to examine all possible inputs in a single quantum operation.

Further, we consider a state $\ket{\phi_2}$ that includes the results of applying a certain function $f$ to all possible inputs $x$. By applying a special quantum gate $U_f$, we encode the output of the function $f$ into the phase of the qubits, thus obtaining the new state

\[
\ket{\phi_2} = \sum_{x \in \{0,1\}^n} \ket{x, f(x)},
\]

this step effectively showcases the efficiency of quantum algorithms, theoretically allowing us to simultaneously compute the value of the function $f$ on all possible inputs.

Now, let us look specifically at how phase separation is implemented in quantum computing. As shown in Figure <ref>.

\[\Qcircuit @!C @!R{
&\lstick{\mid x\rangle}&{/^{n}}\qw&\qw         &\qw&\multigate{1}{U_{f}}&{/^{n}}\qw &\meter\\
&\lstick{\mid 1\rangle}&\qw&\gate{H}    &\qw&\ghost{U_{f}}       &\qw&\qw\\
&                      &\dstick{\mid\phi_{0}\rangle}& &\dstick{\mid\phi_{1}\rangle}& &\dstick{\mid\phi_{2}\rangle}&&

Quantum phase separation and controlled phase flip circuit diagram

Starting with an initial state composed of a determined qubit $x$ and another qubit set to $1$, i.e., $\ket{\phi_0} = \ket{x,1}$, we then apply a Hadamard gate (H gate) to the second qubit, transforming $\ket{1}$ into a superposition state $\ket{0} - \ket{1}$. The result of this operation leads to the state $\ket{\phi_1}$:

\[
\ket{\phi_1} = \ket{x}(\ket{0} - \ket{1}) = (\ket{x,0} - \ket{x,1}).
\]

Subsequently, we apply a special quantum gate $U_f$ to this superposition state, which operates on the qubits based on the value of the function $f$. This causes our system to transition to the state $\ket{\phi_2}$, which can be represented as:

\[
\ket{\phi_2} = \ket{x}(\ket{f(x) \oplus 0} - \ket{f(x) \oplus 1})=\ket{x}(\ket{f(x)}-\overline{\ket{f(x)}}).
\]

Given that the phase of a qubit is a global property, we can further simplify the state $\ket{\phi_2}$ based on the value of $x$. If $x=x_0$, we get:

\[
\ket{\phi_2} = -\ket{x}(\ket{0} - \ket{1}),
\]

otherwise, when $x\neq x_0$, we have:

\[
\ket{\phi_2} = \ket{x}(\ket{0} - \ket{1}).
\]

This shows that we can control the phase of the qubits through the value of the function $f(x)$, a feature that allows us to encode the information of the function $f$ in the output state $\ket{\phi_2}$. Ultimately, the state $\ket{\phi_2}$ can be expressed as:

\[
\ket{\phi_2} = (-1)^{f(x)}\ket{x}(\ket{0} - \ket{1}).
\]

In this expression, we can clearly see how the phase of the quantum state is modulated by the value of the function $f(x)$. This phase modulation is a unique characteristic of quantum algorithms, reflecting the unique advantages of quantum computing in information processing.

Operator R1: From Function \( f \) to Operator \( U_f \)

In Grover's algorithm, the first key operator, R1, is derived from the function \( f \). This function \( f \) is defined as \( f(x) = 1 \) if \( x \) is the target element (our `red ball') and \( f(x) = 0 \) otherwise. The role of R1 is to apply a phase inversion to the target state, and it is realized through the unitary operator \( U_f \) <cit.>.

The operator \( U_f \) is defined as follows:

\begin{equation}
U_f|x\rangle = (-1)^{f(x)}|x\rangle.
\end{equation}

This operation leaves the non-target states (where \( f(x) = 0 \)) unchanged, while it multiplies the target state (where \( f(x) = 1 \)) by -1, effectively applying a phase shift of \(\pi\) to it.