Lecture Notes on Quantum Computation - Single and Two-Qubit Gates

Author

Your Name

Published

February 5, 2025

Introduction

In this lecture, we will explore the construction of quantum circuits, focusing on single-qubit and two-qubit gates. We will begin by revisiting the theorem stating that any unitary operation can be realized using single-qubit unitaries and the CNOT gate. This lecture will constructively examine how to decompose complex unitary operations into sequences of single-qubit gates and CNOT gates. We will analyze single-qubit unitary gates, including the Identity gate, Pauli gates (X, Y, Z), Hadamard gate, Phase gate (S), and $\pi/8$ gate (T), and their representation on the Bloch sphere. We will then discuss two-qubit gates, specifically the Controlled-NOT (CNOT) gate and the Controlled-U gate, and explore the implementation of Controlled-U using CNOT and single-qubit gates. Finally, we will introduce the concept of decomposing unitary operators into two-level operators, which is a key step towards realizing arbitrary unitary operations. This lecture aims to provide a foundational understanding of quantum circuit construction using elementary gates.

Single-Qubit Unitaries

Review of Unitary Decomposition Theorem

As previously stated, a key theorem in quantum computation asserts that any unitary operation can be constructed using single-qubit unitary gates and the CNOT gate. This is a cornerstone of quantum computing, establishing the universality of these gate sets. A more advanced result, not detailed here due to its complexity, demonstrates that a finite set of gates suffices to approximate any unitary operation to arbitrary precision. This section focuses on the constructive aspect of the primary theorem, illustrating the decomposition of unitary operations into sequences of single-qubit and CNOT gates.

Fundamental Single-Qubit Gates

Single-qubit gates operate on individual qubits and serve as elementary operations in quantum circuits. We introduce a set of essential single-qubit gates.

Identity Gate (I)

The Identity gate ($I$) is the most basic single-qubit gate, leaving the qubit state unchanged. It is represented by the identity matrix: \[I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\] While seemingly trivial, the Identity gate is conceptually important and can be used for timing adjustments within quantum circuits.

Pauli Gates (X, Y, Z)

The Pauli gates are a set of fundamental single-qubit gates, corresponding to the Pauli matrices:

Pauli-X Gate (X) or NOT Gate: \[X = \sigma_x = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\] The X gate performs a bit-flip operation, transforming $\left|{0}\right\rangle \leftrightarrow \left|{1}\right\rangle$.
Pauli-Y Gate (Y): \[Y = \sigma_y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}\] The Pauli-Y gate corresponds to a rotation of $\pi$ radians around the Y-axis on the Bloch sphere.
Pauli-Z Gate (Z): \[Z = \sigma_z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\] The Pauli-Z gate introduces a phase of $-1$ to the $\left|{1}\right\rangle$ state, leaving $\left|{0}\right\rangle$ unchanged.

Hadamard Gate (H)

The Hadamard gate ($H$) is essential for creating superposition states. Its matrix representation is: \[H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\] It transforms the computational basis states as: \[H\left|{0}\right\rangle = \frac{\left|{0}\right\rangle + \left|{1}\right\rangle}{\sqrt{2}} = \left|{+}\right\rangle , \quad H\left|{1}\right\rangle = \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} = \left|{-}\right\rangle\]

Phase Gate (S) and $\pi/8$ Gate (T)

The Phase gate ($S$) and the $\pi/8$ gate ($T$) are crucial for introducing phase shifts in quantum computations.

Phase Gate (S): \[S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}\] The S gate applies a phase shift of $\pi/2$ to the $\left|{1}\right\rangle$ state.
$\pi/8$ Gate (T): \[T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\] The T gate, also known as the $\pi/8$ gate, applies a phase shift of $\pi/4$ to the $\left|{1}\right\rangle$ state. The name $\pi/8$ gate arises from an alternative representation involving a global phase factor, although it directly applies a $\pi/4$ phase.

Bloch Sphere Representation of Qubits

The Bloch sphere provides a geometrical representation of single-qubit states. Any qubit state $\left|{\psi}\right\rangle$ can be expressed 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. On the Bloch sphere:

$\left|{0}\right\rangle$ corresponds to the North Pole.
$\left|{1}\right\rangle$ corresponds to the South Pole.
$\theta$ is the angle from the positive Z-axis.
$\phi$ is the angle of the projection onto the XY-plane from the positive X-axis.

Unitary Gates as Bloch Sphere Rotations

Unitary gates on a qubit can be visualized as rotations of the Bloch vector on the Bloch sphere.

Rotation around the Z-axis: $R_z(\alpha)$ and the Z Gate

A rotation around the Z-axis by an angle $\alpha$ is given by the operator $R_z(\alpha)$. It modifies the azimuthal angle $\phi$ while keeping the polar angle $\theta$ constant. The matrix representation is: \[R_z(\alpha) = \begin{pmatrix} e^{-i\alpha/2} & 0 \\ 0 & e^{i\alpha/2} \end{pmatrix}\] Ignoring the global phase factor $e^{-i\alpha/2}$, we can write: \[R_z(\alpha) \propto \begin{pmatrix} 1 & 0 \\ 0 & e^{i\alpha} \end{pmatrix}\] The Pauli-Z gate corresponds to a rotation around the Z-axis by $\alpha = \pi$: \[Z = R_z(\pi) = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\]

Rotation around the Y-axis: $R_y(\alpha)$ and the Y Gate

A rotation around the Y-axis by an angle $\alpha$ is given by $R_y(\alpha)$, which changes the polar angle $\theta$. The matrix representation is: \[R_y(\alpha) = \begin{pmatrix} \cos(\alpha/2) & -\sin(\alpha/2) \\ \sin(\alpha/2) & \cos(\alpha/2) \end{pmatrix}\] The Pauli-Y gate corresponds to a rotation of $\pi$ radians around the Y-axis. While the Pauli-Y matrix $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$ is not directly equal to $R_y(\pi) = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$, they are related by a global phase and basis transformation considerations, and both represent a $\pi$ rotation around the Y-axis on the Bloch sphere. In many contexts, the Pauli-Y gate is considered to implement a rotation around the Y-axis.

Rotation around the X-axis: $R_x(\alpha)$ and the X Gate

Similarly, a rotation around the X-axis by an angle $\alpha$ is given by $R_x(\alpha)$: \[R_x(\alpha) = \begin{pmatrix} \cos(\alpha/2) & -i\sin(\alpha/2) \\ -i\sin(\alpha/2) & \cos(\alpha/2) \end{pmatrix}\] The Pauli-X gate corresponds to a rotation of $\pi$ radians around the X-axis.

Relationships between S, T, and Z Gates

The S, T, and Z gates are related through composition: \[T^2 = S, \quad S^2 = Z\] These relationships can be verified by matrix multiplication: \[T^2 = T \cdot T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/2} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} = S\] \[S^2 = S \cdot S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i^2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = Z\] This shows that the T gate is a square root of the S gate, and the S gate is a square root of the Z gate, indicating that T is a more fundamental gate from which S and Z can be derived.

Euler Angle Decomposition: ZYZ Decomposition

Any single-qubit unitary $U$ can be decomposed into a sequence of rotations around the Z and Y axes, known as Euler angle decomposition, specifically in the Z-Y-Z form, up to a global phase: \[U = e^{i\delta} R_z(\beta) R_y(\gamma) R_z(\zeta)\] where $\delta, \beta, \gamma, \zeta \in \mathbb{R}$. Geometrically, this decomposition can be visualized as:

$R_z(\zeta)$: Rotate around the Z-axis.
$R_y(\gamma)$: Rotate around the Y-axis.
$R_z(\beta)$: Rotate around the Z-axis again.

This decomposition demonstrates that any single-qubit unitary operation can be synthesized using rotations about the Y and Z axes, which are constructible from basic gate sets, highlighting a path towards universal quantum computation.

Theorem: AXBC Decomposition

Every single-qubit unitary transformation $U$ can be expressed as: \[U = AXBC\] where $A, B, C, X$ are single-qubit unitary matrices, and $ABC = I$, with $I$ being the identity matrix.

Proof. Sketch of Proof. The proof is algebraic, derived from the Euler angle decomposition and properties of unitary matrices. Specific forms for $A, B, C$ can be determined such that their product $ABC$ equals the identity matrix, and the decomposition holds. Detailed derivations are available in quantum computation textbooks. ◻

The AXBC decomposition is particularly relevant when considering controlled operations, as will be discussed in the subsequent section.

Two-Qubit Gates and Controlled Operations

Controlled-NOT (CNOT) Gate

The Controlled-NOT (CNOT) gate is a fundamental two-qubit gate that operates on a control qubit and a target qubit. It flips the state of the target qubit if and only if the control qubit is in the state $\left|{1}\right\rangle$. The CNOT gate is essential for creating entanglement and performing conditional quantum operations.

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 given by: \[CNOT = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\] The action of the CNOT gate on the basis states is as follows: \[\begin{aligned}CNOT \left|{00}\right\rangle &= \left|{00}\right\rangle \\CNOT \left|{01}\right\rangle &= \left|{01}\right\rangle \\CNOT \left|{10}\right\rangle &= \left|{11}\right\rangle \\CNOT \left|{11}\right\rangle &= \left|{10}\right\rangle\end{aligned}\] Here, the first qubit is the control and the second is the target. If the control qubit is $\left|{0}\right\rangle$, the target qubit remains unchanged. If the control qubit is $\left|{1}\right\rangle$, the target qubit is flipped, implementing a NOT operation on the target.

Controlled-U Gate

The Controlled-U gate is a generalization of the CNOT gate. It applies a single-qubit unitary operation $U$ to the target qubit conditioned on the state of the control qubit. Specifically, if the control qubit is in the state $\left|{1}\right\rangle$, the unitary $U$ is applied to the target qubit; if the control qubit is in the state $\left|{0}\right\rangle$, the identity operation is applied to the target qubit.

The matrix representation of the Controlled-U gate is given by: \[C-U = \begin{pmatrix} I & 0 \\ 0 & U \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & U_{11} & U_{12} \\ 0 & 0 & U_{21} & U_{22} \end{pmatrix}\] where $I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ is the $2\times 2$ identity matrix, and $U = \begin{pmatrix} U_{11} & U_{12} \\ U_{21} & U_{22} \end{pmatrix}$ is the $2\times 2$ unitary matrix to be controlled.

Decomposition of Controlled-U Gate

The Controlled-U gate can be decomposed into a quantum circuit consisting of CNOT gates and single-qubit gates. This decomposition is crucial for implementing arbitrary quantum computations using a universal gate set.

Simplified Decomposition Circuit based on Transcription

Based on the transcription, a simplified circuit for Controlled-U, using the AXBC decomposition ($U = AXBC$ with $ABC = I$), is suggested as follows:

Note: This circuit diagram is based on a simplified interpretation of the transcription and may not represent a standard or fully accurate Controlled-U decomposition. Standard decompositions often involve different gate arrangements and may include adjoint operations, which are not explicitly detailed in the provided transcription. The inclusion of a Pauli-X gate on the control qubit line in this sequence is also atypical for standard Controlled-U implementations and is likely a simplification or potential misinterpretation in the lecture notes as transcribed.

Matrix Verification Approach from Transcription

The transcription attempts a matrix verification of a decomposition, although the exact circuit and gate definitions are not fully consistent with standard methods. Following the transcription’s described steps for matrix multiplication (in reverse order of gate application in the circuit):

1. Apply $C$ on the target qubit (controlled by $q_1$): $C' = \begin{pmatrix} I & 0 \\ 0 & C \end{pmatrix}$. 2. Apply CNOT gate: $CNOT = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$. 3. Apply $B$ on the target qubit (controlled by $q_1$): $B' = \begin{pmatrix} I & 0 \\ 0 & B \end{pmatrix}$. 4. Apply $X$ (Pauli-X) on the control qubit ($q_1$): $X'' = X \otimes I = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$. 5. Apply $A$ on the target qubit (controlled by $q_1$): $A' = \begin{pmatrix} I & 0 \\ 0 & A \end{pmatrix}$.

The overall matrix, according to the transcription’s flow, would be the product $M = A' X'' B' CNOT C'$. However, it is important to note that this sequence and the resulting matrix product, based on the transcription’s description, deviate from standard and rigorously derived Controlled-U decompositions. The purpose of this verification in the transcription seems to be illustrative, aiming to demonstrate how single and two-qubit gates can be combined to achieve a controlled operation, rather than providing a precise and standard decomposition.

The decomposition circuit and matrix verification presented here are based on a simplified and potentially less accurate interpretation of the lecture transcription. Standard Controlled-U decompositions are more complex and may not align directly with the simplified approach described in the transcription. The inclusion of the Pauli-X gate on the control qubit in this context is particularly unusual in standard decompositions. Therefore, the above should be considered as an illustrative example derived from the lecture notes, rather than a rigorously correct or standard method for Controlled-U gate decomposition. For precise and standard methods, refer to established quantum computation textbooks and literature.

Decomposition of Unitaries into Two-Level Operators

Definition of Two-Level Unitary Operators

A two-level unitary operator is a unitary matrix of dimension $N \times N$ that acts non-trivially only within a two-dimensional subspace of the $N$-dimensional Hilbert space, while acting as the identity on the orthogonal complement. In matrix form, a two-level unitary operator modifies only a $2 \times 2$ principal submatrix, with all other diagonal elements being unity and off-diagonal elements outside this $2 \times 2$ block being zero.

For $N=4$, a two-level unitary operator can be represented as: \[U_{2\text{-level}} = \begin{pmatrix}1 & 0 & 0 & 0 \\0 & u_{11} & u_{12} & 0 \\0 & u_{21} & u_{22} & 0 \\0 & 0 & 0 & 1\end{pmatrix}\] where $U' = \begin{pmatrix} u_{11} & u_{12} \\ u_{21} & u_{22} \end{pmatrix}$ is a $2 \times 2$ unitary matrix. This operator acts non-trivially on the subspace spanned by the second and third basis vectors (assuming 0-based indexing, these are basis vectors $\left|{1}\right\rangle$ and $\left|{2}\right\rangle$).

Decomposition Theorem for General Unitary Operators

The significance of two-level unitary operators lies in their ability to compose any general unitary operator.

Any $N \times N$ unitary matrix $U$ can be expressed as a product of at most $\frac{N(N-1)}{2}$ two-level unitary operators.

This theorem implies that any complex unitary transformation can be constructed from a sequence of simpler two-level operations. The proof of this theorem is constructive, providing an algorithmic approach to determine the sequence of two-level operators. However, the detailed proof, involving computational complexity considerations, is beyond the scope of these lecture notes.

Complexity Analysis

The decomposition of an $N \times N$ unitary matrix into two-level operators requires at most $O(N^2)$ two-level operators in the worst-case scenario, specifically $\frac{N(N-1)}{2}$. For a quantum system of $n$ qubits, the dimension of the Hilbert space is $N = 2^n$. Consequently, the decomposition of a $2^n \times 2^n$ unitary operator may require up to $O((2^n)^2) = O(4^n)$ two-level operators. This exponential scaling indicates that while such a decomposition is theoretically possible, the number of gates can become substantial for larger quantum systems, posing practical challenges for complex unitary operations.

Example: Two-Level Operator in 3D Space

Consider a two-level operator acting on a 3-dimensional Hilbert space (e.g., a qutrit). Let’s define a rotation within the subspace spanned by basis states $\left|{1}\right\rangle$ and $\left|{2}\right\rangle$ (using 0-based indexing). Suppose we aim to apply a $2 \times 2$ rotation matrix $V(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$ in this subspace. The corresponding $3 \times 3$ two-level operator is: \[U_{2\text{-level}}^{(3\times 3)} = \begin{pmatrix}1 & 0 & 0 \\0 & \cos\theta & -\sin\theta \\0 & \sin\theta & \cos\theta\end{pmatrix}\] This operator leaves the state $\left|{0}\right\rangle$ invariant while performing a rotation by an angle $\theta$ in the subspace spanned by $\left|{1}\right\rangle$ and $\left|{2}\right\rangle$.

Role of Gray Codes in Implementing General Unitaries (Preview)

The lecture notes briefly mentioned the potential use of Gray codes in conjunction with two-level operators for implementing general unitary transformations. The underlying idea involves employing Gray codes to systematically navigate through the computational basis of the Hilbert space. This navigation, combined with the strategic application of two-level operators, allows for the manipulation of matrix elements tofacilitate the decomposition of a general unitary. Gray codes provide a structured approach to transform the basis, making it possible to apply two-level operators effectively. A more detailed discussion on the application of Gray codes in this context will be considered in future lectures.

Conclusion

This lecture has laid the groundwork for understanding quantum circuit construction by exploring fundamental single-qubit and two-qubit gates. We examined essential single-qubit gates—Identity, Pauli (X, Y, Z), Hadamard, Phase (S), and $\pi/8$ (T)—and their representation as rotations on the Bloch sphere. We discussed the Euler angle decomposition, demonstrating the synthesis of any single-qubit unitary from rotations around the Y and Z axes, and introduced the AXBC decomposition theorem. For two-qubit operations, we focused on the CNOT and Controlled-U gates, analyzing a simplified approach to decompose Controlled-U using CNOT and single-qubit gates, while noting caveats regarding transcription accuracy and standard methodologies. Finally, we introduced two-level unitary operators and the theorem concerning the decomposition of arbitrary unitaries into products of these operators.

Key Takeaways

Single-qubit gates combined with the CNOT gate form a universal gate set for quantum computation.
Euler angle decomposition (Z-Y-Z) allows for the realization of any single-qubit unitary.
Controlled-U gates, crucial for conditional operations, can be constructed from CNOT and single-qubit gates.
Two-level operator decomposition provides a method to implement general unitary operations in higher-dimensional Hilbert spaces.
Decomposing general unitaries into two-level operators can lead to significant complexity, scaling exponentially with the number of qubits.

Further Inquiry

How are Gray codes specifically utilized to facilitate the decomposition of general unitaries via two-level operators?
What are the detailed steps in the constructive proof for decomposing unitaries into two-level operators, and what is its algorithmic complexity?
How can the decomposition of Controlled-U gates be optimized to minimize the required number of elementary gates?
What are advanced techniques for quantum circuit synthesis to improve efficiency and reduce gate count for complex quantum algorithms?

This lecture provides a foundational understanding for constructing and analyzing quantum algorithms by reducing complex quantum operations to elementary gates. Future lectures will expand upon these concepts, exploring practical implementation aspects and advanced techniques in quantum computation and circuit optimization.

--- title: "Lecture Notes on Quantum Computation - Single and Two-Qubit Gates" 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 In this lecture, we will explore the construction of quantum circuits, focusing on single-qubit and two-qubit gates. We will begin by revisiting the theorem stating that any unitary operation can be realized using single-qubit unitaries and the CNOT gate. This lecture will constructively examine how to decompose complex unitary operations into sequences of single-qubit gates and CNOT gates. We will analyze single-qubit unitary gates, including the Identity gate, Pauli gates (X, Y, Z), Hadamard gate, Phase gate (S), and $\pi/8$ gate (T), and their representation on the Bloch sphere. We will then discuss two-qubit gates, specifically the Controlled-NOT (CNOT) gate and the Controlled-U gate, and explore the implementation of Controlled-U using CNOT and single-qubit gates. Finally, we will introduce the concept of decomposing unitary operators into two-level operators, which is a key step towards realizing arbitrary unitary operations. This lecture aims to provide a foundational understanding of quantum circuit construction using elementary gates. # Single-Qubit Unitaries ## Review of Unitary Decomposition Theorem As previously stated, a key theorem in quantum computation asserts that any unitary operation can be constructed using single-qubit unitary gates and the CNOT gate. This is a cornerstone of quantum computing, establishing the universality of these gate sets. A more advanced result, not detailed here due to its complexity, demonstrates that a finite set of gates suffices to approximate any unitary operation to arbitrary precision. This section focuses on the constructive aspect of the primary theorem, illustrating the decomposition of unitary operations into sequences of single-qubit and CNOT gates. ## Fundamental Single-Qubit Gates Single-qubit gates operate on individual qubits and serve as elementary operations in quantum circuits. We introduce a set of essential single-qubit gates. ### Identity Gate (I) {#subsec:identity_gate} The Identity gate ($I$) is the most basic single-qubit gate, leaving the qubit state unchanged. It is represented by the identity matrix: $$I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$ While seemingly trivial, the Identity gate is conceptually important and can be used for timing adjustments within quantum circuits. ### Pauli Gates (X, Y, Z) {#subsec:pauli_gates} The Pauli gates are a set of fundamental single-qubit gates, corresponding to the Pauli matrices: - **Pauli-X Gate (X) or NOT Gate**: $$X = \sigma_x = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$ The X gate performs a bit-flip operation, transforming $\left|{0}\right\rangle \leftrightarrow \left|{1}\right\rangle$. - **Pauli-Y Gate (Y)**: $$Y = \sigma_y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$$ The Pauli-Y gate corresponds to a rotation of $\pi$ radians around the Y-axis on the Bloch sphere. - **Pauli-Z Gate (Z)**: $$Z = \sigma_z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$ The Pauli-Z gate introduces a phase of $-1$ to the $\left|{1}\right\rangle$ state, leaving $\left|{0}\right\rangle$ unchanged. ### Hadamard Gate (H) {#subsec:hadamard_gate} The Hadamard gate ($H$) is essential for creating superposition states. Its matrix representation is: $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$ It transforms the computational basis states as: $$H\left|{0}\right\rangle = \frac{\left|{0}\right\rangle + \left|{1}\right\rangle}{\sqrt{2}} = \left|{+}\right\rangle , \quad H\left|{1}\right\rangle = \frac{\left|{0}\right\rangle - \left|{1}\right\rangle}{\sqrt{2}} = \left|{-}\right\rangle$$ ### Phase Gate (S) and $\pi/8$ Gate (T) {#subsec:phase_gates} The Phase gate ($S$) and the $\pi/8$ gate ($T$) are crucial for introducing phase shifts in quantum computations. - **Phase Gate (S)**: $$S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}$$ The S gate applies a phase shift of $\pi/2$ to the $\left|{1}\right\rangle$ state. - **$\pi/8$ Gate (T)**: $$T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}$$ The T gate, also known as the $\pi/8$ gate, applies a phase shift of $\pi/4$ to the $\left|{1}\right\rangle$ state. The name $\pi/8$ gate arises from an alternative representation involving a global phase factor, although it directly applies a $\pi/4$ phase. ## Bloch Sphere Representation of Qubits {#subsec:bloch_sphere} The Bloch sphere provides a geometrical representation of single-qubit states. Any qubit state $\left|{\psi}\right\rangle$ can be expressed 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. On the Bloch sphere: - $\left|{0}\right\rangle$ corresponds to the North Pole. - $\left|{1}\right\rangle$ corresponds to the South Pole. - $\theta$ is the angle from the positive Z-axis. - $\phi$ is the angle of the projection onto the XY-plane from the positive X-axis. ## Unitary Gates as Bloch Sphere Rotations {#subsec:rotations_bloch_sphere} Unitary gates on a qubit can be visualized as rotations of the Bloch vector on the Bloch sphere. ### Rotation around the Z-axis: $R_z(\alpha)$ and the Z Gate {#subsubsec:rz_and_z_gate} A rotation around the Z-axis by an angle $\alpha$ is given by the operator $R_z(\alpha)$. It modifies the azimuthal angle $\phi$ while keeping the polar angle $\theta$ constant. The matrix representation is: $$R_z(\alpha) = \begin{pmatrix} e^{-i\alpha/2} & 0 \\ 0 & e^{i\alpha/2} \end{pmatrix}$$ Ignoring the global phase factor $e^{-i\alpha/2}$, we can write: $$R_z(\alpha) \propto \begin{pmatrix} 1 & 0 \\ 0 & e^{i\alpha} \end{pmatrix}$$ The Pauli-Z gate corresponds to a rotation around the Z-axis by $\alpha = \pi$: $$Z = R_z(\pi) = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$ ### Rotation around the Y-axis: $R_y(\alpha)$ and the Y Gate {#subsubsec:ry_and_y_gate} A rotation around the Y-axis by an angle $\alpha$ is given by $R_y(\alpha)$, which changes the polar angle $\theta$. The matrix representation is: $$R_y(\alpha) = \begin{pmatrix} \cos(\alpha/2) & -\sin(\alpha/2) \\ \sin(\alpha/2) & \cos(\alpha/2) \end{pmatrix}$$ The Pauli-Y gate corresponds to a rotation of $\pi$ radians around the Y-axis. While the Pauli-Y matrix $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$ is not directly equal to $R_y(\pi) = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$, they are related by a global phase and basis transformation considerations, and both represent a $\pi$ rotation around the Y-axis on the Bloch sphere. In many contexts, the Pauli-Y gate is considered to implement a rotation around the Y-axis. ### Rotation around the X-axis: $R_x(\alpha)$ and the X Gate {#subsubsec:rx_and_x_gate} Similarly, a rotation around the X-axis by an angle $\alpha$ is given by $R_x(\alpha)$: $$R_x(\alpha) = \begin{pmatrix} \cos(\alpha/2) & -i\sin(\alpha/2) \\ -i\sin(\alpha/2) & \cos(\alpha/2) \end{pmatrix}$$ The Pauli-X gate corresponds to a rotation of $\pi$ radians around the X-axis. ## Relationships between S, T, and Z Gates {#subsec:s_t_z_relations} The S, T, and Z gates are related through composition: $$T^2 = S, \quad S^2 = Z$$ These relationships can be verified by matrix multiplication: $$T^2 = T \cdot T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/2} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} = S$$ $$S^2 = S \cdot S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i^2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = Z$$ This shows that the T gate is a square root of the S gate, and the S gate is a square root of the Z gate, indicating that T is a more fundamental gate from which S and Z can be derived. ## Euler Angle Decomposition: ZYZ Decomposition {#subsec:euler_decomposition} Any single-qubit unitary $U$ can be decomposed into a sequence of rotations around the Z and Y axes, known as Euler angle decomposition, specifically in the Z-Y-Z form, up to a global phase: $$U = e^{i\delta} R_z(\beta) R_y(\gamma) R_z(\zeta)$$ where $\delta, \beta, \gamma, \zeta \in \mathbb{R}$. Geometrically, this decomposition can be visualized as: 1. $R_z(\zeta)$: Rotate around the Z-axis. 2. $R_y(\gamma)$: Rotate around the Y-axis. 3. $R_z(\beta)$: Rotate around the Z-axis again. This decomposition demonstrates that any single-qubit unitary operation can be synthesized using rotations about the Y and Z axes, which are constructible from basic gate sets, highlighting a path towards universal quantum computation. ## Theorem: AXBC Decomposition {#subsec:axbc_theorem} ::: tcolorbox Every single-qubit unitary transformation $U$ can be expressed as: $$U = AXBC$$ where $A, B, C, X$ are single-qubit unitary matrices, and $ABC = I$, with $I$ being the identity matrix. ::: ::: proof *Sketch of Proof.* The proof is algebraic, derived from the Euler angle decomposition and properties of unitary matrices. Specific forms for $A, B, C$ can be determined such that their product $ABC$ equals the identity matrix, and the decomposition holds. Detailed derivations are available in quantum computation textbooks. ◻ ::: The AXBC decomposition is particularly relevant when considering controlled operations, as will be discussed in the subsequent section. # Two-Qubit Gates and Controlled Operations ## Controlled-NOT (CNOT) Gate {#subsec:cnot_gate} The Controlled-NOT (CNOT) gate is a fundamental two-qubit gate that operates on a control qubit and a target qubit. It flips the state of the target qubit if and only if the control qubit is in the state $\left|{1}\right\rangle$. The CNOT gate is essential for creating entanglement and performing conditional quantum operations. 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 given by: $$CNOT = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$ The action of the CNOT gate on the basis states is as follows: $$\begin{aligned}CNOT \left|{00}\right\rangle &= \left|{00}\right\rangle \\CNOT \left|{01}\right\rangle &= \left|{01}\right\rangle \\CNOT \left|{10}\right\rangle &= \left|{11}\right\rangle \\CNOT \left|{11}\right\rangle &= \left|{10}\right\rangle\end{aligned}$$ Here, the first qubit is the control and the second is the target. If the control qubit is $\left|{0}\right\rangle$, the target qubit remains unchanged. If the control qubit is $\left|{1}\right\rangle$, the target qubit is flipped, implementing a NOT operation on the target. ## Controlled-U Gate {#subsec:controlled_u_gate} The Controlled-U gate is a generalization of the CNOT gate. It applies a single-qubit unitary operation $U$ to the target qubit conditioned on the state of the control qubit. Specifically, if the control qubit is in the state $\left|{1}\right\rangle$, the unitary $U$ is applied to the target qubit; if the control qubit is in the state $\left|{0}\right\rangle$, the identity operation is applied to the target qubit. The matrix representation of the Controlled-U gate is given by: $$C-U = \begin{pmatrix} I & 0 \\ 0 & U \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & U_{11} & U_{12} \\ 0 & 0 & U_{21} & U_{22} \end{pmatrix}$$ where $I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ is the $2\times 2$ identity matrix, and $U = \begin{pmatrix} U_{11} & U_{12} \\ U_{21} & U_{22} \end{pmatrix}$ is the $2\times 2$ unitary matrix to be controlled. ## Decomposition of Controlled-U Gate {#subsec:cu_decomposition} The Controlled-U gate can be decomposed into a quantum circuit consisting of CNOT gates and single-qubit gates. This decomposition is crucial for implementing arbitrary quantum computations using a universal gate set. ### Simplified Decomposition Circuit based on Transcription {#subsubsec:simplified_cu_circuit} Based on the transcription, a simplified circuit for Controlled-U, using the AXBC decomposition ($U = AXBC$ with $ABC = I$), is suggested as follows: ::: center ::: ::: tcolorbox **Note:** This circuit diagram is based on a simplified interpretation of the transcription and may not represent a standard or fully accurate Controlled-U decomposition. Standard decompositions often involve different gate arrangements and may include adjoint operations, which are not explicitly detailed in the provided transcription. The inclusion of a Pauli-X gate on the control qubit line in this sequence is also atypical for standard Controlled-U implementations and is likely a simplification or potential misinterpretation in the lecture notes as transcribed. ::: ### Matrix Verification Approach from Transcription {#subsubsec:matrix_verification_transcription} The transcription attempts a matrix verification of a decomposition, although the exact circuit and gate definitions are not fully consistent with standard methods. Following the transcription's described steps for matrix multiplication (in reverse order of gate application in the circuit): 1\. Apply $C$ on the target qubit (controlled by $q_1$): $C' = \begin{pmatrix} I & 0 \\ 0 & C \end{pmatrix}$. 2. Apply CNOT gate: $CNOT = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$. 3. Apply $B$ on the target qubit (controlled by $q_1$): $B' = \begin{pmatrix} I & 0 \\ 0 & B \end{pmatrix}$. 4. Apply $X$ (Pauli-X) on the control qubit ($q_1$): $X'' = X \otimes I = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$. 5. Apply $A$ on the target qubit (controlled by $q_1$): $A' = \begin{pmatrix} I & 0 \\ 0 & A \end{pmatrix}$. The overall matrix, according to the transcription's flow, would be the product $M = A' X'' B' CNOT C'$. However, it is important to note that this sequence and the resulting matrix product, based on the transcription's description, deviate from standard and rigorously derived Controlled-U decompositions. The purpose of this verification in the transcription seems to be illustrative, aiming to demonstrate how single and two-qubit gates can be combined to achieve a controlled operation, rather than providing a precise and standard decomposition. ::: tcolorbox The decomposition circuit and matrix verification presented here are based on a simplified and potentially less accurate interpretation of the lecture transcription. Standard Controlled-U decompositions are more complex and may not align directly with the simplified approach described in the transcription. The inclusion of the Pauli-X gate on the control qubit in this context is particularly unusual in standard decompositions. Therefore, the above should be considered as an illustrative example derived from the lecture notes, rather than a rigorously correct or standard method for Controlled-U gate decomposition. For precise and standard methods, refer to established quantum computation textbooks and literature. ::: # Decomposition of Unitaries into Two-Level Operators {#sec:two_level_operators} ## Definition of Two-Level Unitary Operators {#subsec:definition_two_level_operators} A two-level unitary operator is a unitary matrix of dimension $N \times N$ that acts non-trivially only within a two-dimensional subspace of the $N$-dimensional Hilbert space, while acting as the identity on the orthogonal complement. In matrix form, a two-level unitary operator modifies only a $2 \times 2$ principal submatrix, with all other diagonal elements being unity and off-diagonal elements outside this $2 \times 2$ block being zero. ::: tcolorbox []{#example:4x4_two_level_unitary label="example:4x4_two_level_unitary"} For $N=4$, a two-level unitary operator can be represented as: $$U_{2\text{-level}} = \begin{pmatrix}1 & 0 & 0 & 0 \\0 & u_{11} & u_{12} & 0 \\0 & u_{21} & u_{22} & 0 \\0 & 0 & 0 & 1\end{pmatrix}$$ where $U' = \begin{pmatrix} u_{11} & u_{12} \\ u_{21} & u_{22} \end{pmatrix}$ is a $2 \times 2$ unitary matrix. This operator acts non-trivially on the subspace spanned by the second and third basis vectors (assuming 0-based indexing, these are basis vectors $\left|{1}\right\rangle$ and $\left|{2}\right\rangle$). ::: ## Decomposition Theorem for General Unitary Operators {#subsec:decomposition_theorem_two_level} The significance of two-level unitary operators lies in their ability to compose any general unitary operator. ::: tcolorbox []{#theorem:decomposition_two_level_unitaries label="theorem:decomposition_two_level_unitaries"} Any $N \times N$ unitary matrix $U$ can be expressed as a product of at most $\frac{N(N-1)}{2}$ two-level unitary operators. ::: This theorem implies that any complex unitary transformation can be constructed from a sequence of simpler two-level operations. The proof of this theorem is constructive, providing an algorithmic approach to determine the sequence of two-level operators. However, the detailed proof, involving computational complexity considerations, is beyond the scope of these lecture notes. ## Complexity Analysis {#subsec:complexity_two_level_decomposition} The decomposition of an $N \times N$ unitary matrix into two-level operators requires at most $O(N^2)$ two-level operators in the worst-case scenario, specifically $\frac{N(N-1)}{2}$. For a quantum system of $n$ qubits, the dimension of the Hilbert space is $N = 2^n$. Consequently, the decomposition of a $2^n \times 2^n$ unitary operator may require up to $O((2^n)^2) = O(4^n)$ two-level operators. This exponential scaling indicates that while such a decomposition is theoretically possible, the number of gates can become substantial for larger quantum systems, posing practical challenges for complex unitary operations. ## Example: Two-Level Operator in 3D Space {#subsec:example_two_level_3d} Consider a two-level operator acting on a 3-dimensional Hilbert space (e.g., a qutrit). Let's define a rotation within the subspace spanned by basis states $\left|{1}\right\rangle$ and $\left|{2}\right\rangle$ (using 0-based indexing). Suppose we aim to apply a $2 \times 2$ rotation matrix $V(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$ in this subspace. The corresponding $3 \times 3$ two-level operator is: $$U_{2\text{-level}}^{(3\times 3)} = \begin{pmatrix}1 & 0 & 0 \\0 & \cos\theta & -\sin\theta \\0 & \sin\theta & \cos\theta\end{pmatrix}$$ This operator leaves the state $\left|{0}\right\rangle$ invariant while performing a rotation by an angle $\theta$ in the subspace spanned by $\left|{1}\right\rangle$ and $\left|{2}\right\rangle$. ## Role of Gray Codes in Implementing General Unitaries (Preview) {#subsec:gray_codes_preview} The lecture notes briefly mentioned the potential use of Gray codes in conjunction with two-level operators for implementing general unitary transformations. The underlying idea involves employing Gray codes to systematically navigate through the computational basis of the Hilbert space. This navigation, combined with the strategic application of two-level operators, allows for the manipulation of matrix elements tofacilitate the decomposition of a general unitary. Gray codes provide a structured approach to transform the basis, making it possible to apply two-level operators effectively. A more detailed discussion on the application of Gray codes in this context will be considered in future lectures. # Conclusion {#sec:conclusion} This lecture has laid the groundwork for understanding quantum circuit construction by exploring fundamental single-qubit and two-qubit gates. We examined essential single-qubit gates---Identity, Pauli (X, Y, Z), Hadamard, Phase (S), and $\pi/8$ (T)---and their representation as rotations on the Bloch sphere. We discussed the Euler angle decomposition, demonstrating the synthesis of any single-qubit unitary from rotations around the Y and Z axes, and introduced the AXBC decomposition theorem. For two-qubit operations, we focused on the CNOT and Controlled-U gates, analyzing a simplified approach to decompose Controlled-U using CNOT and single-qubit gates, while noting caveats regarding transcription accuracy and standard methodologies. Finally, we introduced two-level unitary operators and the theorem concerning the decomposition of arbitrary unitaries into products of these operators. ## Key Takeaways - Single-qubit gates combined with the CNOT gate form a universal gate set for quantum computation. - Euler angle decomposition (Z-Y-Z) allows for the realization of any single-qubit unitary. - Controlled-U gates, crucial for conditional operations, can be constructed from CNOT and single-qubit gates. - Two-level operator decomposition provides a method to implement general unitary operations in higher-dimensional Hilbert spaces. - Decomposing general unitaries into two-level operators can lead to significant complexity, scaling exponentially with the number of qubits. ## Further Inquiry - How are Gray codes specifically utilized to facilitate the decomposition of general unitaries via two-level operators? - What are the detailed steps in the constructive proof for decomposing unitaries into two-level operators, and what is its algorithmic complexity? - How can the decomposition of Controlled-U gates be optimized to minimize the required number of elementary gates? - What are advanced techniques for quantum circuit synthesis to improve efficiency and reduce gate count for complex quantum algorithms? This lecture provides a foundational understanding for constructing and analyzing quantum algorithms by reducing complex quantum operations to elementary gates. Future lectures will expand upon these concepts, exploring practical implementation aspects and advanced techniques in quantum computation and circuit optimization.