결과 $MIP^\ast=RE$ 양자 알고리즘에 관하여
(Pending-peer review) 증명 $MIP^\ast=RE$에서 이 미리 인쇄 중요한 돌파구로 환영하고있다. 이 결과의 중요성은 이 블로그 게시물 에서 Henry Yuen (저자 중 한 명) 이 설명 합니다. Scott Aaronson은 또한 이 블로그 게시물 에 몇 가지 주요 의미를 나열합니다 .
로컬이 아닌 게임 ($G$), 비 상대 론적 텐서 제품 전략에 대한 성공 확률의 최고치를 다음과 같이 정의하십시오. $\omega^\ast(G)$, 상대 론적 통근 연산자 (QFT) 전략에 대한 성공 확률의 최고 값은 다음과 같습니다. $\omega^{co}(G)$. 비 상대 론적 QM은 QFT의 특별한 경우이므로 최적의 통근 연산자 기반 전략은 적어도 최적의 텐서 제품 기반 전략만큼 우수합니다.$\omega^\ast(G) \le \omega^{co}(G)$.
Yuen의 게시물에 대한 나의 이해는 $MIP^\ast=RE$ 로컬이 아닌 게임이 존재한다는 것입니다. $\omega^\ast(G) < \omega^{co}(G)$. 특히 그는 말한다
게임이 있어야합니다 $G$그러면 양자 값이 정류 연산자 값과 다릅니다. 그러나 이것은 Tsirelson의 문제에 부정적인 대답이 있음을 의미하므로 Connes의 삽입 추측은 거짓입니다.
QFT (통근 연산자)의 기술을 사용하는 알고리즘이 비 상대 론적 QM (텐서 제품, 양자 회로 형식)의 기술을 사용하는 알고리즘보다 성공 확률이 더 높은 문제가 있다는 것을 이해합니다.
내 질문의 첫 번째 부분은 이 증거가 있다고 가정하는 것입니다 .
- 않습니다 $MIP^\ast=RE$ 비 상대 론적 QM 형식 (기존 양자 회로)보다 QFT (통근 연산자)의 수학적 형식을 사용하여보다 효율적으로 해결할 수있는 문제 세트가 있음을 암시합니까?
내가 잘못 해석하지 않는 한 이것은 Yuen의 진술에서 직접적으로 따르는 것 같습니다. 그렇다면 로컬이 아닌 게임 세트가있을 수 있습니까?$\omega^\ast(G) < 0.5$ 과 $\omega^{co}(G) > 0.5$? 특히 내 질문의 두 번째 부분은 다음과 같습니다.
- 않습니다 $MIP^\ast=RE$ 양자 회로를 사용하여 해결할 수없는 정류 연산자를 사용하여 해결할 수있는 일련의 문제가 있거나있을 수 있음을 암시합니까? 아니면 양자 회로 모델의 보편성에 의해 이러한 가능성이 차단됩니까?
편집 : Henry Yuen 은이 복잡성 클래스를 더 잘 이해하려는 사람들을 위해 MIP * Wiki 를 만들었습니다 .$MIP^\ast = RE$ 결과.
답변
MIP * = RE 결과인지, 특히 비 로컬 게임이 존재한다는 주장은 모르겠습니다. $G$ 어디 $\omega^*(G) \neq \omega^{co}(G)$, 양자 컴퓨터에 대한 알고리즘 의미가 있습니다. 여기서 할 말이 몇 가지 있습니다.
MIP * = RE 결과는 비 로컬 게임으로 해결할 수있는 것과는 반대로 비 로컬 게임을 사용하여 확인할 수있는 계산 문제에 대한 것입니다 (어쨌든 그것이 의미하는 바는 확실하지 않습니다!). 확인과 해결의 차이는 다음과 같은 이유 때문입니다. 로컬이 아닌 게임에서 Alice와 Bob이 문제에 대한 답을 마술처럼 알고 있다고 가정합니다 (따라서 모든 계산 문제를 즉시 해결할 수 있다고 가정합니다). 그들의 도전은 그것을 해결하는 것이 아니라 증명 하는 것입니다.다항식 시간 고전 검증 자에게 그들은 답을 알고 있습니다. 무언가에 대한 답을 안다고해서 다른 사람에게 답을 설득 할 수 있다는 의미는 아닙니다. Alice와 Bob이 텐서 제품 프레임 워크 또는 통근 연산자 프레임 워크의 상관 관계를 사용할 수 있는지 여부는 검증 자에게 증명할 수있는 것에 영향을줍니다. MIP * = RE는 텐서 곱 상관 관계를 통해 Alice와 Bob이 Turing Machine이 결국 중단된다는 것을 알 수 있음을 보여줍니다. 이것은 Alice와 Bob이 통근 연산자 상관 관계를 공유하면 할 수없는 일입니다. 따라서 통근 연산자 모델은 텐서 제품 모델과 다릅니다.
두 번째로 언급하고 싶었던 것은 정류 연산자와 무한 차원 시스템에 대해 이야기하는 양자 계산 모델을 정의 할 수 있는지 여부에 대한 흥미로운 질문입니다. Cleve 등은이를위한 모델을 만들려고 시도한 것으로 보입니다. C * 회로 모델이라고합니다.https://arxiv.org/pdf/1811.12575.pdf. 이것이 흥미로울 것입니다.