4. A Quantum Model of Computation

2021. 1. 10. 07:04ㆍIBM C:LOUDERs/Quantum Computing

728x90

Quantum Circuits

  • 양자회로는 Unitary Operation + Measurement + Input State 의 조합입니다.
  • Input State 가 n 개 이면 , Unitary Matrix 는 2n×2n2^n × 2^n 의 size 입니다
  • Measurement는 회로의 가장 끝단에 위치해야 합니다.

Multi Qubit Gates

  • 생각을 해봅시다. 지금까지 우리가 배운 Unitary Gate의 회로는 다음과 같습니다.
  • 이러한 회로의 형태는 2nd Qubit의 상태를 변화 시킬 수 없습니다

  • 또 우리가 배운 Unitary Gate 만으로는, 2개의 상태를 변화시키는 And Gate 를 만들 수 없습니다.

그렇기 때문에 우리는 새롭게 생각해야 합니다.

새롭게 정의하기에 앞서, Reversible Computing에 대해 알아보겠습니다

Reversible Computing

  • 세가지를 알아보겠습니다.
  • Reversible computing 이란 무엇인지, 예제를 통해 알아보고
  • Reversible Computing 이 왜 필요한 것인지?
  • Reversible Computing 을 정의하기 위해서는 어떻게 수학적으로 표현이 가능한지 입니다.
  • 그리고나서, 이러한 Reversible Computing 의 개념을 활용하여 Multi Qubit Gate를 알아보겠습니다.

1. Reversible Computing 예시

  • Reversible Computing은 말 그대로, Output을 보고 Input을 결정(Determination) 지을 수 있는 것입니다.
  • 현재의 Digital Logic Gate 중에는 NOT gate와 FANOUT gate 단 두가지 만이 Reversible 합니다. Truth-Table을 보시면 아시겠지만, 입력이 1개 뿐입니다.


2. Reversible Computing의 필요성

  • IBM의 Rolf Landauer 물리학자는 1961년에 "컴퓨팅 프로세스의 불가역성과 열 생성"이라는 논문을 발표했습니다. 이 책에서, 랜더워는 기존의 계산 연산의 논리적으로 되돌릴 수 없는 특성이 이러한 연산을 수행하는 장치의 열역학적 동작에 직접적인 영향을 미친다고 주장했습니다. 프로세스는 물리적 엔트로피가 증가하지 않는 경우 물리적으로 되돌릴 수 있다고 합니다. 1960년대 초로 거슬러 올라가는 역방향 컴퓨팅은 디지털 컴퓨팅의 핵심에서 0과 1을 조작하여 실행하거나 되돌릴 수 있도록 논리 작업을 설정하는 것을 의미합니다. 이 프로세스는 작업을 수행하지만 나중에 결과를 무시하는 현재의 접근 방식과 다릅니다. 예를 들어, 컴퓨터가 어떤 것을 "삭제"할 때, 물리적으로 하는 일은 전하를 보유하는 회로의 한 부분인 "전하를 실제로 변환하는 것"과 그것이 나타내는 정보를 열로 만드는 것입니다. 칩이 단시간에 수백만 또는 수십억 개의 소거 및 기타 작동을 수행할 때, 총 열량은 상당한 양이 되어 칩의 성능과 작은 공간에 함께 포장될 수 있는 칩의 수를 모두 제한합니다.
  • 모든 양자 연산은 단일화되어야 하므로 되돌릴 수 있습니다. QM의 간단한 규칙입니다. 단 하나의 측정으로 여러분이 어떤 양자 상태를 가지고 있는지 구별하는 것은 항상 불가능하다는 것을 주목하세요. 따라서 측정을 수행하면 양자 상태가 붕괴되고 대부분의 경우 측정이 비단일, 즉 되돌릴 수 없는 작동으로 계산되는 것을 "실행 취소"할 수 없습니다.
  • 측정을 무시하면 게이트 기반 양자 계산은 그냥 역순 입니다. 양자 컴퓨팅의 특정한 활용 사례로서 생각나는 것은 본질적으로 게이트의 가역적 특성을 이용하는 것입니다. 마이크로소프트가 Repeat-Filt-Success의 양자 회로에 대한 연구 결과입니다. 그 아이디어는, 하나의 관문을 구현하고자 할 때, 그 관문을 분해하는 것이 아마도 성공적일 것이고, 측정으로 성공 여부를 알 수 있다는 것입니다. 성공적이면 성공적이면 실패한 연산을 역행하고 성공할 때까지 다시 시도합니다(이 때문에 "성공할 때까지 반복").
💡
사실 저는 정확히 이해하지 못했습니다. 정보이론의 관점과 열역학의 엔트로피의 관점에서 중요하다고 이야기 하는 것 같은데, 이 부분은 추후에 공부한 뒤 다시 다룰 수 있도록 하겠습니다. 그 때를 위하여 관련자료를 아래에 첨부합니다.
https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/INC19-talk-v5.pdf
Irreversibility and Heat Generation in the Computing Process - IBM Journals & Magazine
IEEE Xplore, delivering full text access to the world's highest quality technical literature in engineering and technology. | IEEE Xplore
https://ieeexplore.ieee.org/document/5392446
https://d1b10bmlvqabco.cloudfront.net/paste/kggopnc188x46i/cc09419545d5f8c2663ea5940d759028b5bb9495b22f12d1331aa5a2b2ff40cc/infor._in_physics__T.Dittrich.pdf


3. Reversible Computing의 수학적 정의

  • 먼저 비 가역적인 상태를 정의하겠습니다. Iff:{0,1}n→{0,1}mIf \quad f:\{0,1\}^n →\{0,1\}^m is a Boolean function, ∣x>→∣f(x)>|x> → |f(x)> 은 비가역적입니다
  • 대신 우리는 아래와 같이 가역적인 상태를 정의하겠습니다. 
  •   ∣x⟩⊗∣0⟩→∣x⟩⊗∣f(x)⟩\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad |x\rangle ⊗ |0\rangle\quad→ \quad |x\rangle ⊗ |f(x)\rangle

Multi Qubit Gates Cont'd ( CNOT Gate )

  • CNOT Gate가 중요한 이유는, 이 Gate를 이용해서 다른 Gate 들을 조합해 낼 수 있는 가장 기본이 되는 Gate 입니다.
  • Control Part는 그대로 출력으로 나오므로 II
  • Target Part 는 NOT이 출력 되어야 하므로

💡
증명 : 2개의 input이므로 vector를 Dirac Notation으로 나열한다 U∣0>∣0>=U∣00>=U∣0>⊗∣0>=U[1(10)0(10)]=U(1000)=(1000)U|0>|0>=U|00>=U|0>⊗|0>=U \begin {bmatrix} 1 \begin {pmatrix} 1\\ 0 \end {pmatrix} \\0 \begin {pmatrix} 1\\ 0 \end {pmatrix} \end {bmatrix} = U \begin {pmatrix} 1\\ 0\\ 0\\ 0 \end {pmatrix} = \begin {pmatrix} 1\\ 0\\ 0\\ 0 \end {pmatrix} 이런식으로 4가지에 대해서 풀면 위와 같은 CNOT Gate를 얻을 수 있습니다.
  • 디지털 회로일 때는 ?
    • ⊕ == XOR
    • XOR은 NOT Gate와 같습니다


Multi Qubit Gates Cont'd ( C-U Gate )

  • 위와 같은 2개의 Input 에 대해 CNOT Gate를 알아보았습니다.
  • 이를 확장 시켜 NOT Gate가 아닌 다른 Gate에서는 어떻게 적용하면 될까요?
  • Control Input 은 {0,1} 로 고정 되어있으니, Target Input 만 고려하면 됩니다.


Multi Qubit Gates Cont'd ( Toffoli Gate - CCNOT )

  • 2개의 Input이 일반적인 C-U Gate를 알아보았습니다.
  • 이번에는 3개의 input에 대해 알아보겠습니다.
  • 이러한 Toffoli gate는 Classic 한 Digital Gate로 구현 할 수 없는 특징이 있습니다. 대신 2-qubit quantum gate로 표현 할 수 있습니다
  • 그리고 이러한 Permutation Matrix는 Unitary 합니다
  • 6개의 CNOT Gate를 사용해서 구현가능
  • NAND / FANOUT 회로

Gate를 이야기 하였으니 Unitary Gate를 몇개 더 이야기 하겠습니다


Rotation gates

  • Idea = eiAx=cos(x)I+isin(x)Ae^{iAx} = cos(x)I + i sin(x)A
  • Rx(θ)≡e−iθX2=cosθ2I−isinθ2X=[cosθ2−isinθ2−isinθ2cosθ2]Rx(θ) ≡ e^{{−iθX}\over 2} \\ = cos {θ \over 2}I − isin {θ \over 2}X \\ = \begin {bmatrix} cos{θ \over 2} \quad − isin {θ\over2}\\ − isin {θ \over 2} \quad cos{θ \over 2} \end {bmatrix}
  • Ry(θ)≡e−iθY2=cosθ2I−isinθ2Y=[cosθ2−sinθ2−sinθ2cosθ2]Ry(θ) ≡ e^{{−iθY}\over 2} \\ = cos {θ \over 2}I − isin {θ \over 2}Y \\ = \begin {bmatrix} cos{θ \over 2} \quad − sin {θ\over2}\\ − sin {θ \over 2} \quad cos{θ \over 2} \end {bmatrix}

  • Rz(θ)≡e−iθZ2=cosθ2I−isinθ2Z=[e−iθ200eiθ2]Rz(θ) ≡ e^{{−iθZ}\over 2} \\ = cos {θ \over 2}I − isin {θ \over 2}Z \\ = \begin {bmatrix} e^{-i{\theta \over 2}} \quad 0 \\ 0 \quad e^{i{\theta \over 2}} \end {bmatrix}


Phase Shift Gates

  • Rϕ=[1  00eiϕ]R_\phi = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i\phi} \end {bmatrix}
  • Z=[1  00eiπ]Z= \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i\pi} \end {bmatrix}
  • S=Z=[1  00eiπ2]S = \sqrt Z= \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i{\pi \over 2}} \end {bmatrix}
  • T=  4Z=[1  00eiπ4]T = \; ^4\sqrt Z = \begin {bmatrix} 1 \quad \;0 \\ 0 \quad e^{i{\pi \over 4}} \end {bmatrix}


Swap Gate

  • Swap 계산의 목적 은 다음과 같습니다. ∣a,b⟩→∣b,a⟩|a,b\rangle → |b,a\rangle
  • 이 때 Idea 는 Tensor Product a⊕a=∣0⟩a⊕a=|0\rangle 에서 착안합니다.

∣a,b⟩  →  ∣a,a⊕b⟩|a,b\rangle \;→\quad \quad \quad \quad \quad \quad\quad\quad\quad \; |a,a⊕b\rangle →∣a⊕(a⊕b),a⊕b⟩=∣b,a⊕b⟩→ |a⊕(a⊕b),a⊕b\rangle = |b,a⊕b\rangle →∣b,(a⊕b)⊕b⟩      =∣b,a⟩→ |b,(a⊕b)⊕b\rangle \quad \; \; \; = |b,a\rangle


Multi Qubit Gates Cont'd ( Fredkin - CSWAP)

  • Fredkin Gate 입니다. Swap Gate에 Control Input을 추가하여 제어 한다고 보시면 됩니다.


Error Approximation


CNOT gate로 Copy가 가능할까?

  • Control Input에 ∣ψ⟩=α ∣0⟩+β ∣1⟩ |\psi\rangle = \alpha \: |0\rangle + \beta \: |1\rangle를 넣고 Output(⊗) 으로 이것을 복제하는 상상을 해보자
  • 이 때 우리가 원하는 Expected Result 는 ∣ψ⟩∣ψ⟩=(α ∣0⟩+β ∣1⟩)⊗(α ∣0⟩+β ∣1⟩) |\psi\rangle |\psi\rangle = (\alpha \: |0\rangle + \beta \: |1\rangle)⊗(\alpha \: |0\rangle + \beta \: |1\rangle) 이다
  • 하지만 실제 연산 결과는 ∣ψ⟩∣0⟩=(α ∣0⟩+β ∣1⟩)⊗∣0⟩ |\psi\rangle |0\rangle = (\alpha \: |0\rangle + \beta \: |1\rangle)⊗|0\rangle 이다
  • 둘을 동일하게 하려면 αβ=0\alpha\beta=0 이어야 하는데, 그렇게 되면 다른 항이 사라져서 불가능하다

  • 이 이론은 no-cloning theorem 으로 1980년대 초반에 이미 증명되었다.


Measurement in other basis ( Bell State , EPR Pairs)

  • 추후 Entangled Protocol에 사용됩니다
💡
Von Neumann 의 정보 Entropy 이야기가 나온다. ... 잘 모르니까 정보이론을 공부해야겠다 .. Shannon 의 Entropy도 .. ㅠㅠ EPR ( Einstein-Podolsky-Rosen pairs ) 또는 Bell State 라고 불리우는 상태는 얽힘 엔트로피가 최대가 되는 상태를 의미한다. Orthonormal Basis 들일 때 최대가 된다
📢
Von Neumann Measurement

  • Measurement 가 뭐였죠 ? Projection 이었죠

  • Hadamard Basis 로 Projection 시켜서 Measure 하고 싶으면 어떻게 해야 할까?
    • ⇒ Rotating 시킨다
    • ⇒ Measurement 하기 전에 Hadamard Gate를 통과 시킨다

  • ∣β00⟩=12∣00⟩+12∣11⟩|β_{00}\rangle = {1 \over \sqrt 2} |00\rangle + {1 \over \sqrt 2} |11\rangle
  • ∣β10⟩=12∣00⟩−12∣11⟩|β_{10}\rangle = {1 \over \sqrt 2} |00\rangle - {1 \over \sqrt 2} |11\rangle
  • ∣β01⟩=12∣01⟩+12∣10⟩|β_{01}\rangle = {1 \over \sqrt 2} |01\rangle + {1 \over \sqrt 2} |10\rangle
  • ∣β11⟩=12∣01⟩−12∣10⟩|β_{11}\rangle = {1 \over \sqrt 2} |01\rangle - {1 \over \sqrt 2} |10\rangle

H gate는 superposition을 CNOT Gate는 Entanglement를 만들어 낸다

Uploaded by Notion2Tistory v1.0.0


'IBM C:LOUDERs > Quantum Computing' 카테고리의 다른 글

6. Introductory Quantum Algorithms  (0) 2021.01.10
5. Superdense Coding & Quantum Teleportation  (0) 2021.01.10
3. Qubits & Framework of Quantum Mechanics  (0) 2021.01.10
2. Linear Algebrea & the Dirac Notation  (0) 2021.01.10
1. Introduction & Background  (0) 2021.01.10

관련글

댓글 0

티스토리툴바