PadhaikoAll subjects

Quantum Gates and Circuits

Quantum Computing (ENCT 328)

Open in the Padhaiko app

2.1 Quantum gates (X, Y, Z, H, Phase, CNOT)

Quantum computation processes information by manipulating state vectors via quantum logic gates. In accordance with Postulate 2 of quantum mechanics, any valid quantum gate acting on a closed register must be represented by a unitary matrix.

Single-Qubit Pauli Gates

The three Pauli matrices, together with the identity matrix , form an orthogonal basis for the space of all complex Hermitian matrices:

  1. Pauli-X Gate (Bit-Flip / Quantum NOT):

Acts as a deterministic bit-flip on computational basis states:

  1. Pauli-Y Gate (Bit- and Phase-Flip):

Flips the bit and introduces an imaginary relative phase:

  1. Pauli-Z Gate (Phase-Flip):

Leaves invariant and flips the phase of :

Hadamard Gate ()

The Hadamard gate is the cornerstone of quantum algorithms, creating an equal superposition of and from computational basis states:

Its action transforms the computational basis into the Hadamard (diagonal) basis:

Because and , applying twice restores the initial state:

Phase Shift Gates (, , and )

Phase gates leave the state untouched and apply a controlled rotation to the phase of the amplitude:

  1. Phase Gate ( or gate, phase shift):

Notice that , so the gate is often called the gate.

  1. Gate ( gate, phase shift):

Notice that and . The gate is essential for achieving universal quantum computation when combined with Clifford gates ().

  1. Arbitrary Phase Rotation Gate ():

Controlled-NOT Gate ( / )

The Controlled-NOT gate is the canonical two-qubit entangling gate. It operates on two qubits: a control qubit () and a target qubit (). If the control qubit is , a bit-flip () is applied to the target qubit; if the control qubit is , the target remains unchanged:

In the computational basis ordered as , its matrix is:

Standard Single- and Two-Qubit Quantum Gates
Gate NameSymbol / DiagramMatrix RepresentationBasis Mapping
Identity ()—[I]—
Pauli-X—[X]— or —(⊕)—
Pauli-Y—[Y]—
Pauli-Z—[Z]—
Hadamard ()—[H]—
Phase ()—[S]—
Gate—[T]—
CNOT (CX)—●— / —⊕—

2.2 Unitary operations and reversibility

Definition

Unitary Operators and Probability Conservation

A linear operator on a Hilbert space is unitary if its conjugate transpose (Hermitian adjoint) equals its inverse:

Unitary operators possess fundamental mathematical and physical properties:

  1. Inner Product Preservation: For any two state vectors and :
  1. Norm and Probability Conservation: The length of any state vector is invariant under unitary transformation:

This ensures that the sum of measurement probabilities across all outcomes remains strictly at all times.

  1. Eigenvalues on the Unit Circle: If , then , meaning for some .
  2. Orthogonality of Eigenvectors: Eigenvectors corresponding to distinct eigenvalues are mutually orthogonal.

Reversibility and Landauer's Principle

Because every unitary matrix has a well-defined inverse , any quantum logic gate operation is strictly reversible:

In classical computing, gates like AND, OR, and NAND are irreversible: observing the output of a 2-input AND gate does not uniquely specify whether the input was , , or . According to Landauer's Principle, any logically irreversible erasure of one bit of information dissipates a minimum thermodynamic energy into the environment:

Because quantum gate operations preserve all information through unitary mappings, they are in principle completely dissipationless.

AspectClassical Logic GatesQuantum Logic Gates
Algebraic ModelBoolean algebra on Linear algebra / Unitary matrices on
ReversibilityGenerally irreversible (AND, OR, NAND lose input history)Strictly reversible; always exists
Fan-out / CopyingWires can branch arbitrarily ()Forbidden by the No-Cloning Theorem ()
Thermal DissipationSubject to Landauer's limit ( per erased bit)Zero fundamental thermodynamic erasure dissipation

2.3 Multi-qubit systems and tensor products

Definition

Tensor Product of Vectors and Operators

Let and . The composite state vector in is given by the tensor product (Kronecker product):

The standard computational basis for a 2-qubit system is:

For linear operators and , the tensor product operator acts on basis states as:

and its matrix representation is the Kronecker block matrix:

Separable vs. Entangled States

A bipartite state is separable (a product state) if and only if there exist individual states and such that:

If no such decomposition exists, the state is entangled. For example:


2.4 Circuit design and visualization

Definition

Quantum Circuit Model and Universality

The quantum circuit model represents a computation as a directed network of quantum wires and quantum logic gates:

  1. Wires: Horizontal lines represent qubits flowing from left to right over time.
  2. Gate Blocks: Rectangular boxes or special symbols intercepting wires represent unitary operations.
  3. Control Points: Solid circles () represent control qubits condition-checked on state ; open circles () denote negative control condition-checked on .
  4. Meter Symbol: Represents projective measurement in the computational basis, collapsing the qubit and outputting a classical bit carried on a double line ().

Universal Quantum Gate Sets

A set of quantum gates is universal if any arbitrary unitary operation on an arbitrary number of qubits can be approximated to any desired accuracy using a finite sequence of gates from the set:

  1. Barenco et al. Theorem (Exact Universality): Any -qubit unitary operator can be composed exactly from single-qubit rotation gates and two-qubit gates.
  2. Solovay-Kitaev Theorem: Any single-qubit gate can be approximated to error using a sequence of gates () chosen from a discrete gate set such as .
  3. Standard Universal Discrete Gate Set: The set (or ) is universal for quantum computing. The subset generates the Clifford group, which by the Gottesman-Knill Theorem can be simulated efficiently on a classical computer in polynomial time. Adding the non-Clifford gate unlocks universal quantum computation.

Classical Reversible Computation: Toffoli and Fredkin Gates

To embed classical algorithms into quantum circuits without measurement collapse, reversible classical gates are employed:

  1. Toffoli Gate (): A 3-qubit gate with two control qubits and one target qubit:

If , the target output is (classical AND). If , the output is (classical NAND). Because NAND is a universal classical gate, the Toffoli gate is universal for classical reversible computation.

  1. Fredkin Gate (): A 3-qubit controlled-swap gate:

Worked Examples

Example 2.1

2.1

Compute the matrix product , where is the Hadamard gate and is the Pauli-Z gate. Prove that (the Pauli-X gate).

Setting Up Gate Matrices: The Hadamard and Pauli-Z matrices are given by:

Computing the Product : Multiplying by :

Multiplying to Obtain : Multiplying from the left:

Simplifying each matrix element:

Answer:

This proves that conjugating the phase-flip operator by Hadamard gates produces the bit-flip operator .

Example 2.2

2.2

A quantum circuit takes two qubits initialized in the state , applies a Hadamard gate to the first qubit, and then applies a gate with the first qubit as control and the second qubit as target.

  1. Determine the state of the system after each gate operation.
  2. Calculate the probability of measuring outcome and at the output.

Initial State and Action of Hadamard Gate: The initial register state is:

Applying to the register:

Expanding the tensor product:

Action of the Gate: The gate acts on basis kets as :

  • For basis state : .
  • For basis state : .

Applying linearity to :

This generates the maximally entangled Bell state .

Evaluating Output Probabilities: By Born's rule:

Answer:
  1. Intermediate state: ; final state:
  2. Probabilities: , ,
Example 2.3

2.3

Prove mathematically that the Hadamard gate is:

  1. Hermitian ().
  2. Unitary ().
  3. Involutory (self-inverse, ).

Proving Hermiticity (): The Hermitian adjoint is the complex conjugate transpose of :

Because , is strictly Hermitian.

Proving Unitary Evolution (): Evaluating the matrix product:

Since , the gate is strictly unitary.

Proving Involutory Property (): From and , substituting for gives:

Thus , proving the gate is its own inverse.

Answer:
  1. (all entries are real and symmetric; Hermitian).
  2. (columns are orthonormal; unitary).
  3. (self-inverse; involutory).

Practice Exercises

Practice Exercises — Quantum Gates and Circuits

Question 1

Compute the output state when the phase gate is applied to the equal superposition state . What state on the Bloch sphere does this produce?

Matrix Multiplication of on : Writing in vector form:

Applying the gate:

In Dirac notation:

Identifying Location on the Bloch Sphere: Matching with :

The state lies on the equator of the Bloch sphere along the positive -axis ().

Answer:
  1. Resulting state:
  2. Bloch sphere location: Equator at , pointing along the positive axis ().
Question 2

Calculate the matrix representation of the composite operator . Determine its effect on the basis state .

Evaluating the Kronecker Product : Given and :

Action on the Basis State : Using the tensor product property of operators:

Since and :

Answer:
  1. Matrix:
  1. Output on :
Question 3

Show that a two-qubit gate can be constructed using exactly three gates arranged in alternating control-target orientations:

Tracing Basis States Through Gate 1 (): Let the input be an arbitrary basis state with . After the first gate (qubit 1 control, qubit 2 target):

Tracing Through Gate 2 (): Applying the second gate (qubit 2 control, qubit 1 target):

Since XOR is commutative and associative, and :

Thus the state becomes:

Tracing Through Gate 3 (): Applying the third gate (qubit 1 control, qubit 2 target):

Simplifying the second register:

Thus the final state is:

Answer:

For all input basis states , the three-gate sequence yields , exactly interchanging the states of the two qubits. Hence, .

Question 4

Prove that the Controlled-Z () gate can be implemented by surrounding the target qubit of a gate with Hadamard gates:

Expressing Target Operation via Gate Identities: From Example 2.1, we proved the single-qubit identity and . Since , sandwiching the target wire of a controlled operation between gates transforms the target operation from to .

Evaluating Action on Computational Basis States: Let the control qubit be and target qubit be :

  1. If : acts as identity on the target wire, yielding . The state is unchanged.
  2. If : applies to the target wire, yielding .
    • For : .
    • For : .

Constructing the Matrix Representation: The resulting operation maps , , , and :

Notice that is completely symmetric with respect to control and target qubits: a phase is applied if and only if both qubits are in state .

Answer:

The sandwiching of Hadamard gates converts the target bit-flip into a target phase-flip , generating the symmetric Controlled-Z gate.

Question 5

Explain how the 3-qubit reversible Toffoli () gate can be configured to simulate classical , , and gates. What is the significance of this for quantum computation?

Toffoli Gate Operation: The Toffoli gate operates on three qubits as:

Synthesizing Classical Logic Gates:

  1. Classical : Prepare the target qubit in state . The target output becomes:
  1. Classical : Prepare the target qubit in state . The target output becomes:
  1. Classical : Set control inputs . The target output becomes:
  1. Classical (Copy): Set . Outputs are , creating a copy of .

Significance for Quantum Computation: Because and form a functionally complete set for all classical Boolean logic, the Toffoli gate proves that any classical irreversible algorithm can be embedded into a reversible quantum circuit with polynomial overhead and zero information loss.

Answer:

By fixing the ancilla input :

  • Setting yields ().
  • Setting yields ().
  • Setting yields ().

This proves that reversible quantum circuits can compute any classical function without information erasure.

← Fundamentals of Quantum ConceptsEntanglement and Quantum Communication →