1935년에 알버트 아인슈타인(Albert Einstein)은 보리스 포돌스키(Boris Podolsky)와 네이선 로젠( Nathan Rosen)과 함께 양자역학의 불완전함을 입증하기 위해 비국소성(non-locality) 문제를 제기했다.

1936년 엘런 튜링(Alan Turing)은 컴퓨터 프로그램이 중단되는지 또는 영원히 반복되는지를 알고리즘적으로 결정하는 문제를 해결할 수 없음을 지적했다.

이후 알고리즘 해법과 함께 효율성을 기준으로 솔루션을 분류하는 것이 중요했졌다. 복잡성 이론은 문제 해결이 얼마나 어려운지에 따라 문제를 분류한다. 문제의 어려움은 계산이 얼마나 오래 지속되는지로 측정된다.

서로 무관했던 이 두 가지 아이디어는 각자의 분야에 혁명을 일으켰다.

시드니기술대(UTS), 토론토대(University of Toronto), 칼텍(Caltech) 등 공동 연구팀은 새로운 연구논문 ‘MIP * = RE‘에서 컴퓨터 과학, 물리학 및 수학 분야의 수많은 열린 문제를 해결하면서 이들을 결합했다.

출판전 논문사이트 아르시브(arxiv)에 공개된 논문은 MIP(multiprover interactive proof)*와 RE는 두 가지 복잡성 클래스(complexity classes)로 이 두 클래스가 동일하다는 것을 보여준다.

양자 얽힘(entanglement) 상태의 여러 양자 증명자(provers)와 상호 작용하는 고전적 검증자(verifier)에 의해 결정될 수 있는 클래스 ‘MIP *’가 재귀적으로 열거 가능한 클래스 ‘RE’와 동일함을 제시했다.

RE는 컴퓨터로 해결할 수 있는 문제를 의미한다.

복잡성

클래스 P는 알려진 알고리즘이 신속하게(기술적으로 다항식 시간에) 해결할 수 있는 문제로 구성된다. 예를 들어, 긴 곱셈은 문제를 해결하는 효율적인 알고리즘이기 때문에 두 숫자를 곱하는 것은 P에 속한다. 숫자의 소인수를 찾는 문제는 P에 있는 것으로 알려져 있지 않다. 문제는 확실히 컴퓨터로 해결할 수 있지만 알려진 효율적 해결 알고리즘은 없다. 주어진 숫자가 소수인지를 결정하는 관련 문제는 효율적인 알고리즘이 이 문제가 P에 있음을 보여준 2004년까지 비슷한 문제였다.

또 다른 복잡성 클래스는 NP다. 미로를 예로 들면, 미로에서 빠져 나갈 방법이 있는가라는 예 / 아니요 질문이다. 대답이 ‘예’인 경우 우리를 설득 할 수있는 간단한 방법이 있다. 단순히 방향을 알려주고 따라 가면 출구를 찾을 수 있다. 그러나 대답이 ‘아니요’라면 확실한 방법을 찾지 못한 채 전체 미로를 횡단해야한다. 예 / 아니오 문제에 대한 대답이 예이면 NP에 속하는 것을 효율적으로 입증할 수 있다. P는 NP에 포함된다. 핵심 질문 P = NP인지 여부는 아무도 모른다.

비국소성 게임

지금까지 설명한 클래스는 일반 컴퓨터가 직면한 문제로 이제 새로운 양자 컴퓨터가 개발되고 있다. 이제 양자 컴퓨터가 등장해 난제 중 하나를 해결한다고 주장한다면 그것이 옳다는 것을 어떻게 신뢰할 수 있는가?

질문자와 증명자라는 두 개체 간의 상호 작용을 상상해보자. 경찰 심문에서 증명자는 무죄를 증명하려는 용의자일 수 있다. 질문자는 증명자가 충분히 설득력이 있는지 여부를 결정해야한다. 불균형이 있다. 지식면에서 질문자는 열등한 위치에 있다. 복잡성 이론에서 질문자는 계산 능력이 제한돼 문제를 해결하려는 사람이다. 증명자는 엄청난 계산 능력을 가진 새로운 컴퓨터다.

대화형 증명 시스템은 검증자가 신뢰할 수 있는 지 여부를 최소한 높은 확률로 결정하기 위해 질문자가 사용할 수 있는 프로토콜이다. 비유하자면 이것은 경찰이 해결할 수 없는 범죄이지만 적어도 무고한 사람들은 경찰에게 무죄를 확신할 수 있다. 이것은 클래스 IP다.

여러 명의 증인을 심문할 수 있고 증인들이 답변을 조작할 수 없는 경우(일반적으로 경찰이 여러 명의 용의자를 심문하는 경우와 같이), 클래스 MIP에 도달한다. 이러한 심문은 증명자의 응답을 교차 조사해 심문자에게 더 큰 권한을 제공하므로 MIP에는 IP가 포함된다.

양자 통신은 큐비트로 수행되는 새로운 형태의 통신이다. 얽힘 즉, 큐비트가 분리되어 있어도 얽힘 상태 양자 특성으로 인해 양자 통신은 일반 통신과 근본적으로 다르다. MIP가 얽힌 큐비트를 공유하면 MIP * 클래스가 된다.

증언자 간의 의사 소통은 심문자가 진실을 발견하는 데 도움이 되지 않고 증언자가 거짓말을 조정하는 데 도움이 될 수 있다는 것이 분명해 보인다. 그렇기 때문에 더 많은 통신을 허용하는 것이 계산 문제를 더 안정적이고 해결 가능하게 만들 것이라고 아무도 예상하지 못했다.

MIP * = RE는 양자 통신이 일반 통신과 다르게 작동함을 설명한다.

의미

1970년대에 알랭 콘(Alain Connes)은 ‘Connes Embedding Problem’으로 알려진 문제를 공식화했다. 이것은 매우 단순화해 무한 행렬을 유한 행렬로 근사할 수 있는 지 여부를 물었다. 새로운 논문은 폰 노이만 대수 이론에서 콘의 임베딩 추측(embedding conjecture)에 대한 반박을 제시했다.

또 연구팀은 1993년 보리스 치렐슨(Boris Tsirelson)은 ‘Tsirelson’s Problem’로 알려진 물리학 문제를 지적했다. 이것은 양자 역학의 단일 상황에 대한 두 가지 다른 수학적 형식에 관한 것이었다. 현재까지 아 원자 세계를 설명하는 성공적인 이론이었다. 동일한 현상에 대한 두 가지 다른 설명이기 때문에 두 형식이 수학적으로 동등할 것으로 예상됐다. 그러나 이제 새로운 논문은 그렇지 않다는 것을 보여준다.