Quantum Algorithm

Query value of function

• $U_f:|x,y\rangle\rightarrow|x,y\oplus f(x)\rangle$
  • $f:\{0,1\}^n\rightarrow\{0,1\}$
  • 对应的矩阵为置换阵 $2^n\times 2^n$
• Quantum Parallelism: $U_f H^{\oplus n}|0^n\rangle=\frac{1}{\sqrt{2^n}}\sum_x|x,f(x)\rangle$
• Store the query in phase: $O_f|x\rangle=(-1)^{f(x)}|x\rangle$
  • $U_f|x,-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$
• Deutsch Algorithm
  • Question: Given a function $f:\{0,1\}\rightarrow\{0,1\}$, decide whether $f(0)=f(1)$
  • $|0\rangle \rightarrow H \rightarrow O_f \rightarrow H \rightarrow M(|0\rangle,|1\rangle)$
• Deutsch-Joszsa Algorithm
  • Question: Given a function $f:\{0,1\}^n\rightarrow\{0,1\}$, it is either constant or balanced($|f^{-1}(0)|=|f^{-1}(1)|=2^{n-1}$).
  • $|0\rangle^{\otimes n}\rightarrow H^{\otimes n}\rightarrow O_f\rightarrow H^{\otimes n}\rightarrow M(|0^n\rangle)$

Quantum Teleportation

Archived figure unavailable in this copy of the notes: Quantum Teleportation.

Super-dense Coding

one qubit encode two bits (tight)

• share EPR state
• $00:I,01:Z,10:X,11:iY$

Bernstein-Vazirani Algorithm

• For $N=2^n$, given $x\in\{0,1\}^N$, there is some unknown $a\in\{0,1\}^n$ such that $x_i=(i\cdot a)\bmod 2$. The goal is to find $a$
• Algorithm
  1. Prepare the state: $H|0^n\rangle$
  2. Make a query $O_f$: $\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{x_i}|i\rangle=\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{i\cdot a}|i\rangle=H^{\otimes n}|a\rangle$
  3. Apply $H^{\otimes n}$: $|a\rangle$

Simon's Algorithm

• Simon's Problem(Hidden Shift): $N=2^n,x-(x_0,\cdots,x_{N-1}),x_i=\{0,1\}^n$, there is some unknown nonzero $s\in\{0,1\}^n$ such that $x_i=x_j$ iff $i=j$ or $i=j\oplus s$. The goal is to find $s$
• Algorithm
  1. Prepare the state: $H^{\oplus n}|0^n\rangle|0^n\rangle=\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}|i\rangle|0^n\rangle$
  2. Make a query: $\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}|i\rangle|x_i\rangle$
  3. Measure the second register.
     • Output $x_i$ w.p. $\frac{1}{2^n}$.
     • Post-measurement state: $\frac{1}{\sqrt{2}}(|i\rangle+|i\otimes s\rangle)$
  4. Apply $H^{\otimes n}$
  5. Measure the register.
     • Output a random element from $\{j:s\cdot s=0\pmod 2\}$
  6. Repeat this procedure until we have obtained $n-1$ independent linear equations involving $s$
  7. Gaussian elimination modulo $2$
• Lower bound
  • decision version
    • Given: $N=2^n,x=(x_0,\cdots,x_{N-1}),x_i\in\{0,1\}^n$
    • Promise: $\exists s\in\{0,1\}^n$ such that $x_i=x_j$ iff $i=j$ or $i=j\oplus s$
    • Task: decide whether $s=0^n$
  • Proof
    • Let $\Pi$ be a $T$-query randomized algorithm that solve the problem w.p. $\geq\frac{2}{3}$
    • Let $r$ be internal randomness of $Pi$ ($\Pi_r$ is a determininistic algorithm)
    • Let $\mu$ be a distribution on the inputs
    • $P_{x\sim\mu}(\Pi(x)\text{ is correct})\geq\frac{2}{3}\Rightarrow P_{x\sim\mu,r}(\Pi_r(x)\text{ is correct})\geq\frac{2}{3}\Rightarrow\exists$ a deterministic $T$-query algorithm that solve the problem with probability $\geq\frac{2}{3}$ under $\mu$ (在一个概率分布下随机化为确定)
    • Find a "hard distribution" $\mu$:
      • $\mu(s=0)=\frac{1}{2}:x$ is a uniform random permutation of $\{0,1\}^n$
      • $\mu(s\not=0)=\frac{1}{2}:s$ is picked from a nonzero string at random. For each pair $\{i,i\oplus s\}$ in a lexicographic order, we pick $x_i$ at random without replacement
    • Let $i_1,\cdots,i_T$ be queries made by algorithm, $P(i_1,\cdots,i_k\text{ is bad})$ should $\leq\frac{1}{3}$
      • $\prod_i(1-x_i)\geq 1-\sum_i x_i$
    • $T=\Omega(\sqrt{2^n})$

Complexity

• BPP: probabilistically polynomial-time computable by a classical computer
• BQP: probabilistically polynomial-time computable by a classical computer
• Theorem
  • $\text{P}\subseteq \text{NP}\subseteq \text{PSPACE}$
  • $\text{P}\subseteq \text{BPP}\subseteq\text{BQP}\subseteq\text{PSPACE}$

Phase estimation

• Given a unitary gate $U$ and an eigenvector $|\varphi\rangle$ of $U$, $U|\varphi\rangle=\lambda|\varphi$, estimate $|\varphi\rangle$ ($\lambda=e^{i\phi}$, estimate $\phi\in [0,2\pi)$)
• Algorithm
  • Prepare the state: $F_N|0^n\rangle|\varphi\rangle=\frac{1}{\sqrt{2^n}}\sum_{j=0}^{N-1}|j\rangle|\varphi\rangle,N=2^n$
  • Make a query: $|j\rangle|\varphi\rangle\rightarrow |j\rangle U^j|\varphi\rangle$
  • Apply $F_N^{-1}$ to first $n$ qubits
  • Get $|\phi_1\phi_2\cdots\phi_n\rangle,\phi=2\pi * 0.\phi_1\phi_2\cdots\phi_n$

Shor's Factoring Algorithm

• Factoring: Given a composite $N$, find an integer $1<p<N,p|N$
• Period-Finding: Given $f:\mathbb{N}\rightarrow Z_{N},f(a)=x^a\bmod N$ with the property for unknown $r\in Z_N,f(a)=f(b)$ iff $a=b\pmod{r}$
• Theorem (Shor): There exists a quantum algortihm solving Period-find algorithm using $O(\log\log N)$ evaluations of $f$ and $O(\log\log N)$ quantum Fourier transforms.
  • time complextity of each evaluation

• Algorithm
  • Find $q=2^l,N^2<q\leq 2N^2$
  • Prepare the state: $\frac{1}{\sqrt{q}}\sum_{a=0}^{q-1}|a\rangle|0^q\rangle$
  • Make a query: $\frac{1}{\sqrt{q}}\sum_{a=0}^{q-1}|a\rangle|f(a)\rangle$
  • Apply $F_q$
    • Condition the second register is $f(s)$, the first register is $\frac{1}{\sqrt{m}}\sum_{j=0}^{m-1}|jr+s\rangle$

$|\varphi_3\rangle=\frac{1}{\sqrt{m}}\sum_{j=0}^{m-1}\frac{1}{\sqrt{q}}\sum_{b=0}^{q-1}e^{\frac{2\pi i(jr+s)b}{q}}|b\rangle=\frac{1}{\sqrt{mq}}\sum_{b=0}^{q-1}=\frac{1}{\sqrt{mq}}\sum_{b=0}^{q-1}e^{2\pi i\frac{sb}{q}}(\sum_{j=0}^{m-1}e^{2\pi i\frac{jrb}{q}})|b\rangle$ $\sum_{j=0}^{m-1}e^{2\pi i\frac{jrb}{q}}=\begin{cases}m & e^{2\pi i\frac{rb}{q}}=1\newline \frac{1-e^{2\pi i\frac{rb}{q}}}{1-e^{2\pi i\frac{rb}{q}}} & o.w.\end{cases}$

• Case 1: $r|q$
  • $m=\frac{q}{r},e^{2\pi i\frac{rb}{q}}=1\iff \frac{rb}{q}$ is an integer $\iff\frac{q}{r}|b$
  • exactly $r$ such $b$ with amplitudes $\frac{1}{r}$
  • Get $b$, $\frac{b}{q}=\frac{c}{r}$
  • $c$ uniformly random in $[1,r-1]$, with probability $\Omega(\frac{1}{\log\log r}),c$ coprime with $r$
  • Repeat algorithm $O(\log\log N)$ times
• Case 2: $r\not|q$
  • $|\frac{1-e^{2\pi i\frac{mrb}{q}}}{1-e^{2\pi i\frac{rb}{q}}}|=|\frac{\sin(\pi mrb/q)}{\sin(\pi rb/q)}|$
  • w.h.p, $|\frac{b}{q}-\frac{c}{r}|\leq\frac{1}{2q}$
  • $r\not=r',r,r'<N$ then $|\frac{c}{r}-\frac{c'}{r'}|>\frac{1}{N^2}$
  • use continued fraction find the fraction with denominator $\leq N$ that is closest to $\frac{b}{q}$, which is $\frac{c}{r}$

Reduction of Factoring to period-finding

• Theorem: $N$ is composite number $L$ bits long and $x$ is non-trival solution to equation $x^2=1\pmod{N}$ in range $1\leq x\leq N$. Then at least one of $\gcd(x-1,N)$ and $\gcd(x+1,N)$ is a non-trivial factor of $n$ that can be computed using $O(L^3)$ operation
  • 找模$N$下 $1$ 的非平凡平方剩余
• Lemma: $p$ is an odd prime, $2^d$ be the largest power of $2$ dividing $\varphi(p^\alpha)$, then $P_{x\sim U[Z^*_{p^\alpha}]}(2^d|\text{ord}(x\bmod p^\alpha))=\frac{1}{2}$
• Theorem: Suppose $N>0$ is an odd composite, $x\sim U[Z^*_N]$ and $r=\text{ord}(x\bmod{N})$, then $P(2|r\wedge x^{\frac{r}{2}}\not=-1\pmod{N})\geq 1-2^{-m}$
• Algorithm
  • if $2|N$, return $2$
  • Determine whether $N=a^b$ for $a\geq 1,b\geq 2$
  • Randomly choose $x$ in $Z_N$, if $\gcd(x,N)>1$ return $\gcd(x,N)$
  • Use period-finding subroutine find the $r=\text{ord}(x\bmod N)$
  • if $2|r,x^{\frac{x}{2}}\not=1\pmod{N}$ then compute $\gcd(x^{\frac{r}{2}-1})$ and $\gcd(x^{\frac{r}{2}+1},N)$, return the non-trivial factor. Otherwise, the algorithm fails.

Hidden Subgroup Algorithm

• Problem: Given a known group $G$ and a map $f:G\rightarrow S$ where $S$ is some finite set. Suppose $f$ has the property that there exists a subgroup $H\leq G$ such that $f$ is constant within each coset and distinct on different cosets.
  • Goal: find $H$
• Discrete logarithm: find $\alpha,A=\gamma^\alpha$
• Algorithm for Abelian HSP
  • Initiate: $|0\rangle|0\rangle$ of dimensions $|G|$ and $|S|$
  • Prepare: $\frac{1}{\sqrt{G}}\sum_{g\in G}|g\rangle|0\rangle$
  • Query: $\frac{1}{\sqrt{g}}\sum_{g\in G}|g\rangle|f(g)\rangle$
  • Mesure the second registerm yielding $f(s)$ for $s\in G$: $\frac{1}{\sqrt{H}}\sum_{h\in H}|s+h\rangle$
  • Apply QFT: $\frac{1}{\sqrt{H}}\sum_{h\in H}|\chi_{s+h}\rangle$
  • Measure and output $g$
    • uniform random $g$ satisfying $\chi_g\in H^{\perp}=\{\chi_k|(\forall h\in H)\chi_k(h)=1\}$
    • output: $g_1,\cdots,g_t$
• Graph isomorphism
• Algorithm for Abelian HSP
  • $|g\rangle\rightarrow\sum_{\rho\in\hat G}\sqrt{\text{dim}\frac{\rho}{|G|}}|\rho\rangle\sum_{i,j=1}^{\text{dim}(\rho)}\rho(g)_{ij}|i,j\rangle$
  • Heisenberg group: $\text{poly}(\log|G|)$
  • solvable groups: $\text{poly}(\log|G|)$
  • nil-2 groups: $\text{poly}(\log|G|)$
  • dihedral groups: $2^{O(\sqrt{\log|G|})}$
• Query complexity of HSP
  • The quantum query complexity of HSP on any group $G$ is $O(\log^2|G|)$

Grover's Search Algorithm

• Problem: $N=2^n$, given an arbitrary $x\in\{0,1\}^N$. The goal is to find $i$ such that $x_i=1$.
• Oracle query: $O|x\rangle|i\rangle=(-1)^{x_i}|x\rangle|i\rangle$ ($O_x|i\rangle=(-1)^{x_i}|i\rangle$)
• 以 $|\varphi\rangle$ 为对称轴反转矩阵：$U=2|\varphi\rangle\langle\varphi|-I$
• Grover iterate: $G=H^{\otimes n}RH^{\otimes n}O_x,R=2|0^n\rangle\langle0^n|-I$
  • $O_x=-(2|i_0\rangle\langle i_0|-I)$ (只有 $i_0=0$)
  • $H^{\otimes n}RH^{\otimes n}=2|\varphi\rangle\langle\varphi|-I$
• Algorithm
  • Initiate: $|U\rangle=H^{\otimes n}|0^n\rangle$
  • Repeat following $k=O(\frac{1}{\sqrt{\epsilon}})$ times
    • Apply $O_x$
    • Apply $H^{\otimes n}RH^{\otimes}$
  • Measure the first register and check that the resulting $i$ is a solution
• $|G\rangle=\frac{1}{\sqrt{t}}\sum_{i:x_i=1}|i\rangle$
• $|B\rangle=\frac{1}{\sqrt{t}}\sum_{i:x_i=0}|i\rangle$
• $O_x$: 在 $|B\rangle$ 上翻转
  • $\sin\theta=\sqrt{\frac{t}{N}}$
  • $|U\rangle=\sin\theta|G\rangle+\cos\theta|B\rangle$
  • $G^k|U\rangle=\sin(2k+1)\theta|G\rangle+\cos(2k+1)\theta|B\rangle$
  • $k'=\frac{\pi}{4\theta}-\frac{1}{2}=O(\frac{1}{\theta})=O(\sqrt{\frac{N}{t}}),t$ 为 $x_i=1$ 的个数
• If $t$ is unknown
  • $t\leq N/2$ then the eigenvalues are $e^{i\theta}$ and $e^{i(2\pi-\theta)}$

Optimality of Grover's algorithm

• Adversary Method
  • $|\psi_k^x\rangle=U_kO_xU_{k-1}O_x\cdots U_1O_x|\psi\rangle$
  • $|\psi_k\rangle=U_kU_{-1}\cdots U_1|\psi\rangle$
  • $D_k=\sum_x\||\psi_k^x\rangle-|\psi_k\rangle\|^2$
  • $D_k\leq 4k^2$
  • $D_k\geq cN$
• Polynomial method

Amplitude amplification

• $\chi:\mathbb{Z}\rightarrow\{0,1\}$ be any Boolean function, suppose we have a quantum algorithm $A$ that uses no intermediate measurements and finds a solution $z\in\chi^{-1}(1)$ with probability $p$
• Suppose we have an algorithm check whether $z$ is a solution.
• Algorithm
  • Initiate: $|U\rangle=A|0\rangle$
  • Repeat $k=O(\frac{1}{\sqrt{p}})$
    • Apply $O_x$
    • Apply
• Application
  • TSP: $O(\sqrt{n!})$
  • Satisfiability: $O(\sqrt{2^n}\text{poly}(n))$

Random walk

• Problem: Given a d-regular simple graph $G=(V,E)$ with $m$ marked vertices, find one of the marked vertex.
• Normalized adjacency matrix $P$: $|V|\times|V|$ matrix $P(x,y)=\frac{1}{d},(x,y)\in E$ else $0$
• $P^kv(x,y)$: $v$ is $1$ at the starting position
• Stationary distribution: $G(V,E)$ is $d$-regular connected non-bipartite simple graph, then for any $v$, $P^kv$ will converge to a uniform distribution over all vertices
  • Spectral gap: $\delta=1-\lambda_2$
• Problem: $G=(V,E)$ with $\epsilon N$ marked vertices where $N=|V|$
  • $S$: set up an initial state $v$
  • $U$: update the current vertex
  • $C$: check whether the given vertex is marked
  • expected cost: $S+\frac{1}{\epsilon}(C+\frac{1}{\delta}U)$
• Quantum walk
  • Prepare: $|U\rangle=\frac{1}{\sqrt{N}}\sum_x|x\rangle|p_x\rangle$
  • Repeat the following $O(\frac{1}{\sqrt{\epsilon}})$ times
    • Reflect through $|B\rangle=\frac{1}{\sqrt{N-|M|}}\sum_{x\not\in M}|x\rangle|p_x\rangle$
    • Reflect through $|U\rangle$
  • Measure the first register and check the $x$ is marked
  • Time complexity: $S+\frac{1}{\sqrt{\epsilon}}(C+\frac{1}{\sqrt{\delta}}U)$
• Application
  • Grover Search
  • Collision Problem (03,tight)
  • Triangle finding problem