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 $f:\{0,1\}^{n}\rightarrow \{0,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, $2^{n-1}+1$ phép so sánh $f$ sẽ được sử dụng. Để chứng minh $f$ 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 $f$ đượ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 $f$ 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ố $k$ lần tính toán cho ta xác suất đưa ra được đáp án đúng cao (khả năng sai là $\epsilon \leq 1/2^{k-1}$). Tuy nhiên, để chắc chắn đáp án đưa ra là chính xác, ta vẫn cần tới $k=2^{n-1}+1$ 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, $f:\{0,1\}\rightarrow \{0,1\}$, hỏi $f$ 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 $n$ 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 $f$. 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.

mạch lượng tử của thuật toán Deutsch-Jozsa

Bắt đầu thuật toán với n+1 bit trạng thái $|0\rangle ^{\otimes n}|1\rangle$ - tức n bit đầu tiên ở trạng thái $|0\rangle$ và bit thứ n+1 ở trạng thái $|1\rangle$. Biến đổi Hadamard cho mỗi bit, ta có trạng thái

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$.

Hàm $f$ là một hộp đen lượng tử. Hộp đen biến trạng thái $|x\rangle |y\rangle$ thành $|x\rangle |y\oplus f(x)\rangle$, với $\oplus$ 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

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )$.

Với mỗi $x$, $f(x)$ là $0$ hoặc $1$. Hai trường hợp này cho ta

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )$.

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

${\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\left[(-1)^{f(x)}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}\right]|y\rangle ={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle$

với $x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}$ 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 $|0\rangle ^{\otimes n}$,

${\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}$

cho kết quả 1 nếu $f(x)$ là bất biến và 0 nếu $f(x)$ 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 $f(0)=f(1)$. Điều này tương đương với việc kiểm tra $f(0)\oplus f(1)$ (với $\oplus$ là phép cộng mô dun 2, có thể xem như cổng XOR lượng tử). Nếu bằng 0, $f$ là bất biến, ngược lại $f$ không phải là bất biến.

Ta bắt đầu với trạng thái 2-qubit $|0\rangle |1\rangle$ mà biến đổi Hadamard cho mỗi qubit, được

${\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).$

Áp dụng hàm chuyển đổi $|x\rangle |y\rangle$ thành $|x\rangle |f(x)\oplus y\rangle$ vào đây, ta có

${\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))$

$={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))$

$=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).$

Bỏ qua bit cuối cùng và phần toàn cục, ta được trạng thái

${\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).$

Sử dụng biến đổi Hadamard lên trạng thái này, sinh ra

${\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )$

$={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).$

Hiển nhiên $f(0)\oplus f(1)=0$ khi và chỉ khi ta đo được bằng 0 và $f(0)\oplus f(1)=1$ khi và chỉ khi ta đo được 1. Vậy ta kết luận được hàm $f(x)$ là bất biến hay cân bằng.

Đọc thêm

• Thuật toán Simon

Tham khảo

1. David Deutsch and Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A 439: 553
2. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca (1998). "Quantum algorithms revisited". Proceedings of the Royal Society of London A 454: 339–354
3. Certainty from Uncertainty
4. David Deutsch (1985). "The Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society of London A 400: 97
5. Lov K. Grover (1996). "A fast quantum mechanical algorithm for database search". Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 212–219
6. Peter W. Shor (1994). "Algorithms for quantum computation: discrete logarithms and factoring" (PDF). Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. pp. 124–134