Deutsch-Jozsa hiểu lầm

Sep 20 2020

Tôi không hiểu thuật toán Deutsch-Jozsa. Như wikipedia gợi ý:${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$. Hàm nhận các giá trị nhị phân gồm n chữ số làm đầu vào và tạo ra 0 hoặc 1 làm đầu ra cho mỗi giá trị đó. Chúng tôi được hứa rằng hàm là không đổi (0 trên tất cả các đầu ra hoặc 1 trên tất cả các đầu ra) hoặc cân bằng (trả về 1 cho một nửa miền đầu vào và 0 cho nửa còn lại). Nhiệm vụ sau đó là xác định xem {\ displaystyle f} f là hằng số hay cân bằng bằng cách sử dụng tiên tri.

Câu hỏi 1: Nếu tôi sử dụng thuật toán xác suất trên một máy tính thông thường, tôi không thể chỉ nhập một lần duy nhất một số 0 trong tiên tri, sau đó nhập một lần duy nhất 1. Và tôi đã hoàn thành.

Tôi cũng đọc ở đây: http://www.diva-portal.org/smash/get/diva2:840938/FULLTEXT01.pdf: Hãy xem xét rằng Bob tạo một danh sách có độ dài tùy ý từ một hàm cân bằng. Sau đó, danh sách sẽ chứa nhiều số không và số bằng nhau, do đó nếu Alice vẽ một phần tử ngẫu nhiên trong danh sách, nó sẽ là một số không hoặc một phần tử với xác suất là 1/2. Nếu cô ấy vẽ hai yếu tố. thì cô ấy có thể nhận được các kết quả "00", "01", "10" và "11", mỗi kết quả có xác suất bằng nhau là 1/4. Nếu bây giờ Alice phải đoán xem hàm không đổi hay cân bằng, cô ấy sẽ đoán đúng một nửa số lần. Thay vào đó, nếu cô ấy rút ra phần tử thứ ba, kết quả sẽ là một phân phối xác suất đồng nhất so với các kết quả có thể có sau đây "000", "001", "010", "011", "100", "101", "110" và "111 ”. Alice bây giờ sẽ đoán đúng sáu trong tám lần.

Câu hỏi 2: Vì vậy, nếu cô ấy có "001" (hoặc trước "01" / "10") thì đó không phải là một hàm cân bằng?

Trả lời

1 MarkS Sep 20 2020 at 08:42

Về câu hỏi đầu tiên của bạn, có $n$ đầu vào cho $f$ và nhiệm vụ là xác định xem $f$là không đổi hoặc cân bằng (dưới lời hứa rằng nó là cái này hay cái kia); bạn có thể thực hiện việc này trên máy tính lượng tử với một truy vấn duy nhất để$f$. Nếu$n=1$, thì theo cách cổ điển, bạn có thể làm như bạn đề xuất, nhập $0$ cho một truy vấn và đầu vào $1$ cho một truy vấn khác, tổng cộng là hai truy vấn, nhưng máy tính lượng tử vẫn thắng với chỉ một truy vấn.

Về câu hỏi thứ hai của bạn, có bạn đúng; Nếu cổ điển bạn nhận được hai đầu ra khác nhau, thì (theo lời hứa), bạn có thể chắc chắn rằng hàm được cân bằng. Tuy nhiên, Deutsch-Josza lưu ý rằng bạn có thể đảm bảo nó cân bằng chỉ với một truy vấn duy nhất .

Thông thường, bạn cần ít nhất hai và tối đa $2^{n-1}+1$, các truy vấn, nhưng về mặt cơ học lượng tử thì chỉ cần một truy vấn duy nhất là đủ.

1 luciano Sep 20 2020 at 20:28

Nếu bạn chưa có, hãy bắt đầu bằng cách xem thuật toán Deutsch, đây là phiên bản qubit đơn của thuật toán Deutsch-Jozsa mà bạn đang xem.