Matrix Cookbook Quantum Computing for Computer Scientists i 2 = − 1 , i 3 = − i , i 4 = 1 i^2 = -1, i^3 = -i, i^4 = 1 i 2 = − 1 , i 3 = − i , i 4 = 1 can also be represented as ( a , b ) (a, b) ( a , b ) a a a b b b commutative 可交换的: c 1 + c 2 = c 2 + c 1 , c 1 c 2 = c 2 c 1 c_1 + c_2 = c_2 + c_1, c_1c_2 = c_2c_1 c 1 + c 2 = c 2 + c 1 , c 1 c 2 = c 2 c 1 associative 结合的: ( c 1 + c 2 ) + c 3 = c 1 + ( c 2 + c 3 ) , ( c 1 c 2 ) c 3 = c 1 ( c 2 c 3 ) (c_1 + c_2) + c_3 = c_1 + (c_2 + c_3), (c_1c_2)c_3 = c_1(c_2c_3) ( c 1 + c 2 ) + c 3 = c 1 + ( c 2 + c 3 ) , ( c 1 c 2 ) c 3 = c 1 ( c 2 c 3 ) distributive 分配的: c 1 ( c 2 + c 3 ) = c 1 c 2 + c 1 c 3 c_1(c_2 + c_3) = c_1c_2 + c_1c_3 c 1 ( c 2 + c 3 ) = c 1 c 2 + c 1 c 3 addition: let c 1 = ( a 1 , b 1 ) , c 2 = ( a 2 , b 2 ) c_1 = (a_1, b_1), c_2 = (a_2, b_2) c 1 = ( a 1 , b 1 ) , c 2 = ( a 2 , b 2 ) then c 1 + c 2 = ( a 1 + a 2 , b 1 + b 2 ) c_1 + c_2 = (a_1 + a_2, b_1 + b_2) c 1 + c 2 = ( a 1 + a 2 , b 1 + b 2 ) multiplication: let c 1 = ( a 1 , b 1 ) , c 2 = ( a 2 , b 2 ) c_1 = (a_1, b_1), c_2 = (a_2, b_2) c 1 = ( a 1 , b 1 ) , c 2 = ( a 2 , b 2 ) then c 1 c 2 = ( a 1 a 2 − b 1 b 2 , a 1 b 2 + a 2 b 1 ) c_1c_2 = (a_1a_2 - b_1b_2, a_1b_2 + a_2b_1) c 1 c 2 = ( a 1 a 2 − b 1 b 2 , a 1 b 2 + a 2 b 1 ) subtraction: c 1 − c 2 = c 1 + ( − c 2 ) c_1 - c_2 = c_1 + (-c_2) c 1 − c 2 = c 1 + ( − c 2 ) division: let ( x , y ) = ( a 1 , b 1 ) ( a 2 , b 2 ) (x,y) = \frac{(a_1, b_1)}{(a_2, b_2)} ( x , y ) = ( a 2 , b 2 ) ( a 1 , b 1 ) then ( a 1 , b 1 ) = ( a 2 , b 2 ) ( x , y ) (a_1, b_1) = (a_2, b_2)(x, y) ( a 1 , b 1 ) = ( a 2 , b 2 ) ( x , y ) a 1 = a 2 x − b 2 y , b 1 = a 2 y + b 2 x a_1 = a_2x - b_2y, b_1 = a_2y + b_2x a 1 = a 2 x − b 2 y , b 1 = a 2 y + b 2 x a 1 a 2 + b 1 b 2 = ( a 2 2 + b 2 2 ) x a_1a_2 + b_1b_2 = (a_2^2 + b_2^2)x a 1 a 2 + b 1 b 2 = ( a 2 2 + b 2 2 ) x a 2 b 1 − a 1 b 2 = ( a 2 2 + b 2 2 ) y a_2b_1 - a_1b_2 = (a_2^2 + b_2^2)y a 2 b 1 − a 1 b 2 = ( a 2 2 + b 2 2 ) y then x = a 1 a 2 + b 1 b 2 a 2 2 + b 2 2 x = \frac{a_1a_2 + b_1b_2}{a_2^2 + b_2^2} x = a 2 2 + b 2 2 a 1 a 2 + b 1 b 2 y = a 2 b 1 − a 1 b 2 a 2 2 + b 2 2 y = \frac{a_2b_1 - a_1b_2}{a_2^2 + b_2^2} y = a 2 2 + b 2 2 a 2 b 1 − a 1 b 2 modulus: ∣ c ∣ = a 2 + b 2 |c| = \sqrt{a^2 + b^2} ∣ c ∣ = a 2 + b 2 algebraically complete: any polynomial equation has a solution in such a field 所有的代数方程的解都在这个域中 conjugate: if c = ( a , b ) c = (a, b) c = ( a , b ) c ˉ = ( a , − b ) \bar{c} = (a, -b) c ˉ = ( a , − b ) field isopmorphism: a bijective homomorphism between two fields bijection: one-to-one and onto 单射和满射 每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值 parallelogram law 平行四边形定律 polar/Catesian representation 极坐标系 ( ρ , θ ) (\rho, \theta) ( ρ , θ ) addition: ( V + W ) [ j ] = V [ j ] + W [ j ] (V+W)[j] = V[j] + W[j] ( V + W ) [ j ] = V [ j ] + W [ j ]
let V = [ v 1 v 2 ] , W = [ w 1 w 2 ] V = \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}, W = \begin{bmatrix} w_1 \\ w_2 \end{bmatrix} V = [ v 1 v 2 ] , W = [ w 1 w 2 ] then V + W = [ v 1 + w 1 v 2 + w 2 ] V + W = \begin{bmatrix} v_1 + w_1 \\ v_2 + w_2 \end{bmatrix} V + W = [ v 1 + w 1 v 2 + w 2 ] commutative: V + W = W + V V + W = W + V V + W = W + V associative: ( V + W ) + X = V + ( W + X ) (V + W) + X = V + (W + X) ( V + W ) + X = V + ( W + X ) inverse: V + ( − V ) = 0 V + (-V) = 0 V + ( − V ) = 0
Abelian group 阿贝尔群: addition, inverse, associative, commutative
scalar: an abitrarily complex number
multiply an element by a scalar: ( c ⋅ V ) [ j ] = c × V [ j ] (c \cdot V)[j] = c \times V[j] ( c ⋅ V ) [ j ] = c × V [ j ]
transpose 转置: V T [ j , k ] = V [ k , j ] V^T[j, k] = V[k, j] V T [ j , k ] = V [ k , j ]
conjugate 共轭，复数相反，实数不变: V ‾ [ j ] = V [ j ] ‾ \overline{V}[j] = \overline{V[j]} V [ j ] = V [ j ]
adjoint/dagger 伴随，转置+共轭: V † [ j , k ] = V [ k , j ] ‾ V^\dagger[j, k] = \overline{V[k, j]} V † [ j , k ] = V [ k , j ]
( V † ) † = V (V^\dagger)^\dagger = V ( V † ) † = V ( c ⋅ V ) † = c ‾ ⋅ V † (c \cdot V)^\dagger = \overline{c} \cdot V^\dagger ( c ⋅ V ) † = c ⋅ V † matrix multiplication: ⋆ \star ⋆
( A ⋆ B ) T = B T ⋆ A T (A \star B)^T = B^T \star A^T ( A ⋆ B ) T = B T ⋆ A T A ⋆ B ‾ = A ‾ ⋆ B ‾ \overline{A \star B} = \overline{A} \star \overline{B} A ⋆ B = A ⋆ B ( A ⋆ B ) † = B † ⋆ A † (A \star B)^\dagger = B^\dagger \star A^\dagger ( A ⋆ B ) † = B † ⋆ A † isomorphism 同构，双射（双向一一对应）
linear independence 线性无关
linear combination: V = c 1 v 1 + c 2 v 2 + ⋯ + c n v n V = c_1v_1 + c_2v_2 + \cdots + c_nv_n V = c 1 v 1 + c 2 v 2 + ⋯ + c n v n 一组向量的线性组合不等于0 0 = c 1 v 1 + c 2 v 2 + ⋯ + c n v n 0=c_1v_1 + c_2v_2 + \cdots + c_nv_n 0 = c 1 v 1 + c 2 v 2 + ⋯ + c n v n c 1 = c 2 = ⋯ = c n = 0 c_1 = c_2 = \cdots = c_n = 0 c 1 = c 2 = ⋯ = c n = 0 basis: a set of linearly independent vectors that span the space v 1 , v 2 , ⋯ , v n {v_1, v_2, \cdots, v_n} v 1 , v 2 , ⋯ , v n canonical/standard basis: a set of vectors with one 1 and the rest are 0 dimension: the number of vectors in the basis trace: sum of the diagonal elements
T r ( A ) = ∑ i = 1 n A [ i , i ] Tr(A) = \sum_{i=1}^{n} A[i, i] T r ( A ) = ∑ i = 1 n A [ i , i ] eigenvalue and eigenvector 特征值和特征向量
for a matrix A A A A v = λ v Av = \lambda v A v = λ v λ \lambda λ v v v symmetric matrix 对称矩阵
hermitian matrix 共轭转置矩阵
invertible matrix 可逆矩阵
A − 1 ⋆ A = A ⋆ A − 1 = I A^{-1} \star A = A \star A^{-1} = I A − 1 ⋆ A = A ⋆ A − 1 = I unitary matrix 幺正矩阵
A † ⋆ A = A ⋆ A † = I A^\dagger \star A = A \star A^\dagger = I A † ⋆ A = A ⋆ A † = I tensor product 张量积
A ⊗ B = [ a 11 B a 12 B a 21 B a 22 B ] A \otimes B = \begin{bmatrix} a_{11}B & a_{12}B \\ a_{21}B & a_{22}B \end{bmatrix} A ⊗ B = [ a 11 B a 21 B a 12 B a 22 B ] orthogonal:
for two vectors v 1 = ( a 1 , b 1 ) , v 2 = ( a 2 , b 2 ) v_1 = (a_1, b_1), v_2 = (a_2, b_2) v 1 = ( a 1 , b 1 ) , v 2 = ( a 2 , b 2 ) if v 1 ⋅ v 2 = 0 v_1 \cdot v_2 = 0 v 1 ⋅ v 2 = 0 v 1 v_1 v 1 v 2 v_2 v 2 v 1 ⋅ v 2 = a 1 a 2 + b 1 b 2 v_1 \cdot v_2 = a_1a_2 + b_1b_2 v 1 ⋅ v 2 = a 1 a 2 + b 1 b 2 normalised:
v ⋅ v = 1 v \cdot v = 1 v ⋅ v = 1 v = v ∣ v ∣ = v v ⋅ v v = \frac{v}{|v|} = \frac{v}{\sqrt{v \cdot v}} v = ∣ v ∣ v = v ⋅ v v also called Dirac notation
linear algebra in complex vector space
ket 表示量子态向量，通常用于描述系统的状态: ∣ v ⟩ |v\rangle ∣ v ⟩
bra 表示量子态向量的共轭转置（Hermitian 共轭），用于内积计算: ⟨ v ∣ \langle v| ⟨ v ∣
∣ 0 ⟩ = 0 1 [ 1 0 ] |0 \rangle = \begin{array}{cc} \begin{array}{c} 0 \\ 1 \end{array} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \end{array} ∣0 ⟩ = 0 1 [ 1 0 ]
∣ 1 ⟩ = 0 1 [ 0 1 ] |1\rangle = \begin{array}{cc} \begin{array}{c} 0 \\ 1 \end{array} \begin{bmatrix} 0 \\ 1 \end{bmatrix} \end{array} ∣1 ⟩ = 0 1 [ 0 1 ]
∣ + ⟩ = ∣ 0 ⟩ + ∣ 1 ⟩ 2 |+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}} ∣ + ⟩ = 2 ∣0 ⟩ + ∣1 ⟩
∣ − ⟩ = ∣ 0 ⟩ − ∣ 1 ⟩ 2 |-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}} ∣ − ⟩ = 2 ∣0 ⟩ − ∣1 ⟩
∣ i ⟩ = ∣ 0 ⟩ + i ∣ 1 ⟩ 2 |i\rangle = \frac{|0\rangle + i|1\rangle}{\sqrt{2}} ∣ i ⟩ = 2 ∣0 ⟩ + i ∣1 ⟩
∣ − i ⟩ = ∣ 0 ⟩ − i ∣ 1 ⟩ 2 |-i\rangle = \frac{|0\rangle - i|1\rangle}{\sqrt{2}} ∣ − i ⟩ = 2 ∣0 ⟩ − i ∣1 ⟩
inner product: ⟨ 0 ∣ 1 ⟩ = 0 \langle 0 | 1 \rangle = 0 ⟨ 0∣1 ⟩ = 0
"bracket" also called dot product/scalar product result in a scalar ⟨ 0 ∣ 1 ⟩ = [ 1 0 ] [ 0 1 ] = [ 1 ∗ 0 0 ∗ 1 ] = 0 \langle 0 | 1 \rangle = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1*0 \\ 0*1 \end{bmatrix} = 0 ⟨ 0∣1 ⟩ = [ 1 0 ] [ 0 1 ] = [ 1 ∗ 0 0 ∗ 1 ] = 0 outer product: ∣ 0 ⟩ ⟨ 1 ∣ | 0 \rangle\langle 1 | ∣0 ⟩ ⟨ 1∣
result in a matrix ∣ 0 ⟩ ⟨ 1 ∣ = [ 1 0 ] [ 0 1 ] = [ 1 ∗ 0 1 ∗ 1 0 ∗ 0 0 ∗ 1 ] = [ 0 1 0 0 ] | 0 \rangle\langle 1 | = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} = \begin{bmatrix} 1*0 & 1*1 \\ 0*0 & 0*1 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} ∣0 ⟩ ⟨ 1∣ = [ 1 0 ] [ 0 1 ] = [ 1 ∗ 0 0 ∗ 0 1 ∗ 1 0 ∗ 1 ] = [ 0 0 1 0 ] ∣ 0 ⟩ ⟨ 0 ∣ = [ 1 0 ] [ 1 0 ] = [ 1 ∗ 1 1 ∗ 0 0 ∗ 1 0 ∗ 0 ] = [ 1 0 0 0 ] |0 \rangle\langle 0 | = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix} = \begin{bmatrix} 1*1 & 1*0 \\ 0*1 & 0*0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} ∣0 ⟩ ⟨ 0∣ = [ 1 0 ] [ 1 0 ] = [ 1 ∗ 1 0 ∗ 1 1 ∗ 0 0 ∗ 0 ] = [ 1 0 0 0 ]
∣ 1 ⟩ ⟨ 1 ∣ = [ 0 1 ] [ 0 1 ] = [ 0 ∗ 0 0 ∗ 1 1 ∗ 0 1 ∗ 1 ] = [ 0 0 0 1 ] |1 \rangle\langle 1 | = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} = \begin{bmatrix} 0*0 & 0*1 \\ 1*0 & 1*1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} ∣1 ⟩ ⟨ 1∣ = [ 0 1 ] [ 0 1 ] = [ 0 ∗ 0 1 ∗ 0 0 ∗ 1 1 ∗ 1 ] = [ 0 0 0 1 ]
e i θ = cos ( θ ) + i sin ( θ ) e^{i\theta} = \cos(\theta) + i\sin(\theta) e i θ = cos ( θ ) + i sin ( θ )
量子比特的旋转可以表示为一个向量在复平面上的旋转 旋转操作可以用幺正矩阵（如 Pauli 矩阵和旋转矩阵）来表示 这些矩阵可以通过指数映射（如 e 的幺正矩阵次方）来生成 ∣ Ψ ⟩ + ∣ Ψ ′ ⟩ = ( c 0 + c 0 ′ ) ∣ 0 ⟩ + ( c 1 + c 1 ′ ) ∣ 1 ⟩ + ⋯ + ( c n + c n ′ ) ∣ n ⟩ |\Psi\rangle + |\Psi'\rangle = (c_0 + c_0')|0\rangle + (c_1 + c_1')|1\rangle + \cdots + (c_n + c_n')|n\rangle ∣Ψ ⟩ + ∣ Ψ ′ ⟩ = ( c 0 + c 0 ′ ) ∣0 ⟩ + ( c 1 + c 1 ′ ) ∣1 ⟩ + ⋯ + ( c n + c n ′ ) ∣ n ⟩ c ∣ Ψ ⟩ = c c 0 ∣ 0 ⟩ + c c 1 ∣ 1 ⟩ + ⋯ + c c n ∣ n ⟩ c|\Psi\rangle = cc_0|0\rangle + cc_1|1\rangle + \cdots + cc_n|n\rangle c ∣Ψ ⟩ = c c 0 ∣0 ⟩ + c c 1 ∣1 ⟩ + ⋯ + c c n ∣ n ⟩ 为什么学？ 解决经典计算机无法解决的问题 对于量子纠错可能性的乐观主义 这是什么？ 基于量子力学的计算机学说 量子化学，量子深度学习 后量子密码学 Physical Qubits: Particles with polarization(photon) 光子 Trapped ions 离子阱 Cold Atoms 冷原子 Quantum dots 量子点 Using Defect in Crystals 晶体缺陷 Superconductors 超导体 Major Players IBM, Google, Microsoft D-Wave, uses Quantum annealing to solve optimization problems Model of Quantum Computer Input Quantum Processor on Cloud Prepare a state Apply gates Measure Output: the probability distribution of the measurement Quantum Dynamics 量子动力学
时间演化算符 薛定谔方程 哈密顿量 态的演化 量子态的叠加 量子测量 the state ∣ Ψ ⟩ |\Psi\rangle ∣Ψ ⟩
∣ Ψ ⟩ = c 0 ∣ 0 ⟩ + c 1 ∣ 1 ⟩ + ⋯ + c n ∣ n ⟩ |\Psi\rangle = c_0|0\rangle + c_1|1\rangle + \cdots + c_n|n\rangle ∣Ψ ⟩ = c 0 ∣0 ⟩ + c 1 ∣1 ⟩ + ⋯ + c n ∣ n ⟩ being simultaneously in all states detect the state with probability x i = ∣ c i ∣ 2 ∑ i = 0 n ∣ c i ∣ 2 x_i = \frac{|c_i|^2}{\sum_{i=0}^{n} |c_i|^2} x i = ∑ i = 0 n ∣ c i ∣ 2 ∣ c i ∣ 2 when observed, it will collapse to one of the basic states 時間反演對稱
U U † = I UU^\dagger = I U U † = I U † U = I U^\dagger U = I U † U = I ∣ ψ ⟩ = U ∣ ϕ ⟩ |\psi\rangle = U|\phi\rangle ∣ ψ ⟩ = U ∣ ϕ ⟩ ⟨ ψ ∣ = ⟨ ϕ ∣ U † \langle\psi| = \langle\phi|U^\dagger ⟨ ψ ∣ = ⟨ ϕ ∣ U † ⟨ ϕ ∣ ψ ⟩ = ⟨ ϕ ∣ U † U ∣ ψ ⟩ \langle\phi|\psi\rangle = \langle\phi|U^\dagger U|\psi\rangle ⟨ ϕ ∣ ψ ⟩ = ⟨ ϕ ∣ U † U ∣ ψ ⟩ 模不变
量子态的模的表示: ⟨ ψ ∣ ψ ⟩ \langle\psi|\psi\rangle ⟨ ψ ∣ ψ ⟩ ⟨ ψ ∣ ψ ⟩ = ⟨ ϕ ∣ U † U ∣ ϕ ⟩ = ⟨ ϕ ∣ ϕ ⟩ \langle\psi|\psi\rangle = \langle\phi|U^\dagger U|\phi\rangle = \langle\phi|\phi\rangle ⟨ ψ ∣ ψ ⟩ = ⟨ ϕ ∣ U † U ∣ ϕ ⟩ = ⟨ ϕ ∣ ϕ ⟩ ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ ∣ ϕ ⟩ |\phi\rangle ∣ ϕ ⟩ 设Ω \Omega Ω ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ λ \lambda λ λ \lambda λ
superposition 叠加: ∣ ψ ⟩ ⟼ α ∣ 0 ⟩ + β ∣ 1 ⟩ |\psi\rangle \longmapsto \alpha|0\rangle + \beta|1\rangle ∣ ψ ⟩ ⟼ α ∣0 ⟩ + β ∣1 ⟩
α \alpha α β \beta β an arbitrary state can be represented as a linear combination of basis states spin 自旋
prototypical way to implement quantum bits of information, or qubits clockwise/anticlockwise transition amplitude 转移振幅
inner product determine how likely a start state will change to an end state (after measurement) entanglement 纠缠
connect two qubits using a gate Bell state
量子比特间的强纠缠关系 ∣ Φ + ⟩ = ∣ 00 ⟩ + ∣ 11 ⟩ 2 |\Phi^+\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}} ∣ Φ + ⟩ = 2 ∣00 ⟩ + ∣11 ⟩ 两个量子比特要么都在状态 ∣ 0 ⟩ |0\rangle ∣0 ⟩ ∣ 1 ⟩ |1\rangle ∣1 ⟩ 最大纠缠态，两个量子比特的状态之间没有相位差，量子态无法分解成两个量子态的直积 ∣ Φ − ⟩ = ∣ 00 ⟩ − ∣ 11 ⟩ 2 |\Phi^-\rangle = \frac{|00\rangle - |11\rangle}{\sqrt{2}} ∣ Φ − ⟩ = 2 ∣00 ⟩ − ∣11 ⟩ ∣ Ψ + ⟩ = ∣ 01 ⟩ + ∣ 10 ⟩ 2 |\Psi^+\rangle = \frac{|01\rangle + |10\rangle}{\sqrt{2}} ∣ Ψ + ⟩ = 2 ∣01 ⟩ + ∣10 ⟩ ∣ Ψ − ⟩ = ∣ 01 ⟩ − ∣ 10 ⟩ 2 |\Psi^-\rangle = \frac{|01\rangle - |10\rangle}{\sqrt{2}} ∣ Ψ − ⟩ = 2 ∣01 ⟩ − ∣10 ⟩ qubit pair: ∣ 0 ⟩ ⨂ ∣ 1 ⟩ |0\rangle \bigotimes |1\rangle ∣0 ⟩ ⨂ ∣1 ⟩ ∣ 0 ⨂ 1 ⟩ |0 \bigotimes 1\rangle ∣0 ⨂ 1 ⟩
00 01 10 11 [ 0 1 0 0 ] \begin{array}{cc} \begin{array}{c} 00 \\ 01 \\ 10 \\ 11\end{array} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} \end{array} 00 01 10 11 0 1 0 0 classical gates
NOT: filp 0 to 1, 1 to 0 [ 0 1 1 0 ] \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} [ 0 1 1 0 ] AND: 1 if both are 1 [ 1 1 1 0 0 0 0 1 ] \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} [ 1 0 1 0 1 0 0 1 ] OR: 1 if either is 1 [ 1 0 0 0 0 1 1 1 ] \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix} [ 1 0 0 1 0 1 0 1 ] NAND: 0 if both are 1 NOT ⋆ \star ⋆ [ 0 1 1 0 ] [ 1 1 1 0 0 0 0 1 ] = [ 0 0 0 1 1 1 1 0 ] \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} [ 0 1 1 0 ] [ 1 0 1 0 1 0 0 1 ] = [ 0 1 0 1 0 1 1 0 ] XOR: 1 if either is 1, but not both NOT ⋆ \star ⋆ [ 0 1 1 0 ] [ 1 0 0 0 0 1 1 1 ] = [ 0 1 1 1 1 0 0 0 ] \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} [ 0 1 1 0 ] [ 1 0 0 1 0 1 0 1 ] = [ 0 1 1 0 1 0 1 0 ] Jyā, koti-jyā and utkrama-jyā 印度的三角函数
bloch sphere 布洛赫球: 用于表示量子比特状态的几何图形
X, Y axis: 0 ≤ θ ≤ 2 π 0 \leq \theta \leq 2\pi 0 ≤ θ ≤ 2 π Z axis: 0 ≤ ϕ ≤ π 2 0 \leq \phi \leq \frac{\pi}{2} 0 ≤ ϕ ≤ 2 π Pauli X,Y,Z
X = [ 0 1 1 0 ] X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} X = [ 0 1 1 0 ] 沿 X 轴旋转 180 度 X is also called NOT gate eigenvalues: 1 and -1 eigenvectors: left ∣ ⟵ ⟩ = ψ x + = ∣ 0 ⟩ + ∣ 1 ⟩ 2 |\longleftarrow\rangle = \psi_{x+} = \frac{|0\rangle + |1\rangle}{\sqrt{2}} ∣ ⟵ ⟩ = ψ x + = 2 ∣0 ⟩ + ∣1 ⟩ right ∣ ⟶ ⟩ = ψ x − = ∣ 0 ⟩ − ∣ 1 ⟩ 2 |\longrightarrow\rangle = \psi_{x-} = \frac{|0\rangle - |1\rangle}{\sqrt{2}} ∣ ⟶ ⟩ = ψ x − = 2 ∣0 ⟩ − ∣1 ⟩ Y = [ 0 − i i 0 ] Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} Y = [ 0 i − i 0 ] 沿 Y 轴旋转 180 度 Y is also called bit-flip gate 从∣ 0 ⟩ |0\rangle ∣0 ⟩ ∣ 1 ⟩ |1\rangle ∣1 ⟩ ∣ 1 ⟩ |1\rangle ∣1 ⟩ ∣ 0 ⟩ |0\rangle ∣0 ⟩ eigenvalues: 1 and -1 eigenvectors: in ∣ ↙ ⟩ = ψ y + = ∣ 0 ⟩ + i ∣ 1 ⟩ 2 |\swarrow\rangle = \psi_{y+} = \frac{|0\rangle + i|1\rangle}{\sqrt{2}} ∣ ↙ ⟩ = ψ y + = 2 ∣0 ⟩ + i ∣1 ⟩ out ∣ ↗ ⟩ = ψ y − = ∣ 0 ⟩ − i ∣ 1 ⟩ 2 |\nearrow\rangle = \psi_{y-} = \frac{|0\rangle - i|1\rangle}{\sqrt{2}} ∣ ↗ ⟩ = ψ y − = 2 ∣0 ⟩ − i ∣1 ⟩ Z = [ 1 0 0 − 1 ] Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} Z = [ 1 0 0 − 1 ] 沿 Z 轴旋转 180 度 Z is also called phase-flip gate 从∣ 1 ⟩ |1\rangle ∣1 ⟩ − ∣ 1 ⟩ -|1\rangle − ∣1 ⟩ eigenvalues: 1 and -1 eigenvectors: up ∣ ↑ ⟩ = ψ z + = ∣ 0 ⟩ |\uparrow\rangle = \psi_{z+} = |0\rangle ∣ ↑ ⟩ = ψ z + = ∣0 ⟩ down ∣ ↓ ⟩ = ψ z − = ∣ 1 ⟩ |\downarrow\rangle = \psi_{z-} = |1\rangle ∣ ↓ ⟩ = ψ z − = ∣1 ⟩ phase shift gate:
R ( θ ) = [ 1 0 0 e θ ] R(\theta) = \begin{bmatrix} 1 & 0 \\ 0 & e^{\theta} \end{bmatrix} R ( θ ) = [ 1 0 0 e θ ] R x ( θ ) = [ cos ( θ 2 ) − i sin ( θ 2 ) − i sin ( θ 2 ) cos ( θ 2 ) ] R_x(\theta) = \begin{bmatrix} \cos(\frac{\theta}{2}) & -i\sin(\frac{\theta}{2}) \\ -i\sin(\frac{\theta}{2}) & \cos(\frac{\theta}{2}) \end{bmatrix} R x ( θ ) = [ cos ( 2 θ ) − i sin ( 2 θ ) − i sin ( 2 θ ) cos ( 2 θ ) ] R y ( θ ) = [ cos ( θ 2 ) − sin ( θ 2 ) sin ( θ 2 ) cos ( θ 2 ) ] R_y(\theta) = \begin{bmatrix} \cos(\frac{\theta}{2}) & -\sin(\frac{\theta}{2}) \\ \sin(\frac{\theta}{2}) & \cos(\frac{\theta}{2}) \end{bmatrix} R y ( θ ) = [ cos ( 2 θ ) sin ( 2 θ ) − sin ( 2 θ ) cos ( 2 θ ) ] R z ( θ ) = [ e − i θ 2 0 0 e i θ 2 ] R_z(\theta) = \begin{bmatrix} e^{-i\frac{\theta}{2}} & 0 \\ 0 & e^{i\frac{\theta}{2}} \end{bmatrix} R z ( θ ) = [ e − i 2 θ 0 0 e i 2 θ ] S: 添加一个 π 2 \frac{\pi}{2} 2 π
S = [ 1 0 0 i ] S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix} S = [ 1 0 0 i ] T: 添加一个 π 4 \frac{\pi}{4} 4 π
T = [ 1 0 0 e i π 4 ] T = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\frac{\pi}{4}} \end{bmatrix} T = [ 1 0 0 e i 4 π ] Hadamard gate
制备叠加态 H = 1 2 [ 1 1 1 − 1 ] H = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} H = 2 1 [ 1 1 1 − 1 ] CNOT
control qubit, target qubit if control qubit is 1, then target qubit is flipped ∣ 00 ⟩ ⟼ ∣ 00 ⟩ |00\rangle \longmapsto |00\rangle ∣00 ⟩ ⟼ ∣00 ⟩ ∣ 01 ⟩ ⟼ ∣ 01 ⟩ |01\rangle \longmapsto |01\rangle ∣01 ⟩ ⟼ ∣01 ⟩ ∣ 10 ⟩ ⟼ ∣ 11 ⟩ |10\rangle \longmapsto |11\rangle ∣10 ⟩ ⟼ ∣11 ⟩ ∣ 11 ⟩ ⟼ ∣ 10 ⟩ |11\rangle \longmapsto |10\rangle ∣11 ⟩ ⟼ ∣10 ⟩ ∣ ψ ⟩ = α ∣ 00 ⟩ + β ∣ 01 ⟩ + γ ∣ 10 ⟩ + δ ∣ 11 ⟩ |\psi\rangle = \alpha|00\rangle + \beta|01\rangle + \gamma|10\rangle + \delta|11\rangle ∣ ψ ⟩ = α ∣00 ⟩ + β ∣01 ⟩ + γ ∣10 ⟩ + δ ∣11 ⟩ C N O T = [ 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ] CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} CNOT = 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ∣ ψ ′ ⟩ = C N O T ⋅ ∣ ψ ⟩ = [ 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ] [ α β γ δ ] = [ α β δ γ ] |\psi'\rangle = CNOT \cdot |\psi\rangle = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} \alpha \ \beta \ \gamma \ \delta \end{bmatrix} = \begin{bmatrix} \alpha \ \beta \ \delta \ \gamma \end{bmatrix} ∣ ψ ′ ⟩ = CNOT ⋅ ∣ ψ ⟩ = 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 [ α β γ δ ] = [ α β δ γ ] ∣ ψ ′ ⟩ = α ∣ 00 ⟩ + β ∣ 01 ⟩ + δ ∣ 10 ⟩ + γ ∣ 11 ⟩ |\psi'\rangle = \alpha|00\rangle + \beta|01\rangle + \delta|10\rangle + \gamma|11\rangle ∣ ψ ′ ⟩ = α ∣00 ⟩ + β ∣01 ⟩ + δ ∣10 ⟩ + γ ∣11 ⟩ control-U gates
if control qubit is 1, then apply U on target qubit C U = [ I 0 0 U ] ^{C}{U} = \begin{bmatrix} I & 0 \\ 0 & U \end{bmatrix} C U = [ I 0 0 U ] Deutch gate:
if both control qubits are 1, then apply a phase shift on target Toffoli gate: 3 qubits, 2 control and 1 target
if both control qubits are 1, then the target qubit is flipped 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 [ 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 ] \begin{array}{} \ 000 \ 001 \ 010 \ 011 \ 100 \ 101 \ 110 \ 111 \\ \begin{array}{c} 000 \\ 001 \\ 010 \\ 011 \\ 100 \\ 101 \\ 110 \\ 111 \end{array} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} \end{array} 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 Fredkin gate: 3 qubits, 1 control and 2 target
if the control qubit is 1, then the target qubits are swapped 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 [ 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 ] \begin{array}{} \ 000 \ 001 \ 010 \ 011 \ 100 \ 101 \ 110 \ 111 \\ \begin{array}{c} 000 \\ 001 \\ 010 \\ 011 \\ 100 \\ 101 \\ 110 \\ 111 \end{array} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{array} 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 all Quantum gates are reversible
n Hadamand gates: H ⨂ n H^{\bigotimes n} H ⨂ n
∣ ψ ⟩ = 1 2 n ∑ i = 0 2 n − 1 ∣ i ⟩ |\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}|i\rangle ∣ ψ ⟩ = 2 n 1 ∑ i = 0 2 n − 1 ∣ i ⟩ reversible function execution:
control: ∣ x ⟩ |x\rangle ∣ x ⟩ U f U_f U f ∣ x ⟩ |x\rangle ∣ x ⟩ target: ∣ 0 ⟩ |0\rangle ∣0 ⟩ U f U_f U f ∣ f ( x ) ⟩ |f(x)\rangle ∣ f ( x )⟩ simple circuit
CNOT: dot + CZ: dot dot SWAP: xx unitary: box U no-cloning theorem: cannot copy an arbitrary unknown quantum state
证明：假设可以复制，那么可以通过两个相同的量子比特，得到一个新的固定的量子比特。但这是不可能的 teleportation
克隆是在不破坏原本的量子比特的情况下复制一个量子比特 传输是将一个量子比特的状态从一个量子比特传输到另一个量子比特，原本的量子态会被破坏 take ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ ∣ x ⟩ |x\rangle ∣ x ⟩ T ( ∣ ψ ⟩ ⨂ ∣ 0 ⟩ ) = ∣ ψ ⟩ ⨂ ∣ 0 ⟩ T(|\psi\rangle \bigotimes |0\rangle) = |\psi\rangle \bigotimes |0\rangle T ( ∣ ψ ⟩ ⨂ ∣0 ⟩) = ∣ ψ ⟩ ⨂ ∣0 ⟩ superdense coding
quantum parallelism: exponential numbers were inputted simultaneously, result was given in next clock, by quantum function
given a quantum representation, only one result can be given, not all solutions
the point is: what algorithm can take advantage of quantum mechanism?
quadratic unconstrained binary optimization 二次无约束二元优化 quantum mechanics can solve combinatorial optimization problems finding optimal objects that satisfy a certain condition Knapsack problem given a set of items, each with a weight and a value determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible n items x i x_i x i v i v_i v i W W W maximize ∑ i = 1 n v i x i \sum_{i=1}^{n} v_i x_i ∑ i = 1 n v i x i subject to ∑ i = 1 n w i x i ≤ W \sum_{i=1}^{n} w_i x_i \leq W ∑ i = 1 n w i x i ≤ W max-cut edges have weights find a cut that maximizes the sum of the weights of the edges that are cut minimum vetec cover find the minimum number of vertices that cover all edges simulated annealing 模拟退火 a probabilistic technique for approximating the global optimum of a given function local search (Monte Carlo) find solution from neighbors Metropolis algorithm reproduce annealing process E i E_i E i i i i if E i − E j > 0 E_i - E_j > 0 E i − E j > 0 j j j if E i − E j < 0 E_i - E_j < 0 E i − E j < 0 j j j e E i − E j K b T e^{\frac{E_i - E_j}{K_b T}} e K b T E i − E j quadratic unconstrained binary optimization (QUBO) m i n o r m a x ∑ i = 1 n ∑ j = 1 n q i j x i x j min \ or \ max \sum_{i=1}^{n} \sum_{j=1}^{n} q_{ij} x_i x_j min or ma x ∑ i = 1 n ∑ j = 1 n q ij x i x j subject to x i ∈ { 0 , 1 } x_i \in \{0, 1\} x i ∈ { 0 , 1 } Y = X T Q X Y = X^T Q X Y = X T QX Q is symmetric or upper triangular NP problem physical system generates optimal solution map optimization problem to physical system ... cool the system to zero ... obtain the lowest energy state an observable is represented by Hermitian matrix ... its eigenvalues are the measured values ... diagonalize the matrix and eigenvalues are the diagonal elements Adiabatic theorem if a system is in the ground state of a Hamiltonian, and the Hamiltonian is slowly changed, then the system will remain in the ground state quantum approximate optimization algorithm 量子近似优化算法 Ask GPT A gpt's explaination of QAOA:
量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是一种混合量子经典算法，用于解决组合优化问题。QAOA 结合了量子计算的并行性和经典优化的灵活性，旨在找到近似最优解。以下是 QAOA 的高层次解释：
QAOA 通过构造一个参数化的量子电路来近似求解组合优化问题。该算法的核心思想是通过调整参数，使得量子电路生成的量子态在测量后能够提供优化问题的近似最优解。
问题表示 ：
将组合优化问题表示为一个二次无约束二进制优化（QUBO）问题或等价的 Ising 模型。 目标是找到一个二进制向量 x \mathbf{x} x C ( x ) C(\mathbf{x}) C ( x ) 初始量子态 ：
准备一个初始量子态，通常是所有量子比特的均匀叠加态 ∣ + ⟩ ⊗ n |+\rangle^{\otimes n} ∣ + ⟩ ⊗ n n n n 参数化量子电路 ：
构造一个参数化的量子电路，该电路由两个交替应用的单元组成： 成本哈密顿量演化 ：应用与目标函数 C ( x ) C(\mathbf{x}) C ( x ) H C H_C H C 混合哈密顿量演化 ：应用混合哈密顿量 H M H_M H M 这些单元交替应用 p p p p p p γ i \gamma_i γ i β i \beta_i β i 量子态演化 ：
初始量子态通过参数化量子电路演化，生成一个新的量子态：∣ ψ ( γ , β ) ⟩ = U M ( β p ) U C ( γ p ) ⋯ U M ( β 1 ) U C ( γ 1 ) ∣ + ⟩ ⊗ n |\psi(\gamma, \beta)\rangle = U_M(\beta_p) U_C(\gamma_p) \cdots U_M(\beta_1) U_C(\gamma_1) |+\rangle^{\otimes n} ∣ ψ ( γ , β )⟩ = U M ( β p ) U C ( γ p ) ⋯ U M ( β 1 ) U C ( γ 1 ) ∣ + ⟩ ⊗ n
其中 U C ( γ i ) = e − i γ i H C U_C(\gamma_i) = e^{-i \gamma_i H_C} U C ( γ i ) = e − i γ i H C U M ( β i ) = e − i β i H M U_M(\beta_i) = e^{-i \beta_i H_M} U M ( β i ) = e − i β i H M 测量和优化 ：
对演化后的量子态进行测量，得到一个二进制向量 x \mathbf{x} x 计算目标函数 C ( x ) C(\mathbf{x}) C ( x ) 使用经典优化算法调整参数 γ \gamma γ β \beta β ⟨ ψ ( γ , β ) ∣ H C ∣ ψ ( γ , β ) ⟩ \langle \psi(\gamma, \beta) | H_C | \psi(\gamma, \beta) \rangle ⟨ ψ ( γ , β ) ∣ H C ∣ ψ ( γ , β )⟩ 迭代 ：
重复量子态演化、测量和参数优化的过程，直到找到近似最优解。 并行性 ：利用量子计算的并行性，可以同时探索多个解空间。灵活性 ：通过调整参数，可以适应不同的优化问题。近似最优解 ：即使在量子计算资源有限的情况下，QAOA 也能找到高质量的近似解。QAOA 可以应用于各种组合优化问题，包括但不限于：
最大割问题（Max-Cut） 旅行商问题（TSP） 图着色问题 集合覆盖问题 资源分配问题 Alice and Bob agree in advance a set with two different basis, say the z-basis or the x-basis Alice sends encoded qubits to Bob using random basis each time Bob measures these qubits using random basis A qubit sent and received correctly if the basis match. They use this fact to arrive at common correctly received bits But how do they discover correct matching? They can announce the basis after the process, they determine which positions of the key has same basis. How do they know Eve has not read? They can compare on a subset of qubits, if their recovered bits are same in all bits in the subset then can conclude that Eve was not there. They can use the rest of bits as a shared key. DFT (Discrete Fourier Transform) map vectors from time domain to frequency domain periodic function story of cryptography
operators: ⊕ \oplus ⊕ ⊗ \otimes ⊗
x ⊕ n y = ( x + y ) m o d n x \oplus_n y = (x + y) \mod n x ⊕ n y = ( x + y ) mod n x ⊗ n y = ( x y ) m o d n x \otimes_n y = (xy) \mod n x ⊗ n y = ( x y ) mod n modular inverse
if x ⊗ n y = 1 x \otimes_n y = 1 x ⊗ n y = 1 y y y x x x y y y x − 1 x^{-1} x − 1 Euler's totient function / Euler's phi function
a,b are relatively prime if gcd ( a , b ) = 1 \gcd(a, b) = 1 g cd( a , b ) = 1 ϕ ( n ) \phi(n) ϕ ( n ) reduced set of residues is a set that contains all numbers less than n that are relatively prime to n ϕ ( p ) = p − 1 \phi(p) = p - 1 ϕ ( p ) = p − 1 ϕ ( p q ) = ( p − 1 ) ( q − 1 ) \phi(pq) = (p - 1)(q - 1) ϕ ( pq ) = ( p − 1 ) ( q − 1 ) RSA PKC
Ron Rivest, Adi Shamir, Leonard Adleman public key cryptography utilize modular exponentiation parameter set K = ( n , p , q , e , d ) K = (n, p, q, e, d) K = ( n , p , q , e , d ) n = p q n = pq n = pq p p p q q q e ∈ ( 1 , ϕ ( n ) ) e \in (1, \phi(n)) e ∈ ( 1 , ϕ ( n )) e d ≡ 1 m o d ϕ ( n ) ed \equiv 1 \mod \phi(n) e d ≡ 1 mod ϕ ( n ) ϕ ( n ) \phi(n) ϕ ( n ) ≡ \equiv ≡ public: ( n , e ) (n, e) ( n , e ) Alice: E k ( x ) = x e m o d n E_k(x) = x^e \mod n E k ( x ) = x e mod n Bob: D k ( y ) = y d m o d n D_k(y) = y^d \mod n D k ( y ) = y d mod n ( x e ) d m o d n = x (x^e)^d \mod n = x ( x e ) d mod n = x 证明如果 e d ≡ 1 m o d ϕ ( n ) ed \equiv 1 \mod \phi(n) e d ≡ 1 mod ϕ ( n ) x e d m o d n = x x^{ed} \mod n = x x e d mod n = x e d = k ϕ ( n ) + 1 ed = k\phi(n) + 1 e d = k ϕ ( n ) + 1 费马小定理/欧拉定理: 如果x,n互质，则x ϕ ( n ) ≡ 1 m o d n x^{\phi(n)} \equiv 1 \mod n x ϕ ( n ) ≡ 1 mod n 证明1: ∏ i = 1 p − 1 A i ≡ ∏ i = 1 p − 1 a A i m o d p \prod_{i=1}^{p-1} A_i \equiv \prod_{i=1}^{p-1} aA_i \mod p ∏ i = 1 p − 1 A i ≡ ∏ i = 1 p − 1 a A i mod p 证明2: a p − 1 = ( 1 + a − 1 ) p − 1 a^{p-1} = (1 + a - 1)^{p-1} a p − 1 = ( 1 + a − 1 ) p − 1 p p p period of modular exponentiation
f ( x ) = a x m o d N f(x) = a^x \mod N f ( x ) = a x mod N f ( x ) = f ( x + r ) f(x) = f(x + r) f ( x ) = f ( x + r ) f ( x ) = f ( x + r ) = f ( x + 2 r ) = ⋯ = f ( x + k r ) f(x) = f(x + r) = f(x + 2r) = \cdots = f(x + kr) f ( x ) = f ( x + r ) = f ( x + 2 r ) = ⋯ = f ( x + k r ) example: f 2 , 15 = 2 x m o d 15 f_{2,15} = 2^x \mod 15 f 2 , 15 = 2 x mod 15 bit needed to represent N N N
n ≥ log 2 N n \geq \log_2 N n ≥ log 2 N because 2 n ≥ N 2^n \geq N 2 n ≥ N Shor's algorithm
use quantum circuit to find period of big N let 0 m 0_m 0 m 0 n 0_n 0 n m = 2 n m = 2n m = 2 n n = log 2 N n = \log_2 N n = log 2 N input: ∣ ψ 0 ⟩ = ∣ 0 m 0 n ⟩ |\psi_0\rangle = |0_m0_n\rangle ∣ ψ 0 ⟩ = ∣ 0 m 0 n ⟩ pass through m Hadamard gates H ⨂ m H^{\bigotimes m} H ⨂ m ∣ ψ 1 ⟩ = 1 2 m ∑ x ∈ [ 0 , 1 ] m ∣ x , 0 n ⟩ |\psi_1\rangle = \frac{1}{\sqrt{2^m}}\sum_{x \in [0,1]^m}|x, 0_n\rangle ∣ ψ 1 ⟩ = 2 m 1 ∑ x ∈ [ 0 , 1 ] m ∣ x , 0 n ⟩ pass through unitary operator U f U_f U f ∣ ψ 2 ⟩ = 1 2 m ∑ x ∈ [ 0 , 1 ] m ∣ x , f a , N ( x ) ⟩ |\psi_2\rangle = \frac{1}{\sqrt{2^m}}\sum_{x \in [0,1]^m}|x, f_{a, N}(x)\rangle ∣ ψ 2 ⟩ = 2 m 1 ∑ x ∈ [ 0 , 1 ] m ∣ x , f a , N ( x )⟩ the bottom n qubits store the superposition of many states a x m o d N a^x \mod N a x mod N ∣ ψ 3 ⟩ = 1 ⌊ 2 m r ⌋ ∑ a x ≡ a x ˉ m o d N ∣ x , a x ˉ m o d N ⟩ |\psi_3\rangle = \frac{1}{\lfloor \frac{2^m}{r} \rfloor}\sum_{a^x \equiv a^{\bar{x}} \mod N}|x, a^{\bar{x}} \mod N\rangle ∣ ψ 3 ⟩ = ⌊ r 2 m ⌋ 1 ∑ a x ≡ a x ˉ mod N ∣ x , a x ˉ mod N ⟩ apply quantum Fourier transform (QFT) on the top m qubits to generate answer: r ...
