7. Algorithms with Superpolynomial Speed-up

Quantum Phase Estimation

---

• Hadamard Gate를 다시 한번 살펴봅시다

• $H|x\rangle={1 \over \sqrt{2}} \Sigma_{y∈{0,1}^n} (-1)^{xy}|y\rangle$

• $H^{⊗n}|x\rangle^{⊗n}={1 \over \sqrt{2^n}} \Sigma_{y∈{0,1}^n} (-1)^{xy}|y\rangle$

• 여기서 잘 보면, n-qubit H Gate는 x를 phases로 encoding 된 것을 decoding 하는 것을 볼 수 있습니다.

• $(-1)^{xy}$ 은 Phase의 특별한 형태입니다. 이 Phase 를 좀 더 보편화 하여 Complex Number 로 표현하면 다음과 같습니다.

  ${1 \over \sqrt{2^n}} \Sigma_{y∈[0,2^n-1]} e^{2\pi iwy}|y\rangle$

  • DFT Form 같죠? 이러한 State에서 적절한 parameter w 를 찾는 것이 Problem 이 되겠습니다.
  • 그리고 1-qubit Phase Rotation Gate $R_k$ 를 정의하겠습니다.

• $R_k = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{2\pi i \over 2^k} \end {bmatrix}$ $R_k^{-1} = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{-2\pi i \over 2^k} \end {bmatrix}$

QFT

---

• m 개의 qubit 에 대해서 Quantum Fourier Transform 하는 연산을 정의하겠습니다.

  $QFT_m : |x\rangle → {1 \over \sqrt{m}} \Sigma_{y∈[0,m-1]} e^{2\pi iy \over m}|y\rangle$

• 자 이제 시각적으로 Computational Basis와 Fourier Basis에서 어떻게 차이나는지 봅시다

• Computational Basis

• Fourier Basis

• Z 축을 중심으로 회전하는 것을 볼 수 있습니다.

• QFT를 하는 Unitary Matrix는 다음과 같습니다

  

• n-qubit QFT를 실행하는 회로는 다음과 같습니다 끝단에서 SWAP을 합니다.

• 성능 m in [1,n] 일 때,
  • m-th qubit에 적용되는 gate의 개수 : H gate 1개 + Rot Gate (N-1)개 ⇒ 총 ${n(n+1) \over 2}$ 개의 Gate가 필요하다
  • SWAP Gate = CNOT Gate 3개
  • 총 게이트 수 = ${n(n+1) \over 2} + {3n \over 2} = {n^2 + 4n \over 2}$ ⇒ 따라서 QFT는 $O(n^2)$ 의 시간 복잡도를 가진다 이는 Classcial Algorithm인 FFT의 $O(n2^n)$ 보다 빠르다

[예제] 3-qubit QFT

$S=R_2 = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{2\pi i \over 2^2} \end {bmatrix}$ , $T=R_3 = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{2\pi i \over 2^3} \end {bmatrix}$ QFT Matrix는 다음과 같다.

Phase Shift Gates

---

• $R_\phi = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i\phi} \end {bmatrix}$

• $Z= \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i\pi} \end {bmatrix}$

• $S = \sqrt Z= \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i{\pi \over 2}} \end {bmatrix}$

• $T = \; ^4\sqrt Z = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i{\pi \over 4}} \end {bmatrix}$

EigenValue Estimation Problem

---

$c-U \;or\; U_f |1\rangle|\psi\rangle=e^{2\pi i \omega}|1\rangle|\psi\rangle$

Order-Finding Problem (Quantum Fatoring Algorithm, Period Finding )

---

---

• 1994년 Peter Shor에 의해 발견되었습니다.

• Classical Computer 에서는 Order-finding Problem을 다항시간 $O(logN)^k)$ 안에 풀수 없었습니다. 이 알고리즘은 추후에 Shor's Algorithm에 중요하게 이용됩니다.

💡

QFT (Quantum Fourier Transform) → QPE (Quantum Phase Estimation) → Order-Finding Problem → Shor's Algorithm

📌

QPE (Quantum Phase Estimation) : Unitary Operator 와 Eigenvector $|u\rangle$ 이 주어졌을 때, Eigenvalue $e^{2\pi \,i \phi}$ 를 찾는 것

Order-Finding Problem

• Order(위수) 의 정의 : GCD(x,N)=1 일 때, $x^r ≡1 (mod \;N)$ 을 만족하는 가장 작은 수 r

• x와 N 이 주어진 이 때, r을 찾는 문제이다.

▶ Order를 구하는게 왜 중요한가요 ? ⇒ 인수분해를 할 수 있습니다

$Pr(|{x\over 2n}-{k \over r}| ≤ {1 \over 2r^2}) ≥ C {1 \over r}$ 을 만족하는 x 를 찾을 수 있는가? (와 같은 말)

해결방법

1. Eigenvalue Estimation Approach (7.3.3)

   $U_a : |s\rangle → |sa \; mod \; N \rangle$ , gcd(a,n)=1 입니다. $2^m > N$ , r=ord(a)

   $U_a^r : |s\rangle → |sa^r \; mod \; N \rangle = |s\rangle$

   이제 어떤 것을 고민해보냐면, $|u_k\rangle = {1 \over \sqrt{r}} \Sigma_{s∈[0,r-1]} e^{-2\pi iks \over r}|a^s \; mod \; N\rangle$

   $u_a|u_k\rangle = {1 \over \sqrt{r}} \Sigma_{s∈[0,r-1]} e^{-2\pi iks \over r}u_a|a^s \; mod \; N\rangle$

   $u_a|u_k\rangle = {1 \over \sqrt{r}} \Sigma_{s∈[0,r-1]} e^{-2\pi iks \over r}|a^{s+1} \; mod \; N\rangle$

   $u_a|u_k\rangle = {1 \over \sqrt{r}} e^{2\pi ik \over r} \Sigma_{s∈[0,r-1]} e^{-2\pi ik(s+1) \over r}|a^{s+1} \; mod \; N\rangle$

   $u_a|u_k\rangle = {1 \over \sqrt{r}} e^{2\pi ik \over r} |u_k\rangle$

   자 그럼 이제 $e^{2\pi i k \over r}$이 EigenVector 가 되겠죠

   결과적으로 $|u_k\rangle$ 는 Eigenstate of Ua with eigenvalue $e^{2\pi i k \over r}$ 이죠

   그럼이제 $|0\rangle |u_k\rangle → |{k \over r}\rangle|u_k\rangle$ ( EEA : Eigenvalue Estimation Algorithm) 에 넣고 돌립니다.

   그러면 k/r 을 구할 수 있습니다. 근데 분해는 했는데 r 값을 알 수가 없어요.

   그래서 이제 뭘 계산할거냐면

   ${1 \over \sqrt{r}} \Sigma_{k∈[0,r-1]}|u_k\rangle = {1 \over \sqrt{r}} \Sigma_{k∈[0,r-1]}{1 \over \sqrt{r}} \Sigma_{s∈[0,r-1]} e^{-2\pi iks \over r}|a^s \; mod \; N\rangle$ 이고 , 이게 $|1\rangle$ 이 될 때는 $s≡0 \; mod \; r$ 일 때 밖에 없습니다.

   if s=0 , 일 떄 $e^{2\pi i k0 \over r} |1\rangle = |1\rangle$이죠. 그러면 ${1 \over \sqrt{r}} {1 \over \sqrt{r}} \Sigma_{k∈[0,r-1]} 1|1\rangle={1 \over {r}}|1\rangle$이 나옵니다.

   Amplitude of state $|1\rangle$가 1이라는 말은 무슨 말인면요, Uk의 Sub로 표현된다는 사실을 알 수 있어요. ${1 \over \sqrt{r}} \Sigma_{k∈[0,r-1]} |u_k\rangle=|1\rangle$. 별거 아닌거 같지만 되게 중요해요

   $|0\rangle|1\rangle={1 \over \sqrt{r}} \Sigma_{k∈[0,r-1]} |0\rangle|u_k\rangle → {1 \over \sqrt{r}} \Sigma_{k∈[0,r-1]}|{k \over r}\rangle|u_k\rangle$ ( EEA 에 넣고 돌립니다 ).

   그럼 이제 k/r 을 measure 해서, r 값의 estimation 을 알아 낼 수 있고, r 값을 알아 낼 수 있습니다.

   

   

   • 성능 Quantum Complexity : - Black-box : $O(log r)$ - Others : $O(n+log^2r)$

   Order-Finding Algorithm - Jay

   지난번에 알아본 QPE(quantum phase estimation)은 order finding 문제를 푸는데 이용될 수 있다. Order finding은 classical computer에서는 polynomial time(다항시간)에 풀리는 알고리듬이 없다. Quantum Fourier Transform(QFT)는 Quantum Phase Estimation(QPE) algorithm에 이용되고 QPE는 Order-Finding algorithm의 핵심개념이 된다. 다시 Order-Finding algorithm은 Shor's algorithm에 중요하게 이용된다. 즉 결론적으로 쇼어의 알고리듬(Shor's algorithm)을 이해하기 위해서는 앞으로 조금...

   https://leejaekyung.com/?p=1084

   

   https://www.d.umn.edu/~vvanchur/2015PHYS4071/Chapter5.pdf

   https://www.cl.cam.ac.uk/teaching/1213/QuantComp/lecture7.pdf

Shor's Algorithm

---

• 1994년 Peter Shor가 제안한 "소인수분해(Prime Factoring)을 Polynomial Time 내에 처리하는 알고리즘" 입니다.

💡

소인수분해 문제 $a^p=mN+1$ 이 있을 때, $(a^{p/2}+1)(a^{p/2}−1)=mN$ 로 표현 할 수 있습니다. "어떻게 하면 잘 p를 추측하는가" 입니다. 고전적으로는 시행착오로 선택되는 a를 계속 선택하고 곱해가면서 체크하는 수 밖에 없습니다. 양자역학적으로는 중첩을 만들 수 있습니다.

1.

2.

3.

4.

5.

⇒ 주기가 반복된다 정도만 알아들었다 ... ㅜㅜ..

그리고 Mod 집합 안에서는 주기 함수이다 ... → 즉, Fourier Transform이 가능하다

6.

⇒ 그리고 측정하면 주기를 확률로써 알 수 있다 정도만 알아들었다 ..ㅜㅜ

📢

쇼어의 알고리즘

STEP 1. gcd(x,N)=1 이고 x<N 인 Random Number x를 고른다

STEP 2. Order Finding 으로 r을 구한다.

STEP 3. n=[$log_2(N+1)$] 을 만족하는 n 을 구하고, n 수 만큼 Qubit 을 준비한다

• 1st Register : |00000....> : n 개

• 2nd Register : |111.......> : n 개

STEP 4. 1st Register에 $H^{⊗n}$ 를 적용한다

• $H^{⊗n}|x\rangle^{⊗n}={1 \over \sqrt{2^n}} \Sigma_{y∈{0,1}^n} (-1)^{xy}|y\rangle$

• $H^{⊗n}|0\rangle^{⊗n}={1 \over \sqrt{2^n}} \Sigma_{a∈{0,2^n-1}} |a\rangle$

STEP 5. 2nd Register에 Unitary 를 적용한다. 1st 에는 변화가 없고, 2nd 에만 결과가 저장된다

• ${1 \over \sqrt{2^n}} \Sigma_{a∈{0,2^n-1}} |a\rangle|f(a)\rangle$

• ${1 \over \sqrt{2^n}} \Sigma_{a∈{0,2^n-1}} |a\rangle|x^a \; mod \; N\rangle$

(아마 아래는 같은 말인거 같다)

$|\psi_0\rangle={1 \over \sqrt{2^n}} \Sigma_{x∈[0,2^n-1]}|x\rangle |a^x\,mod\,N\rangle ={1 \over \sqrt{2^n}} \Sigma_{b∈[0,r-1]} \Sigma_{z∈[0,mb-1]} |zr+b\rangle |a^x\,mod\,N\rangle$ 이 때, $(m_b-1)r+b ≤ 2^n-1$

STEP 6. 2nd Register를 Measure 합니다. 주기를 가진 함수이므로 collapse 됩니다

${1 \over \sqrt{m_b}} \Sigma_{z[0,mb-1]} |zr + b\rangle$

STEP 7. Inverse QFT에 넣는다 $c={2^n \over r} 의 \; 정수배인 \;k배$ 만 살아남는다

$\Sigma_{j[0,r-1]} e^{-2\pi i {b \over r} j} |m_bj\rangle$

STEP 8. 1st Register 측정 → r 을 estimation 하고 , r 을 구할 수 있다

Shor's factoring algorithm - Jay

Overview 쇼어의 알고리듬은 수학자 피터 쇼어(Peter Shor)가 1994년 제안한 "소인수분해(prime factoring)를 다항식 시간(polynomial time) 내에 빠르고 효율적으로 처리할 수 있는 양자알고리듬"이다. 고전 컴퓨터로는 큰 수의 인수분해를 다항식시간 내에 풀 수 있는 알고리듬이 없었지만 양자컴퓨터 위에서 쇼어의 알고리듬을 적용하면 빠른 계산이 가능하다는 것이다. 즉, 고전 알고리듬은 인수분해에 exponential time, 쇼어 알고리듬은...

https://leejaekyung.com/?p=1120

Discrete Logarithm Problem

---

• Input : $a=b^t \; mod \; N$

• Problem : Find t

• Proof
  • $U_a : |s\rangle → |sa \; mod \; N \rangle$ , $U_b : |s\rangle → |sb \; mod \; N \rangle$ , r=ord(b) (r is prime)
  • $|u_k\rangle = {1 \over \sqrt{r}} \Sigma_{s∈[0,r-1]} e^{-2\pi iks \over r}|a^s \; mod \; N\rangle$
  • $u_a|u_k\rangle = e^{2\pi ik \over r} |u_k\rangle$ , Eigenvalue
  • $u_b|u_k\rangle = e^{2\pi ikt \over r} |u_k\rangle$ , Eigenvalue , 여기에는 exp 위에 t가 있어요
  • E.E.A 를 하면 t 값을 알 수가 있죠.

Hidden Subgroup Problem

---

• f 함수가 g→ x 로 맵핑되고요.

• g의 서브 그룹인데, f(x)=f(y) 가 되요. 어떨때? x+s,y+s 가 같은 coset에 있을 떄

• 이럴 때 함수 값들이 같은 , 같은 서브그룹을 찾아봐라 하는 문제입니다.

• S={0}, if f is balanced

• S={0,1}, if f is constant

• f : G → X

• 찾고자 하는 것 f(x)=f(x+a)

• G=Z , X= any finite group a∈H

• f : Z → X

• r = ord(a)

• S= rZ 가 되는 r 을 찾아라 (r값을 알면 끝났죠)

• G = Zr x Zr

• X : Any group H

• a∈H , $a^r$=1 , $b=a^k$

• f(x1,x2)=$a^{x1}b^{x2}$

• f(x1,x2)=f(y1,y2)

• $a^{x1}b^{x2}$=$a^{y1}b^{y2}$

• (x1,x2)-(y1,y2)=(kt,-t)=t(k,-1)

• S-<k,-1> ⇒ k 값을 알 수 있다. (이산대수 문제를 푼다)

• G : Z x Z

• g : permutation of Zn

• h : Z x Z → Zn (x,y) → ay + r mod N

• f = g * h

• S = <(-a,1)>

Uploaded by Notion2Tistory v1.0.0