Unitary complexity in polynomial space

컴퓨팅의 세계에는 기계가 빠르게 할 수 있는 일과 방대한 양의 메모리가 주어졌을 때 할 수 있는 일 사이에 근본적인 격차가 존재합니다. 수십 년 동안 컴퓨터 과학자들은 이러한 영역들을 지도화하여, 풀기 쉬운 문제, 풀기 어려운 문제, 그리고 합리적인 시간 내에 해결하는 것이 불가능해 보이는 문제들을 분류해 왔습니다. 이 분야의 핵심 질문은 더 많은 메모리를 사용하는 능력이 제한된 시간만을 가진 컴퓨터로는 도달할 수 없는 문제들을 해결할 수 있게 해주는가 하는 것입니다. 우리는 이에 대한 강력한 의구심을 가지고 있지만, 이러한 질문 중 상당수는 여전히 증명되지 않은 채 남아 있습니다.

이 고전적인 세계와 평행하게, 양자 컴퓨터가 하부 원자의 특이한 성질을 이용해 정보를 처리하는 양자 컴퓨팅의 영역이 존재합니다. 여기서 규칙은 다릅니다. 양자 컴퓨터는 단순히 비트를 켜거나 끄는 것이 아니라, 복잡한 확률의 파동을 조작합니다. 이를 통해 양자 컴퓨터는 고전적 컴퓨터가 영겁의 시간이 걸릴 법한 특정 작업들을 수행할 수 있습니다. 그러나 깊은 미스터리가 지속되어 왔습니다. 양자 컴퓨팅의 힘이 완전히 새로운 종류의 어려움에 기반하는 것인지, 아니면 비밀리에 아주 효율적인 형태의 고전적 컴퓨팅이 변장한 것에 불과한 것인지 하는 점입니다. 구체적으로, 연구자들은 양자 컴퓨터가 수행할 수 있는 모든 가능한 연산이 적절한 힌트가 주어진다면 결국 고전적 컴퓨터가 알아낼 수 있는 일련의 단계들로 분해될 수 있는지 궁금해해 왔습니다. 만약 답이 '예'라면, 양자 암호학의 독특한 힘은 환상에 불과할 것입니다. 만약 답이 '아니오'라면, 양자 컴퓨터는 고전적 기계가 결코 복제할 수 없는 근본적인 강점을 지니게 됩니다.

두 명의 연구자, 윌리엄 크레치머(William Kretschmer)와 에윈 탱(Ewin Tang)은 최근 이 불확실성을 해결하기 위한 중요한 진전을 이루었습니다. 그들이 미스터리를 완전히 해결한 것은 아니지만, 보안 양자 암호학의 존재를 고전 컴퓨터 과학의 가장 오래되고 완고한 미해결 문제들과 연결하는 강력한 논리적 가교를 구축했습니다. 그들의 연구는 만약 현실 세계에서 보안 양자 암호학이 존재한다면, 다음 두 가지 중 하나가 반드시 참이어야 함을 시사합니다. 즉, 양자 연산을 고전적 명령어로 번역하는 데 있어 근본적인 한계가 존재하거나, 혹은 고전적 컴퓨터의 능력에 관한 수십 년 된 특정한 질문이 놀라운 답을 갖게 될 것이라는 점입니다.

그들의 업적을 이해하려면 먼저 그들이 분석하고 있는 과업의 본질을 파악해야 합니다. 양자 컴퓨터를 복잡하고 다차원적인 물체를 완벽하게 가역적인 방식으로 회전시킬 수 있는 장치라고 상상해 보십시오. '유니터리 합성 문제(unitary synthesis problem)'는 그러한 회전에 대해, 표준 컴퓨터가 그 회전을 재현하기 위해 따를 수 있는 일련의 고전적 명령어를 찾을 수 있는지 묻는 것입니다. 만약 우리가 항상 이를 할 수 있다면, 이는 양자 세계가 어떤 의미에서는 매우 복잡한 버전의 고전 세계에 불과하다는 것을 의미할 것입니다. 연구자들은 이러한 회전들 중에서도 양자 컴퓨터가 적절한 양의 메모리를 사용하여 수행할 수 있는 특정 부류에 집중했습니다. 그들은 이 특정 회전들이 오라클(oracle, 특정 질문에 즉각적으로 답할 수 있는 마법 같은 블랙박스)의 도움을 받는다면 고전적 컴퓨터에 의해 항상 합성될 수 있는지 물었습니다.

저자들은 먼저 실무적인 장애물을 해결하는 것부터 시작했습니다. 즉, 이러한 양자 과업들을 어떻게 정확하게 정의할 것인가 하는 문제입니다. 이전의 시도들은 혼란스러운 결과를 초р낳았는데, 이는 계산 과정 중에 '쓰레기(garbage)'가 남겨지는 것을 허용했기 때문입니다. 양자 컴퓨팅에서 기계가 계산을 수행할 때, 결과에 영향을 주지 않으면서도 단순히 삭제할 수 없는 불필요한 추가 데이터가 남는 경우가 종종 있습니다. 어떤 정의들은 이 지저분한 잔여 데이터를 허용했던 반면, 어떤 정의들은 완벽하게 깨끗한 과정을 요구했습니다. 크레치머와 탱은 대량의 메모리를 사용하는 과업의 경우 이 차이가 중요하지 않음을 보여주었습니다. 그들은 어떤 지저분하고 쓰레기가 포함된 양자 과정이라도 근본적인 난이도를 바꾸지 않으면서 깨끗하고 쓰레기가 없는 과정으로 변환될 수 있음을 증명했습니다. 이는 매우 중요한 단계였는데, 이로 인해 그들이 이 복잡한 양자 연산들을 결여되었던 수학적 명료함을 가지고 다룰 수 있게 되었기 때문입니다.

이러한 정의를 갖춘 후, 그들은 핵심 질문에 달려들었습니다. 그들은 다항 공간(polynomial space, 관리 가능한 양의 메모리)으로 수행할 수 있는 모든 양자 연산에 대해 두 가지 가능성만 존재함을 입증했습니다. 해당 연산이 너무 복잡하여 어떤 고전적 컴퓨터라도, 아무리 영리하고 오라클로부터 아무리 많은 도움을 받더라도 효율적으로 합성할 수 없거나, 혹은 그 연산이 전혀 어렵지 않아서 고전적 컴퓨터가 NEXP 탐색 문제(NEXP search problem)라고 알려진 특정 유형의 어려운 문제에 대해 질문할 수 있다면 효율적으로 합성될 수 있다는 것입니다. 이 두 번째 범주는 고전 컴퓨터 이론에서 매우 높은 기준을 나타내며, 우리가 현재 해결할 수 있다고 알고 있는 가장 어려운 문제들보다 지수적으로 더 어려운 문제들을 의미합니다.

이 발견의 함의는 특히 암호학의 미래에 있어 심오합니다. 양자 암호학은 특정 작업(예를 들어, 비밀을 디지털 상자에 잠가서 변경되거나 훔쳐볼 수 없게 만드는 보안 커밋먼트 스킴(commitment scheme))을 공격자가 깨뜨리는 것이 불가능하다는 아이디어에 의존합니다. 만약 보안 양자 커밋먼트가 존재한다면, 연구자들의 논리에 따르면 우리는 매우 특정한 상황에 놓이게 됩니다. 즉, 유니터리 합성 문제에 대한 부정적인 답, 즉 고전적 합성을 넘어서는 근본적인 양자 연산이 존재하거나, 혹은 주요한 고전적 복잡도 문제가 해결되어야 한다는 것입니다. 구체적으로, 이는 BPP(무작위 확률을 사용하여 빠르게 해결할 수 있는 문제들)라는 클래스가 NEXP(지수 시간과 비결정론으로 해결할 수 있는 문제들)와 같지 않다는 것을 의미합니다. 이는 40년 넘게 열려 있었던 질문입니다.

더 간단히 말하자면, 이 논문은 보안 양자 암호학을 증명하는 것이 단지 더 나은 양자 장치를 만드는 문제가 아님을 주장합니다. 그것은 고전적 컴퓨팅의 가장 깊은 이론적 한계와 불가분하게 연결되어 있습니다. 만약 우리가 양자 커밋먼트가 안전하다는 것을 무조건적으로 증명할 수 있다면, 우리는 동시에 컴퓨터 과학의 거대한 수십 년 된 수수께끼 중 하나에 답해야만 할 것입니다. 우리는 양자 연산이 우리가 생각했던 것보다 근본적으로 더 까다로울 수 있다는 것을 받아들여야 하거나, 혹은 믿을 수 없을 정도로 강력한 특정 유형의 고률적 계산이 표준적인 무작위 계산보다 엄격히 더 유능하다는 것을 증명해야 할 것입니다.

또한 이 연구는 보다 일반적인 의미에서 양자적 힘과 고전적 힘 사이의 관계를 조명합니다. 저자들은 만약 유니터리 합성 문제가 긍정적인 답을 갖는다(즉, 모든 것이 합성 가능하다)고 가정한다면, 대량의 메모리를 가진 양자 컴퓨터의 힘은 NEXP 탐색 문제를 해결하는 고전적 컴퓨터의 힘에 의해 엄격하게 제한된다는 것을 보여주었습니다. 이는 양자 컴퓨팅의 '마법'이 존재한다면, 그것은 자유롭게 떠다니는 현상이 아니라 고전적 복잡도의 구조에 깊이 뿌리박고 있음을 시사합니다. 만약 양자 컴퓨터가 진정으로 새로운 무언가를 할 수 있다면, 그것은 고전적 컴퓨터가 최선의 지름길을 사용하더라도 도달할 수 없는 난이도의 층위에 접근하고 있기 때문입니다.

궁극적으로, 이 연구는 양자 암호학이 안전한지 또는 유니터리 합성 문제가 해결 가능한지를 말해주지는 않습니다. 대신, 이 두 가지 가능성 사이의 지형을 그려냅니다. 그것은 양자 시스템의 보안을 증명하는 경로가 지난 반세기 동안 고전적 복잡도 이론가들이 가장 어려운 문제들을 해결하지 못하게 막았던 바로 그 벽들에 의해 가로막혀 있음을 드러냅니다. 이 논문은 우리가 단순히 더 나은 것을 만들어내는 것만으로는 부족하며, 먼저 계산 자체의 근본적인 한계를 이해해야 한다고 제안합니다. 정의를 명확히 하고 엄격한 연결 고리를 확립함으로써, 크레치머와 탱은 양자 암호학의 운명과 고전적 복잡도 이론의 운명이 이전에는 이해되지 않았던 방식으로 결합되어 있음을 보여주며, 더 명확한 전망을 제공했습니다.