量子计算

Math Foundation

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

Linear Algebra

  • Vector: $|\psi\rangle$
  • Row vector: $\langle\psi|=(\overline{|\psi\rangle})^T$
  • Inner product: $\langle\psi|\varphi\rangle=\sum_i\overline{u}_iv_i$
    • $\langle\varphi|A|\psi\rangle$: Inner product between $|\varphi\rangle$ and $A|\psi\rangle$
    • $\lVert\psi\rVert=\sqrt{\langle\psi|\psi\rangle}$
  • Tensor product: $A=(a_{ij}),B=(b_{ij}),A\otimes B=(c_{(i_1,i_2),(j_1,j_2)})$
    • $H^{\otimes n}=H\otimes H\otimes \cdots \otimes H$
  • $|\psi\rangle|\varphi\rangle=|\psi\rangle\otimes|\varphi\rangle=|\psi\varphi\rangle=|\psi,\varphi\rangle$
    • $|0^n\rangle=|00\cdots0\rangle$
    • $(A\otimes B)(C \otimes D)=(AC)\otimes(BD)$
  • $M^\dagger=\overline{M}^T$
  • Unitary matrix $U$: $U^\dagger U=I$
  • Hermitian matrix: $H=U^\dagger DU$, $U$ is unitary and $D$ is a real diagonal matrix(eigenvalues of $H$)
  • Positive semidefinite: $H$ is Hermitina and its eigenvalues are nonnegative
  • orthonormal basis ${|v_1\rangle,\cdots,|v_d\rangle}$
    • Completeness relation: $\sum_i|v_i\rangle\langle v_i|=I$
    • Computational basis in $\mathbb{C}^d$: $|i\rangle=(0,\cdots,1,0,\cdots,0)^T$
  • noraml operator: $MM^\dagger=M^\dagger M$
    • Spectral/Eigenvalue decomposition: $M=\sum_{i=1}^d\lambda_i|v_i\rangle\langle v_i|=U\Lambda U^*$
      • $M$ is Hermitian iff $\lambda_i$ are reals
      • $M$ is a projector if $M$ is Hermitian and $M^2=M$/$\lambda_i\in{0,1}$
    • $f:\mathbb{C}^d\rightarrow\mathbb{C},f(M)=\sum_{i=1}^df(\lambda_i)|v_i\rangle\langle v_i|$
    • $Tr(A)=\sum_i A_{ii}=\sum_i \langle i|A|i\rangle$
      • $Tr(AB)=Tr(BA)$
      • $Tr(M)=\sum_{i}\lambda_i$

Fourier Transform

  • $\forall v\in\mathbb{C}^N$ view it as $v:{0,1,\cdots,N-1}\rightarrow\mathbb{C},v(i)=v_i$
  • Inner product: $\langle u,v\rangle=\sum_i\overline{u(i)}v(i)$
  • orthonormal basis $(\chi_j)_{0\leq j\leq N-1},\chi_j(k)=\frac{1}{\sqrt{N}}\omega_N^{jk},\omega_N=e^{\frac{2\pi i}{N}}$
    • $\forall v\in\mathbb{C}^N,v=\sum_{j=0}^N\hat v(j)\chi_j$
  • $F_N=\frac{1}{\sqrt{N}}(\chi_j(k))_{N\times N}=\frac{1}{\sqrt{N}}(\chi_1,\cdots,\chi_N)$
    • Unitary and Symmetric
  • Fourier Transform
    • naïve way $O(N^2)$ steps
    • $\hat v=F_N v$
    • $v = F_N^\dagger, v(j)=\sum_k\hat v(N-k)\chi_j(k)$
    • $F_2=H$
  • Convolution: $c_l=(a*b)_l=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}a_jb_{(l-j)\bmod N}$
    • $(\widehat{a*b})_l=\hat a_l\cdot \hat b_l$
  • Fast Fourier Transform: $T(N)=2T(\frac{N}{2})+O(N)\Rightarrow T(N)=O(N\log N)$
    • $\hat v_j=\frac{1}{\sqrt{2}}(\hat v_{\text{even } j}+\omega_N^j\hat v_{\text{odd } j})$
  • Multiplying two polynomials: $p(x)=\sum_{j=0}^d a_jx^j,q(x)=\sum_{k=0}^d b_kx^k$
    • Naïve Alg: $O(d^2)$
    • FFT: $O(d\log d)$
      • $O(d\log d)$: $\hat a,\hat b$
      • $O(d)$: $\widehat{a*b}$
      • $O(d\log d)$: $a*b$
  • Quantum Fourier transform $N=2^n$
    • $F_N|k\rangle=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}e^{2\pi ijk/N}|j\rangle$
    • $F_N|k_1k_2\cdots k_n\rangle=\bigotimes_{l=1}^n\frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi ik/2^l}|1\rangle)=\bigotimes_{l=1}^n\frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i0.k_{n-l+1}\cdots k_n}|1\rangle)$
    • $F_N|0^n\rangle=H^{\otimes n}|0^n\rangle$
  • 经典与量子的区别
    • $\hat v=F_N v$
    • $|\hat v\rangle=F_N|v\rangle$
      • 不考虑量子态的制作时间
      • 无法全部读出 $|\hat v\rangle$

Number Theory and Group Theory

  • $Z_n={0,\cdots,n-1},Z_n^*={x\in Z_n:\gcd(x,n)=1}$
  • $Z_{p^\alpha}$ is cyclic if $p$ is an odd prime and $\alpha$ is a positive integer
  • Continued fractions: $x=[a_0,a_1,\cdots],[a_0,\cdots,a_n]=\frac{p_n}{q_n}$, then $|x-\frac{p_n}{q_n}|\leq\frac{1}{q_n^2}$
    • $p_0=a_0,p_1=a_1a_0+1,p_n=a_np_{n-1}+p_{n-2}$
    • $q_0=1,q_1=a_1,q_n=a_nq_{n-1}+q_{n-2}$
  • homomorphism: $\rho:G\rightarrow H$ is a homomorphism if $\rho(g\cdot h)=\rho(g)\cdot\rho(h),\forall g,h\in G$
  • $\omega_N=e^{\frac{2\pi i}{N}}$
  • representation: homomorphism $\rho: G\rightarrow GL(n,\mathbb{C})$, the character $\chi_\rho(g)=\text{Tr}(\rho(g))$
  • Basi theorem: find Abelian group is isomorphic to $\mathbb{Z}_{N_1}\times\cdots\times\mathbb{Z_{N_t}}$
  • Represention of $\mathbb{Z}_{N}$: ${\chi_k}_{0\leq k\leq N-1},\chi_k(j)=\omega_N^{jk}$
  • Represention of $\mathbb{Z}_{N_1}\times\cdots\times\mathbb{Z_{N_t}}$: ${\chi_{k1}\cdots\chi_{k_t}}_{0\leq k_i\leq N_i-1}$
  • dual group: $\hat G={\text{all characters of } G}$
  • $|\chi\rangle =\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\chi(j)|j\rangle$
  • $F_N|k\rangle=|\chi_k\rangle$