Hậu quả của $MIP^\ast=RE$ Về thuật toán lượng tử

Question

Bằng chứng (đang chờ đánh giá ngang hàng) về $MIP^\ast=RE$trong bản in trước này đã được ca ngợi là một bước đột phá đáng kể. Ý nghĩa của kết quả này được Henry Yuen (một trong những tác giả) giải thích trong bài đăng trên blog này . Scott Aaronson cũng liệt kê một số ý nghĩa chính trong bài đăng trên blog này .

Đối với một trò chơi không cục bộ ($G$), xác định xác suất thành công tối cao cho các chiến lược sản phẩm tensor không tương đối tính như $\omega^\ast(G)$và xác suất thành công tối đa cho chiến lược toán tử đi lại tương đối tính (QFT) là $\omega^{co}(G)$. Vì QM không tương đối tính là một trường hợp đặc biệt của QFT, rõ ràng là chiến lược dựa trên điều hành viên đi lại tối ưu ít nhất cũng tốt như chiến lược dựa trên sản phẩm tensor tối ưu,$\omega^\ast(G) \le \omega^{co}(G)$.

Sự hiểu biết của tôi về bài đăng của Yuen là một trong những hệ quả của $MIP^\ast=RE$ là các trò chơi phi địa phương tồn tại để $\omega^\ast(G) < \omega^{co}(G)$. Cụ thể, anh ấy nói

Phải có một trò chơi $G$, sau đó, giá trị lượng tử khác với giá trị toán tử đi lại. Nhưng điều này ngụ ý rằng vấn đề của Tsirelson có một câu trả lời phủ định, và do đó phỏng đoán nhúng của Connes là sai.

Tôi hiểu điều này có nghĩa là có một loại vấn đề mà các thuật toán sử dụng kỹ thuật từ QFT (toán tử đi lại) có xác suất thành công cao hơn so với các thuật toán sử dụng kỹ thuật từ QM phi tương đối tính (sản phẩm tensor, chủ nghĩa hình thức mạch lượng tử).

Phần đầu tiên của câu hỏi của tôi là, giả sử bằng chứng này là :

• Làm $MIP^\ast=RE$ ngụ ý rằng có một tập hợp các vấn đề có thể được giải quyết hiệu quả hơn bằng cách sử dụng phương thức toán học QFT (toán tử đi lại) thay vì phương thức QM phi tương đối tính (mạch lượng tử thông thường)?

Trừ khi tôi hiểu sai, điều này dường như tiếp nối trực tiếp từ những tuyên bố của Yuen. Nếu đúng như vậy, liệu có tồn tại một tập hợp các trò chơi không dành cho địa phương mà$\omega^\ast(G) < 0.5$ và $\omega^{co}(G) > 0.5$? Cụ thể, phần thứ hai của câu hỏi của tôi là:

• Làm $MIP^\ast=RE$ ngụ ý rằng có (hoặc có thể có) một tập hợp các vấn đề có thể được giải quyết bằng cách sử dụng các toán tử đi lại mà không thể giải quyết được bằng cách sử dụng mạch lượng tử, hay khả năng này bị che khuất bởi tính phổ quát của mô hình mạch lượng tử?

CHỈNH SỬA: Henry Yuen đã tạo MIP * Wiki cho những người muốn hiểu rõ hơn về lớp phức tạp này hoặc$MIP^\ast = RE$ kết quả.

Answer 1

Tôi không biết liệu kết quả MIP * = RE hay không, và cụ thể là tuyên bố rằng có tồn tại một trò chơi phi địa phương $G$ Ở đâu $\omega^*(G) \neq \omega^{co}(G)$, có bất kỳ ý nghĩa thuật toán nào đối với máy tính lượng tử. Có một vài điều cần nói ở đây.

Kết quả MIP * = RE là về những vấn đề tính toán nào có thể được xác minh bằng cách sử dụng trò chơi phi địa phương, trái ngược với những gì có thể giải quyết bằng trò chơi phi địa phương (dù sao thì tôi cũng không chắc điều đó có nghĩa là gì!). Sự khác biệt giữa xác minh và giải là do những điều sau: trong một trò chơi phi địa phương, chúng tôi giả định rằng Alice và Bob biết câu trả lời cho vấn đề một cách kỳ diệu (vì vậy chúng tôi giả định rằng họ có thể giải quyết bất kỳ vấn đề tính toán nào ngay lập tức). Thách thức của họ không phải là giải quyết nó, mà là chứng minhvới một trình xác minh cổ điển thời gian đa thức, họ biết câu trả lời. Chỉ biết câu trả lời cho điều gì đó không có nghĩa là bạn có thể thuyết phục người khác về câu trả lời. Việc Alice và Bob có thể sử dụng các mối tương quan từ khung sản phẩm tensor hoặc khung điều hành đi lại ảnh hưởng đến những gì họ có thể chứng minh với người xác minh. MIP * = RE cho thấy rằng, với tương quan sản phẩm tensor, Alice và Bob có thể chứng minh rằng họ biết Máy Turing cuối cùng sẽ dừng lại. Đây là điều không thể thực hiện được nếu Alice và Bob chia sẻ các mối tương quan về toán tử đi lại; do đó mô hình toán tử đi lại khác với mô hình sản phẩm tensor.

Điều thứ hai tôi muốn đề cập là, một cách riêng biệt, đó là một câu hỏi thú vị liệu người ta có thể định nghĩa một mô hình tính toán lượng tử nói về các toán tử đi lại và các hệ thống chiều vô hạn hay không. Có vẻ như Cleve, et al đã cố gắng đưa ra một mô hình cho điều này, cái mà họ gọi là mô hình mạch C *:https://arxiv.org/pdf/1811.12575.pdf. Bạn có thể thấy điều này thú vị.