量子计算

Quantum Algorithm

2019-09-05 08:00 CST
2019-12-22 15:33 CST
CC BY-NC 4.0

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

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

period find algorithm

  • 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\\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