프레드킨 게이트

프레드킨 게이트(영어: Fredkin gate, 제어-SWAP 게이트(controlled-SWAP gate) 또는 보존 논리 게이트(conservative logic gate)라고도 함)는 에드워드 프레드킨이 발명한 가역 컴퓨팅에 적합한 계산 회로이다. 이는 보편적이며, 이는 모든 논리적 또는 산술적 연산이 전적으로 프레드킨 게이트로 구성될 수 있음을 의미한다. 프레드킨 게이트는 3개의 입력과 3개의 출력을 가진 회로 또는 장치로, 첫 번째 비트는 변경하지 않고 전송하며, 첫 번째 비트가 1인 경우에만 마지막 두 비트를 바꾼다.

프레드킨(제어 스와프) 게이트

배경

MIT 컴퓨터 과학 연구소에서 에드워드 프레드킨과 토마소 토폴리가 개념화한 프레드킨 게이트^[1]는 가역 컴퓨팅 및 보존 논리 분야에서 중추적인 발전이었다. 보존 논리 프레임워크 내에서 개발된 이 게이트는 계산 프로세스를 역동적인 법칙의 가역성 및 에너지 보존과 같은 근본적인 물리적 원칙과 일치하도록 설계되었다. 프레드킨 게이트의 기술적 근거는 비가역적 연산이 일반적으로 상당한 에너지 손실을 초래하는 기존 컴퓨팅의 비효율성을 해결하는 데 뿌리를 두고 있다.

정보를 지우고 란다우어의 원리에 따라 열을 방출하는 기존 논리 게이트와 달리,^[2] 프레드킨 게이트는 계산 과정에서 정보 손실이 없도록 하는 가역성을 유지한다. 게이트의 각 출력 상태는 입력 상태를 고유하게 결정하여 정보가 보존될 뿐만 아니라 에너지 보존 원칙과도 일치한다. 이러한 특성은 계산 능력에 대한 수요가 증가함에 따라 에너지 효율성이 핵심 고려 사항이 되면서 특히 중요하다.

프레드킨 게이트의 발명은 계산 연산의 에너지 발자국을 최소화하려는 노력에서 비롯되었다. 이는 처리 속도 및 전력 소비 측면에서 효율적일 뿐만 아니라 환경적으로도 지속 가능한 컴퓨팅 시스템을 구축할 수 있게 한다. 가역 컴퓨팅의 원리를 구현함으로써 프레드킨 게이트는 디지털 계산과 관련된 에너지 비용을 절감하는 실용적인 솔루션을 제공하여 보다 지속 가능한 컴퓨팅 기술로의 중요한 전환점을 마련했다.

정의

기본 프레드킨 게이트^[3]는 세 개의 입력 (C, I₁, I₂)를 세 개의 출력 (C, O₁, O₂)로 매핑하는 제어 스와프 게이트(CSWAP 게이트)이다. C 입력은 C 출력으로 직접 매핑된다. C = 0이면 스와프가 수행되지 않는다. I₁은 O₁로 매핑되고, I₂는 O₂로 매핑된다. 그렇지 않으면 두 출력이 스와프되어 I₁은 O₂로, I₂는 O₁로 매핑된다. 이 회로는 가역적이며, 즉 역방향으로 실행될 때 자체적으로 "되돌려진다"는 것을 쉽게 알 수 있다. 일반화된 n × n 프레드킨 게이트는 첫 n - 2개의 입력을 해당 출력으로 변경 없이 통과시키고, 첫 n - 2개의 입력이 모두 1인 경우에만 마지막 두 출력을 바꾼다.

• 제어 스와프 논리: 3비트 제어-SWAP 게이트인 프레드킨 게이트는 제어 비트의 상태에 따라 두 개의 대상 비트를 조건부로 교환하여 작동한다. 제어 비트가 1이면 게이트는 대상 비트를 교환하고, 0이면 비트는 변경되지 않고 통과한다.

진리표	치환행렬 형식
입력 출력 C I1 I2 C O1 O2 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1	${\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\\end{bmatrix}}}$

• 가역 컴퓨팅: 이 게이트는 가역적이며, 이는 계산 중에 정보 손실이 없음을 의미한다. 이 속성은 보존 논리 원칙과 일치하여 데이터를 보존하고 에너지 손실을 줄인다. 이는 물리학의 질량 보존 법칙과 잘 부합하며 모델이 낭비적이지 않음을 보여준다.

AND, OR, XOR, NOT을 사용한 진리 함수

프레드킨 게이트는 AND, OR, XOR, NOT과 같은 진리 함수를 사용하여 다음과 같이 정의할 수 있다.

O₁ = I₁ XOR S,

O₂ = I₂ XOR S,

C_out = C_in,

여기서 S = (I₁ XOR I₂) AND C이다.

또는:

O₁ = (NOT C AND I₁) OR (C AND I₂),

O₂ = (C AND I₁) OR (NOT C AND I₂),

C_out = C_in.

완전성

프레드킨 게이트가 보편적임을 알 수 있는 한 가지 방법은 AND, NOT, OR을 구현하는 데 사용될 수 있다는 점을 관찰하는 것이다.

I₂ = 0이면, O₂ = C AND I₁이다.

I₂ = 1이면, O₁ = C OR I₁이다.

I₁ = 0이고 I₂ = 1이면, O₂ = NOT C이다.

하드웨어 설명

베릴로그와 같은 하드웨어 설명 언어로 진리표를 인코딩할 수 있다.

module fredkin_gate (
 input u, input x1, input x2,
 output v, output y1, output y2);
always @(*) begin
    v = u;
    y1 = (~u & x1) | (u & x2);
    y2 = (u & x1) | (~u & x2);
end
endmodule

예시

5개의 프레드킨 게이트를 사용하는 3비트 전가산기(캐리 포함 덧셈)

5개의 프레드킨 게이트를 사용하는 3비트 전가산기(캐리 포함 덧셈). "가비지" 출력 비트 g는 r = 0이면 (p NOR q)이고, r = 1이면 (p NAND q)이다.

두 개의 상수를 포함한 왼쪽 입력은 세 개의 게이트를 통과하여 패리티를 빠르게 결정한다. 설정된 각 입력 비트에 대해 0과 1 비트가 위치를 바꾸어, 네 번째 행에 패리티 비트가, 다섯 번째 행에 패리티의 역이 나타난다.

그 다음, 패리티 비트가 설정되면 캐리 행과 역 패리티 행이 위치를 바꾸고, p 또는 q 입력 비트 중 하나가 설정되면(어떤 것을 사용하든 상관없음) 다시 위치를 바꾸어 결과 캐리 출력이 세 번째 행에 나타난다.

p 및 q 입력은 게이트 제어로만 사용되므로 출력에서 변경되지 않고 나타난다.

응용 분야

양자 광자 칩 구현

최근 연구에 따르면 프레드킨 게이트가 프로그래밍 가능한 실리콘 광자 칩에서 시연되었다. 이 칩들은 마흐-젠더 간섭계 네트워크를 사용하여 광자를 효율적으로 라우팅하며, 다수의 양자 게이트를 처리할 수 있는 다용도 및 확장 가능한 플랫폼을 생성한다. 이러한 접근 방식은 프레드킨 게이트를 대규모 양자 프로세서에 통합할 수 있게 하여 미래 양자 컴퓨팅 발전을 위한 길을 열어준다.^[4]

효율적인 제어-SWAP 연산

광자 설정에서 프레드킨 게이트는 효율적인 제어-SWAP 메커니즘으로 작동하여 대상 큐비트의 조건부 스왑을 가능하게 한다. 이는 양자 통신 및 기타 프로토콜에 중요한 고충실도 그린베르거-호른-자일링거 상태를 생성하는 데 특히 유용하다. 따라서 이 게이트는 효율적인 조건부 연산이 필요한 양자 프로토콜에 강력한 도구를 제공한다.^[5]

양자 상태 추정

프레드킨 게이트의 제어 연산은 자원 집약적인 양자 상태 단층 촬영 없이 양자 상태 간의 중첩을 추정할 수 있게 한다. 이는 효율성과 정확성이 가장 중요한 양자 통신, 측정 및 암호화에 특히 유용하다.^[5]

양자 프레드킨 게이트

2016년 3월 25일, 그리피스 대학교와 퀸즐랜드 대학교 연구원들은 빛 입자의 양자 얽힘을 이용하여 큐비트를 교환하는 양자 프레드킨 게이트를 구축했다고 발표했다. 양자 프레드킨 게이트의 가용성은 양자 컴퓨터 구축을 용이하게 할 수 있다.^[5][6]

같이 보기

• 양자 컴퓨팅
• 양자 게이트
  • 양자 회로
• 양자 프로그래밍
• 토폴리 게이트, 제어-제어-NOT 게이트.