Skip to Content
Quantum Computation

Gates

2019-09-05Original-language archivelegacy assets may be incomplete

matrix = operator = gate

Single qubit operator

  • Pauli operators
    • I=(1,0;0,1)I=(1,0;0,1)
    • X=(0,1;1,0)X=(0,1;1,0) (非门)
      • X∣0⟩=∣1⟩,X∣1⟩=∣0⟩X|0\rangle=|1\rangle,X|1\rangle=|0\rangle
    • Y=(0,−i;i,0)Y=(0,-i;i,0)
      • Y=iXZ,XY=−YX,XZ=−ZX,YZ=−ZYY=iXZ,XY=-YX,XZ=-ZX,YZ=-ZY
    • Z=(1,0;0,−1)Z=(1,0;0,-1)
      • Z∣0⟩=∣0⟩,X∣1⟩=−∣1⟩Z|0\rangle=|0\rangle,X|1\rangle=-|1\rangle
  • Hadamard gate: H=12(1,1;1,−1)H=\frac{1}{\sqrt{2}}(1,1;1,-1)
    • H∣0⟩=∣+⟩=∣0⟩+∣1⟩2,H∣+⟩=∣0⟩H|0\rangle=|+\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}},H|+\rangle=|0\rangle
    • H∣1⟩=∣−⟩=∣0⟩−∣1⟩2,H∣−⟩=∣0⟩H|1\rangle=|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}},H|-\rangle=|0\rangle
    • H⊗n∣0n⟩=12n∑x∈{0,1}n∣x⟩H^{\otimes n}|0^n\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle
    • H∣x⟩=∑z(−1)xz2∣z⟩H|x\rangle=\sum_z\frac{(-1)^{xz}}{\sqrt{2}}|z\rangle
    • H⊕n∣x⟩=∑z(−1)x⋅z∣z⟩2nH^{\oplus n}|x\rangle=\frac{\sum_z(-1)^{x\cdot z}|z\rangle}{\sqrt{2^n}}
      • x⋅zx\cdot z: binary product mod 2
    • HXH=Z,HZH=X,HYH=−YHXH=Z,HZH=X,HYH=-Y
  • Phase Gate: S=(1,0;0,i)S=(1,0;0,i)
  • T gate(π8\frac{\pi}{8} gate): T=(1,0;0,eiπ4)=eiπ8(e−iπ8,0;0,eiπ8)T=(1,0;0,e^{i\frac{\pi}{4}})=e^{i\frac{\pi}{8}}(e^{-i\frac{\pi}{8}}, 0;0,e^{i\frac{\pi}{8}})
  • Rotation
    • R∣0⟩=cos⁡θ∣0⟩−sin⁡θ∣1⟩R|0\rangle=\cos\theta|0\rangle-\sin\theta|1\rangle
    • R∣1⟩=sin⁡θ∣0⟩+cos⁡θ∣1⟩R|1\rangle=\sin\theta|0\rangle+\cos\theta|1\rangle

Approximating unitary operators

  • Bloch sphere and rotation operators
    • 二维复平面球同构与三维实平面球同构 SU(2)≅SO(3)SU(2)\cong SO(3)
    • ∣φ⟩=cos⁡θ2∣0⟩+eiφsin⁡θ2∣1⟩|\varphi\rangle = \cos\frac{\theta}{2}|0\rangle+e^{i\varphi}\sin\frac{\theta}{2}|1\rangle
    • A2=I,eiθA=cos⁡(θ)I+isin⁡(θ)AA^2=I,e^{i\theta A}=\cos(\theta)I+i\sin(\theta)A
    • Rx(θ)=e−iθX/Y/Z2=cos⁡θ2I−isin⁡θ2XR_{x}(\theta)=e^{\frac{-i\theta X/Y/Z}{2}}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}X
    • Ry(θ)=e−iθX/Y/Z2=cos⁡θ2I−isin⁡θ2YR_{y}(\theta)=e^{\frac{-i\theta X/Y/Z}{2}}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}Y
    • Rz(θ)=e−iθX/Y/Z2=cos⁡θ2I−isin⁡θ2ZR_{z}(\theta)=e^{\frac{-i\theta X/Y/Z}{2}}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}Z
    • Rn^=e−in^⋅σ⃗2=cos⁡θ2I−isin⁡θ2(nxX+nyY+nzZ)R_{\hat n}=e^{-i\hat n\cdot\frac{\vec\sigma}{2}}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}(n_xX+n_yY+n_zZ)
      • n^=(nx,ny,nz)\hat n=(n_x,n_y,n_z) real unit vector
  • Z-Y decomposition: U=eiαRz(β)Ry(γ)Rz(δ)U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)
    • U=eiα(β)Rn^Rm^(γ)Rn^(δ)U=e^{i\alpha}(\beta)R_{\hat n}R_{\hat m}(\gamma)R_{\hat n}(\delta)
  • ∥U−V∥=max⁡∣ψ⟩∥(U−V)∣ψ⟩∥\lVert U-V\rVert=\max\limits_{|\psi\rangle}\lVert(U-V)|\psi\rangle\rVert
    • ∣⟨ψ∣U†MiU∣ψ⟩−⟨ψ∣V†MiV∣ψ⟩∣≤2∥U−V∥|\langle\psi|U^\dagger M_iU|\psi\rangle-\langle\psi|V^\dagger M_iV|\psi\rangle|\leq 2\lVert U-V\rVert
    • ∥UtUt−1⋯U1−VtVt−1⋯V1∥≤∑i∥Ui−Vi∥\lVert U_tU_{t-1}\cdots U_1-V_tV_{t-1}\cdots V_1\rVert\leq\sum_i\lVert U_i-V_i\rVert
  • THTH=Rn^(θ),θ=2arccos⁡(cos⁡2π8),n^=(cos⁡π8,sin⁡π8,sin⁡π8)THTH=R_{\hat n}(\theta),\theta=2\arccos(\cos^2\frac{\pi}{8}),\hat n=(\cos\frac{\pi}{8},\sin\frac{\pi}{8},\sin\frac{\pi}{8}) up to a normalization
    • T=Rz(π4)T=R_z(\frac{\pi}{4})
    • HTH=Rx(π4)HTH=R_x(\frac{\pi}{4})
    • THTH=cos⁡π8I−i(cos⁡π8(X+Z)+sin⁡π8Y)sin⁡π8THTH=\cos^{\pi}{8}I-i(\cos\frac{\pi}{8}(X+Z)+\sin\frac{\pi}{8}Y)\sin\frac{\pi}{8}
    • Densely filled: ∀δ>0,N=⌈2πδ⌉+1,∃k!=j∈{1,⋯ ,N}\forall\delta>0,N=\lceil\frac{2\pi}{\delta}\rceil+1,\exists k!=j\in\{1,\cdots,N\} s.t. θ∣k−j∣<δ\theta_{|k-j|}<\delta, then {tθ∣k−j∣∣t=1,2,3,⋯}\{t\theta_{|k-j||t=1,2,3,\cdots}\} fills up [0,2π)[0,2\pi) with δ\delta precision
      • θk=(kθ) mod 2π\theta_k=(k\theta)\bmod 2\pi
      • Implement ∀α,Rn^(α)\forall \alpha,R_{\hat n}(\alpha) to an arbitrary small precisoin
    • HRn^H=Rm^(α),m^=(cos⁡π8,−sin⁡π8,cos⁡π8)HR_{\hat n}H=R_{\hat m}(\alpha),\hat m=(\cos\frac{\pi}{8},-\sin\frac{\pi}{8},\cos\frac{\pi}{8}) up to a normalization
  • U=Rn^(β)Rm^(λ)Rn^(δ)U=R_{\hat n}(\beta)R_{\hat m}(\lambda)R_{\hat n}(\delta) up to a global phase

Quantum Fourier Transform FNF_N

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

  • Rs=(1,0;0,e2πi/2s)R_s=(1,0;0,e^{2\pi i/2^s})
  • gates: O(n2)O(n^2)
  • omit gates RkR_k with k=Ω(log⁡n)k=\Omega(\log n) and obtain a circuit with O(nlog⁡n)O(n\log n) gates implementing QFT with precision 1poly(n)\frac{1}{\text{poly}(n)}

Controlled gates

  • Controlled-U
    • C1(U)∣b⟩⊗∣ψ⟩=∣b⟩⊗Ub∣ψ⟩C^1(U)|b\rangle\otimes|\psi\rangle=|b\rangle\otimes U^b|\psi\rangle
    • Cn(U)C^n(U)
  • Controlled-NOT (generalization of XOR): C-N\text{C-N}
  • Theorem: U=eiαAXBXC,ABC=IU=e^{i\alpha}AXBXC,ABC=I
  • C1(U)∣ab⟩=(I⊕C)C-N(I⊕B)C-N(I⊕A)([1,0;0,eiα]⊕I)C^1(U)|ab\rangle=(I\oplus C)\text{C-N}(I\oplus B)\text{C-N}(I\oplus A)([1,0;0,e^{i\alpha}]\oplus I)
  • Cn(U)C^n(U) = multi C-N + C-U
  • Toffoli gate (C2(U)C^2(U)): ∣abc⟩→∣ab(c⊕a⋅b)⟩|abc\rangle\rightarrow|ab(c\oplus a\cdot b)\rangle
    • generalization of NAND: classic universal gate
    • Classic: 0→∣0⟩,1→∣1⟩0\rightarrow|0\rangle,1\rightarrow|1\rangle
    • Decomposition to H,S,T,C-NH,S,T,\text{C-N}

Decomposition of Arbitrary unitary gates

  • Two-level unitary gates are universal
    • UU acts on dd-dimensial space, then U=V1⋯Vk,k≤d(d−1)2U=V_1\cdots V_k,k\leq \frac{d(d-1)}{2} two-level unitary matrices V1,⋯ ,VkV_1,\cdots,V_k （类似高斯消元）
      • O(4n)O(4^n)
  • Single qubit gates & CNOT gates are universal
    • U~\tilde{U} is the non-trival 2×22\times 2 unitary submatrix of UU
    • UU acts on the space spanned by the computational basis states ∣s⟩,∣t⟩|s\rangle,|t\rangle
    • Gray code: ∣g1⟩→∣gm∣|g_1\rangle\rightarrow|g_{m}|
    • ∣g1⟩→∣gm−1∣,C1(U),∣gm−1⟩→∣g1⟩|g_1\rangle\rightarrow|g_{m-1}|, C^1(U), |g_{m-1}\rangle\rightarrow |g_1\rangle
      • Controlled-U on different bit, controlled by other qubits are same
    • O(n2)O(n^2)
  • Hadamard+T+Phase+CNOT are universal
    • U→Rn^,Rm^,S→H,T,SU\rightarrow R_{\hat n},R_{\hat m},S \rightarrow H,T,S
    • Convergent rate Θ(1ϵ)\Theta(\frac{1}{\epsilon})
    • Solovay-Kitaev Theorem: Fix two universal gate sets that are closed under inverses. Then any tt-gate circuit using one gate set can be implemented to precision ϵ\epsilon using a circuit of t⋅poly(log⁡tϵ)t\cdot\text{poly}(\log\frac{t}{\epsilon})(Θ(log⁡c1ϵ)\Theta(\log^c\frac{1}{\epsilon})M <>? ) gates from other set