양자컴퓨팅 - 5 : 양자 병렬성 및 양자 회로 특징 (Toffoli gate)

2022.05.02 - [가속기 Accelerator/Quantum Computing] - 양자컴퓨팅 - 4 : Quantum Entanglement (양자 얽힘, 슈뢰딩거의 고양이)

이 자료는 김태현 교수님의 양자 컴퓨팅 및 정보의 기초 강의를 바탕으로 정리하였습니다.

 

 

양자 병렬성 Quantum Parallelism

양자 회로는 양자 병렬성을 이용하여 빠른 계산이 가능하다. 양자 병렬성은 양자 회로가 디지털 회로에 비해 빠를 수 있는 이유 중 하나로 양자의 상태 중첩 (Superposition) 을 이용한 특징이다. 다음 Fig 1.과 같이 입력 X에 따라 값을 출력하는 함수 F (unitary operation)이 있다고 하자. X는 F의 입력으로 들어가고, 그 결과 X의 상태가 진화한다. 이후 진화된 X의 값을 측정하면 하나의 상태로 collapse한다. 이때, F(|0⟩), F(|1⟩)의 값을 구하려고 한다.

 

Fig 1. 함수 F를 구현한 양자 회로

 

X = |0⟩ 일 경우, 함수 F에 의해 X = F(|0⟩)이 될 것이고, 이를 측정하면 F(|0⟩)의 값을 구할 수 있을 것이다. 마찬가지로, X = |1⟩ 일 경우, 함수 F에 의해 X = F(|1⟩)이 될 것이고, 이를 측정하면 F(|1⟩)의 값을 구할 수 있을 것이다.

만약 X = α|0⟩ + β|1⟩ (where α + β = 1)일 경우 다음 Eq 1.과 같이 한번에 F(|0⟩)와 F(|1⟩)를 계산할 수 있을 것이다. F는 unitary operation이기에 각 ket에 대하여 분배법칙이 성립한다.

 

Eq 1. 중첩된 상태의 양자 계산

 

따라서 함수 F를 한번만 계산함에도 불구하고, F(X)는 한번에 두 개의 상태 F(|0⟩), F(|1⟩)의 값을 내포하고 있다. 두 가지 상태를 중첩하고 그 중첩된 상태를 unitary operation F를 통해 계산하였기다. 따라서 한번만에 두 가지 상태 (즉, |0⟩, |1⟩)모두에 대해서 F를 적용한 값 (즉, F(|0⟩), F(|1⟩)) 을 계산하였다고 생각할 수 있다.

 

하지만 이렇게 도출된 결과는 우리에게 어떠한 의미도 주지 못한다. 결국 우리는 양자를 측정(관측)하여야 그 상태를 알 수 있는데, 측정 즉시 양자의 중첩 상태는 하나의 상태로 collapse된다. 즉 F(X) = αF(|0⟩) + βF(|1⟩) 일지라도, 측정을 하면 F(X) = F(|0⟩) 혹은 F(X) = F(|1⟩)의 값만을 알수 있다. 따라서 계산은 병렬로 진행되었지만, 실제 사용하고자 할 경우 2번 이상 (측정을 할 경우 F(|1⟩)이 안 나오고, F(|0⟩)만 주구장창 나올 수도 있기 때문이다) 계산을 반복해야 한다.

 

그렇다고, 측정 시 중첩 사태가 붕괴되기에 양자 병렬성이 전혀 필요 없다고 할 수는 없다. 기존 알고리즘에 추가적인 계산 과정을 도입할 경우, 충분히 양자 병렬성을 활용할 수 있는 양자 알고리즘을 만들 수 있다. Deutsch (도이치)는 두 번의 계산이 필요한 문제를 양자의 중첩 및 계산 과정을 조금 더 추가하여 한 번의 계산만으로 문제를 풀 수 있는 알고리즘을 제안하였다.

 

 

 

양자 회로의 특징 - Universal Gate (Toffoli gate)

모든 디지털 회로는 양자 회로로 구현이 가능하다. 따라서 양자 회로는 디지털 회로의 super set이다. (디지털 회로로 양자의 물리적 특성을 이용하는 양자 회로를 구현할 수는 없다. 다만 양자 회로의 기능은 디지털 회로로 시뮬레이션해 볼 수는 있다. 따라서 기존 컴퓨터로 양자 회로의 기능은 테스트해 볼 수 있다.) 

 

디지털 회로를 배울 때 universal gate라는 개념을 배웠을 것이다. 디지털 회로의 gate로는 AND, NOT, OR, XOR 등이 잇는데, NAND 또는 NOR gate 한 종류만 있으면 다른 모든 gate를 구현할 수 있다. 이러한 gate를 universal gate라고 한다.

 

Fig 2. Universal gate [1]

 

Toffoli gate는 양자 회로의 gate로 NAND 동작을 수행할 수 있다. 따라서 Toffoli gate만 있으면 모든 디지털 회로의 gates 및 회로를 만들 수 있다. Toffoli gate는 다음 Fig 3.과 같은 진리표를 가진다.

 

Fig 3. Toffoli gate의 진리표 및 다이어그램 [2] [3]

 

Toffoli gate는 |a⟩, |b⟩ 모두 1일 때, |c⟩에 Not 연산 (정확히는 Pauli X) 을 가하는 gate이다. Fig 4.의 오른쪽과 같이 |c⟩를 |1⟩로 고정할 경우, |a⟩, |b⟩의 NAND 결과를 얻을 수 있다.

 

 

 

Reference

[1] https://ittimepass.wordpress.com/2017/02/09/what-are-universal-gates-explain-with-suitable-example/

[2] https://www.researchgate.net/figure/Truth-table-and-quantum-circuit-of-Toffoli-gate_fig3_338021358

[3] https://prefetch.eu/know/concept/toffoli-gate/

[4] https://en.wikipedia.org/wiki/Fredkin_gate