✨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 $\backslash 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 $\backslash 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\backslash rightarrow\; \{0,1\}^n$, coi như thỏa mãn điều kiện với một số $s\backslash in\; \{0,1\}^n$ ta có với mọi $y,z\backslash in\{0,1\}^n$, $f(y)=f(z)$ khi và chỉ khi $y=z$ or $y\; \backslash 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ơ $\backslash 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. thumb|right|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 :$\backslash sum\_x\; \backslash left|\; x\; \backslash right\backslash rangle\; \backslash left|\; 0\; \backslash right\backslash rangle$ và gọi hộp đen để chuyển trạng thái này thành :$\backslash sum\_x\; \backslash left|\; x\; \backslash right\backslash rangle\; \backslash left|\; f(x)\; \backslash right\backslash rangle$ Biến đổi Hadamard chuyển trạng thái trên thành :$\backslash sum\_y\; \backslash sum\_x\; (-1)^\{x.y\}\; \backslash left|\; y\; \backslash right\backslash rangle\; \backslash left|\; f(x)\; \backslash right\backslash rangle$ Ta thực hiện đo cùng lúc ở cả hai thanh ghi. Nếu $s\; \backslash cdot\; y\; =\; 1$, ta nhận được sự giao thoa giảm. Vậy, chỉ không gian con $s\; \backslash 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