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 . Đơ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,  phép so sánh  sẽ được sử dụng. Để chứng minh  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  đượ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  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ố  lần tính toán cho ta xác suất đưa ra được đáp án đúng cao (khả năng sai là ). Tuy nhiên, để chắc chắn đáp án đưa ra là chính xác, ta vẫn cần tới  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, , hỏi  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  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 . 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ử.