이전 글에서는 간단한 양자 게이트들에 대해서 알아보았습니다. 이번 글에서는 이를 이용해 논리 게이트를 만들고 비트간 덧셈을 수행하는 Half Adder, Full Adder도 만들어보겠습니다.
논리 게이트
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을 결과값으로 출력합니다.
따라서 이는 아래처럼 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일 때만 처리하면 됩니다.
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
먼저 Half Adder 입니다. 두 비트 A, B의 합을 계산하는 S(Sum)과, 두 비트 A, B가 자리수를 넘어갔음을 의미하는 캐리비트 C를 계산하면 됩니다. 우선 위 논리표만 봐서는 아래처럼 쉽게 만들 수 있습니다.
S := XOR(A, B)
C := AND(A, B)다만 양자컴퓨터에서는 타겟 비트인 S와 C가 모두 초기값이 0이어야 한다는 걸 기억해야합니다.
Full Adder
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=3CCX(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) 입니다
그 다음에 최적화된 코드입니다. 제출 점수는 427가 나왔네요
최적화된 코드입니다. 252점을 받았습니다. 사용하는 큐비트도 적고, 회로 수도 더 적습니다.
회로를 비교할 때 사용한 회로 수로 비교하면 안됩니다. 예를 들어 CZ게이트는 실제로는 H 게이트 2개와 CZ게이트 1개로 이루어져있습니다. 즉 회로마다 소모되는 Instruction의 수가 다릅니다. Qiskit은 Unroller를 이용해서 이를 확인해볼 수 있습니다. 예를 들어 위의 최적화되지 않은 덧셈 회로를 펼처보면
이정도 길이가 나옵니다.
