양자 컴퓨팅, 양자 물리학 수학 주요 문제 해결 | 과학 모니터

1935 년 Albert Einstein은 Boris Podolsky 및 Nathan Rosen과 함께 양자 역학의 불완전 성을 입증하기 위해 비 지역성 문제를 제기했습니다.

1936 년에 앨런 튜링은 컴퓨터 프로그램이 영원히 멈추거나 반복 될 것인지를 알고리즘 적으로 결정하는 문제를 해결할 수 없다고 지적했습니다.

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

서로 독립적 인이 두 가지 아이디어는 각자의 분야에 혁명을 일으켰습니다.

시드니 기술 대학교 (UTS), 토론토 대학교, Caltech) 등 새로운 연구 논문 ‘MIP * = RE‘컴퓨터 과학에서 물리학과 수학은 수많은 열린 문제를 해결하면서 그것들을 결합했습니다.

사전 게시 된 논문 사이트 Arxiv에 게시 된 논문에 따르면 MIP (multiprover interactive proof) *와 RE는 두 가지 복잡성 클래스이며이 두 클래스는 동일합니다.

양자 얽힘 상태에서 여러 양자 증명 자와 상호 작용하는 고전적 검증 자에 의해 결정될 수있는 ‘MIP *’클래스는 재귀 적으로 열거 가능한 클래스 ‘RE’와 동일하다고 제안되었습니다. .

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

복잡성

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

또 다른 복잡성 클래스는 NP입니다. 미로를 예로 들어 질문은 예 / 아니오입니다. 미로에서 벗어날 수있는 방법이 있습니까? 대답이 ‘예’라면 우리를 설득하는 간단한 방법이 있습니다. 길을 안내하고 따라 가면 출구를 찾을 수 있습니다. 그러나 대답이 ‘아니오’이면 확실한 방법을 찾지 않고 전체 미로를 횡단해야합니다. 예 / 아니오 질문에 대한 대답이 예인 경우 귀하는 NP에 속해 있음을 효과적으로 증명할 수 있습니다. P는 NP에 포함됩니다. 핵심 질문은 아무도 P = NP인지 모른다는 것입니다.

비 지역성 게임

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

두 개체, 질문자와 증명 자 간의 상호 작용을 상상해보십시오. 경찰 심문에서 증명자는 무죄를 증명하려는 용의자 일 수 있습니다. 질문자는 증명자가 충분히 설득력이 있는지 결정해야합니다. 불균형이 있습니다. 지식 측면에서 질문자는 열등한 위치에 있습니다. 복잡성 이론에서 질문자는 제한된 계산 능력으로 문제를 해결하려는 사람입니다. Prover는 엄청난 계산 능력을 갖춘 새로운 컴퓨터입니다.

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

여러 명의 증인을 심문 할 수 있고 증인이 응답을 조작 할 수없는 경우 (일반적으로 경찰이 여러 명의 용의자를 심문하는 경우) MIP 등급에 도달합니다. 이러한 심문은 증인의 응답을 교차 검토하여 심 문자에게 더 큰 권한을 부여하므로 MIP에 IP가 포함됩니다.

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

증인 간의 의사 소통은 심문자가 진실을 발견하는 데 도움이되지 않지만 증인이 거짓말을 화해하는 데 도움이 될 수 있음이 분명해 보입니다. 따라서 더 많은 의사 소통을 허용하면 계산 문제가 더 안정적이고 해결 가능할 것이라고 아무도 예상하지 못했습니다.

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

의미

1970 년대에 Alain Connes는 Connes Embedding Problem으로 알려진 문제를 공식화했습니다. 이것은 매우 단순하며 무한 행렬을 유한 행렬로 근사 할 수 있는지 묻습니다. 새로운 논문은 von Neumann 대수 이론에 Conn의 내장 추측에 대한 반박을 제시합니다.

팀은 또한 1993 년 Boris Tsirelson에 의해 ‘Tsirelson ‘s Problem’으로 알려진 물리학 문제를 지적했습니다. 이것은 양자 역학에서 단일 상황의 두 가지 다른 수학적 형태였습니다. 지금까지 그것은 아 원자 세계를 설명하는 성공적인 이론이었습니다. 동일한 현상에 대한 두 가지 다른 설명이므로 두 형식은 수학적으로 동일 할 것으로 예상되었습니다. 그러나 이제 새로운 논문은 그렇지 않다는 것을 보여줍니다.