프레드킨 게이트
Fredkin gate
프레드킨 게이트(CSWAP 게이트와 보수 논리 게이트도 마찬가지)는 에드워드 프레드킨이 발명한 가역 컴퓨팅에 적합한 연산 회로다.그것은 보편적이며, 이것은 어떤 논리 연산이나 산술 연산도 전적으로 프레드킨 게이트로 구성될 수 있다는 것을 의미한다.프레드킨 게이트는 3개의 입력과 3개의 출력을 가진 회로 또는 장치로, 첫 번째 비트가 1인 경우에만 첫 번째 비트를 변경하지 않고 전송하고 마지막 두 비트를 교환한다.
정의
기본 프레드킨 게이트는[1] 세 개의 입력(C2, I1, I)을 세 개의 출력(C, O1, O2)에 매핑하는 제어된 스왑 게이트다.C 입력은 C 출력에 직접 매핑된다.C = 0이면 스왑이 수행되지 않고, O에1 매핑하고12, O에 매핑한다2.그렇지 않으면 두 출력이 교환되어 나는1 O에2 매핑되고, 나는2 O에1 매핑된다.이 회로가 되돌릴 수 있다는 것, 즉 거꾸로 달릴 때 "해제"되는 것을 쉽게 알 수 있다.일반화된 n×n 프레드킨 게이트는 첫 번째 n-2 입력을 해당 출력으로 변경되지 않고 통과시키고, 첫 번째 n-2 입력이 모두 1인 경우에만 마지막 두 출력을 스왑한다.
프레드킨 게이트는 마지막 두 비트가 1인 경우에만 교환되는 역전형 3비트 게이트다.
| 진리표 | 순열 매트릭스 양식 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0과 1의 숫자가 전체적으로 보존되는 유용한 속성을 가지고 있는데, 당구공 모델에서 입력과 동일한 수의 공이 출력된다는 것을 의미한다.이것은 물리학의 질량 보존에 잘 부합하며, 모델이 낭비되지 않는다는 것을 보여주는 데 도움이 된다.
진실은 AND, OR, XOR 및 NOT와 함께 기능한다.
프레드킨 게이트는 다음과 같이 AND, OR, XOR 및 NOT의 진실 기능을 사용하여 정의할 수 있다.
- O1 = I1 XOR S
- O2 = I2 XOR S
- Cout= Cin
여기서 S = (I1 XOR I2) 및 C
또는:
- O1 = (C와 I이1 아님) 또는 (C와2 I)
- O2 = (C1 및 I) 또는 (C 및 I 아님2)
- Cout= Cin
완성도
프레드킨 게이트가 보편적이라는 것을 확인하는 한 가지 방법은 프레드킨 게이트가 AND를 구현하는 데 사용될 수 있다는 것을 구현하는 데 사용될 수 있는 것은 NOT와 OR:
- I221 = 0이면 O = C 및 I
- I21 = 1이면 O = C 또는1 I
- I12 = 0이고 I2 = 1이면 O = C가 아니다.
예
프레드킨 게이트 5개를 사용한 3비트 풀 어더더(캐리어 추가)g 가비지 출력 비트는 r=0이면 (p NOR q), r=1이면 (p NAND q)이다.
두 개의 상수를 포함한 왼쪽의 입력은 세 개의 관문을 통과하여 신속하게 패리티를 결정한다.0과 1비트는 설정된 각 입력 비트에 대해 자리를 바꾸어 4번째 행에는 패리티 비트가, 5번째 행에는 패리티의 역비트가 발생한다.
그런 다음 p 또는 q 입력 비트 중 하나가 설정되면(어느 것이 사용되는지는 중요하지 않음) 이동 행과 역 패리티 행이 스왑되고 결과 이동 출력이 세 번째 행에 나타나면 다시 스왑된다.
p와 q 입력은 게이트 제어로만 사용되므로 출력에서 변경되지 않고 나타난다.
퀀텀 프레드킨 게이트
2016년 3월 25일 그리피스 대학교와 퀸즐랜드 대학교의 연구원들은 빛의 입자들이 양자 얽힌 것을 이용하여 쿼트를 교환하는 양자 프레드킨 게이트를 만들었다고 발표했다.양자 프레드킨 게이트의 가용성은 양자 컴퓨터 구축을 촉진할 수 있다.[2][3]
참고 항목
참조
- ^ 브라운, 줄리안, 퀀텀 컴퓨터를 위한 퀘스트, 뉴욕 : 터치스톤, 2000.
- ^ "Quantum computing is now a big step closer thanks to a new breakthrough: The Fredkin gate".
- ^ 양자 프레드킨 게이트 라지 B파텔, 조셉 호, 프랑크 페레이롤, 티모시 C.Ralph and Geoff J. Pride, Science Advance, 2016년 3월 25일, Vol. 2, 3, e1501531, DOI: 10.1126/sciadv.1501531
추가 읽기
- Fredkin, Edward; Toffoli, Tommaso (1982). "Conservative Logic" (PDF). International Journal of Theoretical Physics. 21 (3–4): 219–253. Bibcode:1982IJTP...21..219F. doi:10.1007/BF01857727. S2CID 37305161. Archived from the original (PDF) on October 17, 2006.
