Thuật toán Deutsch-Jozsa

Thuật toán Deutcsh-Jozsa là một thuật toán lượng tử, đưa ra bởi David Deutsch và Richard Jozsa năm 1992 với những cải tiến bởi Richard Cleve, Artur Ekert, Chiara Macchiavello, và Michele Mosca năm 1998. Mặc dù ít có ứng dụng trong thực tế nhưng đây là một trong những ví du đầu tiên cho thấy một thuật toán lượng tử có thể chạy nhanh hơn rất nhiều (một số mũ lần) so với một thuật toán xác định cổ điển. Đây cũng là một thuật toán xác định, tức là nó luôn luôn trả về đáp án, và đáp án này luôn chính xác.
Bài toán.
Trong bài toán Deutsch-Jozsa, ta có một hộp đen máy tính lượng tử thực thi hàm formula_1. Đơn giản mà nói, nó nhận đầu vào là một giá trị nhị phân gồm n ký tự và trả về giá trị 0 hoặc 1. Coi như hàm f hoặc là bất biến (trả về 0 cho mọi đầu vào, hoặc trả về 1 cho mọi đầu vào) hoặc là cân bằng (trả về 0 cho 1 nửa số đầu vào, trả về 1 cho nửa còn lại); nhiệm vụ của chúng ta là xác định xem f là bất biến hay cân bằng dựa vào hộp đen.
Động lực.
Bài toán Deutsch-Jozsa được thiết kế đặc biệt sao cho có thể dễ đang giải được bằng thuật toán lượng tử, tuy nhiên lại khó cho các thuật toán xác định cổ điển. Động lực tạo ra từ bài toán là: chứng minh một bài toán hộp đen có thể được giải quyết rất hiệu quả bằng máy tính lượng tử, nhưng nếu dùng máy tính cổ điển thì phải đòi hỏi hơn rất nhiều (gấp một số mũ lần) truy vấn tới hộp đen. Nói cách khác, nó phân biệt EQP - lớp bài toán có thể giải hoàn toàn chính xác trong thời gian đa thức trên máy tính lượng tử, với P, là khác nhau.
Do bài toán có thể được giải một cách dễ dàng với một thuật toán xác suất trên máy tính cổ điển, nó không thể phân biệt BPP ra với BQP. Để tách biệt 2 dạng bài toán này, bài toán Simon đã ra đời.
Giải pháp cổ điển.
Một thuật toán xác định thông thường trong trường hợp xấu nhất với "n" là số bits/qubits, formula_2 phép so sánh formula_3 sẽ được sử dụng. Để chứng minh formula_3 là bất biến, chỉ cần quá nửa tập đầu vào được tính toán và đầu ra của chúng là giống hệt nhau (lưu ý rằng hàm formula_3 được đảm bảo chỉ có thể là bất biến hoặc cân bằng). Trường hợp tốt nhất là khi hàm formula_3 là cân bằng và 2 đầu ra đầu tiên cho 2 giá trị khác nhau. Với một thuật toán ngẫu nhiên thông thường, một hằng số formula_7 lần tính toán cho ta xác suất đưa ra được đáp án đúng cao (khả năng sai là formula_8). Tuy nhiên, để chắc chắn đáp án đưa ra là chính xác, ta vẫn cần tới formula_9 lần xác định. Thuật toán lượng tử Deutsch-Jozsa cho ta đáp án chính xác với chỉ một lần tính toán.
Lịch sử.
Thuật toán Deutsch-Jozsa cơ bản ra đời năm 1985 bởi David Deutsch, đưa ra đáp án cho trường hợp đơn giản.
Với đầu vào là biến logic 1 bit, formula_10, hỏi formula_3 có phải bất biến không?
Thuật toán ban đầu Deutsch đưa ra không phải là thuật toán xác định. Thuật toán chỉ đúng với xác suất là 1/2.
Năm 1992, Deutsch và Jozsa tạo ra một thuật toán xác định tổng quát hóa cho trường hợp đầu vào formula_12 bits. Không như thuật toán của Deutsch, thuật toán này đòi hỏi hai lần tính toán chứ không phải một.
Một cải tiến nữa của thuật toán Deutsch-Jozsa được đề xuất bởi Cleve et al. Tạo nên một thuật toán vừa xác định, vừa chỉ yêu cầu đúng một lần truy xuất formula_3. Tuy nhiên, thuật toán này vẫn chỉ được lấy tên là Deutsch-Jozsa để ghi nhận những cống hiến đột phá của họ.
Thuật toán Deutsch-Jozsa đã truyền cảm hứng cho Thuật toán Shor và Thuật toán Grover ra đời, đây là 2 trong số những thuật toán lượng tử có ý nghĩa nhất trong cuộc cách mạng lượng tử.
Tính đồng pha.
Để thuật toán Deutsch-Jozsa hoạt động, hộp đen tính toán f(x) từ x phải là một hộp đen lượng tử không làm mất tính đồng pha của x. Cũng không được có một bản sao nào của x sau quá trình gọi hộp đen.
Bắt đầu thuật toán với n+1 bit trạng thái formula_14 - tức n bit đầu tiên ở trạng thái formula_15 và bit thứ n+1 ở trạng thái formula_16. Biến đổi Hadamard cho mỗi bit, ta có trạng thái
Hàm formula_3 là một hộp đen lượng tử. Hộp đen biến trạng thái formula_19 thành formula_20, với formula_21 là phép cộng mô đun 2 (xem bên dưới cho rõ thêm). Qua hộp đen lượng tử, ta được
Với mỗi formula_23, formula_24 là formula_25 hoặc formula_26. Hai trường hợp này cho ta
Lúc này, ta có thể bỏ qua qubit cuối cùng. Sử dụng biến đổi Hadamard vào mỗi qubit, ta được
với formula_29 là tổng của tích các phép biến đổi trên bit.
Cuối cùng, ta xét trường hợp formula_30,
cho kết quả 1 nếu formula_24 là bất biến và 0 nếu formula_24 là cân bằng.
Thuật toán của Deutsch.
Thuật toán của Deutsch là một trường hợp đặc biệt của thuật toán Deutsch-Jozsa. Ta phải kiểm tra điều kiện formula_34. Điều này tương đương với việc kiểm tra formula_35 (với formula_21 là phép cộng mô dun 2, có thể xem như cổng XOR lượng tử). Nếu bằng 0, formula_3 là bất biến, ngược lại formula_3 không phải là bất biến.
Ta bắt đầu với trạng thái 2-qubit formula_39 mà biến đổi Hadamard cho mỗi qubit, được
Áp dụng hàm chuyển đổi formula_41 thành formula_42 vào đây, ta có
Bỏ qua bit cuối cùng và phần toàn cục, ta được trạng thái
Sử dụng biến đổi Hadamard lên trạng thái này, sinh ra
Hiển nhiên formula_49 khi và chỉ khi ta đo được bằng 0 và formula_50 khi và chỉ khi ta đo được 1. Vậy ta kết luận được hàm formula_24 là bất biến hay cân bằng.