Lecture Notes on Quantum Computing and Communication
Introduction
Welcome to this course, Quantum Computing and Communication, a foundational introduction to quantum technologies within the field of informatics. This course is structured into two parts. The first part, presented by myself, a physicist specializing in entanglement theory, will lay the groundwork in quantum theory and introduce the essential tools for understanding quantum technologies. The second part will be conducted by Professor Piazza, an expert in informatics, who will explore quantum complexity and algorithms.
Quantum technology is a rapidly advancing field, achieving notable successes particularly in quantum communications. Its ongoing development makes it crucial to gain knowledge and understanding in this domain.
Our primary reference for this course will be Quantum Computation and Quantum Information by Nielsen and Chuang, published by Cambridge University Press. This textbook will serve as the main guide for both parts of the lectures. While numerous other resources are available, Nielsen and Chuang is highly recommended for its comprehensive and accessible introduction to the subject.
The course is designed to provide a broad overview initially, introducing fundamental concepts and basic algorithms to establish context before delving into more detailed topics. This approach mirrors the structure of our primary textbook, ensuring a coherent learning progression.
Course Outline
The initial overview will cover:
Qubits
Quantum Gates
Quantum Circuits
Basic Quantum Algorithms
Quantum Teleportation
Following this introduction, we will delve deeper into:
Linear Algebra Recap: Focusing on complex numbers, which are essential for quantum mechanics.
Quantum Mechanics Postulates: Introducing the fundamental principles of quantum mechanics, tailored for quantum computing applications.
Quantum Circuits and Algorithms: Detailed exploration of quantum circuit design and significant quantum algorithms.
Computational Complexity: Examining new complexity classes introduced by quantum computation.
Quantum Communication: A key area of quantum technology with current practical applications.
Principles of Quantum Computers: An overview of the fundamental principles behind quantum computer architecture, time permitting.
Today’s lecture will commence with a fundamental introduction to complex numbers, as they are indispensable for the mathematical formulation of quantum mechanics.
Basic Concepts of Quantum Computing
Complex Numbers in Quantum Mechanics
Motivation for Complex Numbers
In classical computing and many areas of mathematics dealing with real-world phenomena, real numbers are sufficient. However, quantum mechanics is fundamentally built upon the framework of complex numbers. This necessity arises from the inherent nature of quantum phenomena, which require a richer mathematical structure to be described accurately. Historically, the expansion of number systems in mathematics has been driven by the need to solve problems that are unsolvable within existing systems. Starting from natural numbers, expanding to integers to accommodate subtraction, then to rational numbers for division, and finally to real numbers for completeness in calculus, each extension broadened the scope of solvable problems. Complex numbers represent a similar, crucial extension for quantum mechanics.
Consider the simple algebraic equation: \[x^2 = -1\] Within the set of real numbers, there is no solution for \(x\). To find a solution, we must extend our number system to include imaginary and complex numbers. This extension is not merely a mathematical abstraction but is essential for describing the wave-like nature of quantum particles and phenomena such as superposition and interference.
Definition of Complex Numbers
To solve equations like \(x^2 = -1\), we introduce the imaginary unit, denoted as \(i\) (in physics and mathematics; engineers often use \(j\)). The imaginary unit is defined as the square root of \(-1\): \[i = \sqrt{-1} \implies i^2 = -1\]
Using the imaginary unit, we define a complex number.
Definition 1 (Complex Number).
A complex number \(z\) is a number of the form: \[z = a + ib\] where \(a\) and \(b\) are real numbers, and \(i\) is the imaginary unit. The real part of \(z\) is \(a\), denoted as \(\operatorname{Re}(z) = a\), and the imaginary part is \(ib\), with the imaginary component being \(b\), denoted as \(\operatorname{Im}(z) = b\).
Basic Operations with Complex Numbers
Let \(z_1 = a + ib\) and \(z_2 = c + id\) be two complex numbers, where \(a, b, c, d \in \mathbb{R}\). We define the basic arithmetic operations as follows:
Addition
Complex number addition is performed by adding the real parts and the imaginary parts separately: \[z_1 + z_2 = (a + ib) + (c + id) = (a+c) + i(b+d)\]
Multiplication
Complex number multiplication is performed using the distributive property and the fact that \(i^2 = -1\): \[\begin{aligned}z_1 \cdot z_2 &= (a + ib) \cdot (c + id) \\&= a \cdot c + a \cdot (id) + (ib) \cdot c + (ib) \cdot (id) \\&= ac + iad + ibc + i^2bd \\&= ac + iad + ibc - bd \quad (\text{since } i^2 = -1) \\&= (ac - bd) + i(ad + bc)\end{aligned}\] The result of multiplying two complex numbers is also a complex number.
Complex Conjugate and Modulus
Definition 2 (Complex Conjugate).
The complex conjugate of a complex number \(z = a + ib\), denoted as \(\overline{z}\) or \(z^*\), is obtained by reversing the sign of the imaginary part: \[\overline{z} = z^* = a - ib\]
Definition 3 (Modulus (or Norm) of a Complex Number).
The modulus (or norm) of a complex number \(z = a + ib\), denoted as \(|z|\), is a non-negative real number representing the "size" or magnitude of the complex number. It is defined as the square root of the product of \(z\) and its complex conjugate \(z^*\): \[|z| = \sqrt{z \cdot z^*} = \sqrt{(a + ib)(a - ib)} = \sqrt{a^2 - (ib)^2} = \sqrt{a^2 - i^2b^2} = \sqrt{a^2 + b^2}\] Equivalently, \(|z|^2 = z \cdot z^* = a^2 + b^2\).
The modulus \(|z|\) is analogous to the absolute value for real numbers and represents the distance of the complex number from the origin in the complex plane.
Geometric Representation: Complex Plane
Complex numbers can be visualized as points in a two-dimensional plane called the complex plane or Argand plane. The horizontal axis is the real axis, representing the real part, and the vertical axis is the imaginary axis, representing the imaginary part. A complex number \(z = a + ib\) is represented by the point \((a, b)\) in this plane, or equivalently, by the vector from the origin to the point \((a, b)\).
The complex conjugate \(z^* = a - ib\) is geometrically represented by reflecting the point \(z\) across the real axis.
Alternatively, we can use polar coordinates to represent a complex number. In polar form, a complex number \(z\) is described by its modulus \(r = |z|\) and the angle \(\phi\) (argument or phase) it makes with the positive real axis, measured counterclockwise. The relationships between Cartesian coordinates \((a, b)\) and polar coordinates \((r, \phi)\) are: \[\begin{aligned}a &= r \cos \phi \\b &= r \sin \phi\end{aligned}\] Thus, a complex number \(z\) can be written in polar form as: \[z = a + ib = r(\cos \phi + i \sin \phi)\]
Euler’s Formula and Phase
A fundamental connection between complex exponentials and trigonometric functions is given by Euler’s formula: \[e^{i\phi} = \cos \phi + i \sin \phi\] where \(\phi\) is a real number, representing an angle in radians. This formula is derived from the Taylor series expansions of the exponential function \(e^x\), cosine function \(\cos x\), and sine function \(\sin x\).
Derivation using Taylor Series Expansions
The Taylor series expansion of \(e^x\) around \(x=0\) is: \[e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \dots\] Substituting \(x = i\phi\) into the Taylor series for \(e^x\): \[e^{i\phi} = \sum_{k=0}^{\infty} \frac{(i\phi)^k}{k!} = 1 + (i\phi) + \frac{(i\phi)^2}{2!} + \frac{(i\phi)^3}{3!} + \frac{(i\phi)^4}{4!} + \dots\] Using the properties of the imaginary unit (\(i^2 = -1, i^3 = -i, i^4 = 1\), etc.), we can separate the real and imaginary terms: \[\begin{aligned}e^{i\phi} &= \left(1 + \frac{(i\phi)^2}{2!} + \frac{(i\phi)^4}{4!} + \dots\right) + \left((i\phi) + \frac{(i\phi)^3}{3!} + \frac{(i\phi)^5}{5!} + \dots\right) \\&= \left(1 - \frac{\phi^2}{2!} + \frac{\phi^4}{4!} - \dots\right) + i\left(\phi - \frac{\phi^3}{3!} + \frac{\phi^5}{5!} - \dots\right)\end{aligned}\] Recognizing the Taylor series for cosine and sine functions: \[\begin{aligned}\cos \phi &= 1 - \frac{\phi^2}{2!} + \frac{\phi^4}{4!} - \dots = \sum_{k=0}^{\infty} \frac{(-1)^k \phi^{2k}}{(2k)!} \\\sin \phi &= \phi - \frac{\phi^3}{3!} + \frac{\phi^5}{5!} - \dots = \sum_{k=0}^{\infty} \frac{(-1)^k \phi^{2k+1}}{(2k+1)!}\end{aligned}\] We arrive at Euler’s formula: \[e^{i\phi} = \cos \phi + i \sin \phi\]
The angle \(\phi\) in \(e^{i\phi}\) is referred to as the phase or argument of the complex number. Using Euler’s formula, the polar form of a complex number \(z\) can be written compactly as: \[z = r e^{i\phi} = |z| e^{i \arg(z)}\] where \(r = |z|\) is the modulus and \(\phi = \arg(z)\) is the argument (phase) of \(z\).
Fundamental Theorem of Algebra
The completeness of complex numbers is highlighted by the Fundamental Theorem of Algebra.
Theorem 1 (Fundamental Theorem of Algebra).
Every non-constant single-variable polynomial with complex coefficients has at least one complex root. Consequently, every polynomial equation of degree \(n \geq 1\) with complex coefficients has exactly \(n\) complex roots, counted with multiplicity.
This theorem is a cornerstone of algebra, ensuring that within the complex number system, every polynomial equation of degree \(n\) has precisely \(n\) solutions. This property does not hold for real numbers, for example, \(x^2 + 1 = 0\) has no real roots but has two complex roots, \(x = \pm i\). The Fundamental Theorem of Algebra underscores the algebraic closure of the complex number field, making it a natural and complete setting for many mathematical theories, including quantum mechanics.
Qubits: Quantum Bits
Definition of a Qubit and Superposition
In classical computing, the basic unit of information is the bit, which can represent either 0 or 1. Quantum computing introduces the qubit (quantum bit) as its fundamental unit. Unlike a classical bit, a qubit leverages the principles of quantum mechanics to exist in a state of superposition.
Definition 4 (Qubit).
A qubit is the quantum analogue of a classical bit. It is a two-level quantum system where its state can be a superposition of two computational basis states, denoted as \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). A general state of a qubit, denoted as \(\left|{\psi}\right\rangle\), is a linear combination of these basis states: \[\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\] where \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\) are orthonormal basis vectors in a two-dimensional complex vector space, and \(\alpha\) and \(\beta\) are complex numbers known as complex amplitudes.
The state \(\left|{\psi}\right\rangle\) is not definitively 0 or 1, but rather a probabilistic combination of both possibilities. This is the principle of superposition, a hallmark of quantum mechanics. It means that before measurement, the qubit exists in a coherent blend of both \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\) states, weighted by the complex amplitudes \(\alpha\) and \(\beta\).
Complex Amplitudes and Normalization
In the superposition state \(\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\), the complex amplitudes \(\alpha\) and \(\beta\) are crucial. They dictate the probabilities of obtaining each basis state upon measurement. These amplitudes must satisfy a normalization condition to ensure that the probabilities sum to unity:
\[|\alpha|^2 + |\beta|^2 = 1\] Here, \(|\alpha|^2\) and \(|\beta|^2\) represent the probabilities of measuring the qubit in state \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\) respectively. The normalization condition ensures that the total probability of all possible outcomes is exactly 1, consistent with the probabilistic interpretation of quantum mechanics.
Information in a Qubit
A classical bit can store either 0 or 1, representing a definite state. In contrast, a qubit, through superposition, can exist in a continuum of states between \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). Described by complex amplitudes \(\alpha\) and \(\beta\), a qubit appears to hold significantly more information than a classical bit. Since each complex number is defined by two real numbers, and real numbers can have infinite precision, it might seem that a single qubit can store an infinite amount of information.
However, this apparent infinite information is not directly accessible. The act of measurement fundamentally limits the information we can extract from a qubit.
Measurement and State Collapse
When a qubit in a superposition state \(\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\) is measured in the computational basis \(\{\left|{0}\right\rangle, \left|{1}\right\rangle\}\), the outcome is probabilistic and causes the qubit’s superposition to collapse.
The measurement process yields one of two outcomes:
Outcome \(\left|{0}\right\rangle\) with probability \(P(\left|{0}\right\rangle) = |\alpha|^2\).
Outcome \(\left|{1}\right\rangle\) with probability \(P(\left|{1}\right\rangle) = |\beta|^2\).
Immediately after measurement, the qubit collapses into the state corresponding to the outcome. This is known as state collapse or wave function collapse.
If the measurement outcome is \(\left|{0}\right\rangle\), the qubit’s state becomes \(\left|{0}\right\rangle\).
If the measurement outcome is \(\left|{1}\right\rangle\), the qubit’s state becomes \(\left|{1}\right\rangle\).
The superposition, which was the defining feature of the qubit, is destroyed by the act of measurement. We extract only classical information—a single bit (0 or 1)—from the measurement. Despite the rich information potentially encoded in the superposition, measurement forces the qubit to choose a definite classical state. Quantum technologies aim to utilize the power of superposition and entanglement before measurement to perform computations and communications in ways that are impossible for classical systems. The challenge lies in designing algorithms and protocols that effectively exploit these quantum properties before decoherence and measurement limit their utility.
Bloch Sphere Representation of a Qubit
The Bloch sphere provides a geometrical visualization of pure qubit states. It maps the abstract state space of a qubit onto the surface of a unit sphere in three dimensions. Any pure state of a qubit can be represented as a point on the surface of the Bloch sphere.
Given a qubit state \(\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\), we can express the complex amplitudes \(\alpha\) and \(\beta\) in terms of real parameters. We can factor out a global phase from \(\alpha\), writing \(\alpha = |\alpha|e^{i\gamma}\) and \(\beta = |\beta|e^{i\delta}\). Then, \(\left|{\psi}\right\rangle = |\alpha|e^{i\gamma} \left|{0}\right\rangle + |\beta|e^{i\delta} \left|{1}\right\rangle = e^{i\gamma} (|\alpha| \left|{0}\right\rangle + |\beta|e^{i(\delta-\gamma)} \left|{1}\right\rangle)\). Since a global phase factor \(e^{i\gamma}\) has no physical observable effect, we can disregard it and consider the state \(\left|{\psi'}\right\rangle = |\alpha| \left|{0}\right\rangle + |\beta|e^{i\phi'} \left|{1}\right\rangle\), where \(\phi' = \delta-\gamma\). Using the normalization condition \(|\alpha|^2 + |\beta|^2 = 1\), we can set \(|\alpha| = \cos(\theta/2)\) and \(|\beta| = \sin(\theta/2)\) for some angle \(\theta \in [0, \pi]\). Let \(\phi = \phi'\). Then, a general qubit state can be parameterized as: \[\left|{\psi}\right\rangle = \cos\left(\frac{\theta}{2}\right) \left|{0}\right\rangle + e^{i\phi} \sin\left(\frac{\theta}{2}\right) \left|{1}\right\rangle\] where \(\theta \in [0, \pi]\) is the polar angle and \(\phi \in [0, 2\pi)\) is the azimuthal angle in spherical coordinates.
In the Bloch sphere visualization (see 1):
The state \(\left|{0}\right\rangle\) is conventionally placed at the North Pole (\(\theta = 0\)).
The state \(\left|{1}\right\rangle\) is at the South Pole (\(\theta = \pi\)).
All other qubit states correspond to points on the surface of the sphere, uniquely determined by the angles \(\theta\) and \(\phi\) (up to a global phase).
The Bloch sphere provides an intuitive way to visualize and understand single-qubit states and transformations.
Physical Implementations of Qubits
Qubits are not abstract mathematical entities but must be physically realized using quantum systems. Various physical systems with two distinguishable quantum states can be employed to create qubits. The choice of physical implementation depends on factors such as coherence time, gate fidelity, scalability, and operational temperature.
Common physical implementations of qubits include:
Spins of Electrons or Nuclei: The intrinsic angular momentum (spin) of particles like electrons or atomic nuclei can be used. Spin-1/2 particles have two spin states, "spin-up" and "spin-down," which can represent \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). Nuclear Magnetic Resonance (NMR) quantum computers were among the earliest implementations using nuclear spins.
Energy Levels of Atoms (Trapped Ions): Atoms have discrete energy levels. Two specific energy levels, such as the ground state and an excited state, can be chosen to represent \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). Trapped ions, where individual ions are confined and controlled using electromagnetic fields, are a prominent platform.
Polarization of Photons: Photons, the quanta of light, have polarization, which describes the orientation of their oscillation. Horizontal and vertical polarizations, or other pairs of orthogonal polarizations, can represent \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). Photonic qubits are particularly relevant for quantum communication.
Superconducting Circuits (Transmons): Superconducting circuits are macroscopic quantum systems. Specifically designed superconducting circuits, such as transmon qubits, exhibit quantum behavior and can be engineered to have two effective quantum states representing \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). Superconducting qubits are currently a leading technology in quantum computing, pursued by companies like Google and IBM.
Quantum Dots: Semiconductor nanocrystals, known as quantum dots, can confine electrons. The spin of an electron in a quantum dot can serve as a qubit.
Topological Qubits: These qubits are based on exotic states of matter with topological properties that make them inherently more robust against decoherence. They are a more theoretical and challenging approach but promise higher stability.
Creating and maintaining functional qubits is a significant technological challenge. Quantum systems are inherently susceptible to interactions with their environment, leading to decoherence. Decoherence is the loss of quantum coherence, where the superposition states degrade into classical mixtures, destroying the quantum information. Unlike classical bits, which are robust and stable, qubits are delicate and require extreme isolation and precise control to minimize decoherence. Extending the coherence time—the duration for which a qubit maintains its quantum properties—and improving the fidelity of quantum gates are major areas of ongoing research and development in quantum computing.
Multiple Qubits and Entanglement
Tensor Product for Multi-Qubit States
To describe systems composed of multiple qubits, we use the mathematical operation of the tensor product. The tensor product combines the state spaces of individual qubits to form the state space of the composite system. For a system of two qubits, if the first qubit is in state \(\left|{\psi_1}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\) and the second qubit is in state \(\left|{\psi_2}\right\rangle = \gamma \left|{0}\right\rangle + \delta \left|{1}\right\rangle\), the state of the combined two-qubit system is given by the tensor product of the individual states: \[\begin{aligned}\left|{\psi_{12}}\right\rangle &= \left|{\psi_1}\right\rangle \otimes \left|{\psi_2}\right\rangle = (\alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle) \otimes (\gamma \left|{0}\right\rangle + \delta \left|{1}\right\rangle) \\&= \alpha\gamma (\left|{0}\right\rangle \otimes \left|{0}\right\rangle) + \alpha\delta (\left|{0}\right\rangle \otimes \left|{1}\right\rangle) + \beta\gamma (\left|{1}\right\rangle \otimes \left|{0}\right\rangle) + \beta\delta (\left|{1}\right\rangle \otimes \left|{1}\right\rangle)\end{aligned}\] For notational convenience, we often write the basis states of a two-qubit system as \(\left|{00}\right\rangle = \left|{0}\right\rangle \otimes \left|{0}\right\rangle\), \(\left|{01}\right\rangle = \left|{0}\right\rangle \otimes \left|{1}\right\rangle\), \(\left|{10}\right\rangle = \left|{1}\right\rangle \otimes \left|{0}\right\rangle\), and \(\left|{11}\right\rangle = \left|{1}\right\rangle \otimes \left|{1}\right\rangle\). Using this notation, the two-qubit state becomes: \[\left|{\psi_{12}}\right\rangle = \alpha\gamma \left|{00}\right\rangle + \alpha\delta \left|{01}\right\rangle + \beta\gamma \left|{10}\right\rangle + \beta\delta \left|{11}\right\rangle\] The computational basis for a two-qubit system is thus \(\{\left|{00}\right\rangle, \left|{01}\right\rangle, \left|{10}\right\rangle, \left|{11}\right\rangle\}\). In general, for a system of \(n\) qubits, the computational basis consists of \(2^n\) states, formed by taking tensor products of \(n\) single-qubit basis states.
Superposition in Multi-Qubit Systems
Similar to single qubits, multi-qubit systems can also exist in superposition states. A general superposition state for a two-qubit system is a linear combination of all four basis states: \[\left|{\Psi}\right\rangle = \alpha_{00} \left|{00}\right\rangle + \alpha_{01} \left|{01}\right\rangle + \alpha_{10} \left|{10}\right\rangle + \alpha_{11} \left|{11}\right\rangle\] where \(\alpha_{00}, \alpha_{01}, \alpha_{10}, \alpha_{11}\) are complex amplitudes. The normalization condition for these amplitudes is: \[|\alpha_{00}|^2 + |\alpha_{01}|^2 + |\alpha_{10}|^2 + |\alpha_{11}|^2 = 1\] This normalization ensures that the sum of probabilities of all possible measurement outcomes is unity. For an \(n\)-qubit system, a general superposition state is a linear combination of all \(2^n\) basis states, with \(2^n\) complex amplitudes that must satisfy a similar normalization condition. This exponential growth in the state space dimension with the number of qubits is what provides quantum computers with the potential for immense computational power.
Probabilities and Measurement of Multiple Qubits
When a measurement is performed on a multi-qubit system, we obtain a classical outcome for each qubit in the system. For a two-qubit state \(\left|{\Psi}\right\rangle = \alpha_{00} \left|{00}\right\rangle + \alpha_{01} \left|{01}\right\rangle + \alpha_{10} \left|{10}\right\rangle + \alpha_{11} \left|{11}\right\rangle\), the probabilities of obtaining each of the four possible outcomes when measuring in the computational basis are given by the squared moduli of the corresponding amplitudes:
Probability of measuring \(\left|{00}\right\rangle\): \(P(\left|{00}\right\rangle) = |\alpha_{00}|^2\)
Probability of measuring \(\left|{01}\right\rangle\): \(P(\left|{01}\right\rangle) = |\alpha_{01}|^2\)
Probability of measuring \(\left|{10}\right\rangle\): \(P(\left|{10}\right\rangle) = |\alpha_{10}|^2\)
Probability of measuring \(\left|{11}\right\rangle\): \(P(\left|{11}\right\rangle) = |\alpha_{11}|^2\)
If we are interested in the probability of measuring a specific outcome for only one qubit, say the first qubit, regardless of the outcome for the second qubit, we sum the probabilities of all basis states consistent with that outcome. For example, the probability of measuring the first qubit to be \(\left|{0}\right\rangle\) is the sum of the probabilities of measuring \(\left|{00}\right\rangle\) and \(\left|{01}\right\rangle\): \[P(\text{first qubit is } \left|{0}\right\rangle) = P(\left|{00}\right\rangle) + P(\left|{01}\right\rangle) = |\alpha_{00}|^2 + |\alpha_{01}|^2\] Similarly, the probability of measuring the first qubit to be \(\left|{1}\right\rangle\) is: \[P(\text{first qubit is } \left|{1}\right\rangle) = P(\left|{10}\right\rangle) + P(\left|{11}\right\rangle) = |\alpha_{10}|^2 + |\alpha_{11}|^2\] And for the second qubit: \[\begin{aligned}P(\text{second qubit is } \left|{0}\right\rangle) &= P(\left|{00}\right\rangle) + P(\left|{10}\right\rangle) = |\alpha_{00}|^2 + |\alpha_{10}|^2 \\P(\text{second qubit is } \left|{1}\right\rangle) &= P(\left|{01}\right\rangle) + P(\left|{11}\right\rangle) = |\alpha_{01}|^2 + |\alpha_{11}|^2\end{aligned}\] After measurement, the state of the system collapses to the measured state, and it must be renormalized if we consider the state after a partial measurement. Forinstance, if we measure the first qubit and obtain \(\left|{0}\right\rangle\), the state collapses to a state proportional to \(\alpha_{00} \left|{00}\right\rangle + \alpha_{01} \left|{01}\right\rangle\). After normalization, the post-measurement state becomes: \[\left|{\Psi'}\right\rangle = \frac{\alpha_{00}}{\sqrt{|\alpha_{00}|^2 + |\alpha_{01}|^2}} \left|{00}\right\rangle + \frac{\alpha_{01}}{\sqrt{|\alpha_{00}|^2 + |\alpha_{01}|^2}} \left|{01}\right\rangle\] This state is now a superposition only within the subspace where the first qubit is \(\left|{0}\right\rangle\).
Bell States: Examples of Entangled States
Bell states, also known as EPR pairs or Bell pairs, are a set of four specific maximally entangled two-qubit states. They are paradigmatic examples of entanglement and are fundamental in quantum information theory and applications, including quantum teleportation and superdense coding. The four Bell states are:
\[\begin{aligned}\left|{\Phi^+}\right\rangle &= \frac{1}{\sqrt{2}} (\left|{00}\right\rangle + \left|{11}\right\rangle) \\\left|{\Phi^-}\right\rangle &= \frac{1}{\sqrt{2}} (\left|{00}\right\rangle - \left|{11}\right\rangle) \\\left|{\Psi^+}\right\rangle &= \frac{1}{\sqrt{2}} (\left|{01}\right\rangle + \left|{10}\right\rangle) \\\left|{\Psi^-}\right\rangle &= \frac{1}{\sqrt{2}} (\left|{01}\right\rangle - \left|{10}\right\rangle)\end{aligned}\] Each Bell state is normalized and orthogonal to the others. Let’s consider the Bell state \(\left|{\Psi^-}\right\rangle = \frac{1}{\sqrt{2}} (\left|{01}\right\rangle - \left|{10}\right\rangle)\) as an example. If we measure the first qubit in the computational basis and find it to be \(\left|{0}\right\rangle\), the state collapses to \(\left|{01}\right\rangle\) (after normalization). If we measure the first qubit and find it to be \(\left|{1}\right\rangle\), the state collapses to \(\left|{10}\right\rangle\) (again, after normalization, and the sign difference is irrelevant for single measurement probabilities). This demonstrates perfect anti-correlation: if the first qubit is measured to be \(\left|{0}\right\rangle\), we know with certainty that the second qubit will be \(\left|{1}\right\rangle\), and vice versa. This instantaneous correlation, regardless of distance, is a key feature of entanglement and is fundamentally non-classical. The correlations exhibited by Bell states are stronger than any classical correlations, a fact formalized by Bell’s theorem, which will be discussed in more detail later in this course. These states are not just theoretical constructs; they are experimentally realizable and have been created and verified in numerous quantum experiments, highlighting the reality and power of quantum entanglement.
Quantum Gates and Quantum Circuits
Quantum Gates: Operations on Qubits
Quantum gates are the fundamental operations in quantum computing, analogous to logic gates in classical digital circuits. However, unlike classical gates that manipulate bits, quantum gates manipulate qubits, leveraging quantum mechanical phenomena like superposition and entanglement to perform computations. Quantum gates are represented mathematically as unitary transformations acting on the state space of qubits.
Classical Gates vs. Quantum Gates: Key Differences
Classical and quantum gates differ significantly in their properties and operational principles.
Reversibility
Classical gates like AND, OR, and NAND are generally irreversible. Irreversibility means that information is lost during the computation, and it’s impossible to uniquely determine the input from the output. For instance, if an AND gate outputs 0, the inputs could be (0,0), (0,1), or (1,0). In contrast, quantum gates, except for measurement, are fundamentally reversible. This reversibility stems from the fact that quantum evolution is described by unitary operators, which are inherently invertible. This implies that no information is lost when a quantum gate is applied, and the original state can always be recovered by applying the inverse quantum gate (adjoint or conjugate transpose).
Parallel Processing
A significant advantage of quantum gates over classical gates is their ability to perform parallel processing of quantum states. If a qubit is in a superposition of states, a quantum gate operates on all components of the superposition simultaneously. Consider a qubit in superposition \(\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\). Applying a quantum gate \(U\) to \(\left|{\psi}\right\rangle\) results in \(U\left|{\psi}\right\rangle = U(\alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle) = \alpha U\left|{0}\right\rangle + \beta U\left|{1}\right\rangle\). The gate \(U\) is applied to both basis states \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\) at the same time, weighted by their respective amplitudes \(\alpha\) and \(\beta\). This inherent parallelism allows quantum computers to explore multiple computational paths simultaneously, offering potential speedups for certain types of problems compared to classical algorithms that must process each state sequentially.
Single-Qubit Gates
Single-qubit gates operate on individual qubits and can be visualized as rotations on the Bloch sphere. Some fundamental single-qubit gates are:
Pauli-X Gate (NOT Gate)
The Pauli-X gate, denoted as \(X\), is analogous to the classical NOT gate. It flips the computational basis states of a qubit: \[\begin{aligned}X\left|{0}\right\rangle &= \left|{1}\right\rangle \\X\left|{1}\right\rangle &= \left|{0}\right\rangle\end{aligned}\] In matrix representation with respect to the computational basis \(\{\left|{0}\right\rangle, \left|{1}\right\rangle\}\), the Pauli-X gate is represented by the matrix: \[X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\] Applying the X gate to a superposition state \(\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\) yields: \[X\left|{\psi}\right\rangle = X(\alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle) = \alpha X\left|{0}\right\rangle + \beta X\left|{1}\right\rangle = \alpha \left|{1}\right\rangle + \beta \left|{0}\right\rangle = \beta \left|{0}\right\rangle + \alpha \left|{1}\right\rangle\] The Pauli-X gate effectively swaps the amplitudes of the \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\) states.
Hadamard Gate (H Gate)
The Hadamard gate, denoted as \(H\), is a crucial single-qubit gate that creates superposition states from definite states. It transforms the basis states as: \[\begin{aligned}H\left|{0}\right\rangle &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle + \left|{1}\right\rangle) \\H\left|{1}\right\rangle &= \frac{1}{\sqrt{2}} (\left|{0}\right\rangle - \left|{1}\right\rangle)\end{aligned}\] The matrix representation of the Hadamard gate is: \[H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\] Applying the Hadamard gate to \(\left|{0}\right\rangle\) or \(\left|{1}\right\rangle\) creates an equal superposition of \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). Applying the Hadamard gate twice in sequence, \(H^2\), results in the identity operation, \(H^2 = I\), up to a global phase for \(\left|{1}\right\rangle\).
Pauli-Z Gate (Z Gate)
The Pauli-Z gate, denoted as \(Z\), leaves the \(\left|{0}\right\rangle\) state unchanged but introduces a phase shift of \(\pi\) (flips the sign) to the \(\left|{1}\right\rangle\) state: \[\begin{aligned}Z\left|{0}\right\rangle &= \left|{0}\right\rangle \\Z\left|{1}\right\rangle &= -\left|{1}\right\rangle\end{aligned}\] The matrix representation of the Pauli-Z gate is: \[Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\] Applying the Z gate to a superposition state \(\left|{\psi}\right\rangle = \alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle\) results in: \[Z\left|{\psi}\right\rangle = Z(\alpha \left|{0}\right\rangle + \beta \left|{1}\right\rangle) = \alpha Z\left|{0}\right\rangle + \beta Z\left|{1}\right\rangle = \alpha \left|{0}\right\rangle - \beta \left|{1}\right\rangle\] The Pauli-Z gate is a phase gate, altering the relative phase between the \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\) components of a superposition.
Two-Qubit Gates
Two-qubit gates operate on pairs of qubits and are essential for creating entanglement and enabling interactions between qubits, which are necessary for complex quantum computations.
Controlled-NOT Gate (CNOT Gate)
The Controlled-NOT (CNOT) gate, often denoted as CNOT or \(CX\), is a fundamental two-qubit gate. It operates on a control qubit and a target qubit. The CNOT gate flips the state of the target qubit (applies the X gate) if and only if the control qubit is in the state \(\left|{1}\right\rangle\). If the control qubit is \(\left|{0}\right\rangle\), the target qubit remains unchanged. Let qubit 1 be the control and qubit 2 be the target. The action of the CNOT gate on the computational basis states is: \[\begin{aligned}\text{CNOT} (\left|{00}\right\rangle) &= \left|{00}\right\rangle \\\text{CNOT} (\left|{01}\right\rangle) &= \left|{01}\right\rangle \\\text{CNOT} (\left|{10}\right\rangle) &= \left|{11}\right\rangle \\\text{CNOT} (\left|{11}\right\rangle) &= \left|{10}\right\rangle\end{aligned}\] The matrix representation of the CNOT gate in the computational basis \(\{\left|{00}\right\rangle, \left|{01}\right\rangle, \left|{10}\right\rangle, \left|{11}\right\rangle\}\) is: \[\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\] The CNOT gate is crucial for creating entanglement. For example, starting with the product state \(\left|{00}\right\rangle\) and applying a Hadamard gate to the first qubit followed by a CNOT gate, we can generate the Bell state \(\left|{\Phi^+}\right\rangle = \frac{1}{\sqrt{2}} (\left|{00}\right\rangle + \left|{11}\right\rangle)\).
Controlled-U Gate (Controlled-Unitary Gate)
The Controlled-U gate, or \(CU\) gate, is a generalization of the CNOT gate. It applies an arbitrary single-qubit gate \(U\) to the target qubit only when the control qubit is in the state \(\left|{1}\right\rangle\). If the control qubit is \(\left|{0}\right\rangle\), the target qubit is left unchanged (effectively applying the identity gate \(I\)). Let \(U\) be any single-qubit gate. The operation of the Controlled-U gate is defined as: \[\begin{aligned}\text{Controlled-}U (\left|{0}\right\rangle\left|{\psi}\right\rangle) &= \left|{0}\right\rangle \otimes (I\left|{\psi}\right\rangle) = \left|{0}\right\rangle\left|{\psi}\right\rangle \\\text{Controlled-}U (\left|{1}\right\rangle\left|{\psi}\right\rangle) &= \left|{1}\right\rangle \otimes (U\left|{\psi}\right\rangle) = \left|{1}\right\rangle U\left|{\psi}\right\rangle\end{aligned}\] where \(\left|{\psi}\right\rangle\) is the state of the target qubit, and \(I\) is the identity gate. The CNOT gate is a specific instance of the Controlled-U gate where \(U = X\).
Universality of Quantum Gates
In quantum computation, a set of quantum gates is considered universal if any arbitrary unitary transformation on any number of qubits can be approximated to any desired degree of accuracy using only gates from this set. Universality is a critical concept because it implies that a small set of gates is sufficient to perform any quantum computation.
CNOT and Single-Qubit Gates: A Universal Set
A fundamental result in quantum computing theory is that the combination of the CNOT gate and all single-qubit gates forms a universal set of quantum gates. This means that any quantum algorithm can be implemented using circuits composed solely of CNOT gates and single-qubit gates. This universality is essential for practical quantum computer design, as it simplifies the hardware requirements and provides a clear path for implementing complex quantum computations. While "all single-qubit gates" is a continuous set, in practice, a finite set of single-qubit gates, such as Hadamard, Phase, and \(\pi/8\) gates, along with the CNOT gate, is sufficient for universality.
Unitary Transformations and Quantum Evolution
Quantum gates are mathematically represented by unitary matrices. A matrix \(U\) is unitary if its conjugate transpose (Hermitian adjoint) \(U^\dagger\) is also its inverse, i.e., \(U^\dagger U = U U^\dagger = I\), where \(I\) is the identity matrix. The conjugate transpose \(U^\dagger\) is obtained by transposing the matrix \(U\) and then taking the complex conjugate of each element. For real matrices, the conjugate transpose is simply the transpose (\(U^\dagger = U^T\)).
Unitary transformations are crucial in quantum mechanics because they preserve the norm (and thus probabilities) of quantum states. If \(\left|{\psi}\right\rangle\) is a normalized quantum state (\(\left\langle{\psi}\middle|{\psi}\right\rangle = 1\)), and \(U\) is a unitary operator, then the transformed state \(\left|{\psi'}\right\rangle = U\left|{\psi}\right\rangle\) is also normalized: \[\left\langle{\psi'}\middle|{\psi'}\right\rangle = \left\langle{U\psi}\middle|{U\psi}\right\rangle = \left\langle{\psi}\right|U^\dagger U\left|{\psi}\right\rangle = \left\langle{\psi}\right|I\left|{\psi}\right\rangle = \left\langle{\psi}\middle|{\psi}\right\rangle = 1\] This norm preservation is essential because probabilities in quantum mechanics are derived from the squared amplitudes of quantum states, and the sum of probabilities must always be 1. The time evolution of a closed quantum system is described by unitary transformations, according to the Schrödinger equation. Quantum gates, as physical operations on qubits, must therefore be implemented by unitary transformations to ensure valid quantum evolution.
Quantum Circuits: Combining Gates for Quantum Algorithms
Quantum circuits are constructed by combining quantum gates in a specific sequence to perform quantum computations. They are analogous to classical electronic circuits, but operate on qubits and utilize quantum gates to implement quantum algorithms.
Circuit Diagrams and Notation
Quantum circuits are visually represented using circuit diagrams. In these diagrams:
Qubit Lines: Horizontal lines represent qubits, with the flow of time proceeding from left to right. Each line typically represents a single qubit throughout the circuit’s duration.
Quantum Gates: Boxes drawn on the qubit lines symbolize quantum gates acting on the qubits. The type of gate is indicated by a symbol or label inside the box (e.g., \(H\), \(X\), \(Z\), CNOT, \(U\)).
Multiple Qubits: Multiple horizontal lines stacked vertically represent a multi-qubit system. Gates acting on multiple qubits, like CNOT, span across the corresponding qubit lines.
Control and Target Qubits: For two-qubit gates like CNOT and Controlled-U, specific notations are used to denote control and target qubits. For CNOT, a filled circle (\(\bullet\)) is often used on the control qubit line, connected by a vertical line to a circled plus (\(\oplus\)) on the target qubit line.
Measurement: Measurement operations are typically depicted by a meter symbol at the end of a qubit line, indicating that the qubit’s state is measured at that point, yielding a classical bit as output.
Circuit diagrams provide a visual and intuitive way to represent quantum algorithms and analyze the sequence of operations performed on qubits.
Example: Qubit Swap Circuit
Let’s analyze the qubit swap circuit presented in the transcript. This circuit is designed to exchange the quantum states of two qubits using a sequence of three CNOT gates. The circuit diagram is as follows:
Let’s trace the operation of this circuit on an arbitrary two-qubit state \(\left|{AB}\right\rangle\), where \(A\) is the state of Qubit 1 and \(B\) is the state of Qubit 2, and \(A, B \in \{0, 1\}\).
First CNOT Gate: The control qubit is Qubit 1, and the target qubit is Qubit 2. The operation transforms the state to \(\text{CNOT}_{12} (\left|{A}\right\rangle\left|{B}\right\rangle) = \left|{A}\right\rangle\left|{A \oplus B}\right\rangle\), where \(\oplus\) denotes addition modulo 2 (XOR operation).
Second CNOT Gate: The control qubit is now Qubit 2 (in state \(\left|{A \oplus B}\right\rangle\)), and the target qubit is Qubit 1 (in state \(\left|{A}\right\rangle\)). The operation \(\text{CNOT}_{21}\) (CNOT with control on qubit 2 and target on qubit 1) transforms the state to \(\text{CNOT}_{21} (\left|{A}\right\rangle\left|{A \oplus B}\right\rangle) = \left|{(A \oplus B) \oplus A}\right\rangle\left|{A \oplus B}\right\rangle = \left|{B}\right\rangle\left|{A \oplus B}\right\rangle\).
Third CNOT Gate: The control qubit is again Qubit 1 (now in state \(\left|{B}\right\rangle\)), and the target qubit is Qubit 2 (in state \(\left|{A \oplus B}\right\rangle\)). The operation \(\text{CNOT}_{12}\) transforms the state to \(\text{CNOT}_{12} (\left|{B}\right\rangle\left|{A \oplus B}\right\rangle) = \left|{B}\right\rangle\left|{B \oplus (A \oplus B)}\right\rangle = \left|{B}\right\rangle\left|{A}\right\rangle\).
Therefore, the overall effect of this three-CNOT circuit is to swap the states of the two qubits: \(\left|{AB}\right\rangle \xrightarrow{\text{Swap Circuit}} \left|{BA}\right\rangle\). This circuit is commonly used in quantum algorithms to exchange qubit information.
Key Differences Between Quantum and Classical Circuits
Quantum circuits exhibit several fundamental differences from classical circuits, arising from the principles of quantum mechanics:
Absence of Loops
Quantum circuits are generally designed as feedforward networks, without feedback loops. The inclusion of loops in quantum circuits can lead to complexities related to causality and maintaining unitarity of quantum evolution. Quantum computations typically proceed in a linear sequence of gate operations followed by measurement.
No Fan-in
In classical circuits, multiple input signals can be combined into a single output using gates like AND or OR (fan-in). In quantum circuits, there is no direct analogue of fan-in for qubits. Quantum information processing maintains a linear flow of qubits through the circuit. While operations can correlate qubits, they do not merge or reduce the number of qubits in the circuit’s progression, except through measurement which extracts classical information.
No Fan-out and the No-Cloning Theorem
A critical distinction is the impossibility of fan-out in quantum circuits, a consequence of the No-Cloning Theorem. In classical circuits, a signal can be duplicated and sent to multiple destinations (fan-out). However, quantum mechanics fundamentally prohibits the perfect cloning of arbitrary unknown quantum states.
Theorem 2 (No-Cloning Theorem).
There exists no unitary operation (and therefore no quantum circuit) that can perfectly duplicate an arbitrary unknown quantum state. More formally, there is no unitary operator \(U\) that can perform the transformation \(U(\left|{\psi}\right\rangle \otimes \left|{0}\right\rangle) = \left|{\psi}\right\rangle \otimes \left|{\psi}\right\rangle\) for all arbitrary quantum states \(\left|{\psi}\right\rangle\).
The No-Cloning Theorem is a cornerstone of quantum information theory. It implies that it is impossible to create a quantum copy machine that can make identical copies of an unknown quantum state. Any attempt to measure or interact with a quantum state to copy it will inevitably disturb the original state, preventing perfect replication.
Remark. Remark 1 (No-Cloning Theorem Implications).
The No-Cloning Theorem implies that it is impossible to create a quantum copy machine that can make identical copies of an unknown quantum state. Any attempt to measure or interact with a quantum state to copy it will inevitably disturb the original state, preventing perfect replication.
The transcript mentioned an attempt to design a quantum copying circuit, which will be discussed further to illustrate why it fails due to the No-Cloning Theorem. This theorem has profound implications for quantum computing and, especially, quantum communication.
Implications for Quantum Communication Security
The No-Cloning Theorem is the foundation of secure quantum communication, particularly in quantum cryptography and quantum key distribution (QKD). Because quantum states cannot be perfectly copied, any attempt by an eavesdropper to intercept and copy a quantum signal transmitted between two parties will inevitably introduce detectable disturbances. This fundamental property ensures the security of quantum communication protocols, as any eavesdropping attempt can be detected, alerting legitimate communicators to the presence of an adversary. Protocols like BB84 leverage the No-Cloning Theorem to establish secure communication channels with information-theoretic security, a level of security not achievable with classical cryptography alone.
Preview of the No-Cloning Theorem and Copying Circuit Failure
The attempted quantum copying circuit mentioned in the lecture serves as a practical demonstration of the No-Cloning Theorem. The inherent linearity and unitarity of quantum mechanics, which are essential for quantum computation, are precisely what prevent the perfect copying of quantum states. The failure of any proposed quantum copying circuit will be explained by the No-Cloning Theorem in subsequent lectures, highlighting the fundamental differences between classical and quantum information manipulation and the unique security advantages offered by quantum communication.
Conclusion
This lecture has laid the groundwork for understanding quantum computing and communication by introducing the fundamental role of complex numbers in quantum mechanics, and then progressing to define qubits, superposition, entanglement, quantum gates, and quantum circuits. We have highlighted the essential distinctions between classical and quantum computing paradigms, focusing on the inherent reversibility of quantum gates, the power of parallel processing through superposition, and the profound implications of the No-Cloning Theorem.
Key Takeaways
Complex Numbers as the Language of Quantum Mechanics: Quantum mechanics fundamentally relies on complex numbers, which are essential for describing quantum states and operations. They enable solutions to equations and representations of phenomena that are impossible within the realm of real numbers alone.
Qubits and Superposition for Enhanced Information Representation: Qubits, unlike classical bits, can exist in superposition states, representing a probabilistic combination of \(\left|{0}\right\rangle\) and \(\left|{1}\right\rangle\). This capability allows qubits to encode and process information in a fundamentally richer way than classical bits.
Entanglement: Quantum Correlations Beyond Classical Limits: Entanglement is a uniquely quantum phenomenon that creates strong correlations between qubits, irrespective of distance. These correlations are fundamentally different from classical correlations and are a critical resource for quantum computation and communication.
Reversible Quantum Gates for Coherent Manipulation: Quantum gates are unitary and therefore reversible, ensuring that quantum operations are coherent and no quantum information is lost during computation (except through measurement). They operate on superpositions in parallel, enabling quantum computers to perform computations in a fundamentally different manner than classical computers.
The No-Cloning Theorem and Security in Quantum Communication: The No-Cloning Theorem is a fundamental constraint in quantum mechanics, stating that unknown quantum states cannot be perfectly duplicated. This theorem is not a limitation but a feature that underpins the security of quantum communication, guaranteeing that eavesdropping attempts can be detected.
Next Steps
In our subsequent lectures, we will expand on these foundational concepts and explore:
The No-Cloning Theorem in Depth: We will rigorously examine why quantum copying circuits inevitably fail, directly linking this failure to the No-Cloning Theorem and the linearity of quantum mechanics.
Formal Proof and Implications of the No-Cloning Theorem: We will delve into the formal proof of the No-Cloning Theorem and discuss its far-reaching implications for quantum information science and technology.
Quantum Algorithms and Computational Advantage: We will begin to explore specific quantum algorithms that leverage superposition and entanglement to solve computational problems more efficiently than known classical algorithms.
Quantum Communication Protocols and Security Applications: We will investigate quantum communication protocols, such as quantum key distribution, and examine how the principles of quantum mechanics, particularly the No-Cloning Theorem, are used to achieve secure communication.
Unitary Transformations and Gate Decomposition: We will further analyze unitary transformations as the mathematical representation of quantum gates and discuss how complex unitary operations can be decomposed into sequences of elementary quantum gates.
Preparation for the Next Lecture:
To prepare for the upcoming lectures, please review the concepts covered today, particularly:
The algebra of complex numbers and Euler’s formula.
The definition of a qubit and the concept of superposition.
The phenomenon of quantum entanglement and Bell states.
The basic single-qubit gates (X, H, Z) and the two-qubit CNOT gate.
The concept of quantum circuits and their differences from classical circuits.
A solid understanding of these fundamental concepts is crucial for grasping the more advanced topics we will explore in the following lectures on quantum computing and communication.