Tách BQP và PH

Question

Tôi đang đọc bài báo Quanta ở đây cho thấy rằng có một vấn đề tồn tại trong việc đạt được "sự phân tách kỳ diệu giữa BQP và PH". Nói một cách dễ hiểu, tồn tại một vấn đề mà máy tính lượng tử có thể giải quyết với số lần gọi tới nhà tiên tri ít hơn nhiều so với máy tính cổ điển có thể (ngay cả trong lĩnh vực mà P = NP).

Tại sao đây là một kết quả mạnh hơn thuật toán Deutsch-Jozsa nổi tiếng để quyết định xem một hàm là hằng số hay cân bằng? Trong trường hợp đó, một máy tính cổ điển phải làm$O(n)$gọi đến một tiên tri (hàm) trong khi một máy tính lượng tử có thể làm như vậy với một truy vấn duy nhất. Điều này không chứng minh rằng máy tính lượng tử khác biệt với bất kỳ máy tính cổ điển nào, ngay cả khi P = NP?

Answer 1

Vấn đề Deutsch-Josza cung cấp một sự tách biệt kỳ diệu giữa $\mathsf{EQP}$ (thời gian lượng tử-đa thức chính xác) và $\mathsf{P}$, nhưng không có sự loại trừ nào chống lại việc thêm ngẫu nhiên để có được một thuật toán cổ điển hiệu quả.

Ví dụ: vấn đề Deutsch-Josza rất nhỏ trong $\mathsf{BPP}$. Người ta chỉ có thể thực hiện một số lượng nhỏ cuộc gọi đến nhà tiên tri; Nếu bạn từng thấy hai đầu ra khác nhau, bạn biết rằng tiên tri là cân bằng, nhưng nếu bạn luôn thấy cùng một kết quả thì bạn có thể kết luận rằng tiên tri là không đổi với xác suất cao.

Hơn nữa, có một phỏng đoán derandomization hợp lý rằng $\mathsf{BPP}$ bằng $\mathsf{P}$. Do đó, vấn đề Deutsch-Josza nằm trong$\mathsf{P}$, modulo một phỏng đoán derandomization như vậy.

Tuy nhiên, "vấn đề tương quan" được xem xét trong bài báo Raz-Tal và được thảo luận trong bài báo Quanta cung cấp một sự tách biệt kỳ diệu giữa $\mathsf{BQP}$ và $\mathsf{PH}$. Vấn đề tương quan này không có khả năng xảy ra trong$\mathsf{BPP}$.

Ví dụ: với xác suất cao, bạn không thể chạy tiên tri của mình với một máy tính cổ điển trong thời gian đa thức, sau đó sử dụng thứ gì đó tương tự như giới hạn của Chernoff trên các kết quả đầu ra để xác định xem phân phối đã cho là phân phối đồng nhất hay phân phối tương quan.