솔로베이-키타예프 정리

양자 정보와 계산에서 솔로베이-키태브 정리는 대략적으로 단일 큐비트 양자 게이트 집합이 SU(2)의 조밀한 부분 집합을 생성하면 해당 집합을 사용하여 상대적으로 짧은 게이트 시퀀스로 원하는 양자 게이트를 근사화할 수 있다고 말합니다. 이 정리는 양자 계산 분야에서 가장 중요한 결과 중 하나로 여겨지며 Robert M에 의해 처음 발표되었습니다. 1995년 솔로베이와 1997년 알렉세이 키타예프에 의해 독립적으로 증명되었습니다.^[1] 마이클 닐슨(Michael Nielsen)과 크리스토퍼 M. 도슨(Christopher M. Dawson)은 이 분야에서의 중요성에 주목했습니다.^[2]

이 정리의 결과는 $m$ ${\displaystyle m}$개의 상수 큐비트 게이트의 양자 회로가 원하는 유한 범용 게이트의 ${\displaystyle O^{}}$(${\displaystyle m^{}\log c}$⁡$(m$ / ε))${\displaystyle$ O(m$\$log ^{c}(m/\varepsilon)} ${\displaystyle \mathrm{게이트}}$의 양자${\displaystyle }회로$에 의해 ε ${\$displaystyle \varepsilon } 오류(연산자 노름)로 근사화될 수 있다는 것입니다.세트의^[3] 이에 비해 게이트 집합이 보편적이라는 것은 상수 큐비트 게이트가 길이에 제한이 없이 게이트 집합에서 유한 회로로 근사될 수 있다는 것을 의미할 뿐입니다. 따라서 솔로베이-키타예프 정리는 이 근사가 놀라울 정도로 효율적으로 만들어질 수 있음을 보여줌으로써 양자 컴퓨터가 양자 계산의 완전한 힘을 얻기 위해 유한한 수의 게이트만 구현하면 된다는 것을 정당화합니다.

진술

Let ${\displaystyle {\mathcal {G}}}$ be a finite set of elements in SU(2) containing its own inverses (so ${\displaystyle g\in {\mathcal {G}}}$ implies ${\displaystyle g^{-1}\in {\mathcal {G}}}$) and such that the group ${\displaystyle \langle {\mathcal {G}}\rangle }$ they 생성은 SU(2)에서 조밀합니다. 일부ε > 0 ${\displaystyle$ \$varepsilon$ 0}을(를) 고려합니다. 그런 다음 $상수$ c$${\$displaystyle$ c$}$가 존재하므로$,$ $임의$의 ${\displaystyle \mathrm{U}}$∈$SU$ (2) ${\displaystyle$U\에 대하여$\mathrm${SU} (2)에 대하여, 게이트 $S$- U$$‖ ≤$$ε$${\displaystyle \ S-U \ \ \leq \varepsilon }$$이 ${\displaystyle \mathrm{되도록}}$ $길이$ $log$ ${\displaystyle c^{}}$⁡$(1$ /$$‖))의 G {\$displaystyle$ ${\mathcal$ {$G}}$ ${\displaystyle \{\backslash }$displaystyle O$(\$log ^{${\displaystyle c}\}($1/\$varepsilon$${\displaystyle ))\}}$에서 ε$S$ - U$$display ≤ \ {\displaystyle \ S-U \ \ \ leq \varepsilon $}$ 가 ${\displaystyle \mathrm{됩니다}}$. 즉, ${\displaystyle S}$ ${\displaystyle$ $S$$}$은(는) $U{\displaystyle }$ ${\displaystyle$ U$}$을(를) 연산자 norm 오류로 근사합니다$$.^[2]

정량적 한계

$상수$ $c$ ${\displaystyle c}$는 임의의 고정 δ > 0 {\displaystyle \delta > $0$에${\displaystyle }$대해 3$$+ δ ${\displaystyle$3+\delta }로 만들 수 있습니다. 그러나 c = 1 {\displaystyle c=1}을 취할 수 있는 특정 게이트 세트가 있으므로 게이트 시퀀스의 길이가 일정 인자까지 촘촘해집니다.

증명 아이디어

솔로베이-키태브 정리의 증명은 ${\displaystyle U}$∈$SU$ ⁡(2) ${\displaystyle$U\in $\operatorname$ $\{$SU}(2)}에 점점 더 좋은 근사치를 제공하는 게이트 시퀀스를 재귀적으로 구성하여 진행됩니다. $U$ - 1 ε SU ⁡$($2) ${\displaystyle$U_{$n-1$}\$in$ \operatorname {SU$\}({\displaystyle 2)\}}$에 U$$- U - $1$‖ ≤$$‖$$n - $1${\$displaystyle$\U-U_{n-1}\leq \varepsilon _{n-1}}이 있다고 가정합니다. Our goal is to find a sequence of gates approximating ${\displaystyle UU_{n-1}^{-1}}$ to ${\displaystyle \varepsilon _{n}}$ error, for ${\displaystyle \varepsilon _{n}<\varepsilon _{n-1}}$. By concatenating this sequence of gates with ${\displaystyle U_{n-1}}$, ‖${\displaystyle U_{}}$-$U$ ‖ ≤ ε n {\$displaystyle$ \U-U_{n}\leq \varepsilon_{n}을 gates하는 게이트${\displaystyle {}_{}}$U {\$displaystyle$ U_{$n}$의 시퀀스가 나타납니다.

핵심 아이디어는 아이덴티티에 가까운 요소들의 교환기들이 "예상보다 더 나은" 근사화될 수 있다는 것입니다. Specifically, for ${\displaystyle V,W\in \operatorname {SU} (2)}$ satisfying ${\displaystyle \ V-I\ \leq \delta _{1}}$ and ${\displaystyle \ W-I\ \leq \delta _{1}}$ and approximations ${\displaystyle {\tilde {V}},$${\tilde {W}}\in \operatorname${${\displaystyle {}_{}}$$} (2)}$ ${\displaystyle 만족}$ $‖$${\displaystyle }$V${\displaystyle }$- V$$~ $‖$≤ $δ$$$2${\displaystyle$ \V-{\tilde {V}}\ \leq \delta _{2}} 및 $‖$ W - W ~ $δ$≤ $‖$ 2 {\displaystyle \W-{\tilde {W}\leq \delta _{2}, 그러면

${\displaystyle \ VWV^{-1}W^{-1}-{\tilde {V}}{\tilde {W}}{\tilde {V}}^{-1}{\tilde {W}}^{-1}\ \leq O(\delta _{1}\delta _{2}),}$

여기서 빅 O 표기법은 고차항을 숨깁니다. 위 식을 $($δ 2) ${\displaystyle O(\delta_$2})}로 순진하게 바인딩할 수 있지만 그룹 커뮤터 구조로 인해 상당한 오류 취소가 발생합니다.

저희는 그룹 정류기 ${\displaystyle U_{}^{}}$ n -${\displaystyle {}_1^{}}$- 1 = ${\displaystyle V_{}}$ ${\displaystyle n{}_{}}$- 1$$W n - ${\displaystyle 1_{}}$ W n - 1 W n - 1 W n - 1 {\display UU_{n-1}^{-1}=V_{n-1}W_{n-1}V_{n-1}^{-1}W_{n-1}^{-1}}로 근사화하고자 하는 식을 다시 작성하여 이 관측치를 사용합니다. ${\displaystyle {이렇게}_{}^{}}$ 하면 V${\displaystyle {\mathrm{n}}_{}^{}}$${\displaystyle {}_{}}$- 1 ${\displaystyle V_{n-1}}$ 및 ${\displaystyle W_{}}$- ${\displaystyle 1_{}}$ ${\displaystyle W_{n-1}}$가 모두 동일성에 가깝습니다$($‖ U n -${\displaystyle {}_{}^{}1}$ - ${\displaystyle I_{}}$ ‖ ≤ ε$$n -$1 {\displaystyle$ \$UU_${n-1$}^{-I\$leq \varepsilon _{n-1}}). $따라서$ V ${\displaystyle n_{}}$- ${\displaystyle 1_{}}$ ${\displaystyle V_{n-1}}$ 및 ${\displaystyle {\mathrm{W}}_{}}$- ${\displaystyle 1_{}}$ ${\displaystyle W_{n-1}}$에서$$ε n - 1${\$displaystyle$\varepsilon_${n-1}에 가까운 게이트 시퀀스를 재귀적으로 계산하면, ε$$ {\$displaystyle$ \varepsilon_{n$}^{-$1}에$$가까운 U ${\displaystyle {Un}_{}^{}}$ - 1${\displaystyle$ $UU_{$n-1$}^{-$1}에서 원하는${\displaystyle {}_{}^{}}$더 나은 정밀도 ε n {\displaystyle \$varepsilon_{$n}에 가까운 게이트 시퀀스를 얻습니다. 우리는 충분히 긴 모든 게이트 시퀀스를 단순한 계산으로 ${\displaystyle {일정}_{}}$한$$ε 0 ${\displaystyle \varepsilon_${0}으로 기본 케이스 근사치를 얻을 수 있습니다.

참고문헌