# Quantum Computation and Information

## 1 Preliminaries #

### 1.1 Quantum States #

#### Hilbert spaces $$\mathcal{H}$$ #

Definition: an inner product space in which each Cauchy sequence of vectors has a limit.

Sounds daunting, however, in quantum computing we only care about finite dimensional space. In this case a Hilbert space degenerates to exactly a “normal” inner product space, which is what we learned in our undergraduate level linear algebra course.

#### Dirac Notation #

Normally we write vectors like the following:

• Column vector: $$x$$
• Conjugate transpose of $$x$$ (which is a row vector): $$x^{\dagger}$$
• Inner product of $$x$$ and $$y$$: $$x^{\dagger}y$$ or $$\braket{x,y}$$

A reminder: Doing a inner product in complex vector space requires taking a “conjugate transpose” instead of simply a “transpose”.

In quantum computing, people usually use a different notation to represent vectors:

• Column vector: $$\ket{\varphi}$$
• Conjugate transpose of $$\ket{\varphi}$$ (which is a row vector): $$\bra{\varphi}$$
• Inner product of $$\ket{\varphi}$$ and $$\ket{\psi}$$: $$\braket{\varphi | \psi}$$

The advantage of Dirac notation is that we can easily know whether a value is a column vector, a row vector, or a scalar. Read the article by Prof. E. F. Redish for more information.

## 2 Rotate, Compute, Rotate #

Quantum Mechanics = probability with minus signs

Probabilistic Computing = deterministic computing + coin flip instruction

Strongly Believed: Every (compute-a-function) problem in P probabilistically, also in P deterministically. (pseudo-random generator)

Probabilistic computing gives speedups over deterministic computing, from one P algorithm to another for many problems.

Quantum computing gives speedups over probabilistic computing, from one P algorithm to another for many problems. (E.g., Grover)

(Seems, because factoring may be in P) Quantum computing gives exponential speedups over probabilistic computing for factoring

Strongly Believed: quantum computing does not give exponential speedups for NP-complete problems. (E.g., SAT)

Strongly believed: NP != BPP, factoring is not NP complete

## 3 Measurements #

### 3.1 General Measurements #

Quantum measurement operators: $$\{M_m\}$$ such that $$\sum_m M_m^{\dagger} M_m = I$$.

Measurement of a single qubit in the computational basis: $$M_0=\ket{0}\bra{0}$$, $$M_1=\ket{1}\bra{1}$$.

#### For Pure States #

If the state is $$\ket{\psi}$$, result $$m$$ occurs with probability:

$p(m)= \bra{\psi} M_m^{\dagger} M_m \ket{\psi}$

and the state after the measurement snaps to:

$\frac{M_m \ket{\psi}}{\sqrt{p(m)}}$

#### For Mixed States #

If the state is $$\rho$$, result $$m$$ occurs with probability:

$p(m)=\tr \left( M_m^{\dagger} M_m \rho \right)$

and the state after the measurement snaps to:

$\frac{M_m \rho M_m^{\dagger}}{p(m)}$

### 3.2 Projective Measurements #

Most literature only introduces this kind of measurements.

Observable $$M = \sum_m m P_m$$, a Hermitian operator. $$P_m$$ is a orthogonal projection matrix, i.e., $$P^2 = P^{\dagger} = P$$.

In quantum mechanics, the measurement of an observable $$M$$ prepares an eigenstate of $$M$$, and the observer learns the value of the corresponding eigenvalue.

“Measure in basis $$\ket{m}$$” means $$P_m = \ket{m}\bra{m}$$. Often people simply list a set of basis instead of giving the observable $$M$$.

#### For Pure States #

If the state is $$\ket{\psi}$$, result $$m$$ occurs with probability:

$p(m)= \|P_m \ket{\psi}\|^2 = \bra{\psi} P_m \ket{\psi}$

and the state after the measurement snaps to:

$\frac{P_m \ket{\psi}}{\sqrt{p(m)}}$

Note

If $$P_m=\ket{m}\bra{m}$$, then

$p(m)=\bra{\psi} \ket{m} \bra{m} \ket{\psi} = |\bra{m} \ket{\psi}|^2$

and the state snaps to:

$\frac{\bra{m} \ket{\psi}\ket{m}}{|\bra{m} \ket{\psi}|}$

If many identically prepared states $$\ket{\psi}$$ are measured, then the expectation value of the outcomes is

$\langle M \rangle = \sum_{m} m \cdot p(m) = \sum_{m} m \bra{\psi} P_m \ket{\psi} = \bra{\psi} M \ket{\psi}$

#### For Mixed States #

If the state is $$\rho$$, result $$m$$ occurs with probability:

$p(m)=\tr \left( P_m \rho \right)$

and the state after the measurement snaps to:

$\frac{P_m \rho P_m^{\dagger}}{p(m)}$

Note

If $$P_m=\ket{m}\bra{m}$$, then

$p(m) = \tr(\ket{m}\bra{m} \rho) = \tr(\bra{m} \rho \ket{m}) = \bra{m} \rho \ket{m}$

and the state snaps to:

$\ket{m}\bra{m}$

Note

Since a density matrix $$\rho$$ can be written as an ensemble of pure states:

$\rho = \sum_i p_i \ket{\psi_i} \bra{\psi_i}$

If the observable $$M=\sum_{m} m \ket{\psi_m} \bra{\psi_m}$$, then $$p_i=p(m) = \tr(\ket{\psi_m}\bra{\psi_m} \rho)$$.

### 3.3 POVM Measurements #

Positive operator $$E_m \triangleq M_m^{\dagger} M_m$$, such that $$\sum_m E_m = I$$.

#### For Pure States #

If the state is $$\ket{\psi}$$, result $$m$$ occurs with probability:

$p(m)= \bra{\psi} E_m \ket{\psi}$

and POVM measurements do not consider the state after the measurement.

#### For Mixed States #

If the state is $$\rho$$, result $$m$$ occurs with probability:

$p(m)=\tr \left( E_m \rho \right)$

and POVM measurements do not consider the state after the measurement.

## 4 Operator-Sum Representation #

Derivation of equation (8.10) in the textbook by Nielsen & Chuang.

Equation (8.6):

$\mathcal{E}(\rho)=\tr_B \left[ U(\rho \otimes \rho_B) U^{\dagger}\right]$

Let $$\ket{e_k}$$ be an orthonormal basis for system $$B$$. Assume system $$B$$ has the initial state $$\rho_B = \ket{e_0}\bra{e_0}$$.

To derive equation (8.10), the trick is the following fact:

$\begin{split} &\rho \otimes \ket{e_0}\bra{e_0}\\ =& (\rho \otimes I_B) (I_A \otimes \ket{e_0}) (I_A \otimes \bra{e_0})\\ =& (\rho I_A \otimes I_B \ket{e_0}) (I_A \otimes \bra{e_0})\\ =& (I_A \rho \otimes \ket{e_0} \cdot 1) (I_A \otimes \bra{e_0})\\ =& (I_A \otimes \ket{e_0}) (\rho \otimes 1) (I_A \otimes \bra{e_0})\\ =& (I_A \otimes \ket{e_0}) \rho (I_A \otimes \bra{e_0}) \end{split}$

Therefore, equation (8.10):

$\begin{split} \mathcal{E}(\rho)&=\tr_B \left[ U(\rho \otimes \ket{e_0}\bra{e_0}) U^{\dagger}\right]\\ &= \sum_k (I_A \otimes \bra{e_k}) \left[ U \left( \rho \otimes \ket{e_0}\bra{e_0} \right) U^{\dagger} \right] (I_A \otimes \ket{e_k})\\ &= \sum_k \underbrace{(I_A \otimes \bra{e_k}) U (I_A \otimes \ket{e_0})}_{E_k} \rho \underbrace{(I_A \otimes \bra{e_0}) U^{\dagger} (I_A \otimes \ket{e_k})}_{E_k^{\dagger}}\\ \end{split}$

Reference: StackExchange.

## 5 Reduced Density Matrix #

Definition in Nielsen & Chuang:

$\tr_B \left( \ket{a_1}\bra{a_2} \otimes \ket{b_1}\bra{b_2} \right) \triangleq \ket{a_1}\bra{a_2} \tr \left( \ket{b_1}\bra{b_2} \right)$

Another definition from the lecture notes by Dave Bacon:

$\tr_B(\rho) = \sum_{i=1}^{\dim \mathcal{H}_{B}} \bra{\phi_i}_B \rho \ket{\phi_i}_B$ where the quantum system is defined in Hilbert space $$\mathcal{H}=\mathcal{H}_A \otimes \mathcal{H}_B$$, and $$\ket{\phi_i}$$ is a basis for $$\mathcal{H}_B$$. $$\ket{\phi_i}_B \triangleq I_A \otimes \ket{\phi_i}$$.

The two definitions are equivalent.

Proof

If $$\rho = \ket{a_1}\bra{a_2} \otimes \ket{b_1}\bra{b_2}$$, then from the second definition:

$\begin{split} &\tr_B \left( \ket{a_1}\bra{a_2} \otimes \ket{b_1}\bra{b_2} \right)\\ =& \sum_i (I_A \otimes \bra{\phi_i}) \ket{a_1}\bra{a_2} \otimes \ket{b_1}\bra{b_2} (I_A \otimes \ket{\phi_i})\\ =& \sum_i \ket{a_1}\bra{a_2} \otimes \braket{\phi_i | b_1} \braket{b_2 | \phi_i}\\ =& \ket{a_1}\bra{a_2} \otimes \sum_i \braket{\phi_i | b_1} \braket{b_2 | \phi_i}\\ =& \ket{a_1}\bra{a_2} \tr \left( \ket{b_1} \bra{b_2} \right) \end{split}$

## 6 Circuit Implementation #

### 6.1 Implementation $$Q_{F}$$ #

For $$F: \{0,1\}^n \to \{0,1\}^m$$ ($$m$$ is usually 1)

Implements:

$\ket{x}\ket{b} \stackrel{Q_F}{\longrightarrow} \ket{x}\ket{b\oplus F(x)}$

where $$x \in \{0,1\}^n, b \in \{0,1\}^m$$, $$\oplus$$ is bitwise XOR.

### 6.2 Sign-implementation $$Q_F^{\pm}$$ #

For $$F: \{0,1\}^n \to \{0,1\}$$ (only for $$m=1$$)

Implements:

$\ket{x} \stackrel{Q_F^{\pm}}{\longrightarrow} (-1)^{F(x)}\ket{x}$

where $$x \in \{0,1\}^n$$.

### 6.3 Quantum Random Access Memory (QRAM) #

Given a superposition of address in the address register $$a$$, QRAM returns a superposition of data in the data register $$d$$, correlated to the address register. Let $$D_i$$ be the content of the $$i$$th memory cell. This is shown in the formula: $\sum_{i} \alpha_i \ket{i}_a \longrightarrow \sum_{i} \alpha_i \ket{i}_a \ket{D_i}_d$

## 7 Quantum Gates #

### 7.1 Pauli Group over $$n$$ Qubits: $$\mathcal{P}_n$$ #

$$\mathcal{P}_1$$ on 1 qubit has 16 elements (2×2 unitary matrices) consisting of all the Pauli matrices: $I=\begin{bmatrix}1&0\\0&1\end{bmatrix}, \quad X=\begin{bmatrix}0&1\\1&0\end{bmatrix}, \quad Y=\begin{bmatrix}0&-i\\i&0\end{bmatrix}, \quad Z=\begin{bmatrix}1&0\\0&-1\end{bmatrix}$ together with the products of these matrices with factors $$\pm 1$$ and $$\pm i$$.

Therefore,

$\mathcal{P}_1 = \{\pm I,\pm iI,\pm X,\pm iX,\pm Y,\pm iY,\pm Z,\pm iZ\}$

$$\mathcal{P}_n$$ is generated by the operators described above applied to each of $$n$$ qubits in the tensor product Hilbert space $$(\CC^2)^{\otimes n}$$.

### 7.2 Clifford Group over $$n$$ Qubits: $$\mathcal{C}_n$$ #

The Clifford group is defined as the group of unitaries that transforms Paulis into other Paulis:

$\mathcal{C}_n = \set{V \in U(2^n): V P V^{\dagger} \in \mathcal{P}_n, \forall P \in \mathcal{P}_n}$

## 8 Measures for Quantum Information #

### 8.1 Fidelity #

#### Fidelity of Quantum States #

Given two density matrix $$\rho$$ and $$\sigma$$, the fidelity is generally defined as the quantity $F(\rho, \sigma) = \left(\operatorname{tr} \sqrt{\sqrt\rho \sigma\sqrt\rho}\right)^2$

Note that for a pure state $$\ket{\psi}$$, the square root of its density matrix is the density matrix itself (easy to verify).

Usually we compute the fidelity between a pure state $$\ket{\psi}$$ and an arbitrary mixed state $$\rho$$.

$\begin{split} F(\ket{\psi}, \rho) &= \left( \tr \sqrt{(\ket{\psi}\bra{\psi})^{\frac{1}{2}} \rho (\ket{\psi}\bra{\psi})^{\frac{1}{2}}} \right)^2\\ &= \left( \tr \sqrt{\ket{\psi}\bra{\psi} \rho \ket{\psi}\bra{\psi}} \right)^2\\ &= \bra{\psi} \rho \ket{\psi} \end{split}$

Note

In Nielsen & Chuang, the definition does not have the square.

#### Fidelity of Quantum Channels #

The average fidelity of a quantum channel $$\mathcal{E}$$ is defined by $F(\mathcal{E})=\int \dd{\psi} \bra{\psi} \mathcal{E}(\ket{\psi}\bra{\psi})\ket{\psi}$ where the integral is over the uniform (Haar) measure on state space, normalized so $$\int \dd{\psi}=1$$.

## 9 Useful Transformations #

### 9.1 Hadamard Transform #

There are several kinds of notations (denote $$N=2^n$$): $\begin{split} H^{\otimes n} \ket{x} &= H x_1 \otimes H x_2 \otimes \dots \otimes H x_n\\ &= \bigotimes_{i=1}^n \frac{1}{\sqrt{2}} \left( \ket{0} + (-1)^{x_i}\ket{1} \right)\\ &= \frac{1}{\sqrt{2^n}} \sum_{s \in \{0,1\}^{n}} (-1)^{\sum_{i=1}^{n} s_i x_i} \ket{s} \\ &= \frac{1}{\sqrt{2^n}} \sum_{s \in \{0,1\}^{n}} (-1)^{\sum_{i=1}^{n} s_i x_i \mod 2} \ket{s} \\ &= \frac{1}{\sqrt{2^n}} \sum_{s \in \{0,1\}^{n}} (-1)^{\mathrm{XOR}_s(x)} \ket{s} \\ &= \frac{1}{\sqrt{2^n}} \sum_{s \in \{0,1\}^{n}} (-1)^{s \cdot x} \ket{s}\\ &= \frac{1}{\sqrt{N}} \sum_{s=0}^{N-1} (-1)^{s \cdot x} \ket{s} \end{split}$

Denote $$\ket{g} \triangleq \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \ket{x}$$, where $$g: \{0,1\}^n \to \CC$$ and satisfies $$\frac{1}{N} \sum_{x=0}^{N-1} |g(x)|^2=1$$ (so $$\ket{g}$$ is really a quantum state).

Define $$\mathcal{X}_s(x) \triangleq (-1)^{s \cdot x}$$, then the above equation can be written as

$H^{\otimes n} \ket{s} = \ket{\mathcal{X}_{s}}$

Note that $$H^{\otimes n}$$ is its own inverse, so we also have

$H^{\otimes n} \ket{\mathcal{X}_{s}} = \ket{s}$

Using this transform, we can get some useful results:

$\begin{split} H^{\otimes n} \ket{g} &= H^{\otimes n} \left( \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \ket{x} \right) \\ &= \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) H^{\otimes n}\ket{x}\\ &= \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \frac{1}{\sqrt{N}} \sum_{s=0}^{N-1} (-1)^{s \cdot x} \ket{s}\\ &= \frac{1}{N} \sum_{s=0}^{N-1} \sum_{x=0}^{N-1} (-1)^{s \cdot x} g(x) \ket{s}\\ &= \sum_{s=0}^{N-1} \hat{g}(s) \ket{s}\\ \end{split}$

where $$\hat{g}(s)$$ is the “strength” of pattern $$\ket{\mathcal{X}_s}$$ for $$\ket{g}$$, defined as

$\begin{split} \hat{g}(s) &\triangleq \braket{\mathcal{X}_s}{g}\\ &= \frac{1}{N} \sum_{x=0}^{N-1} \mathcal{X}_s(x)^{\dagger} g(x)\\ &= \frac{1}{N} \sum_{x=0}^{N-1} (-1)^{s \cdot x} g(x) \end{split}$

Again multiply $$H^{\otimes n}$$ on both sides, we have

$\ket{g} = \sum_{s=0}^{N-1} \hat{g}(s) H^{\otimes n} \ket{s} = \sum_{s=0}^{N-1} \hat{g}(s) \ket{\mathcal{X}_s}$

In summary, $$H^{\otimes n}$$ transforms $$\ket{g}$$ from $$\mathcal{X}$$-basis into standard basis (actually Boolean Fourier transform):

$\ket{g} = \sum_{s=0}^{N-1} \hat{g}(s) \ket{\mathcal{X}_s} \stackrel{H^{\otimes n}}{\longrightarrow} \sum_{s=0}^{N-1} \hat{g}(s) \ket{s}$

Also it transforms it back (Boolean Fourier inverse transform).

### 9.2 Quantum Fourier Transform #

Define $$N$$ functions $$\mathcal{X}_0, \mathcal{X}_2, \dots, \mathcal{X}_{N-1}: \ZZ_N \to \CC$$,

$\mathcal{X}_s(x) = \omega_N^{s\cdot x}$

where $$\omega_N = e^{\frac{2\pi i}{N}}$$.

Facts

1. $$\mathcal{X}_0(x) \equiv 1$$
2. $$\mathcal{X}_s(x)^N=1$$, i.e., it is an $$N$$-th root of unity
3. $$\mathcal{X}_s(x)^{*} = \left( \omega_N^{s \cdot x} \right)^{*} = \omega_N^{-s \cdot x} = \mathcal{X}_{-s}(x)$$
4. $$\mathcal{X}_s(x) = \mathcal{X}_x(s)$$
5. $$\ket{\mathcal{X}_0}, \ket{\mathcal{X}_2}, \dots, \ket{\mathcal{X}_{N-1}}$$ are orthonormal.

Define the inverse transform matrix as

$\begin{split} \text{DFT}_N^{\dagger} &\triangleq \begin{bmatrix} \rvert & & \rvert\\ \ket{\mathcal{X}_0} & \dots & \ket{\mathcal{X}_{N-1}}\\ \rvert & & \rvert \end{bmatrix}\\ &= \frac{1}{\sqrt{N}} \begin{bmatrix} \omega_N^0 & \omega_N^0 & \omega_N^0 & \dots & \omega_N^0\\ \omega_N^0 & \omega_N^1 & \omega_N^2 & \dots & \omega_N^{N-1}\\ \omega_N^0 & \omega_N^2 & \omega_N^4 & \dots & \omega_N^{2(N-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ \omega_N^0 & \omega_N^{N-1} & \omega_N^{2(N-1)} & \dots & \omega_N^{(N-1)(N-1)} \end{bmatrix} \end{split}$

Therefore if $$\ket{x}$$ is a basis state, we have the Quantum Fourier Transform:

$\text{DFT}_N \ket{x} = \frac{1}{\sqrt{N}} \sum_{s=0}^{N-1} \mathcal{X}_s(x)^{*} \ket{s}$

I.e., $$\text{DFT}_N \ket{s} = \ket{\mathcal{X}^{*}_s}$$

And the Quantum Fourier Inverse Transform:

$\text{DFT}^{\dagger}_N \ket{x} = \frac{1}{\sqrt{N}} \sum_{s=0}^{N-1} \mathcal{X}_s(x) \ket{s}$

I.e., $$\text{DFT}^{\dagger}_N \ket{s} = \ket{\mathcal{X}_s}$$

An equivalent definition is: (See proof in Nielsen & Chuang, formula (5.5) – (5.10))

$\text{DFT}_N \ket{x} = \frac{1}{\sqrt{N}} \left( \ket{0}+e^{\frac{2\pi i}{2}x} \ket{1} \right) \otimes \left( \ket{0}+e^{\frac{2\pi i}{2^2}x} \ket{1} \right) \otimes \dots \otimes \left( \ket{0}+e^{\frac{2\pi i}{2^{n-1}}x} \ket{1} \right) \otimes \left( \ket{0}+e^{\frac{2\pi i}{2^n}x} \ket{1} \right)$

Similar with Hadamard Transform, we have

$\begin{split} \text{DFT}_N \ket{g} &= \text{DFT}_N \left( \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \ket{x} \right) \\ &= \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \text{DFT}_N\ket{x}\\ &= \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \frac{1}{\sqrt{N}} \sum_{s=0}^{N-1} \mathcal{X}_s(x)^{*} \ket{s}\\ &= \frac{1}{N} \sum_{s=0}^{N-1} \sum_{x=0}^{N-1} \mathcal{X}_s(x)^{*} g(x) \ket{s}\\ &= \sum_{s=0}^{N-1} \hat{g}(s) \ket{s}\\ \end{split}$

where $\begin{split} \hat{g}(s) &\triangleq \braket{\mathcal{X}_s}{g}\\ &= \frac{1}{N} \sum_{x=0}^{N-1} \mathcal{X}_s(x)^{\dagger} g(x) \end{split}$

Taking the inverse transform on both sides, we have

$\ket{g} = \sum_{s=0}^{N-1} \hat{g}(s) \text{DFT}^{\dagger}\ket{s} = \sum_{s=0}^{N-1} \hat{g}(s) \ket{\mathcal{X}_s}$

In summary, the Fourier Transform and the Inverse Transform converts function between two bases, as shown in the table

Original Function Transformed Function
Std. Basis $$\displaystyle \ket{g} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} g(x) \ket{x}$$ $$\displaystyle\sum_{s=0}^{N-1} \hat{g}(s) \ket{s}$$
$$\ket{\mathcal{X}_s}$$ Basis $$\displaystyle\sum_{s=0}^{N-1} \hat{g}(s) \ket{\mathcal{X}_s}$$ $$\displaystyle\frac{1}{\sqrt{N}} \sum_{s=0}^{N-1} g(s) \ket{\mathcal{X}^{*}_s}$$

## 10 Algorithms #

### 10.2 Phase Kickback #

Suppose we have a one-qubit unitary $$U$$ which has an eigenvector $$\ket{\psi}$$ and $$e^{2\pi i \theta}$$ is the corresponding eigenvalue.

Start with $$\ket{0}\ket{\psi}$$, apply the Hadamard gate on the first qubit and then the controlled-$$U$$ gate on the two qubits (the first qubit is the control bit), we have

$\text{C}(U) (H \otimes I) (\ket{0}\otimes\ket{\psi}) = \frac{\ket{0} + e^{2\pi \theta}\ket{1}}{\sqrt{2}} \ket{\psi}$

The overall effect is to add a phase shift to the control qubit, and the second qubit remains intact. This is why it is called phase kickback.

For example, assume $$U=X$$ (i.e., NOT gate), where $$X \ket{-} = -\ket{-}$$. We have

$\begin{split} &\text{CNOT}((H \otimes I) (\ket{0}\otimes\ket{-}))\\ =& \text{CNOT} (\ket{+}\ket{-})\\ =& \ket{-}\ket{-} \end{split}$

### 10.3 Amplitude Amplification #

Boolean function $$\chi: \ZZ \to \set{0,1}$$. If $$\chi(x)=1$$, $$\ket{x}$$ is a “good” state, otherwise it is a “bad” state.

Define unitary operator: $Q=-\mathcal{A}S_0\mathcal{A}^{-1}S_{\chi}$

Where:

$$S_0$$ changes the sign of the amplitude if and only if the state is $$\ket{0}$$. The algebraic expression is $$S_0 = I-2\ket{0}\bra{0}$$. In other words, $$-S_0$$ is just the sign-implementation of the logical OR function: $$Q^{\pm}_{\text{OR}}$$.

$$S_{\chi}$$ changes the sign of the amplitudes of the “good” states:

$S_{\chi}\ket{x} = \left\{ \begin{array}{[email protected]{\quad:\quad}l} -\ket{x} & \text{if } \chi(x)=1\\ \phantom{-}\ket{x} & \text{if } \chi(x)=0 \end{array}\right.$

The algebraic expression is $$S_{\chi} = I-2\Pi_1$$, where $$\Pi_i$$ is a projection operator defined as

$\Pi_i=\sum_{x: \chi(x)=i} \ket{x}\bra{x}, \quad i \in \set{0,1}$

In particular, if there is only one “good state”, say $$\ket{\psi}$$, then $$S_{\chi} = I-2\ket{\psi}\bra{\psi}$$.

$$\mathcal{A}$$ is any quantum algorithm (unitary) and define

$\begin{split} &\ket{\Psi}=\mathcal{A}\ket{0}\\ &\ket{\Psi_i}=\Pi_i\ket{\Psi} = \Pi_i\mathcal{A}\ket{0}, \quad i \in \set{0,1} \end{split}$

Note that $$\ket{\Psi_i}$$ are orthogonal and NOT normalized. By definition, we have $$\ket{\Psi} = \ket{\Psi_0}+\ket{\Psi_1}$$, and $$S_{\chi}\ket{\Psi_0}=\ket{\Psi_0}$$, $$S_{\chi}\ket{\Psi_1}=-\ket{\Psi_1}$$.

Lemma \begin{aligned} Q\ket{\Psi_1}&=(1-2a)\ket{\Psi_1}-2a\ket{\Psi_0} \\ Q\ket{\Psi_0}&=2(1-a)\ket{\Psi_1}+(1-2a)\ket{\Psi_0} \end{aligned} where $$a = \braket{\Psi_1}{\Psi_1}$$.

Proof

First proof a useful equality: $\begin{split} \mathcal{A}S_0\mathcal{A}^{-1} &= \mathcal{A}(I-2\ket{0}\bra{0})\mathcal{A}^{\dagger}\\ &= I - 2 \mathcal{A}\ket{0}\bra{0}\mathcal{A}^{\dagger}\\ &= I-2\left(\ket{\Psi_0}+\ket{\Psi_1}\right)\left(\bra{\Psi_0}+\bra{\Psi_1}\right) \end{split}$

And since $$\braket{\Psi}{\Psi} = \braket{\Psi_0}{\Psi_0} + \braket{\Psi_1}{\Psi_1} = 1$$, we have $$\braket{\Psi_0}{\Psi_0}=1-a$$.

Therefore

$\begin{split} Q\ket{\Psi_0} &= - \left[ I-2\left(\ket{\Psi_0}+\ket{\Psi_1}\right)\left(\bra{\Psi_0}+\bra{\Psi_1}\right) \right] S_{\chi} \ket{\Psi_0}\\ &= -\left[ \ket{\Psi_0}-2\left(\ket{\Psi_0}+\ket{\Psi_1}\right)\braket{\Psi_0}{\Psi_0}\right]\\ &= 2(1-a)\ket{\Psi_1}+(1-2a)\ket{\Psi_0} \end{split}$

The other one is similar.

In fact, $$a$$ is the success probability of algorithm $$\mathcal{A}$$.

Define the angle $$\theta$$ such that $$\sin^2(\theta) = a$$. And we normalize $$\ket{\Psi_1}$$ and $$\ket{\Psi_0}$$ to $$\frac{1}{\sqrt{a}}\ket{\Psi_1}$$ and $$\frac{1}{\sqrt{1-a}}\ket{\Psi_0}$$ respectively, so that they can be used as an orthonormal basis. We call the space spanned by them $$\mathcal{H}_{\Psi}$$. The above lemma can be reformulated as:

\begin{aligned} Q\frac{1}{\sqrt{a}}\ket{\Psi_1}&=\cos(2\theta)\frac{1}{\sqrt{a}}\ket{\Psi_1}-2\sin(\theta)\cos(\theta) \frac{1}{\sqrt{1-a}}\ket{\Psi_0} \\ Q\frac{1}{\sqrt{1-a}}\ket{\Psi_0}&=2\sin(\theta)\cos(\theta)\frac{1}{\sqrt{a}}\ket{\Psi_1}+\cos(2\theta)\frac{1}{\sqrt{1-a}}\ket{\Psi_0} \end{aligned}

Thus if a vector is in the space $$\mathcal{H}_{\Psi}$$, applying $$Q$$ on it corresponds to a rotation by the angle $$2\theta$$, which can be represented by the rotation matrix:

$Q = \begin{bmatrix}\cos(2\theta)& -\sin(2\theta)\\ \sin(2\theta) & \phantom{-}\cos(2\theta)\end{bmatrix}$

Thus applying $$Q$$ $$n$$ times on state $$\ket{\Psi}$$ gives:

$\begin{split} Q^n\ket{\Psi} &= Q^n(\ket{\Psi_1} + \ket{\Psi_0})\\ &= \frac{1}{\sqrt{a}} (\sin(2n\theta))\cos(\theta)+\cos(2n\theta)\sin(\theta)) \ket{\Psi_1} + \frac{1}{\sqrt{1-a}} (\cos(2n\theta)\cos(\theta)-\sin(2n\theta)\sin(\theta))\ket{\Psi_0}\\ &= \frac{1}{\sqrt{a}} \sin((2n+1)\theta) \ket{\Psi_1} + \frac{1}{\sqrt{1-a}} \cos((2n+1)\theta)\ket{\Psi_0}\\ \end{split}$

(The original paper uses a different derivation, see Brassard et al. 2000)

Now measure, the probability of finding a “good” state is $$\sin^2((2n+1)\theta)$$. To maximize it, let $$(2n+1)\theta=\frac{\pi}{2}$$, we get $$n=\frac{\pi}{4\theta}-\frac{1}{2}$$. So we choose $$n=\lfloor \frac{\pi}{4\theta}\rfloor$$. Since $$\sin(\theta)\ll 1$$, we can approximate as follows:

$n=\left\lfloor \frac{\pi}{4\theta}\right\rfloor \approx \left\lfloor \frac{\pi}{4\sin(\theta)}\right\rfloor = O\left(\frac{1}{\sqrt{a}}\right)$

Since the classical algorithm $$\mathcal{A}$$ has a success probability $$a$$, the expected number of applications of $$\mathcal{A}$$ is $$\frac{1}{a}$$. Therefore we obtain a quadratic speedup over the best possible classical algorithm.

### 10.4 Grover’s Algorithm #

In the amplitude amplification algorithm, let $$\chi=f$$, and let $$\mathcal{A}=H^{\otimes n}$$ be the Hadamard transform on $$n$$ qubits. The operator $Q = -\mathcal{A}S_0\mathcal{A}^{-1}S_{\chi} = -H^{\otimes n}S_0 \left(H^{\otimes n}\right)^{\dagger}S_f = H^{\otimes n} Q^{\pm}_{\text{OR}} H^{\otimes n}S_f$

### 10.5 Phase Estimation #

Given a unitary operator $$U$$, the algorithm estimates $$\theta$$ in $$U\ket{\psi}=e^{2\pi i \theta} \ket{\psi}$$. Here $$\ket{\psi}$$ is an eigenvector and $$e^{2\pi i\theta}$$ is the corresponding eigenvalue.

Intuition: Using phase kickback to write the phase of $$U$$ (in the Fourier basis) to the $$t$$ qubits in the “counting register”. Then using the inverse transform to translate this from the Fourier basis into the computational basis, which we can measure. $$t$$ is chosen according to the accuracy we wish to have in our estimate of $$\theta$$.

1. Prepare state. The first register (“counting register”) has $$t$$ qubits initialized to $$\ket{0}$$. The second register is initialized to $$\ket{\psi}$$: $\ket{\psi_0}=\ket{0}^{\otimes t} \ket{\psi}$

2. Apply $$H^{\otimes t}$$ on the first register: $\ket{\psi_1}= \frac{1}{\sqrt{N}} \left( \ket{0}+\ket{1} \right)^{\otimes t} \ket{\psi}$

3. Apply controlled-$$U^{2^j}$$ with $$0\leq j \leq t-1$$, where $U^{2^j} \ket{\psi} = U^{2^j-1}U\ket{\psi} = U^{2^j-1} e^{2\pi i \theta}\ket{\psi} = \dots = e^{2\pi i 2^j \theta}\ket{\psi}$

Using the relation: $U^{2^j}(\ket{+}\ket{\psi}) = \frac{1}{\sqrt{2}} U^{2^j}\left( \ket{0}\ket{\psi} + \ket{1}\ket{\psi} \right) = \frac{1}{\sqrt{2}} \left( \ket{0} + e^{2\pi i 2^j \theta} \ket{1} \right) \otimes \ket{\psi}$

We get the final state of the both registers:

$\begin{split} \ket{\psi_2} &= \frac{1}{\sqrt{N}}\left( \ket{0} + e^{2\pi i 2^{t-1} \theta} \ket{1} \right) \otimes \dots \otimes \left( \ket{0} + e^{2\pi i 2^1 \theta} \ket{1} \right) \otimes \left( \ket{0} + e^{2\pi i 2^0 \theta} \ket{1} \right) \otimes \ket{\psi}\\ &= \frac{1}{\sqrt{N}} \sum_{k=0}^{2^{t}-1} e^{2\pi i k \theta} \ket{k}\ket{\psi} \end{split}$ The second equality is due to the definition of the Quantum Fourier Transform.

4. Perform the inverse transform on the first register, we get

$\ket{2^t \theta}\ket{\psi}$

Now measure and we get the phase in the first register.

### 10.6 Amplitude Estimation #

In Amplitude Amplification, if $$a$$ is unknown, we can estimate it using Amplitude Estimation.

The algorithm uses Phase Estimation to estimate the eigenvalues of the Grover iteration $$Q$$. Since $$Q$$ is a rotation matrix, if the angle of rotation is $$\theta$$, then its eigenvalue is $$e^{i \theta}$$ and $$e^{i(2\pi-\theta)}$$. And since $$a=\sin^2(\frac{\theta}{2})$$, we can estimate $$\theta$$ so we know $$a$$.

### 10.7 Quantum Counting #

Grover’s algorithm attempts to find a solution to the oracle, whereas the quantum counting algorithm tells us how many of these solutions there are.

### 10.8 Twirling Quantum Channels #

Denote $$\mathcal{U}(d)$$ be the set of all $$d \times d$$ unitary matrices. Twirling the quantum channel $$\Lambda$$ on a density operator $$\rho$$ is

$\rho \mapsto \int_{\mathcal{U}(d)} \dd{\eta(U)} U^{\dagger} \Lambda (U \rho U^{\dagger}) U$ where $$U$$ is chosen randomly with respect to the Haar measure $$\eta$$.

Intuitively, twirling a channel is equivalent to taking the average, or expected value, of conjugation with all possible $$U \in \mathcal{U}(d)$$.

### 10.9 Entanglement Distillation (Purification) #

Transform $$N$$ arbitrary states $$\rho$$ into some number of approximately pure Bell pairs.

## 11 Number Theory #

### 11.1 If $$(a \mod n) = (b \mod n)$$, and $$\gcd(a,n)=1$$, then $$\gcd(b,n)=1$$. #

Proof

Let $$r \triangleq a \mod n = b \mod n$$, then

$a = pn + r, \quad b=qn+r$

So $a=pn+b-qn=b+(p-q)n$

Since $$\gcd(b,n)$$ divides $$b$$ and $$n$$, so it also divides $$a$$.

By condition, $$\gcd(a,n)=1$$, so the only number that divides $$a$$ and $$n$$ is 1. So $$\gcd(b,n)=1$$.