항상 즐겁게 잘 듣고 있습니다. 양자컴퓨터 관련해서 몇 가지 커멘트할 것이 있어서 글 남깁니다. 아마도 시간 관계상 혹은 기술적으로 복잡하다고 생각해서 생략하신 것들이 있어서 그런 것 같습니다만, 가역/양자 계산에 대해 몇 가지 중요한 문제들이 살짝 아쉽게 다루어진 것 같아서요.

1. 김현철 교수님께서 처음부터 비가역적인 것을 가역적으로 바꾸는 것은 원천적으로 불가능한 것 아니냐는 질문을 주셨었는데, 여기에 대한 이진형 교수님의 답변은 가역/비가역에 대해서만 집중해서 답을 주셔서 약간 아쉬운 면이 있었습니다. 가역/양자 계산에서 사실 이 부분은 가장 본질적인 문제라...
   
   
   처음부터 비가역적일 수밖에 없는 계산이 있습니다. 예를 들어 x를 x^2로 보내는 함수는 일대일 함수가 아닌데, 일대일 함수가 아니므로 본질적으로 x를 x^2로 보내는 과정은 비가역적입니다. 4라는 답이 나왔을 때에, 그 답이 2에서 온 것인지, 아니면 -2에서 온 것인지 알아낼 방법은 없습니다. 일반적으로, 일대일 함수가 아닌 임의의 함수 f(x)는 원칙적으로 비가역적일 수밖에 없습니다. 이 상황을 생각하면, 모든 계산을 가역적으로 하겠다는 시도가 있었다는 이야기 자체가 얼핏 이상하게 들립니다. 대체 어떻게 그런 것이 가능하지?
   
   
   가역 계산에서는 이 문제를 매우 간단하게 해결합니다: 계산이라는 것을 x로부터 f(x)를 얻는 과정이라고 보는 것이 아니라, x로부터 (x, f(x))를 얻는 과정이라고 재해석합니다. 즉, 입력으로부터 출력만 얻고, 입력을 '지우는' 것이 아니라, 입력으로부터의 결과값이 출력 뿐만 아니라 입력까지 같이 출력한다고 봅니다. 앞의 예로 돌아가면, 2가 입력이면, 결과는 (2, 4)가 되고, -2가 입력이었다면 결과는 (-2, 4)가 됩니다. 함수 f(x)=x^2 자체는 일대일함수가 아니므로 원천적으로 가역적으로 구현될 희망이 없지만, 입력값을 굳이 '지우지' 않고 계속 끌고간다고 한다면 x -> (x, f(x))는 일대일함수이므로 가역적으로 구현될 희망이 있습니다. (보다 기술적으로는, (x, y)로부터 (x, y+f(x))를 계산하는 식으로 처리합니다. 이 경우 출력을 받을 변수인 y를 0으로 놓고 시작하면, (x, 0)으로부터 (x, f(x))가 계산됩니다.)
2. 이진형 교수님이 모르는 양자 상태는 지울 수 없다는 언급을 간략히 하고 넘어가셨는데, 나중에 오정근 박사님이 이를 받아서, 입력을 받아서 답만 내면 괜찮은데, 가역적으로 일을 하려면 어떤 연산을 했는지를 모두 기록해둬야 하므로 (지울 수가 없으니까?) 메모리가 너무 많이 필요하다는 언급을 하십니다. 어떤 의미에서는 이 커멘트는 앞에서 제가 언급한, 입력을 지우지 않고 출력과 함께 적어주는 것과 관련이 있습니다. 실제로, 계산 과정이란 자잘한 계산들의 합성이라고 생각할 수 있습니다. f라는 계산을 하고, 그 다음에 g라는 계산을 하면, x로부터 f 계산을 가역적으로 하면 (x, f(x))를 얻을 것이고, 그 다음에 f(x) 부분을 g에 대한 입력이라고 생각하고 g 계산을 가역적으로 하면 (x, f(x), g(f(x)))를 얻을 것입니다. 우리가 진짜로 하고 싶은 것은 g(f(x))의 계산이므로, 앞에서 입력값을 유지하는 패러다임을 도입하면 (x, g(f(x)))를 얻었어야 했는데, 가역적인 구현 떄문에 입력 뿐만 아니라 중간 계산 결과인 f(x)까지도 추가로 남게 됩니다. 이러한 쓰레기를 수거하지 않고 남겨두면, 계산의 단계 단계에서 이런 중간값들이 계속 누적되게 되고, 따라서 오정근 박사님 말씀대로 가역성을 얻는 대신에 너무나 많은 메모리를 필요로 하게 되어 현실적이지 않을 것입니다.
   
   
   하지만, 가역 계산을 연구했던 사람들이 (Bennett이나 Toffoli 등) 이 문제를 몰랐던 것도 아니고, 또한 여기에 대해 이미 아름다운 답을 내놓은 것이 있습니다. 힌트는 이진형 교수님의 언급에 이미 들어있습니다: '모르는' 양자 상태는 지울 수 없다는 것입니다. 즉, 역으로, '아는 상태''는 꼭 지우는 것이 불가능한 것은 아니라는 이야기지요. 앞에서 (x, f(x), g(f(x)))까지 얻은 상태에서 보자면, f(x)에 대한 정보는 어떤 의미에서는 이미 x 부분에 들어있습니다: 따라서, f(x)를 지울 수 있어요. 앞에서 f의 계산은 (x, 0)으로부터 (x, f(x))를 구하는 것이라고 했었는데, 이것이 만일 가역적으로 구현되어 있다고 하면, (x, f(x), g(f(x))) 상태에서 앞의 두 성분에 f의 가역적인 구현을 '거꾸로 돌리는'' 일을 할 수 있습니다. 가역적이니까요. 소위 'uncomputing'이라고 불리우는 이 일을 하고 난 결과는 (x, 0, g(f(x)))이 되겠죠. f(x)는 모르는 상태가 아니라 아는 상태이기 때문에, f(x)를 맞춤형으로 지울 수가 있습니다. 이렇게 하고 나면 다시 입력 x와 출력 g(f(x))만이 살아남고, 중간에 f(x)를 담고 있던 공간은 빈 공간이 됩니다.  물론 이 빈 공간은 다시 다음 계산을 하는 데에 재활용될 수 있습니다.
   
   
   뭔가를 가역적으로 만들었고, 그게 뭐고 그걸 어떻게 만들었는지 알고 있다면, 그걸 만든 과정이 가역적이었으니 물론 그 과정을 거꾸로 돌려서 그 뭔가를 '지우는' 것이 가능합니다. 이 uncomputing이 실제 가역 계산을 가능하게 하는 강력한 도구가 됩니다.  결론적으로, 가역/양자 컴퓨팅이라고 기존의 고전적 계산을 구현할 때에 메모리를 과도하게 더 많이 사용하지는 않습니다.  사용 메모리를 uncomputing을 통해 그때 그때 지우고 재사용할 수 있기 때문에, 대강 고전 컴퓨터의 수준 정도로 메모리 사용량을 유지할 수 있습니다.  (물론 양자컴퓨팅의 경우에는 비트가 아니라 값비싼 큐빗을 써야 하므로 비슷한 수준이라고 해도 훨씬 비싸긴 하겠습니다만, 어쨌든...)