[Note] Quantum Computation and Quantum Information - Chapter 5: The quantum Fourier transform and its applications

上課筆記，原文書:

Quantum Computation and Quantum Information, Michael A. Nielsen & Isaac L. Chuang

5.1 The quantum Fourier transform

• Discrete Fourier transform
  • $F_N: \mathbb{C}^N\to\mathbb{C}^N$ $$\left[\begin{matrix}x_0\\x_1\\\vdots\\x_{N-1}\end{matrix}\right] \xrightarrow{F_N} \left[\begin{matrix}y_0\\y_1\\\vdots\\y_{N-1}\end{matrix}\right],\quad y_k\equiv\frac{1}{\sqrt N}\sum^{N-1}_{j=0}x_je^{2\pi~ijk/N}$$
• Quantum Fourier transform $$\sum^{N-1}_{j=0}x_j\vert j\rangle \xrightarrow{QFT_N}\sum^{N-1}_{k=0}y_k\vert k\rangle, \quad y_k\equiv\frac{1}{\sqrt N}\sum^{N-1}_{j=0}x_je^{2\pi~ijk/N}$$

Prove this transformation is unitary

• Some notations $\vert j\rangle$
  • Binary representation: $j=j_1j_2\dots j_n$
    • $j=j_12^{n-1}+j_22^{n-2}+\cdots+j_n2^0$
    • e.g. $110_2\Rightarrow4+2+0=6$
  • Binary fraction: $0.j_lj_{l+1}\dots j_m$
    • $j_l/2+j_{l+1}/4+\cdots+j_m/2^{m-l+1}$
    • $0.11_2=1/2+1/4=3/4$

Take $N=2^n$, prove the product representation of quantum Fourier transform

$$\vert j_1,\dots,j_n\rangle\to\frac{1}{2^{n/2}}\left(\vert 0\rangle+e^{2\pi i0.j_n}\vert 1\rangle\right)\left(\vert 0\rangle+e^{2\pi i0.j_{n-1}j_n}\vert 1\rangle\right)\cdots\left(\vert 0\rangle+e^{2\pi i0.j_1j_2\dots j_n}\vert 1\rangle\right)$$

Proof By definition:

$$\begin{align*}\vert j\rangle &\to \frac{1}{2^{N/2}}\sum^{2^n-1}_{k=0}e^{2\pi ijk/2^n}\vert k\rangle\\ &= \frac{1}{2^{n/2}}\sum^1_{k_1=0}\sum^1_{k_2=0}\cdots\sum^1_{k_n=0}e^{2\pi ij(\sum^n_{l=1}k_l2^{-l})}\vert k_1\dots k_n\rangle\\ &= \frac{1}{2^{n/2}}\bigotimes^n_{l=1}\left[\sum^1_{k_l=0}e^{2\pi ijk_j2^{-l}}\vert k_l\rangle\right]\\ &= \frac{1}{2^{n/2}}\bigotimes^n_{l=1}\left[ \vert 0\rangle+e^{2\pi ij2^{-l}}\vert 1\rangle \right]\\ &= \frac{1}{2^{n/2}}\left( \vert 0\rangle + e^{2\pi i0.j_n}\vert 1\rangle \right)\otimes\left( \vert 0\rangle + e^{2\pi i0.j_{n-1}j_n}\vert 1\rangle \right)\otimes\cdots\\ &\qquad\qquad\qquad\qquad\qquad\otimes\left( \vert 0\rangle + e^{2\pi i0.j_1j_2\dots j_n}\vert 1\rangle \right)\end{align*}$$

• Easy to derive an efficient circuit for the product representaiton
  • $R_k$ gate $$R_k\equiv\left[\begin{matrix} 1&0\\0&e^{2\pi i/2^k} \end{matrix}\right]$$

QFT circuit

1. Input: $\vert j_1j_2\dots j_n\rangle$
2. Hadamard on first qubit: $$\frac{1}{2^{n/2}}(\vert 0\rangle+e^{2\pi i0.j_1}\vert 1\rangle)\otimes \vert j_2\dots j_n\rangle,\quad\because e^{2\pi i0.j_1}=(-1)^{j_1}$$
3. Applying controlled-$R_2$ on first qubit: $$\frac{1}{2^{n/2}}(\vert 0\rangle + e^{2\pi i0.j_1j_2}\vert 1\rangle)\otimes\vert j_2\dots j_n\rangle$$
4. Similarly, controlled-$R_3$, $\dots$, $R_n$ on first qubit: $$\frac{1}{2^{n/2}}(\vert 0\rangle + e^{2\pi i0.j_1j_2\dots j_n}\vert 1\rangle)\otimes \vert j_2\dots j_n\rangle$$
5. On second qubit, Hadamard: $$\frac{1}{2^{n/2}}(\vert 0\rangle + e^{2\pi i0.j_1j_2\dots j_n}\vert 1\rangle)\otimes (\vert 0\rangle + e^{2\pi i0.j_2}\vert 1\rangle)\otimes \vert j_3\dots j_n\rangle$$
6. Controlled-$R_2$, $\dots$, $R_{n-1}$ on second qubit: $$\frac{1}{2^{n/2}}(\vert 0\rangle + e^{2\pi i0.j_1j_2\dots j_n}\vert 1\rangle)\otimes (\vert 0\rangle + e^{2\pi i0.j_2\dots j_n}\vert 1\rangle)\otimes \vert j_3\dots j_n\rangle$$
7. ~$n$-th qubit: $$\frac{1}{2^{n/2}}(\vert 0\rangle + e^{2\pi i0.j_1j_2\dots j_n}\vert 1\rangle)\otimes (\vert 0\rangle + e^{2\pi i0.j_2\dots j_n}\vert 1\rangle)\otimes \cdots\otimes (\vert 0\rangle+e^{2\pi i0.j_n}\vert1\rangle)$$
8. Reverse order of qubits with $SWAP$ gates $\Rightarrow$ get QFT.

5.2 Phase estimation

Suppose a unitary $U$ (oracle) has an eigenvector $\vert u\rangle$ with eigenvalue $e^{2\pi i\varphi}$, estimate phase $\varphi$.

• Assume we can do controlled-$U$. Also for efficient implementation, assume we have controlled-$U^{2^j}$.
• $U\vert u\rangle=e^{2\pi i\varphi}\vert u\rangle$

Small case: suppose $\varphi=\frac{1}{2} \text{ or } 0\Rightarrow U\vert u\rangle=\vert u\rangle \text{ or } U\vert u\rangle=-\vert u\rangle$

$$\begin{align*} \vert \psi \rangle &= \text{C-}U\vert+\rangle\vert u\rangle\\ &= \frac{1}{\sqrt 2}\text{C-}U(\vert 0\rangle\vert u\rangle+\vert 1\rangle\vert u\rangle)\\ &= \frac{1}{\sqrt 2}(\vert 0\rangle\vert u\rangle+\vert 1\rangle e^{2\pi i\varphi}\vert u\rangle)\\ &= \frac{1}{\sqrt 2}(\vert 0\rangle+2^{2\pi i\varphi}\vert 1\rangle)\otimes \vert u\rangle\\ &= \begin{cases} \vert +\rangle\otimes \vert u\rangle, &\text{if } \varphi=0,\\ \vert -\rangle\otimes \vert u\rangle, &\text{if } \varphi=\frac{1}{2} \end{cases} \end{align*}$$

$\Rightarrow$

$\Rightarrow$ Only works for $\varphi=0.j_1$

General case: $\varphi=0.j_1j_2\dots j_n$

• Final state: $$\begin{align*} &\frac{1}{2^{t/2}}(\vert 0\rangle+e^{2\pi i2^{t-1}\varphi}\vert 1\rangle)(\vert 0\rangle+e^{2\pi i2^{t-2}\varphi}\vert 1\rangle)\cdots(\vert 0\rangle+e^{2\pi i\varphi}\vert 1\rangle)\\ &\quad\because 2^{t-1}\varphi=j_1j_2\dots j_n\\ \end{align*}$$ $$\begin{align*} \Rightarrow ~&\frac{1}{2^{t/2}}(\vert 0\rangle+e^{2\pi i0.j_t}\vert 1\rangle)(\vert 0\rangle+e^{2\pi i0.j_{t-1}j_t}\vert 1\rangle)\cdots(\vert 0\rangle+e^{2\pi i0.j_1j_2\dots j_t}\vert 1\rangle)\\ \Rightarrow ~&QFT_t\vert 2^t\varphi\rangle = \frac{1}{2^{t/2}}\sum^{2^t-1}_{k=0} e^{2\pi ik\varphi}\vert k\rangle \end{align*}$$
• Apply $(QFT_t)^{-1}$ to get $\vert \varphi\rangle$
  

5.2.1 Performance and requirements

The algorithm has “good” accuracy even if $\varphi$ isn’t exactly $t$ bit binary expansion, i.e. $\varphi$ can be irrational.

Let $b=\text{first } t \text{ bits of } \varphi$,

$$\varphi=0.\underbrace{b_1b_2\dots b_t}_bb_{t+1}b_{t+2}\dots$$

define $\delta\equiv \varphi - b/2^t$

$$\frac{1}{2^{t/2}}\sum^{2^t-1}_{k=0}e^{2\pi i\varphi k}\vert k\rangle \xrightarrow{QFT^{-1}}\frac{1}{2^t}\sum^{2^t-1}_{l=0}\sum^{2^t-1}_{k=0} e^{-2\pi i\frac{kl}{2^t}}e^{2\pi i\varphi k}\vert l\rangle$$

Let $\alpha_l$ be the amplitude of $\vert b+l~(\text{mod }2^t)\rangle$,

$$\begin{align*} \alpha_l &\equiv\frac{1}{2^t}\sum^{2^t-1}_{k=0} e^{2\pi ik(\varphi-\frac{b+l}{2^t})}\\ &=\frac{1}{2^t}\sum^{2^t-1}_{k=0}\left[e^{2\pi i(\varphi-\frac{b+l}{2^t})}\right]^k\quad(\because\alpha_l \text{ is a geometric series } \frac{1-r^n}{1-r})\\ &= \frac{1}{2^t}\frac{1-e^{2\pi i(2^t\varphi-(b+l))}}{1-e^{2\pi i(\varphi-(b+l)/2^t)}}\\ &= \frac{1}{2^t}\frac{1-e^{2\pi i(2^t\delta-l)}}{1-e^{2\pi i(\delta-l/2^t)}} \end{align*}$$

Suppose measurement outcome is $m$, the probability of getting error results is

$$P(\vert m-b\vert>e)=\sum_{-2^{t-1}<l\le-(e+1)}\vert\alpha_l\vert^2+\sum_{e+1\le l\le2^{t-1}}\vert\alpha_l\vert^2$$

where $e$ is a positive integer characterizing desired tolerance to error.

For any real $\theta$, $\vert1-e^{i\theta}\vert\le 2$,

$$\vert \alpha_l\vert = \left\vert\frac{1}{2^t}\frac{1-e^{2\pi i(2^t\delta-l)}}{1-e^{2\pi i(\delta-l/2^t)}}\right\vert\le\frac{1}{2^t}\frac{2}{\vert1-e^{2\pi i(\delta-l/2^t)}\vert}$$

By geometry or calculus $\vert 1-e^{i\theta}\vert\ge\frac{2\vert \theta\vert}{\pi}$ whenever $-\pi\le\theta\le\pi$. But when $-2^{t-1}<l\le 2^{t-1}$ we have $-\pi\le 2\pi(\delta-l/2^t)\le \pi$. Thus

$$\vert \alpha_l\vert \le \frac{1}{2^{t+1}\vert \delta-l/2^t\vert}$$

Then

$$\begin{align*} P(\vert m-b\vert > e) &\le \frac{1}{4}\left[ \sum^{-(e+1)}_{l=-2^{t-1}+1}\frac{1}{(l-2^t\delta)^2}+\sum^{2^{t-1}}_{l=e+1}\frac{1}{(l-2^t\delta)^2} \right]\\ &\le \frac{1}{4}\left[ \sum^{-(e+1)}_{l=-2^{t-1}+1}\frac{1}{l^2}+\sum^{2^{t-1}}_{l=e+1}\frac{1}{(l-1)^2} \right] \quad(\because 0\le2^t\delta\le 1)\\ &\le \frac{1}{2}\sum^{2^{t-1}-1}_{l=e}\frac{1}{l^2}\\ &\le \frac{1}{2}\int^{2^{t-1}-1}_{e-1}dl\frac{1}{l^2}=\frac{1}{2(e-1)} \end{align*}$$

To have accuracy $2^{-n}$ with probability of success at least $l-\epsilon$, where $\epsilon$ is error rate, choose $e\equiv2^{t-n}-1$ and let $t=n+p$ qubits,

$$\epsilon = \frac{1}{2(2^p-2)} \Rightarrow p=\left\lceil \log\left(2+\frac{1}{2\epsilon}\right) \right\rceil$$ $$\Rightarrow~t=n+\left\lceil \log\left(2+\frac{1}{2\epsilon}\right) \right\rceil$$

If we don’t have eigenstate $\vert u\rangle$, pick a “random” state $\vert \psi\rangle = \sum_u c_u\vert u\rangle$.

$$\sum_uc_u\vert u\rangle \xrightarrow{p.e.}\sum_u c_u\vert \varphi_u\rangle\vert u\rangle$$

5.3 Applications: order-finding and factoring

5.3.1 Application: order-finding

Given $x, N$, $x<N$, $\text{gcd}(x,N)=1$, the order of $x$ module $N$ is the least positive integer $r$, s.t. $x^r=1(\text{mod }N)$.

• Problem size $L\equiv\lceil\log(N)\rceil$
• Classical: no poly$(L)$
• Quantum: $O(L^3)$
  • Can reduce factoring to order finding
  • Order-finding is the phase estimation applied to the unitary $U_x$ $$U_x\vert y\rangle\equiv \vert xy~(\text{mod } N)\rangle, \quad y\in\{x,y\}^L$$
  • $U_x$ does the cyclic permutation on $x$: $$\begin{align*} x&\xrightarrow{U_x}x^2,\\ x^2&\xrightarrow{U_x}x^3\\ &~~~\vdots\\ x^{r-1}&\xrightarrow{U_x}x^r\\ x^r&\xrightarrow{U_x}x \end{align*}$$
  • $\vert x^r ~(\text{mod }N)\rangle=\vert 1 ~(\text{mod }N)\rangle$
  • $\vert u_0\rangle\equiv\vert x\rangle+\vert x^2\rangle+\cdots\vert x^r\rangle$ is an eigenstate of $U_x$. $\because U_x\vert u_0\rangle=\vert x^2\rangle+\vert x^3\rangle+\cdots\vert x\rangle=\vert u_0\rangle$.
  • Let $\omega=e^{-\frac{2\pi i}{r}}$, $\vert u_1\rangle\equiv\omega\vert x\rangle+\omega^2\vert x^2\rangle+\cdots+\omega^r\vert x^r\rangle$ is also an eigenstate of $U_x$. $\because U_x\vert u_1\rangle=\omega\vert x^2\rangle+\omega^2\vert x^3\rangle+\cdots+\underbrace{\omega^r}_{=1}\vert x\rangle=\omega^{-1}\vert u_1\rangle$

The eigenstates of $U_x$ can be defined by

$$\vert u_s\rangle = \frac{1}{\sqrt r}\sum^{r-1}_{k=0}e^{-\frac{2\pi isk}{r}} \vert x^k \text{ mod}~N\rangle$$

for integer $0\le s\le r-1$, since

$$\begin{align*} U_x\vert u_s\rangle &= \frac{1}{\sqrt r}\sum^{r-1}_{k=0}e^{-\frac{2\pi isk}{r}}\vert x^{k+1} \text{ mod}~N\rangle\\ &= e^{\frac{2\pi is}{r}}\vert u_s\rangle \end{align*}$$

Two requirements to use the phase estimation:

• Implement a controlled-$U^{2^j}$ for any integer $j$.
  • Can be resolved by using modular exponentiation
• Efficiently prepare an eigenstate $\vert u_s\rangle$ with a non-trivial eigenvalue, or at least a superposition of such eigenstates.
  • Observe that $\frac{1}{\sqrt r}\sum^{r-1}_{s=0}\vert u_s\rangle=\vert 1\rangle$, use $\vert 1\rangle$ as the input for second register.

$$\begin{align*}\frac{1}{\sqrt r}\sum^{r-1}_{s=0}\vert u_s\rangle &= \frac{1}{\sqrt r}\sum^{r-1}_{s=0}\left( \frac{1}{\sqrt r}\sum^{r-1}_{k=0}e^{-\frac{2\pi isk}{r}} \vert x^k \text{ mod } N\rangle \right)\\ &= \frac{1}{r}\sum^{r-1}_{s=0}\sum^{r-1}_{k=0}e^{-\frac{2\pi isk}{r}} \vert x^k \text{ mod } N\rangle\\ &= \frac{1}{r}\sum^{r-1}_{k=0}\left(\sum^{r-1}_{s=0}e^{-\frac{2\pi isk}{r}}\right) \vert x^k \text{ mod } N\rangle\\ &= \frac{1}{r}\sum^{r-1}_{k=0}r\delta_{k,0} \vert x^k \text{ mod } N\rangle\\ &= \vert x^0 \text{ mod } N\rangle =\vert 1\rangle\end{align*}$$

Apply phase estimation (PE):

$$\begin{align*} \vert 0\rangle^{\otimes t}\vert 1\rangle \xrightarrow{\text{PE of }U_x} &~\frac{1}{\sqrt r}\sum_s\vert \frac{s}{r}\rangle \vert u_s\rangle\\ \Rightarrow&~\text{get }\frac{s}{r}\text{ with uniform random }s\\ \Rightarrow&~\text{get a few of }\frac{s_1}{r_1}, \frac{s_2}{r_2}, \cdots\\ \Rightarrow&~\text{calculate }r. \end{align*}$$

If we use $t=2L+1+\left\lceil \log(2+\frac{1}{2\epsilon}) \right\rceil$ qubits in phase estimation, we will obtain an estimate of the phase $\varphi\approx s/r$ accuract to $2L+1$ bits, with probability at least $(1-\epsilon)/r$. Then, we find $r$ using contined fraction expansion.

Modular exponential:

• example: compute $x^{17}=\underbrace{x\cdot x\cdot\cdots\cdot x}_\text{17 terms}$ $\Rightarrow$ $16$ multiplications.
• $x\cdot x=x^2$, $x^2\cdot x^2=x^4$, $x^4\cdot x^4=x^8$, $x^8\cdot x^8=x^{16}$, $x^{16}\cdot x=x^{17}$ $\Rightarrow$ $5$ multiplication.
• In general can do $x^r$ with $O(\text{poly}\log(r))$ multiplications.

The continued fraction expansion

• Given $\varphi\approx s/r$, how to find $s$, $r$?
• ex. $\varphi=0.25001$, $s/r=1/4$? $$\begin{align*} \varphi&=\frac{25001}{100000}=\frac{1}{\frac{100000}{25001}}=\frac{1}{3+\frac{24997}{25001}}\\ &=\frac{1}{3+\frac{1}{\frac{25001}{24997}}}=\frac{1}{3+\frac{1}{1+\underbrace{\frac{4}{24997}}_{\text{small}}}} \end{align*}$$

Theorem 5.1: Suppose $s/r$ is a rational number such that

$$\left\vert \frac{s}{r}-\varphi \right\vert\le \frac{1}{2r^2}$$

Then $s/r$ is a convergent of the continued fraction for $\varphi$, and thus can be computed in $O(L^3)$ operations using the continued fractions algorithm.

Since $\varphi$ is an approximation of $s/r$ accurate to $2L+1$ bits, it follows that $\vert s/r-\varphi\vert\le 2^{-2L-1}\le 1/2r^2$, since $r\le N\le 2^L$. Thus, the theorem applies.

Performance

Some considerations:

• phase estimation might produce a bad estimate to $s/r$ with probability $\epsilon$.
• $s$, $r$ have a common factor, in which case the number $r’$ returned by continued fractions algorithm be a factor of $r$, and not $r$ itself $\Rightarrow$ $s$, $r$ might not be co-prime.

1. Solution $1$
   • The number of prime numbers less than $r$ is at least $r/2\log r$
   • The chance that $s$ is prime is at least $1/2\log(r)>1/2\log(N)$
   • Repeating algorithm $2\log(N)$ times ($s_1/r_1, s_2/r_2, \dots$) will have high probability to obtain co-prime $s$, $r$.
2. Solution $2$
   • if $r’\ne r~\Rightarrow~r’$ is a factor of $r$. The probability is $1/r\le1/2$

   • 待補

3. Solution $3$
   • Do phase estimation and continued fractions twice, get $r’_1$, $s’_1$, $r’_2$, $s’_2$. Find $r$ from $r_1$, $r_2$.
   • If $LCM(r_1, r_2)\ne r$, exist $q$ s.t. $q$ divides $s’_1$ and $q$ divides $s’_2$. The probability that $s’_1$, $s’_2$ have common factors satisfies $$\sum_qp(q\vert s'_1 \cap q\vert s'_2)=\sum_qp(q\vert s'_1)p(q\vert s'_2)\le \sum_q\frac{1}{q^2}\le \sum^\infty_{q=2}\frac{1}{q^2}\le\frac{3}{4}$$
   • The probability of obtaining the correct $r$ is at least $1/4$

5.3.2 Application: factoring

• Reducing factor to order finding
• Randomly pick $x$ co-prime to $N$, find order $r$ s.t. $x^r\equiv 1(\text{mod }N)$
  • if $r$ is odd, try another $r$ (with const probability)
  • if $r$ is even, compose $x^{r/2} (\text{mod }N)$
• We know $(x^{r/2})^2\equiv 1(\text{mod }N)\Rightarrow (x^{r/2}-1)(x^{r/2}+1)\equiv 0(\text{mod }N)$
• 4 cases, if $N=pq$

$\text{gcd}(x^{r/2}-1, N)$	$\text{gcd}(x^{r/2}+1, N)$
$pq$	$1$	$x^{r/2}\equiv 1(\text{mod }N)$ impossible
$1$	$pq$	$x^{r/2}\equiv -1(\text{mod }N)$ const probability
$p$	$q$	Non-trivial factor, calculate $\text{gcd}(x^{r/2}-1, N)$
$q$	$p$	Non-trivial factor, calculate $\text{gcd}(x^{r/2}+1, N)$

Theorem 5.2: Suppose $N$ is an $L$ bit composite number, and $x$ is a non-trivial solution to the equation $x^2=1(\text{mod} N)$ in the range $1\le x\le N$, that is, neither $x=1(\text{mod} N)$ nor $x=N-1=-1(\text{mod} N)$. Then at least one of $\text{gcd}(x-1, N)$ and $\text{gcd}(x+1, N)$ is a non-trivial factor of $N$ that can be computed using $O(L^3)$ operations.

Theorem 5.3: Suppose $N=p^{\alpha_1}_{1}\dots p^{\alpha_m}_m$ is the prime factorization of an odd composite positive integer. Let $x$ be an integer chosen uniformly at random, subject to the requirements that $1\le x\le N-1$ and $x$ is co-prime to $N$. Let $r$ be the order of $x$ module $N$. Then

$$p(r\text{ is even and }x^{r/2}\ne -1(\text{mod}N))\ge \text{const.}$$

Detail algorithm:

• Input $N$

1. If $N$ can be divided by $2$, return $2$
2. Determine whether $N=a^b$ by calculating $N^{1/2}, N^{1/3}, \dots, N^{1/L}$ (classical algorithm $O(L^3)$)
3. Choose random $x$ s.t. $1\le x\le N-1$, calculate $\text{gcd}(x, N)$. If $\text{gcd}(x, N)\ne 1$, return $\text{gcd}(x, N)$
   • Now we know $N$ is odd and has more than $1$ prime factor, and $x$ is coprime to $N$.
4. Use order finding algorithm to find minimum $r$ s.t. $x^r\equiv 1(\text{mod }N)$
5. If $r$ is even and $x^{r/2}\not\equiv-1 (\text{mod }N)$, return $\text{gcd}(x^{r/2}-1, N)$
6. Go back to step 3 and try another $x$

• By theorem 5.3, this algorithm terminates in constant number of trails.

5.4 General applications of the quantum Fourier transform

5.4.1 Period-finding

Given oracle $\tilde{U}_f: \tilde{U}_f\vert x\rangle\vert y\rangle = \vert x\rangle\vert f(x)\oplus y\rangle$ for some $f:N\to N$

• Promise: $\exists 1\le r\le c$ s.t. $f(x)=f(y)$ iff $r\mid \vert x-y\vert$ ($r$ is period of $f$)
• Problem: Use $\tilde{U}_f$ to find $r$ s.t. $f(x+r)=f(x)$
  • Classical: $\Omega(c)$ queries
  • Quantum: One query, short alg

Algorithm (Period-finding)

• Inputs:
  1. A blackbox with performs the operation $U\vert x\rangle\vert y\rangle = \vert x \rangle\vert y\oplus f(x)\rangle$
  2. a state to store the function evaluation, initialized to $\vert 0\rangle$
  3. $t=O(L+\log(1/\epsilon))$ qubits initialized to $\vert 0\rangle$
• Outputs: The least integer $r>0$ such that $f(x+r)=f(x)$
• Runtime: One use of $U$, and $O(L^2)$ operations. Succeeds with probability $O(1)$.
• Prodecure:
  1. $\vert 0\rangle\vert 0\rangle$ (initial state)
  2. $\to \displaystyle\frac{1}{\sqrt{2^t}}\sum^{2^t-1}_{x=0}\vert x\rangle \vert 0\rangle$ (create superposition)
  3. $\to \displaystyle\frac{1}{\sqrt{2^t}}\sum^{2^t-1}_{x=0}\vert x\rangle\vert f(x)\rangle$ (apply $U$)
     $\approx\displaystyle\frac{1}{\sqrt{r2^t}}\sum^{r-1}_{\ell=0}\sum^{2^t-1}_{x=0}e^{2\pi i\ell x/r}\vert x\rangle \vert \hat{f}(\ell)\rangle$
  4. $\to\displaystyle\frac{1}{\sqrt r}\sum^{r-1}_{l=0}\tilde{\vert\ell/r\rangle}\vert \hat{f}(\ell)\rangle$ (apply inverse Fourier transform to first register)
  5. $\to\tilde{\ell/r}$ (measure first register)
  6. $\to r$ (apply continued fractions algorithm)

Hidden shift problem

Given $\tilde{U}_f\vert x\rangle\vert f(y)\rangle=\vert x\rangle \vert f(x+y)\rangle$, also given $(x_0, f(x_0))$ for some $x_0$

• Problem: find $r$
• $\displaystyle\frac{1}{\sqrt r}\sum_j e^{2\pi i\frac{j}{r}}\vert f(x_0+j)\rangle$ are eigenvalues of $\tilde{U}_f\vert 1\rangle$
  • Use phase estimation to get $\displaystyle\frac{s}{r}$

Blackbox generalization of order finding

• Period finding v.s. Hidden shift: Period finding is the mainstream. No phase estimation

5.4.2 Discrete logarithms

待補

5.4.3 The hidden subgroup problem

待補

5.4.4 Other quantum algorithm

待補

Bonus

Group theory

• A group $G$ is a set of elements $\{a,b,c,\dots\}$ with a “multiplication” operation $\cdot$ satisfying the following properties
  1. Closure: $(a\cdot b)$ is an element of $G$
  2. Associative: $a\cdot(b\cdot c)=(a\cdot b)\cdot c$
  3. Identity: exist an element $e$ s.t. $e\cdot a=a$ and $a\cdot e=a$, $\forall a\in G$
  4. Inverse: $\forall a\in G$, exist $a^{-1}$ s.t. $a\cdot a^{-1}=e=a^{-1}\cdot a$
• Order of a group $\vert G\vert$: number of elements of $G$
• Subgroup: subset of $G$ that is also a group (with same multiplication) (most importantly, closure)
• If $H$ is a subgroup of $G$, $\vert H\vert$ divides $\vert G\vert$

Example: multiplication group mod $7$

• elements: $\{1,2,3,4,5,6\}\Rightarrow$ order $6$
• operation: multiplication mod $7$
• closure: $a\nmid 7, b\nmid 7 \Rightarrow ab\nmid 7$
• association: from integer multiplication
• identity: $1$
• inverse: $x^r\equiv 1 (\text{mod } 7)\Rightarrow (x^{r-1})\cdot x^r=1\Rightarrow x^{r-1}\equiv x^{-1}$
• subgroup: $\{x, x^2, x^3,\cdots, \underbrace{x^r}_{=1}\}$ is a subgroup, $\forall x$
  • $\{1,2,4\}\Rightarrow$ order $3$
  • $\{1,6\}\Rightarrow$ order $2$

In general, multiplication mod $P$ for some prime $P$ is a group $\Rightarrow$ order $P-1$

$$r\mid(P-1)\Rightarrow (P-1)=c\cdot r\Rightarrow x^{(P-1)}=(x^r)^c\equiv 1(\text{mod }P)$$

Suppose $N=pq$, and $p,q$ is prime

• Define: $\varphi(N)$ (Euler’s totient function) is the number of $x$ s.t. $1\le x\le N-1$ and $\text{gcd}(x,N)=1$
• Claim: $\varphi(N)=(p-1)(q-1)$
• Example: $p=3$, $q=5$ $\Rightarrow N=15\Rightarrow\varphi(N)=2\cdot4=8$

$\text{mod }3 \backslash\text{mod }5$	$1$	$2$	$3$	$4$
$1$	$1$	$10+12=22\\\equiv 7(\text{mod }15)$	$10+18=28\\\equiv 13(\text{mod }15)$	$10+24=34\\\equiv 4(\text{mod }15)$
$2$	$20+6=26\\\equiv 11(\text{mod }15)$	$20+12=32\\\equiv 2(\text{mod }15)$	$20+18=38\\\equiv 8(\text{mod }15)$	$20+24=44\\\equiv 14(\text{mod }15)$

$10=5\cdot 2\equiv 1 (\text{mod }3)$

$6=3\cdot 2\equiv 1(\text{mod } 5)$

$\Rightarrow 10\cdot a+6\cdot b\equiv a(\text{mod } 3)\equiv b(\text{mod } 5)$

Let $f(a,b)\equiv 10a+6b (\text{mod }15)\Rightarrow f(a,b)\cdot f(c,d)\equiv f(a+c \text{ mod }3, b+d \text{ mod }5)\text{mod }15$

RSA public key encryption

Construction phase:

• Select random large prime $p$ and $q$
• calculate $N=pq$, $\varphi(N)=(p-1)(q-1)$
• pick encryption key $e$ s.t. $\text{gcd}(e, \varphi(N))=1$
• calculate decryption key $d$ s.t. $de\equiv 1(\text{mod }\varphi(N))$ (efficiently with extended Euler’s algorithm)

Operations:

• Server send out $(N, e)$ as public key
• User encode $m$ as $m^e(\text{mod }N)\equiv E(m)$ (Suppose user’s message is some $m$ coprime to $N$)
• Server decrypt by calculating $(E(m))^d=(m^e)^d=m^{ed}=m (\text{mod }N)$

Proof:
Recall:

1. $ed-1\equiv 0(\text{mod }\varphi(N))$
2. Recall $r\mid \varphi(N)\Rightarrow \varphi(N)=c’\cdot r$

$m^{ed-1}\stackrel{\text{by 1}}{=}m^{c\cdot \varphi(N)}\stackrel{\text{by 2}}{=} m^{cc’r}\equiv 1(\text{mod }N)\Rightarrow m^{ed-1}\equiv 1 \Rightarrow m^{ed}\equiv m(\text{mod }N)$

extend eular:
$\varphi(N)=8, e=3\Rightarrow 8-(3\cdot 2)=2, 3-2=1$

$\Rightarrow 1=3-2=3-(8-3\cdot 2)=3\cdot 3-8$

$3\cdot 3-8=1 (\text{mod }8)\Rightarrow 3\cdot 3\equiv 1(\text{mod }8)$

Shor’s algorithm without phase estimation

• writing out the phase estimation part of order finding (The only quantum part of shor’s algorithm)
  

• $U_x\vert y\rangle = \vert xy (\text{mod }N)\rangle$

• $CU_x^j\vert j\rangle\vert y\rangle = \vert j\rangle\vert x^j y\rangle$

$$\begin{align*} \vert \psi_1\rangle&=\frac{1}{2^{t/2}}\sum^{2^t-1}_{j=0}\vert j\rangle\vert 1\rangle\\ \vert \psi_2\rangle&=\frac{1}{2^{t/2}}\sum^{2^t-1}_{j=0}\vert j\rangle\vert x^{j}\rangle \end{align*}$$

Two changes we can make on the order finding algorithm:

• Get $\vert \psi_2\rangle$ from a different oracle
• measure the second qubit after the oracle

Let $\tilde{U}_x: \tilde{U}_x\vert j\rangle\vert y\rangle=\vert j\rangle\vert x^j\oplus y(\text{mod }N)\rangle$

$$\begin{align*} \vert \psi_1\rangle &= \frac{1}{2^{t/2}}\sum^{2^t-1}_{j=0}\vert j\rangle \vert 0\rangle\\ \vert \psi_2\rangle &= \frac{1}{2^{t/2}}\sum^{2^t-1}_{j=0}\vert j\rangle \vert x^j\rangle \end{align*}$$

Possible $x^j$: $x, x^2, x^3,\dots, x^r$
$\Rightarrow$ measure second register, get $x^s$ with some $s\in\{0, 1,\dots r-1\}$

$$\begin{align*} \vert \psi_3\rangle &\propto \left( \vert s\rangle+\vert s+r\rangle+\vert s+2r\rangle+\cdots \right)\otimes \vert x^s\rangle\\ &=\frac{1}{\sqrt m}\sum^{m-1}_{j=0}\vert s+j\cdot r\rangle \otimes \vert x^s\rangle\qquad m\sim\frac{2^t}{r} \end{align*}$$

$QFT(\sum_j\vert s+jr\rangle)=?$

• Easy case: suppose $r\mid 2^t$, i.e. $2^t=m\cdot r$

  $$\begin{align*} \vert \psi_4\rangle &= QFT^{-1}(\sum_j\vert s+jr\rangle)\\ &= \frac{1}{\sqrt m}\frac{1}{\sqrt{2^t}}\sum^{m-1}_{j=0}\sum^{2^t-1}_{k=0}e^{-2\pi i \frac{(s+jr)k}{2^t}}\vert k\rangle\\ &= \frac{1}{\sqrt{m2^t}}\sum^{2^t-1}_{k=0}e^{-2\pi i\frac{sk}{2^t}}\sum^{m-1}_{j=0}e^{-2\pi i\frac{jk}{m}}\vert k\rangle\\ \Rightarrow \left\vert \langle k\vert\psi_4\rangle\right\vert^2 &= \begin{cases} \left\vert \sqrt{\frac{m}{2^t}}e^{i\phi_k} \right\vert^2=\frac{1}{r}, & \text{if } m\mid k,\\ 0, & \text{otherwise}\\ \end{cases}\\ \Rightarrow m\mid k\Rightarrow &k=cm \Rightarrow \displaystyle\frac{k}{2^t}=\frac{c}{r} \end{align*}$$

• Hard case: $r\not\mid 2^t$

  • Has error like when doing phase estimation and $\varphi\ne 0.b_1b_2\dots b_t$
  • error similar to what we get in phase estimation (geometric sum)
  • do continued fraction to get rid of error

Some comparisons

• Same output distribution, different oracles
• Oracle of second interpretation has phase
• Second interpretation is similar to Simon’s algorithm

Shor’s algorithm for $N=3\times17=51$

Recall

• $N=pq$, where $p$ and $q$ are primes.
• Randomly pick $1<x\le N-1$ co-prime to $N$, find order $x^r \equiv 1(\text{mod}~N)$
  • if $r$ is odd, try another $r$ (with const probability)
  • if $r$ is even, compose $x^{r/2}(\text{mod}~N)$
• We know $(x^{r/2})^2\equiv (\text{mod}~N)\Rightarrow (x^{r/2}-1)(x^{r/2}+1)\equiv 0(\text{mod}~N)$

1. Pick $x=2$, find $r$ s.t. $x^r\equiv 1 (\text{mod}~N)$ (Using order-finding algorithm)
   $\Rightarrow r=8$ ($r$ is even)
2. $x^{r/2}+1=17, \quad x^{r/2}-1=15$
3. Find $\text{gcd}(x^{r/2}-1, N)=\text{gcd}(15, 51)=3$

Order-finding part (assume $t=6$, $2^t=64$, $2^t-1=63$):

$$\begin{align*} \vert \psi_1\rangle &= (H^{\otimes 6}\vert 0\rangle^{\otimes 6})\otimes \vert 1\rangle =\frac{1}{8}\sum^{63}_{j=0}\vert j\rangle\otimes \vert 1\rangle\\ \vert \psi_2\rangle &= \frac{1}{8}\sum^{63}_{j=0}\vert j\rangle \otimes \vert x^j\rangle \end{align*}$$

Recall:

$$\begin{align*}&\frac{1}{\sqrt r}\sum^{r-1}_{s=0}\vert u_s\rangle=\vert 1\rangle\\\vert u_s\rangle &= \frac{1}{\sqrt r}\sum^{r-1}_{k=0}e^{-\frac{2\pi isk}{r}} \vert x^k \text{ mod}~N\rangle\\U_x\vert u_s\rangle &= \frac{1}{\sqrt r}\sum^{r-1}_{k=0}e^{-\frac{2\pi isk}{r}}\vert x^{k+1} \text{ mod}~N\rangle = e^{\frac{2\pi is}{r}}\vert u_s\rangle\end{align*}$$

$$\begin{align*} \Rightarrow&&\vert 1\rangle &= \frac{1}{\sqrt 8}\sum^{7}_{s=0}\vert u_s\rangle, \quad \vert u_s\rangle = \frac{1}{\sqrt8}\sum^{7}_{y=0}e^{-2\pi i\frac{sy}{8}}\vert x^y\rangle\\ &&(x^j)\vert u_s\rangle &= \frac{1}{\sqrt8}\sum^{7}_{y=0} e^{-2\pi i\frac{sy}{8}}\vert x^{j+y}\rangle \qquad (y'=j+y,~~y=y'-j)\\ &&&= \frac{1}{\sqrt8}\sum^{7}_{y=0} e^{-2\pi i\frac{s(y'-j)}{8}} \vert x^{y'}\rangle\\ &&&= e^{2\pi i\frac{sj}{8}}\vert u_s\rangle\\ \Rightarrow&&\vert \psi_1\rangle &= \frac{1}{8}\sum^{63}_{j=0}\vert j\rangle \otimes \frac{1}{\sqrt 8}\sum^{7}_{s=0}\vert u_s\rangle\\ \Rightarrow&&\vert \psi_2\rangle &= \frac{1}{8\sqrt8}\sum^{7}_{s=0}\sum^{63}_{j=0}\vert j\rangle \otimes e^{2\pi i\frac{sj}{8}}\vert u_s\rangle\\ &&QFT_t\vert k\rangle &= \frac{1}{8}\sum^{63}_{j=0}e^{2\pi i\frac{kj}{64}}\vert j\rangle,\quad e^{2\pi i\frac{sj}{8}}=e^{2\pi i\frac{(8s)j}{64}}\\ &&\Rightarrow~~&\frac{1}{8}\sum^{63}_{j=0}e^{2\pi i\frac{sj}{8}}\vert j\rangle = \frac{1}{8}\sum^{63}_{j=0}e^{2\pi i\frac{(8s)j}{64}}\vert j\rangle=QFT_t\vert 8s\rangle\\ &&\Rightarrow~~&QFT^{-1}_t\big(QFT_t\vert 8s\rangle\big) = \vert 8s\rangle\\ \Rightarrow&&\vert \psi_3\rangle&=\big(QFT^{-1}_t\otimes I\big)\vert \psi_2\rangle = \frac{1}{\sqrt 8}\sum^{7}_{s=0}\vert 8s\rangle \otimes \vert u_s\rangle \end{align*}$$

Measure the first register will randomly get $\{0, 8, 16, 24, 32, 40, 48, 56\}$

$\Rightarrow$ Solve $r=8$