Một câu hỏi về việc thực hiện tính toán lượng tử trên các chồng chất thống nhất

bạn có thể chạy Thuật toán Grover ở trên cùng $n$ bit của thanh ghi cho $2^{n/2}$ các bước, nhưng điều này có thể kém hiệu quả hơn bạn mong đợi.

Bất cứ thứ gì tốt hơn Grover đều không có khả năng hoạt động (Tôi không chắc Zalka không đi được bao xa dẫn đến "Thuật toán tìm kiếm lượng tử của Grover là tối ưu" mở rộng sang phần sau). Thuật toán như vậy sẽ đủ để đảo ngược một hoán vị tùy ý trên $\mathbb F_2^n$ (và do đó bất kỳ hoán vị nào là một hệ quả tất yếu). Để thấy điều này, giả sử chúng ta được phú cho một mạch điện $U_\pi$ để đánh giá hoán vị bí ẩn của chúng tôi $\pi(x)$. Chúng tôi tạo ra trạng thái $|\phi\rangle|0^n\rangle$ và áp dụng $U_\pi$ để có được $|\psi\rangle:=\sum 2^{-n/2}|x\rangle|\pi(x)\rangle$. Lưu ý rằng trận chung kết $n$ các bit ở trạng thái $|\phi\rangle$ bởi vì $\pi$ là một hoán vị. Nếu hoán đổi nửa đầu và nửa sau của thanh ghi thì chúng ta có $\sum 2^{-n/2}|x\rangle|\pi^{-1}(x)\rangle$ và chạy thuật toán giả định của chúng tôi cho vấn đề của bạn sẽ cho phép chúng tôi tính toán $\pi^{-1}(x^*)$ bất cứ gì $x^*$. Hạn chế trong trường hợp $0^n$ làm gì để giảm sức mạnh của một thuật toán như vậy bằng cách xem xét chức năng (hoán vị tương ứng) $f(x\oplus x^*)$ (tương ứng $\pi(x)\oplus x^*$).