가역 컴퓨팅

가역 컴퓨팅(reversible computing)은 계산 과정의 모든 단계가 시간 가역적인 컴퓨팅 모델이다. 이는 계산의 출력이 주어지면 입력을 완벽하게 재구성할 수 있음을 의미한다. 한 상태에서 다른 상태로 결정론적으로 진행하는 시스템에서 가역성을 위한 핵심 요구 사항은 각 상태와 그 후속 상태 간의 일대일 대응이다. 가역 컴퓨팅은 비전통적인 컴퓨팅 접근 방식으로 간주되며 양자 컴퓨팅과 밀접하게 관련되어 있는데, 양자 컴퓨팅에서는 양자 역학의 원리가 본질적으로 가역성을 보장한다(양자 상태가 측정되거나 "붕괴"되지 않는 한).^[1]

가역성

이 목적에 특히 관심이 있는 두 가지 주요하고 밀접하게 관련된 가역성 유형이 있다. 물리적 가역성과 논리적 가역성이다..^[2]

어떤 과정이 물리적 엔트로피 증가를 초래하지 않으면 물리적으로 가역적이라고 한다. 이는 등엔트로피적이다. 이상적으로 이 속성을 나타내는 회로 설계 방식이 있는데, 이를 전하 회복 논리, 단열 회로, 또는 단열 컴퓨팅이라고 한다(자세한 내용은 단열과정 참조). 비록 실제로는 비정상 물리 과정이 정확히 물리적으로 가역적이거나 등엔트로피적일 수 없지만, 시스템의 진화를 설명하는 물리 법칙이 정확히 알려져 있고 알려지지 않은 외부 환경과의 상호 작용으로부터 충분히 잘 격리된 시스템에서는 완벽한 가역성에 얼마나 가깝게 접근할 수 있는지에 대한 알려진 한계는 없다.

가역 컴퓨팅을 구현하기 위한 기술 연구의 동기는, 이 기술들이 컴퓨터의 계산 에너지 효율 (즉, 소모된 에너지 단위당 수행되는 유용한 연산)을 근본적인 폰 노이만-란다우어 한계^[3][4]인 비가역 비트 연산당 kT ln(2)의 에너지 소모를 넘어 개선할 수 있는 유일한 잠재적인 방법을 제공한다는 점이다.

란다우어 한계는 2000년대 컴퓨터의 에너지 소비량보다 수백만 배 낮았고, 2010년대에는 수천 배 낮았다.^[5] 가역 컴퓨팅 옹호자들은 이러한 에너지 소비의 상당 부분이 아키텍처 오버헤드로 인한 것이라고 주장한다. 이러한 오버헤드는 컴퓨터를 작동시키는 데 필요한 전선, 트랜지스터, 메모리와 같은 비계산 부분과 관련된 에너지 비용이다. 그들은 현재 기술이 가역 컴퓨팅 원리를 채택하지 않고서는 훨씬 더 큰 에너지 효율을 달성하기 어렵다고 믿는다. ^[6]

열역학과의 관계

IBM에서 근무하던 중 롤프 란다우어가 처음 주장했듯이,^[7] 계산 과정이 물리적으로 가역적이기 위해서는 논리적으로도 가역적이어야 한다. 란다우어의 원리는 알려진 정보 n비트의 무의식적인 삭제가 항상 열역학적 엔트로피에서 nkT ln(2)의 비용을 발생시킨다는 관찰이다. 이산적이고 결정론적인 계산 과정은 오래된 계산 상태를 새로운 상태로 매핑하는 전이 함수가 단사 함수일 때 논리적으로 가역적이라고 한다. 즉, 출력 논리 상태가 계산 연산의 입력 논리 상태를 고유하게 결정한다.

비결정론적 (확률적이거나 무작위적인 의미에서) 계산 과정의 경우, 이전 상태와 새 상태 간의 관계는 일가 함수가 아니며, 물리적 가역성을 얻기 위해 필요한 조건은 약간 더 약한 조건이다. 즉, 계산이 앞으로 진행됨에 따라 가능한 초기 계산 상태의 주어진 앙상블 크기가 평균적으로 감소하지 않아야 한다.

물리적 가역성

란다우어의 원리(그리고 사실상 열역학 제2법칙)는 일반적인 해밀턴 역학 정식화와 보다 구체적으로 양자역학의 단일 시간-진화 연산자에 반영된 기본 물리학의 가역성의 직접적인 논리적 귀결로 이해될 수도 있다.^[8]

따라서 가역 컴퓨팅의 구현은 원하는 계산 작업을 수행하기 위한 메커니즘의 물리적 역학을 특성화하고 제어하는 방법을 배우는 것에 해당하며, 이는 수행되는 각 논리 연산당 메커니즘의 완전한 물리적 상태에 대한 총 불확실성이 무시할 수 있는 양만큼 축적되도록 정밀하게 제어하는 것이다. 다시 말해, 기계 내에서 계산 작업을 수행하는 데 관련된 활성 에너지의 상태를 정확하게 추적하고, 이 에너지의 대부분이 열의 형태로 소멸되도록 허용하는 대신 후속 작업을 위해 재사용될 수 있는 조직된 형태로 회수되도록 기계를 설계한다.

이 목표를 달성하는 것은 컴퓨팅을 위한 초정밀 신형 물리 메커니즘의 설계, 제조 및 특성화에 상당한 난관을 제시하지만, 현재로서는 이 목표가 궁극적으로 달성될 수 없다고 생각할 근본적인 이유는 없다. 언젠가 내부적으로 수행하는 각 유용한 논리 연산에 대해 1비트 가치보다 훨씬 적은 물리적 엔트로피를 생성하고 kT ln 2 에너지보다 훨씬 적은 에너지를 열로 소모하는 컴퓨터를 만들 수 있을 것이다.

오늘날 이 분야는 상당한 학술 문헌을 보유하고 있다. 물리학자, 전기 공학자, 컴퓨터 과학자들이 다양한 가역 장치 개념, 논리 회로, 전자 회로, 프로세서 아키텍처, 프로그래밍 언어 및 응용 알고리즘을 설계하고 분석했다.

이 연구 분야는 고품질, 비용 효율적이며 거의 가역적인 논리 장치 기술의 상세한 개발을 기다리고 있다. 이 기술에는 고효율 클럭킹 및 동기화 메커니즘이 포함되거나 비동기 설계를 통해 이러한 필요성을 피하는 기술이 필요하다. 이러한 종류의 견고한 엔지니어링 진전이 이루어져야 가역 컴퓨팅에 대한 방대한 이론적 연구가 실제 컴퓨터 기술의 에너지 효율성에 대한 다양한 단기적 장벽(폰 노이만-란다우어 경계 포함)을 극복하는 데 실질적인 응용을 찾을 수 있을 것이다. 이는 열역학 제2법칙 때문에 논리적으로 가역적인 컴퓨팅을 사용해야만 극복될 수 있다.^[9]

논리적 가역성

계산 연산이 논리적으로 가역적이라는 것은 해당 연산의 출력(또는 최종 상태)이 입력(또는 초기 상태)으로부터 계산될 수 있고, 그 반대도 마찬가지임을 의미한다. 가역 함수는 단사적이어야 한다. 이는 가역 게이트(및 회로, 즉 여러 게이트의 조합)가 일반적으로 출력 비트와 동일한 수의 입력 비트를 가진다는 것을 의미한다(모든 입력 비트가 연산에 의해 소비된다고 가정).

인버터 (NOT) 게이트는 되돌릴 수 있으므로 논리적으로 가역적이다. 그러나 NOT 게이트는 구현 방식에 따라 물리적으로 가역적이지 않을 수도 있다.

배타적 논리합 (XOR) 게이트는 단일 출력에서 두 입력을 명확하게 재구성할 수 없으므로 비가역적이다. 또는 정보 소거가 가역적이지 않기 때문이기도 하다. 그러나 XOR 게이트의 가역 버전인 제어 NOT 게이트 (CNOT)는 입력 중 하나를 두 번째 출력으로 보존함으로써 정의될 수 있다. CNOT 게이트의 세 입력 변형은 토폴리 게이트라고 불린다. 이는 두 입력 a, b를 보존하고 세 번째 입력 c를 ${\displaystyle c\oplus (a\cdot b)}$로 대체한다. ${\displaystyle c=0}$일 때 AND 함수를 제공하고, ${\displaystyle a\cdot b=1}$일 때 NOT 함수를 제공한다. AND와 NOT이 함께 함수적으로 완전한 집합이므로, 토폴리 게이트는 범용적이며 (충분히 초기화된 보조 비트가 주어진다면) 모든 불 함수를 구현할 수 있다.

가역 회로, 그 구성 및 최적화, 그리고 최근 연구 과제에 대한 조사가 가능하다.^{[10][11][12][13][14]}

가역 튜링 기계 (RTM)

가역 튜링 기계(RTM)는 가역 컴퓨팅의 기초 모델이다. RTM은 전이 함수가 가역적이며, 각 기계 구성(상태 및 테이프 내용)이 최대 하나의 선행 구성을 갖도록 보장하는 튜링 기계로 정의된다. 이는 역방향 결정론을 보장하여 계산 기록을 고유하게 추적할 수 있도록 한다.^[15]

RTM의 공식적인 정의는 지난 수십 년 동안 발전해 왔다. 초기 정의는 가역 전이 함수에 초점을 맞추었지만, 더 일반적인 공식화는 단계당 제한된 헤드 이동 및 셀 수정을 허용한다. 이러한 일반화는 RTM 집합이 합성 (RTM ${\displaystyle A}$ 실행 후 RTM ${\displaystyle B}$ 실행은 새로운 RTM을 생성함) 및 역 (RTM의 역도 RTM임)에 대해 닫혀 있음을 보장하여 가역 계산을 위한 그룹 구조를 형성한다. 이는 합성이 동일한 클래스의 기계를 생성하지 않을 수도 있는 일부 고전적인 TM 정의와 대조된다.^[16] RTM의 동역학은 지역 규칙에 기반하여 구성을 매핑하는 전역 전이 함수로 설명될 수 있다.^[17]

이브 르세르프는 1963년 논문에서 가역 튜링 기계를 제안했지만,^[18] 란다우어의 원리를 알지 못했는지 그 주제를 더 이상 추구하지 않고 그의 경력 대부분을 민족언어학에 헌신했다.

1973년 찰스 H. 베넷이 발표한 획기적인 결과는 모든 표준 튜링 기계를 가역 튜링 기계로 시뮬레이션할 수 있음을 입증했다.^[19] 베넷의 구성은 보조 "기록 테이프"로 TM을 보강하는 것을 포함한다. 시뮬레이션은 세 단계로 진행된다.^[20]

1. 계산: 원래 TM의 계산이 시뮬레이션되고, 적용된 모든 전이 규칙의 기록이 기록 테이프에 기록된다.
2. 출력 복사: 작업 테이프의 최종 결과가 별도의, 처음에는 비어 있는 출력 테이프에 복사된다. 이 복사 작업 자체는 가역적으로 수행되어야 한다(예: CNOT 게이트 사용).
3. 계산 취소: 시뮬레이션은 역방향으로 실행되며, 기록 테이프를 사용하여 순방향 계산의 각 단계를 되돌린다. 이 과정은 작업 테이프와 기록 테이프를 지워서 초기 빈 상태로 되돌리고, 원래 입력(그 테이프에 보존됨)과 최종 출력만 출력 테이프에 남긴다.

이 구성은 RTM이 계산 가능한 함수의 관점에서 표준 TM과 계산적으로 동등하다는 것을 증명하며, 이 점에서 가역성이 계산 능력을 제한하지 않는다는 것을 확립한다.^[20] 그러나 이 표준 시뮬레이션 기술에는 비용이 따른다. 기록 테이프는 계산 시간에 선형적으로 증가할 수 있어 잠재적으로 큰 공간 오버헤드를 초래하며, 종종 ${\displaystyle S'(n)=O(S(n)T(n))}$로 표현되는데, 여기서 ${\displaystyle S}$와 ${\displaystyle T}$는 원래 계산의 공간과 시간이다.^[19] 더욱이, 기록 기반 접근 방식은 지역 합성성에 대한 문제에 직면한다. 이 방법을 사용하여 독립적으로 가역화된 두 계산을 결합하는 것은 간단하지 않다. 이는 이론적으로 강력하지만, 베넷의 원래 구성이 가역 계산을 달성하는 가장 실용적이거나 효율적인 방법은 아니며, 많은 양의 "쓰레기" 기록을 축적하지 않는 방법을 찾기 위한 동기를 부여한다는 것을 나타낸다.^[20]

RTM은 정확히 단사(일대일) 계산 가능한 함수의 집합을 계산한다. RTM은 비단사 함수(본질적으로 정보를 손실하는 함수)를 직접 계산할 수 없기 때문에 고전적인 의미에서 엄격하게 범용적이지는 않다. 그러나 RTM은 "RTM-범용성"이라는 형태의 범용성을 가지며 자체 해석이 가능하다.^[15]

상용화

런던에 본사를 둔 Vaire 컴퓨팅은 2025년에 시제품 칩을 개발 중이며, 2027년에 출시할 예정이다.^[21]

같이 보기

• 단열 회로
• 양방향 변환
• 당구공 컴퓨터
• 프레드킨 게이트
• 일반화된 리프팅
• 야누스 (시간 가역 컴퓨팅 프로그래밍 언어)
• 최대 엔트로피 열역학, 열역학 제2법칙의 불확실성 해석에 대해
• 맥스웰의 도깨비
• 역계산
• 가역 셀룰러 오토마타
• 가역 동역학
• 가역과정
• 양자 컴퓨팅
• 양자점 셀룰러 오토마타, 가역 셀룰러 오토마타의 변형
• 토폴리 게이트
• 초전도 양자 컴퓨팅
• 계산 취소
• 비전통적 컴퓨팅