8. Algorithms Based on Amplitude Amplification

Search Problem

---

• Problem

  Input : $x ∈ \begin {Bmatrix} {0,1} \end {Bmatrix}^n$ 이고 , $f : \begin {Bmatrix} 0,1 \end {Bmatrix} ^n → \begin {Bmatrix} 0,1 \end {Bmatrix}$, $f(x)= \begin {Bmatrix} 1 \quad if \; x \; is \; a\; solution\\ 0 \quad if \; x \; is \; not \; a \; solution \end {Bmatrix}$ 일 때, $f(x)=1$ 을 찾는 문제

• 그러한 Black-box(Oracle) 는 $U_f : |x\rangle|q\rangle → |x\rangle|q ⊕ f(x) \rangle$ 이다 이 떄 $|q\rangle = { |0\rangle - |1\rangle \over \sqrt 2}$로 두면, $|x\rangle → (-1)^{f(x)}|x\rangle$ 로 표현 될 수 있다.

• 그러면 k 개의 query (x들) 에 대해 $f(x)=1$ 일 확률은 ${k+1 \over 2^n}$ 이 된다. 따라서 Complexity는 $O(\sqrt{2^n})$ 이 된다

Grover's Search Algorithm

---

• 1996년 Lov Grover에 의해 고안된 개념입니다.

• 정렬되지 않은(unstructured) DB로부터 원하는 특정 데이터를 찾는 알고리즘 입니다.

• Classic Computer 에서는 $O(N)=O(2^n)$ 의 Time-Complexity but , Grover's Algorithm $O(\sqrt N)=O(2^{n \over 2})$ ⇒ Amplitude Boosting , Quadratically Faster 이러한 Time-Complexity는 두가지에 의해 설명 될 수 있습니다.
  • $|x\rangle → (-1)^{f(x)}|x\rangle$ 이런 Oracle(Black-box) $O(\sqrt N)$

  이 Quadratic Speed-up 은 NP-Complete Problem에 사용 될 수 있습니다.

• 이 알고리즘은 단순히 DB에서 특정데이터를 추출하는데 쓰이는 것만이 아니고, 다양한 Search Algorithm에 사용될 수 있습니다.

Grover Gate

---

STEP 1. Qubit을 준비

• 우리가 찾고자 하는 $x_0$=2=10(state)라고 하자.

• |0⟩|0⟩|1⟩을 준비한다. (세번째 큐비트는 보조큐비트)

STEP 2. Hadamard gate 적용

STEP 3. Oracle 적용

STEP 4. Diffusion operator 적용

• Phase Shift Operato

  

  

  

  

  

• DIffusion Operator

  

  

  

  

양자 알고리즘의 세계

피터 쇼어Peter Shor의 소인수 분해 알고리즘은 사람들이 양자 컴퓨터에 많은 관심을 갖게 된 시발점이었다. 양자 컴퓨터를 이용해 현실적으로 중요한 문제를 해결하는 데 필요한 연산량을 혁신적으로 줄일 수 있다는 사실은 많은 과학자들 사이에서 상당한 반향을 일으켰다. 만약 양자 컴퓨터가 소인수 분해를 더 빠르게 할 수 있다면, 다른 문제들도 빠르게 풀 수 있지 않을까?

https://horizon.kias.re.kr/14565/

Grover's Algorithm

You have likely heard that one of the many advantages a quantum computer has over a classical computer is its superior speed searching databases. Grover's algorithm demonstrates this capability.

https://qiskit.org/textbook/ch-algorithms/grover.html

Amplitude Estimation Algorithm

---

Uploaded by Notion2Tistory v1.0.0