Quantum Computation and Information

\( \renewcommand{\vec}[1]{\boldsymbol{#1}} \DeclareMathOperator*{\E}{\mathbb{E}} \DeclareMathOperator*{\Var}{\mathrm{Var}} \DeclareMathOperator*{\Cov}{\mathrm{Cov}} \DeclareMathOperator*{\argmin}{\mathrm{arg\,min\;}} \DeclareMathOperator*{\argmax}{\mathrm{arg\,max\;}} \def\ZZ{{\mathbb Z}} \def\NN{{\mathbb N}} \def\RR{{\mathbb R}} \def\CC{{\mathbb C}} \def\QQ{{\mathbb Q}} \def\FF{{\mathbb FF}} \def\EE{{\mathbb E}} \newcommand{\tr}{{\rm tr}} \newcommand{\sign}{{\rm sign}} \newcommand{\1}{𝟙} \newcommand{\inprod}[2]{\left\langle #1, #2 \right\rangle} \newcommand{\set}[1]{\left\{#1\right\}} \require{physics} \)

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:

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:

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\).

8.2 Trace Distance #

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.1 Fourier Sampling #

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\).

11.2 \(\gcd(a,n)=1\) if and only if \(\exists x,y \in \ZZ\), such that \(xa+yn=1\). #

11.3 Let \(G\) be a finite group with \(m=|G|\), the order of the group. Then for any element \(g \in G\), \(g^m=1\). #


Links to this note