1 circuits

1.1 classical

A collection of gates and wires.

• NOT: x \mapsto 1 - x
• AND (x, y) \mapsto x \cdot y
• COPY: x \mapsto (x, x)
• OR: (x, y) \mapsto x + y - xy
• CNOT: (x, y) \mapsto (x, x \oplus y) where \oplus is XOR
• CCNOT (TOFFELI): (x, y, z) \mapsto (x, y, z \oplus xy)

circuit: \{0, 1\}^{n_{\text{IN}}} \to \{0, 1\}^{n_{\text{OUT}}}

Theorem: any function f: \{0, 1\}^n \to \{0, 1\}^m has a circuit and vice versa

1.1.1 reversible gates

A gate G where G is its inverse. Or actually, a gate for which we can use itself to restore \bar x from G(\bar x)

Theorem: any function f: \{0, 1\}^n \to \{0, 1\}^m has a circuit made of reversible gates {CNOT, CCNOT, COPY, NOT}

1.2 axioms of quantum mechanics

1.2.1 1. state of a quantum system

The quantum state is a unit vector in a Hilbert space. The state of n qubits is | \psi \rangle \in \mathbf{C}^{2^n} with ||| \psi \rangle||^2 = 1

1.2.2 2. time evolution

1. norm-preservation: ||f(| \psi \rangle)|| = ||| \psi \rangle||
2. linearity: f(\alpha| \psi_1 \rangle + \beta| \psi_2 \rangle) = \alpha f(| \psi_1 \rangle) + \beta f(| \psi_2 \rangle)

Equivalently, we can say that an operation is a unitary matrix U \in \mathbf{C}^{2 \times 2}: f(| \psi \rangle) = U| \psi \rangle

1.2.3 3. measurement

We observe x \in \{0, 1\}^n with probability |\alpha_x|^2

1.2.4 4. composition

If quantum system 1 is in state | \psi_1 \rangle \in \mathbf{C}^{2^{n_1}} and quantum system 2 is in state| \psi_2 \rangle \in \mathbf{C}^{2^{n_2}} then the join state is | \psi_{12} \rangle = | \psi_1 \rangle \otimes | \psi_2 \rangle

An entangled state is such that cannot be decomposed into a product of two other ones. There is no simple way to know if a state is entangled or not.

1.3 quantum gates

1.3.1 X gate (NOT)

• | 0 \rangle \mapsto | 1 \rangle
• | 1 \rangle \mapsto | 0 \rangle

\begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix}

1.3.2 T gate (Phase)

• | 0 \rangle \mapsto | 0 \rangle
• | 1 \rangle \mapsto e^{i\frac{\pi}{4}}| 0 \rangle

\begin{pmatrix} 1 & 0 \\ 0 & e^{i\frac{\pi}{4}} \\ \end{pmatrix}

1.3.3 H gate (Hadamard)

• | 0 \rangle \mapsto | + \rangle
• | 1 \rangle \mapsto | - \rangle

\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}

1.3.4 CNOT gate

• | 0 \rangle| 0 \rangle \mapsto | 0 \rangle| 0 \rangle
• | 0 \rangle| 1 \rangle \mapsto | 0 \rangle| 1 \rangle
• | 1 \rangle| 0 \rangle \mapsto | 1 \rangle| 1 \rangle
• | 1 \rangle| 1 \rangle \mapsto | 1 \rangle| 0 \rangle
• | x \rangle| y \rangle \mapsto | x \rangle| y \oplus x \rangle

\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}

1.3.5 SWAP gate

• | x \rangle| y \rangle \mapsto | y \rangle| x \rangle

\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}

1.3.6 Q oracle

Turns any function into an invertible one.

For f: \{0, 1\}^n \to \{0, 1\}^m we define \tilde f: \{0, 1\}^{n+m} \to \{0, 1\}^{n+m} as (x, y) \mapsto (x, y \oplus f(x))

Theorem: For all unitary matrices U \in \mathbf{C}^{2 \times 2} and all \delta > 0 there exists \tilde U such that

1. \tilde U is a product of only T and H gates
2. ||U - \tilde U||_\infty \le \delta

Theorem: For all unitary matrices U \in \mathbf{C}^{2^n \times 2^n} and all \delta > 0 there exists \tilde U such that

1. \tilde U is a quantym circuit with gates of only T, H, and CNOT gates
2. ||U - \tilde U||_\infty \le \delta