Fourier transformation 就是把群的正则表示进行直和分解
数学上，Fourier 变换是一个酉变换F : C G → ⨁ σ ∈ G ^ ( C dim σ ⊗ C dim σ ) F:\mathbb{C}G\to \bigoplus_{\sigma\in\hat{G}}(\mathbb{C}^{\dim\sigma}\otimes \mathbb{C}^{\dim\sigma}) F : C G → ⨁ σ ∈ G ^ ( C d i m σ ⊗ C d i m σ ) C G \mathbb{C}G C G
这个变换是保持维度的，因为根据 Burnside 引理，对于所有不等价、不可约的酉表示σ ∈ G ^ \sigma\in\hat{G} σ ∈ G ^
dim C G = ∣ G ∣ = ∑ σ ∈ G ^ dim σ 2 = dim ⨁ σ ∈ G ^ ( C dim σ ⊗ C dim σ ) . \dim \mathbb{C}G=|G|=\sum_{\sigma\in\hat{G}}\dim\sigma^2=\dim \bigoplus_{\sigma\in\hat{G}}(\mathbb{C}^{\dim\sigma}\otimes \mathbb{C}^{\dim\sigma}).
dim C G = ∣ G ∣ = σ ∈ G ^ ∑ dim σ 2 = dim σ ∈ G ^ ⨁ ( C d i m σ ⊗ C d i m σ ) .
具体地，对于每个x ∈ G x\in G x ∈ G ∣ x ⟩ ∈ C G |x\rangle\in\mathbb{C}G ∣ x ⟩ ∈ C G
F ∣ x ⟩ = ∣ x ^ ⟩ ≜ ∑ σ ∈ G ^ dim σ ∣ G ∣ ∣ σ , σ ( x ) ⟩ , F|x\rangle=|\hat{x}\rangle\triangleq\sum_{\sigma\in\hat{G}}\frac{\dim\sigma}{|G|}|\sigma,\sigma(x)\rangle,
F ∣ x ⟩ = ∣ x ^ ⟩ ≜ σ ∈ G ^ ∑ ∣ G ∣ dim σ ∣ σ , σ ( x ) ⟩ ,
其中∣ σ ⟩ |\sigma\rangle ∣ σ ⟩
∣ σ ( x ) ⟩ ≜ ∑ j , k = 1 dim σ σ ( x ) j , k dim σ ∣ j , k ⟩ ∈ C dim σ ⊗ C dim σ |\sigma(x)\rangle\triangleq\sum_{j,k=1}^{\dim\sigma}\frac{\sigma(x)_{j,k}}{\sqrt{\dim\sigma}}|j,k\rangle\in\mathbb{C}^{\dim\sigma}\otimes \mathbb{C}^{\dim\sigma}
∣ σ ( x ) ⟩ ≜ j , k = 1 ∑ d i m σ dim σ σ ( x ) j , k ∣ j , k ⟩ ∈ C d i m σ ⊗ C d i m σ
可以看作是酉矩阵σ ( x ) ∈ C dim σ × dim σ \sigma(x)\in\mathbb{C}^{\dim\sigma\times \dim\sigma} σ ( x ) ∈ C d i m σ × d i m σ
所以 Fourier 变换写为F = ∑ x ∈ G ∣ x ^ ⟩ ⟨ x ∣ F=\sum_{x\in G}|\hat{x}\rangle\langle x| F = ∑ x ∈ G ∣ x ^ ⟩ ⟨ x ∣
此外，还可以注意到，Fourier 变换实际上就是对群的正则表示的直积分解。考虑左正则表示L L L
∀ x , y ∈ G , L ( x ) ∣ y ⟩ = ∣ x y ⟩ . \forall x,y\in G,\quad L(x)|y\rangle=|xy\rangle.
∀ x , y ∈ G , L ( x ) ∣ y ⟩ = ∣ x y ⟩ .
那么根据群表示的正交性，
F L ( x ) F † = ∑ y ∈ G ∣ x y ^ ⟩ ⟨ y ^ ∣ = ∑ y ∈ G ∑ σ , σ ′ ∈ G ^ ∑ j , k = 1 dim σ ∑ j ′ , k ′ = 1 dim σ ′ dim σ dim σ ′ ∣ G ∣ σ ( x y ) j , k σ ′ ( y ) j ′ , k ′ ∣ σ , j , k ⟩ ⟨ σ ′ , j ′ , k ′ ∣ = ∑ y ∈ G ∑ σ , σ ′ ∈ G ^ ∑ j , k , l = 1 dim σ ∑ j ′ , k ′ = 1 dim σ ′ dim σ dim σ ′ ∣ G ∣ σ ( x ) j , l σ ( y ) l , k σ ′ ( y ) j ′ , k ′ ∣ σ , j , k ⟩ ⟨ σ ′ , j ′ , k ′ ∣ = ∑ σ ∈ σ ^ ∑ j , k , l = 1 dim σ σ ( x ) j , l ∣ σ , j , k ⟩ ⟨ σ , l , k ∣ = ⨁ σ ∈ G ^ ( σ ( x ) ⊗ I dim σ ) . \begin{aligned}
FL(x)F^\dagger &=\sum_{y\in G}|\hat{xy}\rangle\langle \hat{y}|\\
&=\sum_{y\in G}\sum_{\sigma,\sigma'\in\hat{G}}\sum_{j,k=1}^{\dim\sigma}\sum_{j',k'=1}^{\dim\sigma'}\frac{\sqrt{\dim\sigma \dim\sigma'}}{|G|}\sigma(xy)_{j,k}\sigma'(y)_{j',k'}|\sigma,j,k\rangle\langle \sigma',j',k'|\\
&=\sum_{y\in G}\sum_{\sigma,\sigma'\in\hat{G}}\sum_{j,k,l=1}^{\dim\sigma}\sum_{j',k'=1}^{\dim\sigma'}\frac{\sqrt{\dim\sigma \dim\sigma'}}{|G|}\sigma(x)_{j,l}\sigma(y)_{l,k}\sigma'(y)_{j',k'}|\sigma,j,k\rangle\langle \sigma',j',k'|\\
&=\sum_{\sigma\in\hat{\sigma}}\sum_{j,k,l=1}^{\dim\sigma}\sigma(x)_{j,l}|\sigma,j,k\rangle\langle\sigma,l,k|\\
&=\bigoplus_{\sigma\in\hat{G}}\big ( \sigma(x) \otimes I_{\dim\sigma}\big ).
\end{aligned}
F L ( x ) F † = y ∈ G ∑ ∣ x y ^ ⟩ ⟨ y ^ ∣ = y ∈ G ∑ σ , σ ′ ∈ G ^ ∑ j , k = 1 ∑ d i m σ j ′ , k ′ = 1 ∑ d i m σ ′ ∣ G ∣ dim σ dim σ ′ σ ( x y ) j , k σ ′ ( y ) j ′ , k ′ ∣ σ , j , k ⟩ ⟨ σ ′ , j ′ , k ′ ∣ = y ∈ G ∑ σ , σ ′ ∈ G ^ ∑ j , k , l = 1 ∑ d i m σ j ′ , k ′ = 1 ∑ d i m σ ′ ∣ G ∣ dim σ dim σ ′ σ ( x ) j , l σ ( y ) l , k σ ′ ( y ) j ′ , k ′ ∣ σ , j , k ⟩ ⟨ σ ′ , j ′ , k ′ ∣ = σ ∈ σ ^ ∑ j , k , l = 1 ∑ d i m σ σ ( x ) j , l ∣ σ , j , k ⟩ ⟨ σ , l , k ∣ = σ ∈ G ^ ⨁ ( σ ( x ) ⊗ I d i m σ ) .
类似地，有F R ( x ) F † = ⨁ σ ∈ G ^ ( I dim σ ⊗ σ ( x ) † ) FR(x)F^\dagger=\bigoplus_{\sigma\in\hat{G}}\big ( I_{\dim\sigma}\otimes \sigma(x)^\dagger\big ) F R ( x ) F † = ⨁ σ ∈ G ^ ( I d i m σ ⊗ σ ( x ) † ) R ( x ) = ∑ y ∈ G ∣ y x ⟩ ⟨ y ∣ R(x)=\sum_{y\in G}|yx\rangle\langle y| R ( x ) = ∑ y ∈ G ∣ y x ⟩ ⟨ y ∣
实际上，metacyclic 群（循环群半直积得到的群）的 Fourier 变换都可以被量子线路高效地实现，譬如 dihedral 群和 symmetric 群。但是譬如G L GL G L
# Fourier Sampling我们先考虑 hidden subgroup problem，考虑一个子群H ≤ G H\leq G H ≤ G f : G → X f:G\to X f : G → X
∀ x , y ∈ G , f ( x ) = f ( y ) ⟺ x H = y H ⟺ y − 1 x ∈ H . \forall x,y\in G,\ f(x)=f(y)\iff xH=yH\iff y^{-1}x\in H.
∀ x , y ∈ G , f ( x ) = f ( y ) ⟺ x H = y H ⟺ y − 1 x ∈ H .
然后有一个 oracle O ∣ x , y ⟩ = ∣ x ⟩ ∣ x , y ⊕ f ( x ) ⟩ O|x,y\rangle=|x\rangle|x,y\oplus f(x)\rangle O ∣ x , y ⟩ = ∣ x ⟩ ∣ x , y ⊕ f ( x ) ⟩
1 ∣ G ∣ ∑ x ∈ G ∣ x ⟩ ∣ f ( x ) ⟩ , \frac{1}{|G|}\sum_{x\in G}|x\rangle|f(x)\rangle,
∣ G ∣ 1 x ∈ G ∑ ∣ x ⟩ ∣ f ( x ) ⟩ ,
在测量第二个寄存器后，会等概率 (g ∈ G g\in G g ∈ G
∣ g H ⟩ = 1 ∣ H ∣ ∑ h ∈ H ∣ g h ⟩ , |gH\rangle=\frac{1}{\sqrt{|H|}}\sum_{h\in H}|gh\rangle,
∣ g H ⟩ = ∣ H ∣ 1 h ∈ H ∑ ∣ g h ⟩ ,
丢掉测量结果，即得到一个混合态
ρ H = 1 ∣ G ∣ ∑ g ∈ G ∣ g H ⟩ ⟨ g H ∣ = 1 ∣ G ∣ ⋅ ∣ H ∣ ∑ g ∈ G ∑ h , h ′ ∈ H ∣ g h ⟩ ⟨ g h ′ ∣ = 1 ∣ G ∣ ⋅ ∣ H ∣ ∑ g ∈ G ∑ h , h ′ ∈ H R ( h ) ∣ g ⟩ ⟨ g ∣ R ( h ′ ) † = 1 ∣ G ∣ ⋅ ∣ H ∣ ∑ h , h ′ ∈ H R ( h ) R ( h ′ ) † = 1 ∣ G ∣ ⋅ ∣ H ∣ ∑ h , h ′ ∈ H R ( h h ′ − 1 ) = 1 ∣ G ∣ ∑ h ∈ H R ( h ) . \begin{aligned}
\rho_H&=\frac{1}{|G|}\sum_{g\in G}|gH\rangle\langle gH|\\
&=\frac{1}{|G|\cdot|H|}\sum_{g\in G}\sum_{h,h'\in H}|gh\rangle\langle gh'|\\
&=\frac{1}{|G|\cdot|H|}\sum_{g\in G}\sum_{h,h'\in H}R(h)|g\rangle\langle g|R(h')^\dagger\\
&=\frac{1}{|G|\cdot|H|}\sum_{h,h'\in H}R(h)R(h')^\dagger\\
&=\frac{1}{|G|\cdot|H|}\sum_{h,h'\in H}R(hh'^{-1})\\
&=\frac{1}{|G|}\sum_{h\in H}R(h).\\
\end{aligned}
ρ H = ∣ G ∣ 1 g ∈ G ∑ ∣ g H ⟩ ⟨ g H ∣ = ∣ G ∣ ⋅ ∣ H ∣ 1 g ∈ G ∑ h , h ′ ∈ H ∑ ∣ g h ⟩ ⟨ g h ′ ∣ = ∣ G ∣ ⋅ ∣ H ∣ 1 g ∈ G ∑ h , h ′ ∈ H ∑ R ( h ) ∣ g ⟩ ⟨ g ∣ R ( h ′ ) † = ∣ G ∣ ⋅ ∣ H ∣ 1 h , h ′ ∈ H ∑ R ( h ) R ( h ′ ) † = ∣ G ∣ ⋅ ∣ H ∣ 1 h , h ′ ∈ H ∑ R ( h h ′ − 1 ) = ∣ G ∣ 1 h ∈ H ∑ R ( h ) .
那么根据先前的推理，可以知道
ρ ^ H ≜ F G ρ H F G † = 1 ∣ G ∣ ⨁ σ ∈ G ^ ( I dim σ ⊗ σ ( H ) † ) , \hat{\rho}_H\triangleq F_G\rho_H F_G^\dagger =\frac{1}{|G|}\bigoplus_{\sigma\in\hat{G}}\left (I_{\dim\sigma}\otimes \sigma(H)^\dagger\right ),
ρ ^ H ≜ F G ρ H F G † = ∣ G ∣ 1 σ ∈ G ^ ⨁ ( I d i m σ ⊗ σ ( H ) † ) ,
其中，σ ( H ) = ∑ h ∈ H σ ( h ) \sigma(H)=\sum_{h\in H}\sigma(h) σ ( H ) = ∑ h ∈ H σ ( h )
因此ρ ^ H \hat{\rho}_H ρ ^ H σ \sigma σ σ ( H ) † \sigma(H)^\dagger σ ( H ) †
因此如果我们可以在不可约表示基下进行测量，就会有得到σ ∈ G ^ \sigma\in\hat{G} σ ∈ G ^
Pr ( σ ) = 1 ∣ G ∣ t r ( I dim σ ⊗ σ ( H ) † ) = dim σ ∣ G ∣ ∑ h ∈ H χ σ ( h ) ∗ = dim σ ⋅ ∣ H ∣ ∣ G ∣ ( χ σ , χ 1 ) , \Pr(\sigma)=\frac{1}{|G|}tr\left (I_{\dim\sigma}\otimes\sigma(H)^\dagger\right )=\frac{\dim\sigma}{|G|}\sum_{h\in H}\chi_\sigma(h)^*=\frac{\dim\sigma\cdot |H|}{|G|}(\chi_\sigma,\chi_1),
Pr ( σ ) = ∣ G ∣ 1 t r ( I d i m σ ⊗ σ ( H ) † ) = ∣ G ∣ dim σ h ∈ H ∑ χ σ ( h ) ∗ = ∣ G ∣ dim σ ⋅ ∣ H ∣ ( χ σ , χ 1 ) ,
其中( χ σ , χ 1 ) (\chi_\sigma,\chi_1) ( χ σ , χ 1 ) H H H χ 1 \chi_1 χ 1
这个过程和测量被称为 weak Fourier sampling，接下来我们考虑它怎么用来 reveal 一些子群H H H
如果G G G ρ H \rho_H ρ H
如果H H H σ ( H ) = λ I \sigma(H)=\lambda I σ ( H ) = λ I g ∈ G g\in G g ∈ G g H g − 1 = H gHg^{-1}=H g H g − 1 = H
σ ( H ) = 1 ∣ G ∣ ∑ g ∈ G , h ∈ H σ ( g h g − 1 ) , \sigma(H)=\frac{1}{|G|}\sum_{g\in G,h\in H}\sigma(ghg^{-1}),
σ ( H ) = ∣ G ∣ 1 g ∈ G , h ∈ H ∑ σ ( g h g − 1 ) ,
可以验证这个算子和σ ( g ) , g ∈ G \sigma(g),g\in G σ ( g ) , g ∈ G σ ( H ) = λ I \sigma(H)=\lambda I σ ( H ) = λ I ρ ^ H \hat{\rho}_H ρ ^ H λ I \lambda I λ I
这可以看作是 Abelian 群的一个推广。Abelian 群的表示都是 1 维的数字，而正规子群的表示都是λ I \lambda I λ I
此时 weak Fourier sampling 的测量概率如下：
Pr ( σ ) = { dim σ 2 ⋅ ∣ H ∣ / ∣ G ∣ , if H ≤ ker σ , 0 otherwise. \Pr(\sigma)=\begin{cases}
\dim\sigma^2\cdot |H|/|G|, & \text{if } H\leq \ker\sigma,\\
0 & \text{otherwise.}
\end{cases}
Pr ( σ ) = { dim σ 2 ⋅ ∣ H ∣ / ∣ G ∣ , 0 if H ≤ ker σ , otherwise.
因为如果H ≤ ker σ H\cancel\leq \ker\sigma H ≤ ker σ h ′ ∈ H h'\in H h ′ ∈ H σ ( h ′ ) ≠ I \sigma(h')\neq I σ ( h ′ ) = I
σ ( h ′ ) ∑ h ∈ H σ ( h ) = ∑ h ∈ H σ ( h ) , \sigma(h')\sum_{h\in H}\sigma(h)=\sum_{h\in H}\sigma(h),
σ ( h ′ ) h ∈ H ∑ σ ( h ) = h ∈ H ∑ σ ( h ) ,
又因为σ ( h ′ ) \sigma(h') σ ( h ′ ) σ ( H ) = λ I \sigma(H)=\lambda I σ ( H ) = λ I σ ( H ) = 0 \sigma(H)=\mathbf{0} σ ( H ) = 0 H ≤ ker σ H\leq \ker\sigma H ≤ ker σ ∀ h ∈ H , χ ( h ) = dim σ \forall h\in H,\ \chi(h)=\dim\sigma ∀ h ∈ H , χ ( h ) = dim σ
怎么得到H H H O ( log ∣ G ∣ ) O(\log |G|) O ( log ∣ G ∣ ) σ ∈ G ^ \sigma\in\hat{G} σ ∈ G ^ H H H
假设测量了若干次后，求交得到了一个子群K ⊴ G K\unlhd G K ⊴ G H ≠ K H\neq K H = K H < K ⊴ G H<K\unlhd G H < K ⊴ G σ \sigma σ K ≤ ker σ K\leq \ker\sigma K ≤ ker σ
∣ H ∣ ∣ G ∣ ∑ σ : K ≤ ker σ dim σ 2 = ∣ H ∣ ∣ K ∣ ≤ 1 2 , \frac{|H|}{|G|}\sum_{\sigma:K\leq\ker\sigma}\dim\sigma^2=\frac{|H|}{|K|}\leq\frac{1}{2},
∣ G ∣ ∣ H ∣ σ : K ≤ k e r σ ∑ dim σ 2 = ∣ K ∣ ∣ H ∣ ≤ 2 1 ,
这里的等号是因为，把之前的Pr ( σ ) \Pr(\sigma) Pr ( σ ) H H H K K K
1 = ∑ σ ∈ G ^ Pr ( σ ) = ∑ σ : K ≤ ker σ dim σ 2 ⋅ ∣ K ∣ ∣ G ∣ . 1=\sum_{\sigma\in\hat{G}}\Pr(\sigma)=\sum_{\sigma:K\leq\ker\sigma}\frac{\dim\sigma^2\cdot |K|}{|G|}.
1 = σ ∈ G ^ ∑ Pr ( σ ) = σ : K ≤ k e r σ ∑ ∣ G ∣ dim σ 2 ⋅ ∣ K ∣ .
而∣ H ∣ / ∣ K ∣ ≤ 1 / 2 |H|/|K|\leq 1/2 ∣ H ∣ / ∣ K ∣ ≤ 1 / 2
因此我们可以总结：
只需要进行O ( log ∣ G ∣ ) O(\log |G|) O ( log ∣ G ∣ )
# Strong Fourier Sampling回顾之前在做完 Fourier 变换的状态ρ ^ H \hat{\rho}_H ρ ^ H σ ∈ G ^ \sigma\in\hat{G} σ ∈ G ^
ρ ^ H , σ = σ ( H ) † ∑ h ∈ H χ σ ( h ) ∗ . \hat{\rho}_{H,\sigma}=\frac{\sigma(H)^\dagger}{\sum_{h\in H}\chi_\sigma(h)^*}.
ρ ^ H , σ = ∑ h ∈ H χ σ ( h ) ∗ σ ( H ) † .
实际上这个状态和投影算子只差一个系数。注意到
σ ( H ) 2 = ∑ h , h ′ σ ( h h ′ ) = ∣ H ∣ σ ( H ) , \sigma(H)^2=\sum_{h,h'}\sigma(hh')=|H|\sigma(H),
σ ( H ) 2 = h , h ′ ∑ σ ( h h ′ ) = ∣ H ∣ σ ( H ) ,
因此
ρ ^ H , σ 2 = ∣ H ∣ ∑ h ∈ H χ σ ( h ) ∗ ρ ^ H , σ . \hat{\rho}_{H,\sigma}^2=\frac{|H|}{\sum_{h\in H}\chi_\sigma(h)^*}\hat{\rho}_{H,\sigma}.
ρ ^ H , σ 2 = ∑ h ∈ H χ σ ( h ) ∗ ∣ H ∣ ρ ^ H , σ .
所以∑ h ∈ H χ σ ( h ) ∗ ∣ H ∣ ρ ^ H , σ \frac{\sum_{h\in H}\chi_\sigma(h)^*}{|H|}\hat{\rho}_{H,\sigma} ∣ H ∣ ∑ h ∈ H χ σ ( h ) ∗ ρ ^ H , σ
r a n k ( ∑ h ∈ H χ σ ( h ) ∗ ∣ H ∣ ρ ^ H , σ ) = ∑ h ∈ H χ σ ( h ) ∗ ∣ H ∣ ⋅ t r ( ρ ^ H , σ ) = ∑ h ∈ H χ σ ( h ) ∗ ∣ H ∣ . rank\left (\frac{\sum_{h\in H}\chi_\sigma(h)^*}{|H|}\hat{\rho}_{H,\sigma}\right )=\frac{\sum_{h\in H}\chi_\sigma(h)^*}{|H|}\cdot tr(\hat{\rho}_{H,\sigma})=\frac{\sum_{h\in H}\chi_\sigma(h)^*}{|H|}.
r a n k ( ∣ H ∣ ∑ h ∈ H χ σ ( h ) ∗ ρ ^ H , σ ) = ∣ H ∣ ∑ h ∈ H χ σ ( h ) ∗ ⋅ t r ( ρ ^ H , σ ) = ∣ H ∣ ∑ h ∈ H χ σ ( h ) ∗ .
注意到经过 weak Fourier sampling 后，测量结果会得到一个不可约表示σ \sigma σ ρ ^ H , σ \hat{\rho}_{H,\sigma} ρ ^ H , σ dim σ \dim\sigma dim σ
但是这样的测量基往往是不好找的！C dim σ \mathbb{C}^{\dim\sigma} C d i m σ U ( C dim σ ) U(\mathbb{C}^{\dim\sigma}) U ( C d i m σ )
Random measurement bases, quantum state distinction and applications to the hid- den subgroup problem 这篇文章就说明了这样随机选取基可以成功得到子群H H H σ ∈ G ^ \sigma\in\hat{G} σ ∈ G ^ r a n k ( ρ ^ H , σ ) = p o l y ( log ∣ G ∣ ) rank(\hat{\rho}_{H,\sigma})=poly(\log|G|) r a n k ( ρ ^ H , σ ) = p o l y ( log ∣ G ∣ )
但是实际上，这样的均匀随机选取基往往是失败的，特别是在对称群情况。
