소프트웨어학부생의 양자컴퓨터 학습노트 — 2. 논리 게이트 만들기

이전 글에서는 간단한 양자 게이트들에 대해서 알아보았습니다. 이번 글에서는 이를 이용해 논리 게이트를 만들고 비트간 덧셈을 수행하는 Half Adder, Full Adder도 만들어보겠습니다.

Image for post
Image for post
Photo by ThisisEngineering RAEng on Unsplash

논리 게이트

NOT Gate

이전 글에서 X 혹은 Y 게이트가 NOT 연산과 동일하게 사용될 수 있다고 말씀드렸습니다. 따라서

NOT(a) = X(a) = Y(a)

AND GATE

CCX 게이트가 AND 게이트의 역할을 수행합니다. CCX 게이트는 두 컨트롤 비트가 1일 때 타겟 비트의 확률을 반전시킵니다. 따라서 C가 0일 경우 AND 게이트의 역할을 수행할 수 있습니다.

C가 0일 경우 CCX(A, B, C)는 C = AND(A,B)

NAND Gate

NAND(Not AND) 게이트는 CCX 게이트에다가 X(NOT)를 이어주면 됩니다.

XOR Gate

OR 게이트를 보기 전에 먼저 XOR 게이트를 보겠습니다. XOR 게이트는 A, B 두 개의 비트값이 다를 경우 1, 같을 경우 0을 결과값으로 출력합니다.

Image for post
Image for post

따라서 이는 아래처럼 CX 게이트를 두 번 수행하면 됩니다.

if C := 0, 순서 상관 없음1. CX(A, C)
1. CX(B, C)

CX 게이트는 컨트롤 비트가 1일 경우 타겟 비트의 확률을 반전시킵니다. A가 1일 경우 C가 반전되서 1이 되고, 또 B가 1이라면 반전되서 C가 0이 됩니다. A, B 둘 다 0이라면 C는 반전되지 않아서 0이 되고, A, B 둘 중 하나만 1일 때 C가 한 번 반전되서 1이 됩니다.

OR Gate

OR GATE는 XOR 게이트에 두 컨트롤 비트가 1일 때만 처리하면 됩니다.

Image for post
Image for post
if C := 0, 순서 상관 없음1. CX(A, C) 
2. CX(B, C)
3. CCX(A, B, C)

XOR 게이트에서 CCX만 추가된 모습입니다. CCX는 A, B 둘 다 1일 때 부호를 반전시킵니다. A, B 둘 중 하나만 1일 때는 부호가 반전되지 않아서 이전의 XOR에서 이미 C가 1이 되고, 둘 다 1일 때는 C가 0인 상태였다가 CCX에 의해 다시 1이 됩니다.

NOR GATE

OR 게이트에 NOT을 이어주면 됩니다.

덧셈 회로 만들기

이제 이 논리 게이트들을 이용해 학부 디지털회로 수업때 만들었던 Half Adder, Full Adder를 설계해보겠습니다.

Half Adder

Image for post
Image for post

먼저 Half Adder 입니다. 두 비트 A, B의 합을 계산하는 S(Sum)과, 두 비트 A, B가 자리수를 넘어갔음을 의미하는 캐리비트 C를 계산하면 됩니다. 우선 위 논리표만 봐서는 아래처럼 쉽게 만들 수 있습니다.

S := XOR(A, B)
C := AND(A, B)

다만 양자컴퓨터에서는 타겟 비트인 S와 C가 모두 초기값이 0이어야 한다는 걸 기억해야합니다.

Full Adder

Image for post
Image for post

Full Adder는 두 비트 A, B의 합 뿐만 아니라, 낮은 자리수의 adder에서 온 캐리비트의 값까지 함께 더해주어야 합니다. 따라서 위와 같은 논리표가 만들어지죠, 우선 자세한 유도는 생략하고 결과만 보면

S := A xor B xor X
C := (A and B) or (A and X) or (B and X)

입니다. 물론 Half Adder와 마찬가지로 S와 C가 초기값이 0이어야합니다.

그렇다면 위 식을 그대로 양자회로로 만들면 될까요? 결과는 잘 나오겠지만 최적의 회로는 아닙니다. 더 적은 회로를 써서 같은 결과를 얻을 수 있습니다. 우선 S는 위의 식을 그대로 바꿔서 아래처럼 XOR 연산을 두번 해서 얻을 수 있습니다.

T는 여분의 큐비트입니다CX(A, T) # T := A xor B
CX(B, T)
CX(X, S) # S := X xor T
CX(T, S)

이제 C를 계산해보겠습니다.

T는 위에서 계산했던 A xor B입니다, U, V는 여분의 큐비트입니다.
U=6,V=3
CCX(A, B, V) # V := A and B
CCX(X, T, U) # U := X and T
X(V) # V := not V
X(U) # U := not U
CCX(V, U, C) # C := V and C
X(C) # C := not C
정리하면
V = A nand B
U = X nand (A xor B)
C = V nand U

회로의 양을 비교해봅시다. 먼저 C := (A and B) or (A and X) or (B and X) 입니다

Image for post
Image for post

그 다음에 최적화된 코드입니다. 제출 점수는 427가 나왔네요

Image for post
Image for post

최적화된 코드입니다. 252점을 받았습니다. 사용하는 큐비트도 적고, 회로 수도 더 적습니다.

회로를 비교할 때 사용한 회로 수로 비교하면 안됩니다. 예를 들어 CZ게이트는 실제로는 H 게이트 2개와 CZ게이트 1개로 이루어져있습니다. 즉 회로마다 소모되는 Instruction의 수가 다릅니다. Qiskit은 Unroller를 이용해서 이를 확인해볼 수 있습니다. 예를 들어 위의 최적화되지 않은 덧셈 회로를 펼처보면

Image for post
Image for post

이정도 길이가 나옵니다.

Written by

2020.12.8 ~ 2022.6.9 군복무중 Serving in the South Korean Military Service

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store