Lecture Notes on Quantum Computing: Foundations and Research

Author

Your Name

Published

February 5, 2025

Introduction

Quantum computing represents a paradigm shift from classical computation, necessitating a re-evaluation of fundamental concepts in logic and probability. This lecture will explore the foundational differences between classical and quantum approaches, drawing inspiration from the paper "Machine logics and quantum physics" by Dalla Chiara and Giuntini. We will begin by questioning the basis of classical logic and its applicability to quantum systems. Through the example of a random bit generator and its physical realization using a half-silvered mirror, we will demonstrate the limitations of classical probability in describing quantum phenomena. This will motivate the introduction of complex numbers and the concept of quantum interference as essential tools for modeling quantum systems. Furthermore, we will briefly discuss the potential for quantum computation to achieve significant speedups over classical methods and provide an overview of the ongoing quantum computing research at our university. This lecture aims to set the stage for a deeper exploration of the technical aspects of quantum computing, highlighting the crucial role computer scientists play in this evolving field.

Classical vs. Quantum Logic

Why Classical Logic?

Classical logic, the bedrock of our intuitive reasoning and digital computation, is deeply rooted in our everyday experiences with the macroscopic world. We readily accept its principles, such as the behavior of conjunction: "A and B" is true only if both A and B are true. This seems self-evident, a matter of common sense. But why is our common sense structured this way? As explored in the paper "Machine logics and quantum physics," the adherence to classical logic may stem from the fact that the macroscopic objects we encounter daily behave in accordance with these logical rules. Even before the advent of electrical circuits, Boolean logic was formulated, later proving to be an effective tool for describing digital circuits where signals are definitively either 0 or 1. However, the crucial question arises: is classical logic universally valid, especially when we delve into the microscopic realm governed by quantum mechanics? If logic is to accurately model observed phenomena, we must consider revising our logical frameworks when dealing with quantum systems, where the familiar laws of classical logic may break down.

Limitations of Classical Probability: The Random Bit Generator

To illustrate the inadequacy of classical logic and probability in the quantum context, let us consider a seemingly simple device: a random bit generator. This hypothetical device takes a single bit (0 or 1) as input and produces a single bit (0 or 1) as output, with probabilistic behavior.

Let $P_{ij}$ represent the probability of obtaining output $j$ when the input is $i$, where $i, j \in \{0, 1\}$. In classical probability theory, these probabilities are real numbers within the range $[0, 1]$. For a well-defined random bit generator, the probabilities must satisfy the normalization conditions: \[\begin{aligned}P_{00} + P_{01} &= 1 \\P_{10} + P_{11} &= 1\end{aligned}\] These equations ensure that for each input, the sum of probabilities for all possible outputs is unity.

Now, let’s analyze the composition of two such random bit generators in sequence. Let $P_{ij}$ be the probabilities for the first generator and $Q_{ij}$ for the combined circuit. We aim to compute $Q_{ij}$. Specifically, consider $Q_{00}$, the probability of obtaining output 0 from the cascaded circuit given input 0. This can occur through two mutually exclusive paths:

Input 0 yields Output 0 from the first generator, and then Input 0 yields Output 0 from the second generator. The probability of this path is $P_{00} \times P_{00}$.
Input 0 yields Output 1 from the first generator, and then Input 1 yields Output 0 from the second generator. The probability of this path is $P_{01} \times P_{10}$.

According to the rules of classical probability, the total probability $Q_{00}$ is the sum of the probabilities of these disjoint paths: \[Q_{00} = P_{00}P_{00} + P_{01}P_{10}\] Similar calculations can be performed to determine $Q_{01}, Q_{10},$ and $Q_{11}$.

Example 1 (Uniform Random Bit Generator). Consider a uniform random bit generator as a specific case, where all probabilities are equal: $P_{00} = P_{01} = P_{10} = P_{11} = \frac{1}{2}$. For this uniform generator, \[Q_{00} = \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) + \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}\] In fact, for a uniform random bit generator, it can be shown that all $Q_{ij} = \frac{1}{2}$. Thus, cascading two uniform random bit generators results in another uniform random bit generator.

Now, let us explore whether we can configure a random bit generator such that its square behaves like a classical NOT gate. A NOT gate has the deterministic behavior:

Input 0 $\rightarrow$ Output 1 (probability 1), Output 0 (probability 0).
Input 1 $\rightarrow$ Output 0 (probability 1), Output 1 (probability 0).

For the squared random bit generator to act as a NOT gate, we would require $Q_{00} = 0$ and $Q_{01} = 1$ (and similarly $Q_{10} = 1$ and $Q_{11} = 0$). Focusing on the condition $Q_{00} = 0$: \[Q_{00} = P_{00}P_{00} + P_{01}P_{10} = 0\] Since probabilities are non-negative real numbers, for this sum to be zero, both terms must individually be zero: \[P_{00}P_{00} = 0 \implies P_{00} = 0\] \[P_{01}P_{10} = 0 \implies \text{either } P_{01} = 0 \text{ or } P_{10} = 0\] If $P_{00} = 0$, then from the normalization condition $P_{00} + P_{01} = 1$, we deduce $P_{01} = 1$. Similarly, by considering the input 1 and the requirement $Q_{11} = 0$, we would find $P_{11} = 0$ and $P_{10} = 1$.

Remark. Remark 1. However, if $P_{01} = 1$ and $P_{10} = 1$, the random bit generator itself is already a NOT gate:

Input 0 $\rightarrow$ Output 1 (probability 1).
Input 1 $\rightarrow$ Output 0 (probability 1).

If the first stage is already a NOT gate, then applying it twice yields an identity gate (NOT followed by NOT), not a NOT gate.

Theorem 1 (Impossibility of Square Root of NOT in Classical Probabilistic Logic). We have formally shown that within the framework of classical probabilistic logic, it is impossible to construct a probabilistic gate whose composition with itself behaves as a NOT gate, unless the gate is already essentially a NOT gate itself. This impossibility strongly suggests that classical probability is insufficient to model certain physical operations, hinting at the necessity of a more comprehensive mathematical framework, such as quantum mechanics.

This impossibility strongly suggests that classical probability is insufficient to model certain physical operations, hinting at the necessity of a more comprehensive mathematical framework, such as quantum mechanics.

Physical Implementation: The Half-Silvered Mirror and Quantum Behavior

The limitations of classical probability become strikingly apparent when we consider physical implementations of seemingly simple operations. Let’s examine a device based on a half-silvered mirror, also known as a beam splitter, which experimentally demonstrates behavior fundamentally incompatible with classical predictions, acting as a "square root of NOT" gate.

Single Photon Random Bit Generator

Consider a setup where single photons are used as inputs. We define input $\left|{0}\right\rangle$ as a photon incident from one direction and input $\left|{1}\right\rangle$ as a photon incident from a perpendicular direction. The central component is a half-silvered mirror.

Single Photon Experiment Setup with Half-Silvered Mirror

When a single photon enters as input $\left|{0}\right\rangle$, it encounters the half-silvered mirror. This mirror is designed to reflect approximately half of the incident light intensity and transmit the other half. For a single photon, this translates to a 50% probability of reflection (detected at Detector 0) and a 50% probability of transmission (detected at Detector 1). The behavior is symmetrical for input $\left|{1}\right\rangle$.

Experimentally, if we repeatedly send single photons as input $\left|{0}\right\rangle$, we observe that Detector 0 and Detector 1 each click approximately half the time. This is consistent with the behavior of a uniform random bit generator, as discussed in [sec:classical_vs_quantum_logic].

The Paradox of Cascaded Half-Silvered Mirrors

Now, let’s consider a configuration where we cascade two half-silvered mirrors. To properly direct the photon paths, we introduce two standard mirrors in between. The setup is illustrated below:

Cascaded Half-Silvered Mirrors Setup

Classically, if we input a photon as $\left|{0}\right\rangle$, at the first half-silvered mirror (HSM 1), there’s a 50% chance of reflection upwards and 50% chance of transmission downwards. Following each path classically, one might expect that at the second half-silvered mirror (HSM 2), each component again has a 50/50 chance of reflection or transmission. Based on classical probability, we would predict that for input $\left|{0}\right\rangle$, the probability of reaching Output 0 (Detector 0) should be around 50%, similar to the single half-silvered mirror case.

However, experimental results dramatically contradict this classical intuition. When we perform this experiment with single photons and input $\left|{0}\right\rangle$, Detector 0 never registers a photon, while Detector 1 always (or nearly always, in ideal conditions) registers a photon. This observed behavior is the opposite of what classical probability predicts. Similarly, for input $\left|{1}\right\rangle$, Detector 0 always clicks, and Detector 1 never clicks. Remarkably, the cascaded device behaves like a deterministic NOT gate, despite being built from probabilistic components according to classical understanding.

Quantum Interference: Wave-like Photon Behavior

The resolution to this paradox lies in the quantum mechanical nature of light and the phenomenon of interference. Unlike classical particles, photons can exhibit wave-like properties. When a photon encounters a half-silvered mirror, it does not simply randomly choose to be reflected or transmitted. Instead, it enters a superposition of both possibilities; it effectively takes both paths simultaneously.

In the cascaded setup, the photon, originating from input $\left|{0}\right\rangle$, propagates through both paths created by the first HSM. These paths then recombine at the second HSM. Crucially, due to the wave nature of photons and the physics of beam splitters, a phase difference is introduced between the reflected and transmitted components at each half-silvered mirror. When the components from the two paths recombine at HSM 2, they interfere. In this specific configuration, the interference is destructive for the path leading to Output 0 and constructive for the path leading to Output 1 when the input is $\left|{0}\right\rangle$. Conversely, for input $\left|{1}\right\rangle$, the interference patterns are reversed, leading to Output 0.

This interference effect is analogous to the famous double-slit experiment, where wave interference patterns are observed even when single particles are sent through the slits one at a time. Each photon effectively interferes with itself, traversing both possible paths and exhibiting wave-like behavior.

An important aspect of quantum mechanics is the role of measurement. If we were to place a detector within the cascaded setup, for instance, to observe which path the photon takes after the first HSM, we would destroy the quantum superposition and the interference pattern. In such a case, the device would revert to behaving classically, with approximately 50% probability for each output, eliminating the NOT gate behavior. This illustrates the principle that measurement in quantum mechanics collapses superposition and disrupts interference phenomena.

The Square Root of NOT Gate

Definition 1 (Square Root of NOT Gate). Since two cascaded half-silvered mirrors, exploiting quantum interference, realize a NOT gate, a single half-silvered mirror is appropriately termed a "square root of NOT" gate. Applying this gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [sec:classical_vs_quantum_logic] that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate.

Remark. Remark 2. Applying the Square Root of NOT gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [sec:classical_vs_quantum_logic] that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate.

The half-silvered mirror, acting as a square root of NOT gate, is not merely a probabilistic classical gate; it is a fundamentally quantum gate that leverages wave-like properties and interference. Its existence underscores the potential of quantum mechanics to perform operations that are impossible to achieve within the confines of classical probability and logic.

Mathematical Formalism: Complex Amplitudes and Quantum Gates

To move beyond the limitations of classical probability and accurately describe quantum phenomena like interference and the square root of NOT gate, we must employ the mathematical framework of complex numbers and linear algebra.

Complex Amplitudes and Probabilities

Definition 2 (Complex Amplitudes for Beam Splitter). Let’s assume the following convention for a beam splitter:

Amplitude for Transmission: $t = \frac{1}{\sqrt{2}}$
Amplitude for Reflection: $r = \frac{i}{\sqrt{2}}$

Definition 3 (Imaginary Unit $i$). Here, $i = \sqrt{-1}$ is the imaginary unit.

The square modulus of these amplitudes are $|t|^2 = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$ and $|r|^2 = \left|\frac{i}{\sqrt{2}}\right|^2 = \frac{1}{2}$, corresponding to the 50% probability of transmission and reflection, respectively. The imaginary unit $i$ in the reflection amplitude is essential; it represents a phase shift of $\pi/2$ upon reflection, which is the origin of quantum interference in this system.

Definition 4 (Quantum States $\left|{0}\right\rangle$ and $\left|{1}\right\rangle$). We represent the quantum states of a photon’s path using Dirac notation (ket notation). The state $\left|{0}\right\rangle$ represents the photon entering from input port 0, and $\left|{1}\right\rangle$ represents the photon entering from input port 1. Mathematically, we represent these as column vectors in a complex vector space: \[\left|{0}\right\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \left|{1}\right\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\]

Definition 5 (Qubit State). A general quantum state, or qubit, can be a superposition of these basis states: \[\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}\] where $\alpha, \beta \in \mathbb{C}$ are complex amplitudes, and the normalization condition $|\alpha|^2 + |\beta|^2 = 1$ ensures that the total probability is 1. $|\alpha|^2$ is the probability of measuring the state in $\left|{0}\right\rangle$ and $|\beta|^2$ is the probability of measuring in $\left|{1}\right\rangle$.

Quantum Gates as Unitary Operators

Definition 6 (Unitary Operator). Quantum operations, such as the square root of NOT gate, are mathematically described by unitary operators. A unitary operator $U$ is a linear transformation that preserves the inner product, and in matrix form, it satisfies $U U^\dagger = U^\dagger U = I$, where $U^\dagger$ is the conjugate transpose of $U$, and $I$ is the identity operator.

Remark. Remark 3. The unitarity of quantum gates is crucial because it ensures that quantum evolution preserves probabilities; the norm of the state vector remains constant throughout the computation.

Matrix Representation of the Square Root of NOT Gate

Definition 7 (Matrix Representation of Square Root of NOT Gate). Based on the complex amplitudes for transmission and reflection, the square root of NOT gate, realized by a half-silvered mirror, can be represented by the following $2 \times 2$ unitary matrix: \[\text{SquareRootNOT} = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix}\]

Applying this SquareRootNOT gate to the input state $\left|{0}\right\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$: \[\text{SquareRootNOT} \left|{0}\right\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} i \\ 1 \end{pmatrix} = \frac{i}{\sqrt{2}} \left|{0}\right\rangle + \frac{1}{\sqrt{2}} \left|{1}\right\rangle\] Now, applying the SquareRootNOT gate again to the resulting state: \[\text{SquareRootNOT} (\text{SquareRootNOT} \left|{0}\right\rangle) = \text{SquareRootNOT} \left( \frac{1}{\sqrt{2}} \begin{pmatrix} i \\ 1 \end{pmatrix} \right) = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix} \frac{1}{\sqrt{2}} \begin{pmatrix} i \\ 1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} i \cdot i + 1 \\ 1 \cdot i + i \cdot 1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} -1 + 1 \\ 2i \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 0 \\ 2i \end{pmatrix} = \begin{pmatrix} 0 \\ i \end{pmatrix} = i \begin{pmatrix} 0 \\ 1 \end{pmatrix} = i \left|{1}\right\rangle\]

Example 2 (Cascaded Square Root of NOT Gate). The final state is $i \left|{1}\right\rangle$. When we measure this output, the probability of obtaining outcome $\left|{0}\right\rangle$ is $|0|^2 = 0$, and the probability of obtaining outcome $\left|{1}\right\rangle$ is $|i|^2 = 1$. This perfectly matches the experimental observation that two cascaded half-silvered mirrors act as a NOT gate for input $\left|{0}\right\rangle$, resulting in output $\left|{1}\right\rangle$ with certainty. The factor $i$ is a global phase, which does not affect measurement probabilities. Similarly, applying SquareRootNOT twice to $\left|{1}\right\rangle$ will result in $\left|{0}\right\rangle$.

Quantum Interference: The Role of Complex Numbers

Remark. Remark 4. The mathematical framework of complex amplitudes and unitary operators elegantly captures quantum interference. The crucial aspect is that complex numbers can have both magnitude and phase, allowing for both constructive and destructive interference. In the cascaded half-silvered mirror example, the specific complex amplitudes associated with reflection and transmission, combined through matrix multiplication (representing sequential quantum operations), lead to the observed interference patterns. The fact that $i \times i = -1$ is central to achieving destructive interference. In the calculation above, the term $i^2 = -1$ directly contributes to the zero amplitude for the $\left|{0}\right\rangle$ component in the final state, leading to the deterministic NOT gate behavior, a phenomenon impossible to replicate with classical probabilities alone.

Quantum Computation and Potential for Speedup

The significance of the square root of NOT gate extends beyond a mere demonstration of quantum weirdness. It serves as a fundamental building block in quantum algorithms, which hold the promise of solving certain computational problems far more efficiently than their classical counterparts.

Quantum Advantage: Deutsch’s Algorithm

Example 3 (Deutsch’s Algorithm and Quantum Speedup). Deutsch’s algorithm is a seminal example illustrating the potential for quantum speedup. This algorithm, and its generalization, the Deutsch-Jozsa algorithm, demonstrates a scenario where a quantum computer can solve a specific problem with significantly fewer queries to a function oracle compared to any classical deterministic algorithm. In essence, these algorithms highlight a quantum advantage in query complexity.

While the original formulation of Deutsch’s algorithm often employs the Hadamard gate and controlled operations, it’s important to note that quantum algorithms, including those demonstrating speedup, can be constructed using various sets of quantum gates, potentially including the square root of NOT gate in conjunction with other necessary gates to achieve universality. This underscores the versatility of quantum gates like the square root of NOT as components in more complex quantum circuits. Note: While the square root of NOT gate is a crucial quantum gate, it is not universal on its own. Universality typically requires a combination of gates, such as Hadamard, Phase, CNOT, and potentially others. This detail, while important, is not explicitly emphasized in this section of the transcript, so we maintain focus on the core message of speedup and the role of quantum gates as building blocks.

Quantum computation, therefore, offers a fundamentally different approach to computation compared to both classical deterministic and probabilistic models, opening avenues for computational advantages in specific problem domains.

Contrasting Computational Models: Deterministic, Probabilistic, and Quantum

To better understand the nature of quantum speedup, it is helpful to contrast quantum computation with classical computational paradigms:

Deterministic Computation: Classical deterministic computation follows a single, predetermined sequence of steps from an initial state to a unique output. Each step is uniquely defined, and the computation path is fixed.
Non-deterministic Computation: Non-deterministic computation explores multiple computational paths simultaneously. An outcome is considered valid if at least one of these paths leads to a desired result. While non-determinism is a valuable concept in theoretical computer science for problem classification (e.g., NP complexity), it is typically simulated deterministically, often incurring an exponential time overhead.
Probabilistic Computation: Probabilistic computation introduces randomness into the computational process. Transitions between states occur with certain probabilities (represented by real numbers between 0 and 1). For a given input, there are multiple possible computational paths, each with an associated probability. The probability of a particular output is the sum of the probabilities of all paths leading to that output. Probabilistic algorithms can offer efficiency advantages over deterministic algorithms for certain problems, but they inherently involve a possibility of error, albeit controllable by repeating the computation.
Quantum Computation: Quantum computation, unlike classical approaches, leverages the principles of quantum mechanics, particularly superposition and interference. Computational states are represented by superpositions of basis states, and operations are performed using unitary transformations. Crucially, computation proceeds through multiple paths simultaneously, but instead of classical probabilities, these paths are associated with complex amplitudes. Quantum interference, arising from the properties of complex numbers, allows for both constructive and destructive interference between these computational paths. This unique feature enables quantum algorithms to achieve outcomes that are fundamentally different from, and in some cases superior to, both deterministic and probabilistic classical computation. For instance, destructive interference can selectively cancel out undesirable computational paths, potentially leading to exact solutions or significantly enhanced probabilities of correct results, surpassing the capabilities of probabilistic methods.

Remark. Remark 5. In summary, quantum computation harnesses the quantum phenomena of superposition and interference to explore computational possibilities in a fundamentally novel way. This approach offers the potential for exponential speedups for specific classes of problems, marking a significant departure from the limitations of classical computation.

Quantum Computing Research at the University

Riccardo Romanello, a PhD student in our department, provided insights into the quantum computing research activities at the university, highlighting several key areas of investigation.

Quantum Automata Theory

Remark. Remark 6. Our research in quantum automata theory delves into the quantum mechanical counterparts of classical automata models. This field investigates the fundamental differences in computational power and expressiveness between classical and quantum automata. A central theme is understanding how the principles of quantum mechanics, such as superposition and unitarity, alter the capabilities of automata. Interestingly, and somewhat counter-intuitively, it has been shown that basic models of quantum automata are fundamentally limited in recognizing even simple formal languages. Specifically, unlike classical automata, basic quantum automata cannot recognize finite languages. This limitation arises from the constraints imposed by unitarity, which restricts the types of operations permissible in quantum automata, leading to significant departures from classical automata theory.

Quantum Random Walks and Graph Algorithms

Remark. Remark 7. Another significant research direction is the study of quantum random walks, which are quantum analogues of classical random walks on graphs. Classical random walks are a versatile tool in computer science, with applications ranging from graph analysis to algorithm design. Our research explores the potential of quantum random walks to provide more efficient algorithms for various graph problems compared to classical random walk-based approaches. A core challenge in this area is the representation of graph structures in a quantum computational framework. Specifically, to perform quantum random walks on a graph, the graph’s structure must be encoded into a unitary operator. Developing methods to achieve this encoding is a key focus.

Algorithm 1 (Graph Encoding Algorithm). We have developed a classical algorithm that can encode any graph into a unitary matrix, enabling quantum random walks. However, this encoding process may necessitate the addition of edges to the original graph to ensure the resulting matrix is unitary. The complexity of this encoding algorithm is quadratic in the size of the graph. This research aims to leverage the unique properties of quantum mechanics to enhance graph algorithms and explore new computational paradigms for network analysis.

Quantum Circuit Compilation and Synthesis

Remark. Remark 8. Quantum circuit compilation is a critical area of research focused on bridging the gap between high-level quantum algorithms and their physical implementation on quantum hardware. Analogous to classical circuit compilation, quantum circuit compilation involves translating abstract quantum operations, often represented as large unitary matrices, into concrete sequences of elementary quantum gates from a universal gate set. This process is essential for executing quantum algorithms on actual quantum computers. A major challenge in quantum circuit compilation stems from the exponential scaling of quantum state spaces. For an $n$-qubit system, the unitary matrices describing quantum operations are of size $2^n \times 2^n$, making direct manipulation and decomposition computationally demanding.

Algorithm 2 (Quantum Circuit Compilation Techniques). Our research focuses on developing efficient classical algorithms for quantum circuit compilation, particularly for decomposing complex unitary operations into sequences of simpler, physically realizable gates. Currently, we are developing programming models and compilation techniques specifically targeted at optimizing circuits composed of controlled-NOT (CNOT) gates, a crucial two-qubit gate in quantum computation. This work aims to make quantum algorithms more practical and accessible for implementation on near-term quantum devices.

Complexity Theory of Quantum Problems

Remark. Remark 9. Finally, our research in quantum complexity theory addresses fundamental questions about the computational resources required to solve quantum problems and the inherent complexity of quantum computation itself. This area seeks to classify quantum computational problems within the framework of computational complexity theory, analogous to the P vs. NP question in classical complexity. We investigate the complexity classes of problems solvable by quantum computers and explore the relationships between quantum and classical complexity classes. A specific problem under investigation is the complexity of quantum circuit synthesis: given a unitary matrix, what is the complexity of finding an optimal (e.g., shortest) sequence of gates from a universal set that implements this matrix? While the precise complexity classification remains an open question, preliminary analysis suggests that this problem may be related to PSPACE-completeness, potentially reducible to planning problems. Determining the complexity landscape of quantum problems is crucial for understanding the ultimate capabilities and limitations of quantum computers and for guiding the development of efficient quantum algorithms.

Conclusion

This lecture has laid the groundwork for understanding quantum computing by contrasting it with classical logic and computation. We have seen that classical logic, while intuitive for macroscopic phenomena, fails to explain the behavior of quantum systems. The experiment with cascaded half-silvered mirrors starkly demonstrated the limitations of classical probability and necessitated the introduction of complex amplitudes and the concept of quantum interference. The square root of NOT gate emerged as a quintessential example of a quantum gate, impossible to realize classically, highlighting the unique computational primitives offered by quantum mechanics. Furthermore, we briefly surveyed the active quantum computing research at our university, spanning quantum automata theory, quantum algorithms for graph problems, quantum circuit compilation, and the complexity theory of quantum problems. These areas represent both fundamental theoretical inquiries and practical challenges in realizing the potential of quantum computation.

Building upon these foundational concepts, future lectures and studies will delve into more advanced topics, including:

A rigorous treatment of unitary operators, their properties, and their role in quantum computation.
The concept of universal quantum gate sets and their construction.
In-depth analysis of quantum algorithms such as Deutsch’s algorithm and other algorithms demonstrating quantum speedup, including complexity analysis.
Quantum error correction techniques and the principles of fault-tolerant quantum computation, essential for building reliable quantum computers.
An overview of various physical platforms for quantum computing and the engineering challenges in their development and scaling.

These future explorations will further illuminate the exciting and rapidly evolving field of quantum computing, building upon the fundamental principles introduced in this lecture.

Consider a uniform random bit generator as a specific case, where all probabilities are equal: $P_{00} = P_{01} = P_{10} = P_{11} = \frac{1}{2}$. For this uniform generator, \[Q_{00} = \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) + \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}\] In fact, for a uniform random bit generator, it can be shown that all $Q_{ij} = \frac{1}{2}$. Thus, cascading two uniform random bit generators results in another uniform random bit generator.

However, if $P_{01} = 1$ and $P_{10} = 1$, the random bit generator itself is already a NOT gate:

Input 0 $\rightarrow$ Output 1 (probability 1).
Input 1 $\rightarrow$ Output 0 (probability 1).

If the first stage is already a NOT gate, then applying it twice yields an identity gate (NOT followed by NOT), not a NOT gate.

We have formally shown that within the framework of classical probabilistic logic, it is impossible to construct a probabilistic gate whose composition with itself behaves as a NOT gate, unless the gate is already essentially a NOT gate itself. This impossibility strongly suggests that classical probability is insufficient to model certain physical operations, hinting at the necessity of a more comprehensive mathematical framework, such as quantum mechanics.

Since two cascaded half-silvered mirrors, exploiting quantum interference, realize a NOT gate, a single half-silvered mirror is appropriately termed a "square root of NOT" gate. Applying this gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [sec:classical_vs_quantum_logic] that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate.

Applying the Square Root of NOT gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [sec:classical_vs_quantum_logic] that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate.

Let’s assume the following convention for a beam splitter:

Amplitude for Transmission: $t = \frac{1}{\sqrt{2}}$
Amplitude for Reflection: $r = \frac{i}{\sqrt{2}}$

Here, $i = \sqrt{-1}$ is the imaginary unit.

We represent the quantum states of a photon’s path using Dirac notation (ket notation). The state $\left|{0}\right\rangle$ represents the photon entering from input port 0, and $\left|{1}\right\rangle$ represents the photon entering from input port 1. Mathematically, we represent these as column vectors in a complex vector space: \[\left|{0}\right\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \left|{1}\right\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\]

A general quantum state, or qubit, can be a superposition of these basis states: \[\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}\] where $\alpha, \beta \in \mathbb{C}$ are complex amplitudes, and the normalization condition $|\alpha|^2 + |\beta|^2 = 1$ ensures that the total probability is 1. $|\alpha|^2$ is the probability of measuring the state in $\left|{0}\right\rangle$ and $|\beta|^2$ is the probability of measuring in $\left|{1}\right\rangle$.

Quantum operations, such as the square root of NOT gate, are mathematically described by unitary operators. A unitary operator $U$ is a linear transformation that preserves the inner product, and in matrix form, it satisfies $U U^\dagger = U^\dagger U = I$, where $U^\dagger$ is the conjugate transpose of $U$, and $I$ is the identity operator.

The unitarity of quantum gates is crucial because it ensures that quantum evolution preserves probabilities; the norm of the state vector remains constant throughout the computation.

Based on the complex amplitudes for transmission and reflection, the square root of NOT gate, realized by a half-silvered mirror, can be represented by the following $2 \times 2$ unitary matrix: \[\text{SquareRootNOT} = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix}\]

The final state is $i \left|{1}\right\rangle$. When we measure this output, the probability of obtaining outcome $\left|{0}\right\rangle$ is $|0|^2 = 0$, and the probability of obtaining outcome $\left|{1}\right\rangle$ is $|i|^2 = 1$. This perfectly matches the experimental observation that two cascaded half-silvered mirrors act as a NOT gate for input $\left|{0}\right\rangle$, resulting in output $\left|{1}\right\rangle$ with certainty. The factor $i$ is a global phase, which does not affect measurement probabilities. Similarly, applying SquareRootNOT twice to $\left|{1}\right\rangle$ will result in $\left|{0}\right\rangle$.

The mathematical framework of complex amplitudes and unitary operators elegantly captures quantum interference. The crucial aspect is that complex numbers can have both magnitude and phase, allowing for both constructive and destructive interference. In the cascaded half-silvered mirror example, the specific complex amplitudes associated with reflection and transmission, combined through matrix multiplication (representing sequential quantum operations), lead to the observed interference patterns. The fact that $i \times i = -1$ is central to achieving destructive interference. In the calculation above, the term $i^2 = -1$ directly contributes to the zero amplitude for the $\left|{0}\right\rangle$ component in the final state, leading to the deterministic NOT gate behavior, a phenomenon impossible to replicate with classical probabilities alone.

Deutsch’s algorithm is a seminal example illustrating the potential for quantum speedup. This algorithm, and its generalization, the Deutsch-Jozsa algorithm, demonstrates a scenario where a quantum computer can solve a specific problem with significantly fewer queries to a function oracle compared to any classical deterministic algorithm. In essence, these algorithms highlight a quantum advantage in query complexity.

In summary, quantum computation harnesses the quantum phenomena of superposition and interference to explore computational possibilities in a fundamentally novel way. This approach offers the potential for exponential speedups for specific classes of problems, marking a significant departure from the limitations of classical computation.

Our research in quantum automata theory delves into the quantum mechanical counterparts of classical automata models. This field investigates the fundamental differences in computational power and expressiveness between classical and quantum automata. A central theme is understanding how the principles of quantum mechanics, such as superposition and unitarity, alter the capabilities of automata. Interestingly, and somewhat counter-intuitively, it has been shown that basic models of quantum automata are fundamentally limited in recognizing even simple formal languages. Specifically, unlike classical automata, basic quantum automata cannot recognize finite languages. This limitation arises from the constraints imposed by unitarity, which restricts the types of operations permissible in quantum automata, leading to significant departures from classical automata theory.

Another significant research direction is the study of quantum random walks, which are quantum analogues of classical random walks on graphs. Classical random walks are a versatile tool in computer science, with applications ranging from graph analysis to algorithm design. Our research explores the potential of quantum random walks to provide more efficient algorithms for various graph problems compared to classical random walk-based approaches. A core challenge in this area is the representation of graph structures in a quantum computational framework. Specifically, to perform quantum random walks on a graph, the graph’s structure must be encoded into a unitary operator. Developing methods to achieve this encoding is a key focus.

We have developed a classical algorithm that can encode any graph into a unitary matrix, enabling quantum random walks. However, this encoding process may necessitate the addition of edges to the original graph to ensure the resulting matrix is unitary. The complexity of this encoding algorithm is quadratic in the size of the graph. This research aims to leverage the unique properties of quantum mechanics to enhance graph algorithms and explore new computational paradigms for network analysis.

Quantum circuit compilation is a critical area of research focused on bridging the gap between high-level quantum algorithms and their physical implementation on quantum hardware. Analogous to classical circuit compilation, quantum circuit compilation involves translating abstract quantum operations, often represented as large unitary matrices, into concrete sequences of elementary quantum gates from a universal gate set. This process is essential for executing quantum algorithms on actual quantum computers. A major challenge in quantum circuit compilation stems from the exponential scaling of quantum state spaces. For an $n$-qubit system, the unitary matrices describing quantum operations are of size $2^n \times 2^n$, making direct manipulation and decomposition computationally demanding.

Our research focuses on developing efficient classical algorithms for quantum circuit compilation, particularly for decomposing complex unitary operations into sequences of simpler, physically realizable gates. Currently, we are developing programming models and compilation techniques specifically targeted at optimizing circuits composed of controlled-NOT (CNOT) gates, a crucial two-qubit gate in quantum computation. This work aims to make quantum algorithms more practical and accessible for implementation on near-term quantum devices.

Finally, our research in quantum complexity theory addresses fundamental questions about the computational resources required to solve quantum problems and the inherent complexity of quantum computation itself. This area seeks to classify quantum computational problems within the framework of computational complexity theory, analogous to the P vs. NP question in classical complexity. We investigate the complexity classes of problems solvable by quantum computers and explore the relationships between quantum and classical complexity classes. A specific problem under investigation is the complexity of quantum circuit synthesis: given a unitary matrix, what is the complexity of finding an optimal (e.g., shortest) sequence of gates from a universal set that implements this matrix? While the precise complexity classification remains an open question, preliminary analysis suggests that this problem may be related to PSPACE-completeness, potentially reducible to planning problems. Determining the complexity landscape of quantum problems is crucial for understanding the ultimate capabilities and limitations of quantum computers and for guiding the development of efficient quantum algorithms.

--- title: "Lecture Notes on Quantum Computing: Foundations and Research" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction Quantum computing represents a paradigm shift from classical computation, necessitating a re-evaluation of fundamental concepts in logic and probability. This lecture will explore the foundational differences between classical and quantum approaches, drawing inspiration from the paper \"Machine logics and quantum physics\" by Dalla Chiara and Giuntini. We will begin by questioning the basis of classical logic and its applicability to quantum systems. Through the example of a random bit generator and its physical realization using a half-silvered mirror, we will demonstrate the limitations of classical probability in describing quantum phenomena. This will motivate the introduction of complex numbers and the concept of quantum interference as essential tools for modeling quantum systems. Furthermore, we will briefly discuss the potential for quantum computation to achieve significant speedups over classical methods and provide an overview of the ongoing quantum computing research at our university. This lecture aims to set the stage for a deeper exploration of the technical aspects of quantum computing, highlighting the crucial role computer scientists play in this evolving field. # Classical vs. Quantum Logic ## Why Classical Logic? Classical logic, the bedrock of our intuitive reasoning and digital computation, is deeply rooted in our everyday experiences with the macroscopic world. We readily accept its principles, such as the behavior of conjunction: \"A and B\" is true only if both A and B are true. This seems self-evident, a matter of common sense. But why is our common sense structured this way? As explored in the paper \"Machine logics and quantum physics,\" the adherence to classical logic may stem from the fact that the macroscopic objects we encounter daily behave in accordance with these logical rules. Even before the advent of electrical circuits, Boolean logic was formulated, later proving to be an effective tool for describing digital circuits where signals are definitively either 0 or 1. However, the crucial question arises: is classical logic universally valid, especially when we delve into the microscopic realm governed by quantum mechanics? If logic is to accurately model observed phenomena, we must consider revising our logical frameworks when dealing with quantum systems, where the familiar laws of classical logic may break down. ## Limitations of Classical Probability: The Random Bit Generator To illustrate the inadequacy of classical logic and probability in the quantum context, let us consider a seemingly simple device: a *random bit generator*. This hypothetical device takes a single bit (0 or 1) as input and produces a single bit (0 or 1) as output, with probabilistic behavior. Let $P_{ij}$ represent the probability of obtaining output $j$ when the input is $i$, where $i, j \in \{0, 1\}$. In classical probability theory, these probabilities are real numbers within the range $[0, 1]$. For a well-defined random bit generator, the probabilities must satisfy the normalization conditions: $$\begin{aligned}P_{00} + P_{01} &= 1 \\P_{10} + P_{11} &= 1\end{aligned}$$ These equations ensure that for each input, the sum of probabilities for all possible outputs is unity. Now, let's analyze the composition of two such random bit generators in sequence. Let $P_{ij}$ be the probabilities for the first generator and $Q_{ij}$ for the combined circuit. We aim to compute $Q_{ij}$. Specifically, consider $Q_{00}$, the probability of obtaining output 0 from the cascaded circuit given input 0. This can occur through two mutually exclusive paths: 1. Input 0 yields Output 0 from the first generator, and then Input 0 yields Output 0 from the second generator. The probability of this path is $P_{00} \times P_{00}$. 2. Input 0 yields Output 1 from the first generator, and then Input 1 yields Output 0 from the second generator. The probability of this path is $P_{01} \times P_{10}$. According to the rules of classical probability, the total probability $Q_{00}$ is the sum of the probabilities of these disjoint paths: $$Q_{00} = P_{00}P_{00} + P_{01}P_{10}$$ Similar calculations can be performed to determine $Q_{01}, Q_{10},$ and $Q_{11}$. ::: example **Example 1** (Uniform Random Bit Generator). Consider a *uniform random bit generator* as a specific case, where all probabilities are equal: $P_{00} = P_{01} = P_{10} = P_{11} = \frac{1}{2}$. For this uniform generator, $$Q_{00} = \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) + \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$ In fact, for a uniform random bit generator, it can be shown that all $Q_{ij} = \frac{1}{2}$. Thus, cascading two uniform random bit generators results in another uniform random bit generator. ::: Now, let us explore whether we can configure a random bit generator such that its square behaves like a classical NOT gate. A NOT gate has the deterministic behavior: - Input 0 $\rightarrow$ Output 1 (probability 1), Output 0 (probability 0). - Input 1 $\rightarrow$ Output 0 (probability 1), Output 1 (probability 0). For the squared random bit generator to act as a NOT gate, we would require $Q_{00} = 0$ and $Q_{01} = 1$ (and similarly $Q_{10} = 1$ and $Q_{11} = 0$). Focusing on the condition $Q_{00} = 0$: $$Q_{00} = P_{00}P_{00} + P_{01}P_{10} = 0$$ Since probabilities are non-negative real numbers, for this sum to be zero, both terms must individually be zero: $$P_{00}P_{00} = 0 \implies P_{00} = 0$$ $$P_{01}P_{10} = 0 \implies \text{either } P_{01} = 0 \text{ or } P_{10} = 0$$ If $P_{00} = 0$, then from the normalization condition $P_{00} + P_{01} = 1$, we deduce $P_{01} = 1$. Similarly, by considering the input 1 and the requirement $Q_{11} = 0$, we would find $P_{11} = 0$ and $P_{10} = 1$. ::: remark **Remark 1**. However, if $P_{01} = 1$ and $P_{10} = 1$, the random bit generator itself is already a NOT gate: - Input 0 $\rightarrow$ Output 1 (probability 1). - Input 1 $\rightarrow$ Output 0 (probability 1). If the first stage is already a NOT gate, then applying it twice yields an identity gate (NOT followed by NOT), not a NOT gate. ::: ::: theorem **Theorem 1** (Impossibility of Square Root of NOT in Classical Probabilistic Logic). *We have formally shown that within the framework of classical probabilistic logic, it is impossible to construct a probabilistic gate whose composition with itself behaves as a NOT gate, unless the gate is already essentially a NOT gate itself. This impossibility strongly suggests that classical probability is insufficient to model certain physical operations, hinting at the necessity of a more comprehensive mathematical framework, such as quantum mechanics.* ::: This impossibility strongly suggests that classical probability is insufficient to model certain physical operations, hinting at the necessity of a more comprehensive mathematical framework, such as quantum mechanics. # Physical Implementation: The Half-Silvered Mirror and Quantum Behavior The limitations of classical probability become strikingly apparent when we consider physical implementations of seemingly simple operations. Let's examine a device based on a half-silvered mirror, also known as a beam splitter, which experimentally demonstrates behavior fundamentally incompatible with classical predictions, acting as a \"square root of NOT\" gate. ## Single Photon Random Bit Generator Consider a setup where single photons are used as inputs. We define input $\left|{0}\right\rangle$ as a photon incident from one direction and input $\left|{1}\right\rangle$ as a photon incident from a perpendicular direction. The central component is a half-silvered mirror. <figure id="fig:single_photon_setup_physical"> <figcaption>Single Photon Experiment Setup with Half-Silvered Mirror</figcaption> </figure> When a single photon enters as input $\left|{0}\right\rangle$, it encounters the half-silvered mirror. This mirror is designed to reflect approximately half of the incident light intensity and transmit the other half. For a single photon, this translates to a 50% probability of reflection (detected at Detector 0) and a 50% probability of transmission (detected at Detector 1). The behavior is symmetrical for input $\left|{1}\right\rangle$. Experimentally, if we repeatedly send single photons as input $\left|{0}\right\rangle$, we observe that Detector 0 and Detector 1 each click approximately half the time. This is consistent with the behavior of a uniform random bit generator, as discussed in [\[sec:classical_vs_quantum_logic\]](#sec:classical_vs_quantum_logic){reference-type="ref+label" reference="sec:classical_vs_quantum_logic"}. ## The Paradox of Cascaded Half-Silvered Mirrors Now, let's consider a configuration where we cascade two half-silvered mirrors. To properly direct the photon paths, we introduce two standard mirrors in between. The setup is illustrated below: <figure id="fig:two_hsm_setup_physical"> <figcaption>Cascaded Half-Silvered Mirrors Setup</figcaption> </figure> Classically, if we input a photon as $\left|{0}\right\rangle$, at the first half-silvered mirror (HSM 1), there's a 50% chance of reflection upwards and 50% chance of transmission downwards. Following each path classically, one might expect that at the second half-silvered mirror (HSM 2), each component again has a 50/50 chance of reflection or transmission. Based on classical probability, we would predict that for input $\left|{0}\right\rangle$, the probability of reaching Output 0 (Detector 0) should be around 50%, similar to the single half-silvered mirror case. However, experimental results dramatically contradict this classical intuition. When we perform this experiment with single photons and input $\left|{0}\right\rangle$, Detector 0 *never* registers a photon, while Detector 1 *always* (or nearly always, in ideal conditions) registers a photon. This observed behavior is the opposite of what classical probability predicts. Similarly, for input $\left|{1}\right\rangle$, Detector 0 always clicks, and Detector 1 never clicks. Remarkably, the cascaded device behaves like a deterministic NOT gate, despite being built from probabilistic components according to classical understanding. ## Quantum Interference: Wave-like Photon Behavior The resolution to this paradox lies in the quantum mechanical nature of light and the phenomenon of *interference*. Unlike classical particles, photons can exhibit wave-like properties. When a photon encounters a half-silvered mirror, it does not simply randomly choose to be reflected or transmitted. Instead, it enters a *superposition* of both possibilities; it effectively takes both paths simultaneously. In the cascaded setup, the photon, originating from input $\left|{0}\right\rangle$, propagates through both paths created by the first HSM. These paths then recombine at the second HSM. Crucially, due to the wave nature of photons and the physics of beam splitters, a *phase difference* is introduced between the reflected and transmitted components at each half-silvered mirror. When the components from the two paths recombine at HSM 2, they *interfere*. In this specific configuration, the interference is *destructive* for the path leading to Output 0 and *constructive* for the path leading to Output 1 when the input is $\left|{0}\right\rangle$. Conversely, for input $\left|{1}\right\rangle$, the interference patterns are reversed, leading to Output 0. This interference effect is analogous to the famous double-slit experiment, where wave interference patterns are observed even when single particles are sent through the slits one at a time. Each photon effectively interferes with itself, traversing both possible paths and exhibiting wave-like behavior. An important aspect of quantum mechanics is the role of measurement. If we were to place a detector within the cascaded setup, for instance, to observe which path the photon takes after the first HSM, we would destroy the quantum superposition and the interference pattern. In such a case, the device would revert to behaving classically, with approximately 50% probability for each output, eliminating the NOT gate behavior. This illustrates the principle that measurement in quantum mechanics collapses superposition and disrupts interference phenomena. ## The Square Root of NOT Gate ::: definition **Definition 1** (Square Root of NOT Gate). Since two cascaded half-silvered mirrors, exploiting quantum interference, realize a NOT gate, a single half-silvered mirror is appropriately termed a \"square root of NOT\" gate. Applying this gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [\[sec:classical_vs_quantum_logic\]](#sec:classical_vs_quantum_logic){reference-type="ref+label" reference="sec:classical_vs_quantum_logic"} that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate. ::: ::: remark **Remark 2**. Applying the Square Root of NOT gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [\[sec:classical_vs_quantum_logic\]](#sec:classical_vs_quantum_logic){reference-type="ref+label" reference="sec:classical_vs_quantum_logic"} that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate. ::: The half-silvered mirror, acting as a square root of NOT gate, is not merely a probabilistic classical gate; it is a fundamentally quantum gate that leverages wave-like properties and interference. Its existence underscores the potential of quantum mechanics to perform operations that are impossible to achieve within the confines of classical probability and logic. # Mathematical Formalism: Complex Amplitudes and Quantum Gates To move beyond the limitations of classical probability and accurately describe quantum phenomena like interference and the square root of NOT gate, we must employ the mathematical framework of complex numbers and linear algebra. ## Complex Amplitudes and Probabilities ::: definition **Definition 2** (Complex Amplitudes for Beam Splitter). Let's assume the following convention for a beam splitter: - **Amplitude for Transmission:** $t = \frac{1}{\sqrt{2}}$ - **Amplitude for Reflection:** $r = \frac{i}{\sqrt{2}}$ ::: ::: definition **Definition 3** (Imaginary Unit $i$). Here, $i = \sqrt{-1}$ is the imaginary unit. ::: The square modulus of these amplitudes are $|t|^2 = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$ and $|r|^2 = \left|\frac{i}{\sqrt{2}}\right|^2 = \frac{1}{2}$, corresponding to the 50% probability of transmission and reflection, respectively. The imaginary unit $i$ in the reflection amplitude is essential; it represents a phase shift of $\pi/2$ upon reflection, which is the origin of quantum interference in this system. ::: definition **Definition 4** (Quantum States $\left|{0}\right\rangle$ and $\left|{1}\right\rangle$). We represent the quantum states of a photon's path using Dirac notation (ket notation). The state $\left|{0}\right\rangle$ represents the photon entering from input port 0, and $\left|{1}\right\rangle$ represents the photon entering from input port 1. Mathematically, we represent these as column vectors in a complex vector space: $$\left|{0}\right\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \left|{1}\right\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$ ::: ::: definition **Definition 5** (Qubit State). A general quantum state, or qubit, can be a superposition of these basis states: $$\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}$$ where $\alpha, \beta \in \mathbb{C}$ are complex amplitudes, and the normalization condition $|\alpha|^2 + |\beta|^2 = 1$ ensures that the total probability is 1. $|\alpha|^2$ is the probability of measuring the state in $\left|{0}\right\rangle$ and $|\beta|^2$ is the probability of measuring in $\left|{1}\right\rangle$. ::: ## Quantum Gates as Unitary Operators ::: definition **Definition 6** (Unitary Operator). Quantum operations, such as the square root of NOT gate, are mathematically described by *unitary operators*. A unitary operator $U$ is a linear transformation that preserves the inner product, and in matrix form, it satisfies $U U^\dagger = U^\dagger U = I$, where $U^\dagger$ is the conjugate transpose of $U$, and $I$ is the identity operator. ::: ::: remark **Remark 3**. The unitarity of quantum gates is crucial because it ensures that quantum evolution preserves probabilities; the norm of the state vector remains constant throughout the computation. ::: ## Matrix Representation of the Square Root of NOT Gate ::: definition **Definition 7** (Matrix Representation of Square Root of NOT Gate). Based on the complex amplitudes for transmission and reflection, the square root of NOT gate, realized by a half-silvered mirror, can be represented by the following $2 \times 2$ unitary matrix: $$\text{SquareRootNOT} = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix}$$ ::: Applying this SquareRootNOT gate to the input state $\left|{0}\right\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$: $$\text{SquareRootNOT} \left|{0}\right\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} i \\ 1 \end{pmatrix} = \frac{i}{\sqrt{2}} \left|{0}\right\rangle + \frac{1}{\sqrt{2}} \left|{1}\right\rangle$$ Now, applying the SquareRootNOT gate again to the resulting state: $$\text{SquareRootNOT} (\text{SquareRootNOT} \left|{0}\right\rangle) = \text{SquareRootNOT} \left( \frac{1}{\sqrt{2}} \begin{pmatrix} i \\ 1 \end{pmatrix} \right) = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix} \frac{1}{\sqrt{2}} \begin{pmatrix} i \\ 1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} i \cdot i + 1 \\ 1 \cdot i + i \cdot 1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} -1 + 1 \\ 2i \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 0 \\ 2i \end{pmatrix} = \begin{pmatrix} 0 \\ i \end{pmatrix} = i \begin{pmatrix} 0 \\ 1 \end{pmatrix} = i \left|{1}\right\rangle$$ ::: example **Example 2** (Cascaded Square Root of NOT Gate). The final state is $i \left|{1}\right\rangle$. When we measure this output, the probability of obtaining outcome $\left|{0}\right\rangle$ is $|0|^2 = 0$, and the probability of obtaining outcome $\left|{1}\right\rangle$ is $|i|^2 = 1$. This perfectly matches the experimental observation that two cascaded half-silvered mirrors act as a NOT gate for input $\left|{0}\right\rangle$, resulting in output $\left|{1}\right\rangle$ with certainty. The factor $i$ is a global phase, which does not affect measurement probabilities. Similarly, applying SquareRootNOT twice to $\left|{1}\right\rangle$ will result in $\left|{0}\right\rangle$. ::: ## Quantum Interference: The Role of Complex Numbers ::: remark **Remark 4**. The mathematical framework of complex amplitudes and unitary operators elegantly captures quantum interference. The crucial aspect is that complex numbers can have both magnitude and phase, allowing for both constructive and destructive interference. In the cascaded half-silvered mirror example, the specific complex amplitudes associated with reflection and transmission, combined through matrix multiplication (representing sequential quantum operations), lead to the observed interference patterns. The fact that $i \times i = -1$ is central to achieving destructive interference. In the calculation above, the term $i^2 = -1$ directly contributes to the zero amplitude for the $\left|{0}\right\rangle$ component in the final state, leading to the deterministic NOT gate behavior, a phenomenon impossible to replicate with classical probabilities alone. ::: # Quantum Computation and Potential for Speedup The significance of the square root of NOT gate extends beyond a mere demonstration of quantum weirdness. It serves as a fundamental building block in quantum algorithms, which hold the promise of solving certain computational problems far more efficiently than their classical counterparts. ## Quantum Advantage: Deutsch's Algorithm ::: example **Example 3** (Deutsch's Algorithm and Quantum Speedup). Deutsch's algorithm is a seminal example illustrating the potential for quantum speedup. This algorithm, and its generalization, the Deutsch-Jozsa algorithm, demonstrates a scenario where a quantum computer can solve a specific problem with significantly fewer queries to a function oracle compared to any classical deterministic algorithm. In essence, these algorithms highlight a quantum advantage in query complexity. ::: While the original formulation of Deutsch's algorithm often employs the Hadamard gate and controlled operations, it's important to note that quantum algorithms, including those demonstrating speedup, can be constructed using various sets of quantum gates, potentially including the square root of NOT gate in conjunction with other necessary gates to achieve universality. This underscores the versatility of quantum gates like the square root of NOT as components in more complex quantum circuits. **Note:** While the square root of NOT gate is a crucial quantum gate, it is not universal on its own. Universality typically requires a combination of gates, such as Hadamard, Phase, CNOT, and potentially others. This detail, while important, is not explicitly emphasized in this section of the transcript, so we maintain focus on the core message of speedup and the role of quantum gates as building blocks. Quantum computation, therefore, offers a fundamentally different approach to computation compared to both classical deterministic and probabilistic models, opening avenues for computational advantages in specific problem domains. ## Contrasting Computational Models: Deterministic, Probabilistic, and Quantum To better understand the nature of quantum speedup, it is helpful to contrast quantum computation with classical computational paradigms: - **Deterministic Computation:** Classical deterministic computation follows a single, predetermined sequence of steps from an initial state to a unique output. Each step is uniquely defined, and the computation path is fixed. - **Non-deterministic Computation:** Non-deterministic computation explores multiple computational paths simultaneously. An outcome is considered valid if *at least one* of these paths leads to a desired result. While non-determinism is a valuable concept in theoretical computer science for problem classification (e.g., NP complexity), it is typically simulated deterministically, often incurring an exponential time overhead. - **Probabilistic Computation:** Probabilistic computation introduces randomness into the computational process. Transitions between states occur with certain probabilities (represented by real numbers between 0 and 1). For a given input, there are multiple possible computational paths, each with an associated probability. The probability of a particular output is the sum of the probabilities of all paths leading to that output. Probabilistic algorithms can offer efficiency advantages over deterministic algorithms for certain problems, but they inherently involve a possibility of error, albeit controllable by repeating the computation. - **Quantum Computation:** Quantum computation, unlike classical approaches, leverages the principles of quantum mechanics, particularly superposition and interference. Computational states are represented by superpositions of basis states, and operations are performed using unitary transformations. Crucially, computation proceeds through multiple paths simultaneously, but instead of classical probabilities, these paths are associated with *complex amplitudes*. **Quantum interference**, arising from the properties of complex numbers, allows for both constructive and destructive interference between these computational paths. This unique feature enables quantum algorithms to achieve outcomes that are fundamentally different from, and in some cases superior to, both deterministic and probabilistic classical computation. For instance, destructive interference can selectively cancel out undesirable computational paths, potentially leading to exact solutions or significantly enhanced probabilities of correct results, surpassing the capabilities of probabilistic methods. ::: remark **Remark 5**. In summary, quantum computation harnesses the quantum phenomena of superposition and interference to explore computational possibilities in a fundamentally novel way. This approach offers the potential for exponential speedups for specific classes of problems, marking a significant departure from the limitations of classical computation. ::: # Quantum Computing Research at the University Riccardo Romanello, a PhD student in our department, provided insights into the quantum computing research activities at the university, highlighting several key areas of investigation. ## Quantum Automata Theory ::: remark **Remark 6**. Our research in quantum automata theory delves into the quantum mechanical counterparts of classical automata models. This field investigates the fundamental differences in computational power and expressiveness between classical and quantum automata. A central theme is understanding how the principles of quantum mechanics, such as superposition and unitarity, alter the capabilities of automata. Interestingly, and somewhat counter-intuitively, it has been shown that basic models of quantum automata are fundamentally limited in recognizing even simple formal languages. Specifically, unlike classical automata, basic quantum automata cannot recognize finite languages. This limitation arises from the constraints imposed by unitarity, which restricts the types of operations permissible in quantum automata, leading to significant departures from classical automata theory. ::: ## Quantum Random Walks and Graph Algorithms ::: remark **Remark 7**. Another significant research direction is the study of quantum random walks, which are quantum analogues of classical random walks on graphs. Classical random walks are a versatile tool in computer science, with applications ranging from graph analysis to algorithm design. Our research explores the potential of quantum random walks to provide more efficient algorithms for various graph problems compared to classical random walk-based approaches. A core challenge in this area is the representation of graph structures in a quantum computational framework. Specifically, to perform quantum random walks on a graph, the graph's structure must be encoded into a unitary operator. Developing methods to achieve this encoding is a key focus. ::: ::: algorithm **Algorithm 1** (Graph Encoding Algorithm). We have developed a classical algorithm that can encode any graph into a unitary matrix, enabling quantum random walks. However, this encoding process may necessitate the addition of edges to the original graph to ensure the resulting matrix is unitary. The complexity of this encoding algorithm is quadratic in the size of the graph. This research aims to leverage the unique properties of quantum mechanics to enhance graph algorithms and explore new computational paradigms for network analysis. ::: ## Quantum Circuit Compilation and Synthesis ::: remark **Remark 8**. Quantum circuit compilation is a critical area of research focused on bridging the gap between high-level quantum algorithms and their physical implementation on quantum hardware. Analogous to classical circuit compilation, quantum circuit compilation involves translating abstract quantum operations, often represented as large unitary matrices, into concrete sequences of elementary quantum gates from a universal gate set. This process is essential for executing quantum algorithms on actual quantum computers. A major challenge in quantum circuit compilation stems from the exponential scaling of quantum state spaces. For an $n$-qubit system, the unitary matrices describing quantum operations are of size $2^n \times 2^n$, making direct manipulation and decomposition computationally demanding. ::: ::: algorithm **Algorithm 2** (Quantum Circuit Compilation Techniques). Our research focuses on developing efficient classical algorithms for quantum circuit compilation, particularly for decomposing complex unitary operations into sequences of simpler, physically realizable gates. Currently, we are developing programming models and compilation techniques specifically targeted at optimizing circuits composed of controlled-NOT (CNOT) gates, a crucial two-qubit gate in quantum computation. This work aims to make quantum algorithms more practical and accessible for implementation on near-term quantum devices. ::: ## Complexity Theory of Quantum Problems ::: remark **Remark 9**. Finally, our research in quantum complexity theory addresses fundamental questions about the computational resources required to solve quantum problems and the inherent complexity of quantum computation itself. This area seeks to classify quantum computational problems within the framework of computational complexity theory, analogous to the P vs. NP question in classical complexity. We investigate the complexity classes of problems solvable by quantum computers and explore the relationships between quantum and classical complexity classes. A specific problem under investigation is the complexity of quantum circuit synthesis: given a unitary matrix, what is the complexity of finding an optimal (e.g., shortest) sequence of gates from a universal set that implements this matrix? While the precise complexity classification remains an open question, preliminary analysis suggests that this problem may be related to PSPACE-completeness, potentially reducible to planning problems. Determining the complexity landscape of quantum problems is crucial for understanding the ultimate capabilities and limitations of quantum computers and for guiding the development of efficient quantum algorithms. ::: # Conclusion This lecture has laid the groundwork for understanding quantum computing by contrasting it with classical logic and computation. We have seen that classical logic, while intuitive for macroscopic phenomena, fails to explain the behavior of quantum systems. The experiment with cascaded half-silvered mirrors starkly demonstrated the limitations of classical probability and necessitated the introduction of complex amplitudes and the concept of quantum interference. The square root of NOT gate emerged as a quintessential example of a quantum gate, impossible to realize classically, highlighting the unique computational primitives offered by quantum mechanics. Furthermore, we briefly surveyed the active quantum computing research at our university, spanning quantum automata theory, quantum algorithms for graph problems, quantum circuit compilation, and the complexity theory of quantum problems. These areas represent both fundamental theoretical inquiries and practical challenges in realizing the potential of quantum computation. Building upon these foundational concepts, future lectures and studies will delve into more advanced topics, including: - A rigorous treatment of unitary operators, their properties, and their role in quantum computation. - The concept of universal quantum gate sets and their construction. - In-depth analysis of quantum algorithms such as Deutsch's algorithm and other algorithms demonstrating quantum speedup, including complexity analysis. - Quantum error correction techniques and the principles of fault-tolerant quantum computation, essential for building reliable quantum computers. - An overview of various physical platforms for quantum computing and the engineering challenges in their development and scaling. These future explorations will further illuminate the exciting and rapidly evolving field of quantum computing, building upon the fundamental principles introduced in this lecture. ::: tcolorbox Consider a *uniform random bit generator* as a specific case, where all probabilities are equal: $P_{00} = P_{01} = P_{10} = P_{11} = \frac{1}{2}$. For this uniform generator, $$Q_{00} = \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) + \left(\frac{1}{2}\right)\left(\frac{1}{2}\right) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$ In fact, for a uniform random bit generator, it can be shown that all $Q_{ij} = \frac{1}{2}$. Thus, cascading two uniform random bit generators results in another uniform random bit generator. ::: ::: tcolorbox However, if $P_{01} = 1$ and $P_{10} = 1$, the random bit generator itself is already a NOT gate: - Input 0 $\rightarrow$ Output 1 (probability 1). - Input 1 $\rightarrow$ Output 0 (probability 1). If the first stage is already a NOT gate, then applying it twice yields an identity gate (NOT followed by NOT), not a NOT gate. ::: ::: tcolorbox We have formally shown that within the framework of classical probabilistic logic, it is impossible to construct a probabilistic gate whose composition with itself behaves as a NOT gate, unless the gate is already essentially a NOT gate itself. This impossibility strongly suggests that classical probability is insufficient to model certain physical operations, hinting at the necessity of a more comprehensive mathematical framework, such as quantum mechanics. ::: ::: tcolorbox Since two cascaded half-silvered mirrors, exploiting quantum interference, realize a NOT gate, a single half-silvered mirror is appropriately termed a \"square root of NOT\" gate. Applying this gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [\[sec:classical_vs_quantum_logic\]](#sec:classical_vs_quantum_logic){reference-type="ref+label" reference="sec:classical_vs_quantum_logic"} that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate. ::: ::: tcolorbox Applying the Square Root of NOT gate twice results in the NOT operation. This is a purely quantum effect, as we demonstrated in [\[sec:classical_vs_quantum_logic\]](#sec:classical_vs_quantum_logic){reference-type="ref+label" reference="sec:classical_vs_quantum_logic"} that no classical probabilistic gate can be composed with itself to produce a deterministic NOT gate. ::: ::: tcolorbox Let's assume the following convention for a beam splitter: - **Amplitude for Transmission:** $t = \frac{1}{\sqrt{2}}$ - **Amplitude for Reflection:** $r = \frac{i}{\sqrt{2}}$ ::: ::: tcolorbox Here, $i = \sqrt{-1}$ is the imaginary unit. ::: ::: tcolorbox We represent the quantum states of a photon's path using Dirac notation (ket notation). The state $\left|{0}\right\rangle$ represents the photon entering from input port 0, and $\left|{1}\right\rangle$ represents the photon entering from input port 1. Mathematically, we represent these as column vectors in a complex vector space: $$\left|{0}\right\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \left|{1}\right\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$ ::: ::: tcolorbox A general quantum state, or qubit, can be a superposition of these basis states: $$\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}$$ where $\alpha, \beta \in \mathbb{C}$ are complex amplitudes, and the normalization condition $|\alpha|^2 + |\beta|^2 = 1$ ensures that the total probability is 1. $|\alpha|^2$ is the probability of measuring the state in $\left|{0}\right\rangle$ and $|\beta|^2$ is the probability of measuring in $\left|{1}\right\rangle$. ::: ::: tcolorbox Quantum operations, such as the square root of NOT gate, are mathematically described by *unitary operators*. A unitary operator $U$ is a linear transformation that preserves the inner product, and in matrix form, it satisfies $U U^\dagger = U^\dagger U = I$, where $U^\dagger$ is the conjugate transpose of $U$, and $I$ is the identity operator. ::: ::: tcolorbox The unitarity of quantum gates is crucial because it ensures that quantum evolution preserves probabilities; the norm of the state vector remains constant throughout the computation. ::: ::: tcolorbox Based on the complex amplitudes for transmission and reflection, the square root of NOT gate, realized by a half-silvered mirror, can be represented by the following $2 \times 2$ unitary matrix: $$\text{SquareRootNOT} = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix}$$ ::: ::: tcolorbox The final state is $i \left|{1}\right\rangle$. When we measure this output, the probability of obtaining outcome $\left|{0}\right\rangle$ is $|0|^2 = 0$, and the probability of obtaining outcome $\left|{1}\right\rangle$ is $|i|^2 = 1$. This perfectly matches the experimental observation that two cascaded half-silvered mirrors act as a NOT gate for input $\left|{0}\right\rangle$, resulting in output $\left|{1}\right\rangle$ with certainty. The factor $i$ is a global phase, which does not affect measurement probabilities. Similarly, applying SquareRootNOT twice to $\left|{1}\right\rangle$ will result in $\left|{0}\right\rangle$. ::: ::: tcolorbox The mathematical framework of complex amplitudes and unitary operators elegantly captures quantum interference. The crucial aspect is that complex numbers can have both magnitude and phase, allowing for both constructive and destructive interference. In the cascaded half-silvered mirror example, the specific complex amplitudes associated with reflection and transmission, combined through matrix multiplication (representing sequential quantum operations), lead to the observed interference patterns. The fact that $i \times i = -1$ is central to achieving destructive interference. In the calculation above, the term $i^2 = -1$ directly contributes to the zero amplitude for the $\left|{0}\right\rangle$ component in the final state, leading to the deterministic NOT gate behavior, a phenomenon impossible to replicate with classical probabilities alone. ::: ::: tcolorbox Deutsch's algorithm is a seminal example illustrating the potential for quantum speedup. This algorithm, and its generalization, the Deutsch-Jozsa algorithm, demonstrates a scenario where a quantum computer can solve a specific problem with significantly fewer queries to a function oracle compared to any classical deterministic algorithm. In essence, these algorithms highlight a quantum advantage in query complexity. ::: ::: tcolorbox In summary, quantum computation harnesses the quantum phenomena of superposition and interference to explore computational possibilities in a fundamentally novel way. This approach offers the potential for exponential speedups for specific classes of problems, marking a significant departure from the limitations of classical computation. ::: ::: tcolorbox Our research in quantum automata theory delves into the quantum mechanical counterparts of classical automata models. This field investigates the fundamental differences in computational power and expressiveness between classical and quantum automata. A central theme is understanding how the principles of quantum mechanics, such as superposition and unitarity, alter the capabilities of automata. Interestingly, and somewhat counter-intuitively, it has been shown that basic models of quantum automata are fundamentally limited in recognizing even simple formal languages. Specifically, unlike classical automata, basic quantum automata cannot recognize finite languages. This limitation arises from the constraints imposed by unitarity, which restricts the types of operations permissible in quantum automata, leading to significant departures from classical automata theory. ::: ::: tcolorbox Another significant research direction is the study of quantum random walks, which are quantum analogues of classical random walks on graphs. Classical random walks are a versatile tool in computer science, with applications ranging from graph analysis to algorithm design. Our research explores the potential of quantum random walks to provide more efficient algorithms for various graph problems compared to classical random walk-based approaches. A core challenge in this area is the representation of graph structures in a quantum computational framework. Specifically, to perform quantum random walks on a graph, the graph's structure must be encoded into a unitary operator. Developing methods to achieve this encoding is a key focus. ::: ::: tcolorbox We have developed a classical algorithm that can encode any graph into a unitary matrix, enabling quantum random walks. However, this encoding process may necessitate the addition of edges to the original graph to ensure the resulting matrix is unitary. The complexity of this encoding algorithm is quadratic in the size of the graph. This research aims to leverage the unique properties of quantum mechanics to enhance graph algorithms and explore new computational paradigms for network analysis. ::: ::: tcolorbox Quantum circuit compilation is a critical area of research focused on bridging the gap between high-level quantum algorithms and their physical implementation on quantum hardware. Analogous to classical circuit compilation, quantum circuit compilation involves translating abstract quantum operations, often represented as large unitary matrices, into concrete sequences of elementary quantum gates from a universal gate set. This process is essential for executing quantum algorithms on actual quantum computers. A major challenge in quantum circuit compilation stems from the exponential scaling of quantum state spaces. For an $n$-qubit system, the unitary matrices describing quantum operations are of size $2^n \times 2^n$, making direct manipulation and decomposition computationally demanding. ::: ::: tcolorbox Our research focuses on developing efficient classical algorithms for quantum circuit compilation, particularly for decomposing complex unitary operations into sequences of simpler, physically realizable gates. Currently, we are developing programming models and compilation techniques specifically targeted at optimizing circuits composed of controlled-NOT (CNOT) gates, a crucial two-qubit gate in quantum computation. This work aims to make quantum algorithms more practical and accessible for implementation on near-term quantum devices. ::: ::: tcolorbox Finally, our research in quantum complexity theory addresses fundamental questions about the computational resources required to solve quantum problems and the inherent complexity of quantum computation itself. This area seeks to classify quantum computational problems within the framework of computational complexity theory, analogous to the P vs. NP question in classical complexity. We investigate the complexity classes of problems solvable by quantum computers and explore the relationships between quantum and classical complexity classes. A specific problem under investigation is the complexity of quantum circuit synthesis: given a unitary matrix, what is the complexity of finding an optimal (e.g., shortest) sequence of gates from a universal set that implements this matrix? While the precise complexity classification remains an open question, preliminary analysis suggests that this problem may be related to PSPACE-completeness, potentially reducible to planning problems. Determining the complexity landscape of quantum problems is crucial for understanding the ultimate capabilities and limitations of quantum computers and for guiding the development of efficient quantum algorithms. :::