Thuật toán Simon

Trong lý thuyết độ phức tạp tính toán và tính toán lượng tử, bài toán Simon là một bài toán thuộc dạng cây quyết định hay dạng truy vấn, được diễn tả bởi Daniel Simon năm 1994. Simon đã đưa ra một thuật toán lượng tử, thường được gọi là thuật toán Simon, để giải quyết bài toán nhanh hơn rất nhiều (một số mũ lần) so với bất kì thuật toán (xác định hay xác suất) cổ điển nào.

Thuật toán Simon sử dụng $O(n)$ truy vấn trong hộp đen, trong khi thuật toán xác suất cổ điển mạnh nhất cũng phải mất tối thiểu $\Omega (2^{n/2})$ truy vấn. Thuật toán Simon cũng được coi là tốt nhất, do bất kì thuật toán lượng tử nào để giải quyết bài toán này cũng cần tối thiểu $\Omega (n)$ truy vấn. Bài toán này chỉ ra sự phân tách giữa BPP và BQP, không giống như của thuật toán Deutsch-Jozsa - phân tách P và EQP.

Mặc dù bài toán thực ra có ít ứng dụng trong thực tế, tuy nhiên nó vẫn rất đáng được chú ý khi đã tạo ra một sự tăng tốc theo hàm mũ so với các thuật toán cổ điển. Thêm vào đó, đây cũng là cơ sở ý tưởng cho Thuật toán Shor. Cả hai bài toán đều là dạng đặc biệt của bài toán nhóm con ẩn giao hoán, là bài toán đến nay đã có thuật toán lượng tử để giải quyết một cách hiệu quả.

Mô tả bài toán và thuật toán

Đầu vào của bài toán là một hàm (thực thi bởi hộp đen) $f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}$, coi như thỏa mãn điều kiện với một số $s\in \{0,1\}^{n}$ ta có với mọi $y,z\in \{0,1\}^{n}$, $f(y)=f(z)$ khi và chỉ khi $y=z$ or $y\oplus z=s$. Chú ý rằng trường hợp $s=0^{n}$ cũng được chấp nhận, tương ứng với $f$ là một hoán vị. Vấn đề cần giải quyết là tìm s.

Tập của các xâu n-bit là một không gian vec tơ $\mathbb {Z} _{2}$ dưới thao tác bit XOR. Giả sử hàm gốc của f hoặc rỗng, hoặc tạo nên các tập-hợp-chung có n-1 chiều. Sử dụng các thuật toán lượng tử, ta có thể, với xác suất cao, xác định được các véc tơ cơ sở sinh ra n-1 không gian con này, vì s là véc tơ vuông góc với toàn bộ các véc tơ cơ sở trên.

Hàm lượng tử trong thuật toán Simon

Xét không gian Hilbert chứa đựng tích ten-xơ của không gian Hilbert của các xâu đầu vào, và cho ra đầu ra là các xâu. Sử dụng biến đổi Hadamard, ta có thể tạo trạng thái ban đầu

$\sum _{x}\left|x\right\rangle \left|0\right\rangle$

và gọi hộp đen để chuyển trạng thái này thành

$\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle$

Biến đổi Hadamard chuyển trạng thái trên thành

$\sum _{y}\sum _{x}(-1)^{x.y}\left|y\right\rangle \left|f(x)\right\rangle$

Ta thực hiện đo cùng lúc ở cả hai thanh ghi. Nếu $s\cdot y=1$, ta nhận được sự giao thoa giảm. Vậy, chỉ không gian con $s\cdot y=0$ là được chọn. Thử với một số lượng y, ta có thể tìm được n-1 véc tơ cơ sở, và tính s.

Tương tự

• Thuật toán Deutsch-Jozsa

Tham khảo

1. Simon, D.R. (1994), "On the power of quantum computation", Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on: 116–123, retrieved 2011-06-06

2. Koiran, P.; Nesme, V.; Portier, N. (2007), "The quantum query complexity of the abelian hidden subgroup problem", Theoretical Computer Science 380 (1-2): 115–126,doi:10.1016/j.tcs.2007.02.057, retrieved 2011-06-06

3. Koiran, P.; Nesme, V.; Portier, N. (2005), "A quantum lower bound for the query complexity of Simon's Problem", Proc. ICALP 3580: 1287–1298, arXiv:quant-ph/0501060, retrieved 2011-06-06