Thuật toán lượng tử

Tổng quan

Thuật toán lượng tử thường được mô phỏng, trong mô hình tính toán thông qua mạch lượng tử được sử dụng phổ biến nhất, bằng một mạch lượng tử hoạt động với đầu vào là một vài qubit chứa thông tin lượng tử và kết thúc bằng việc đo lường. Một mạch lượng tử bao gồm những cổng lượng tử đơn giản hoạt động trên các qubit với số lượng xác đình, thường là 2 hoặc 3. Thuật toán lượng tử cũng có thể được diễn tả thông qua những mô hình tính toán lượng tử khác.
Những thuật toán lượng tử có thể được phân loại bằng những kĩ thuật chủ yếu được sử dụng bởi thuật toán. Một vài kĩ thuật – ý tưởng được sử dụng phổ biến trong thuật toán lượng tử bao gồm biến đổi Fourier lượng tử, khuếch đại biên độ và lý thuyết trường lượng tử topo,... Thuật toán lượng tử cũng có thể được nhóm lại bởi những loại vấn đề đã được giải quyết, ví dụ về khảo sát trên thuật toán lượng tử với những vấn đề đại số.

Thuật toán dựa trên biến đổi Fourier lượng tử

Biến đổi Fourier lượng tử là một phép biến đổi tuyến tính trên các qubit, phép biến đổi này tương tự như biến đổi Fourier rời rạc. Biến đổi Fourier lượng tử là một trong những thuật toán lượng tử quan trọng nhất, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc.
Biến đổi Fourier lượng tử dựa trên thuật toán biến đổi Fourier nhanh của James Cooley và John Tukey. Nó có thể được thực hiện hiệu quả trên máy tính lượng tử, bởi nó có thể triệt tiêu các thành phần bằng cách nhân với các ma trận unita (áp dụng toán tử). Biến đổi Fourier lượng tử có thể được cài đặt và thực hiện trên một mạch lượng tử.

Ước lượng các tổng Gauss

Một tổng Gauss là một loại tổng theo hàm số mũ. Thuật toán cổ điển nổi tiếng nhất về ước lượng những tổng này hoạt động với thời gian chạy theo hàm số mũ. Bởi vì vấn đề logarit rời rạc làm rút gọn phép ước lượng tổng Gauss nên một thuật toán cổ điển hiệu quả về việc ước lượng các tổng Gauss sẽ bao hàm một thuật toán cổ điển hiệu quả về tính toán logarit rời rạc, điều mà không chắc có được. Tuy nhiên, các máy tính lượng tử có thể ước lượng các tổng Gauss đển độ chính xác đa thức trong thời gian đa thức.

Bài toán cân cá và kiểm tra Fourier

Chúng ta có một máy oracle gồm có n hàm Boolean ngẫu nhiên ánh xạ n xâu bit nhị phân vào một giá trị Boolean. Chúng ta được yêu cầu tìm n xâu bit nhị phân z₁, …, zₙ sao cho với phép biển đổi Hadamard – Fourier, ít nhất ¾ các xâu bit thỏa mãn.
Và ít nhất ¼ thỏa mãn
Điều này có thể thực hiện bởi thuật toán xác suất chặn lỗi.

Những thuật toán dựa trên khuếch đại biên độ

Khuếch đại biên độ là một kĩ thuật cho phép khuếch đại trên một vùng không gian con xác định của một trạng thái lượng tử. Những ứng dụng của khuếch đại biên độ thường dẫn đến sự tăng tốc bậc hai trên những thuật toán cổ điển tương ứng. Nó có thể được coi như là một sự tổng quát hóa của thuật toán Grover.

Đếm lượng tử

Đếm lượng tử giải quyết một cách tổng quát các vấn đề tìm kiếm. Phương pháp này giải quyết vấn đề thông qua đếm số lượng các phần tử được đánh dấu trong một danh sách không có thứ tự, thay vì chỉ phát hiện ra khi một phần tử tồn tại. Đặc biệt hơn nữa, nó có thể đếm số lượng những phần tử được đánh dấu trong danh sách N phần tử, với lỗi  thuộc trong khoảng   truy vấn, trong đó  là số lượng phần tử được đánh dấu trong danh sách. Chính xác hơn nữa, thuật toán có đầu ra  là một ước lượng với , số lượng phần tử được đánh dấu, cùng với độ chính xác phép đo .

Đánh giá công thức

Một công thức là một cái cây với một cổng tại mỗi nút trong một bit đầu vào tại mỗi nút lá. Vấn đề là phải đánh giá công thức, cái mà đầu ra nằm ở nút gốc, được cho bởi truy cập oracle tới đầu vào. Một công thức nghiên cứu tốt là một cây nhị phân cân bằng với chỉ cổng NAND. Loại công thức này đòi hỏi Θ(Nᶜ) truy vấn sử dụng một cách ngẫu nhiên (nơi mà  ) nhưng có thể được giải quyết qua Θ(N0.5) truy vấn bởi một thuật toán lượng tử. Không có thuật toán lượng tử nào tốt hơn cho trường hợp này được biết đến tới tận khi một công thức được tìm ra cho mô hình máy oracle Hamiltonian khác biệt. Kết quả tương tự cho thiết lập chuẩn mực sớm được theo dõi.
Những thuật toán lượng tử nhanh cho những hàm phức tạp hơn cũng được biết đến.

Nhóm giao hoán

Vấn đề là phải xác định liệu một nhóm hộp đen, cho bởi k hàm sinh, có giao hoán hay không. Một nhóm hộp đen là một nhóm với một hàm oracle, hàm mà hẳn đã được dùng để thể hiện một nhóm các toán tử (nhân, nghịch đảo, và so sánh với đồng nhất thức). Chúng ta quan tâm tới độ phức tạp truy vấn, tức là số lượng của những lời gọi oracle cần tới để giải quyết bài toán. Những độ phức tạp truy vấn một cách xác định và ngẫu nhiên là  và   một cách tương ứng. Một thuật toán lượng tử đòi hỏi   truy vấn nhưng thuật toán nổi tiếng nhất sử dụng   truy vấn.

Lượng tử bất biến tính toán nút

Witten đã chỉ ra rằng và lý thuyết thuyết trường lượng tử topo Chern – Simons (TQFT) có thể được giải quyết trong trường hợp của những đa thức Jones. Một máy tính lượng tử có thể dựa theo một TQFT, và vì thế xấp xỉ với những đa thức Jones, điều mà như chúng ta biết là rất khó để tính toán một cách cổ điển trong trường hợp tồi nhất.

Mô hình hóa lượng tử

Vấn đề mà những máy tính lượng tử có thể mạnh hơn máy tính cổ điển bắt nguồn từ quan điểm của Richard Feynman rằng tất cả những máy tính cổ điển có vẻ đòi hỏi thời gian đa thức để mô hình hóa những hệ thống lượng tử đa hạt. Từ đó, ý tưởng về những máy tính lượng tử có thể mô hình hóa các quá trình vật lý lượng tử theo hàm số mũ nhanh hơn những máy tính cổ điển được hình thành. Những thuật toán lượng tử có hiệu suất đã được phát triển để mô phỏng các hệ thống hạt boson và fermion. Trong một số trường hợp nhất định, việc mô hình hóa các phản ứng hóa học vượt quá khả năng của siêu máy tính cổ điển hiện thời chỉ đòi hỏi một vài trăm qubit. Những máy tính lượng tử cũng có thể mô hình hóa một cách có hiệu quả lý thuyết trường lượng tử topo. Bên cạnh mối quan tâm bản chất bên trong của nó, kết quả này đã dẫn đến những thuật toán lượng tử có hiệu suất cao trong việc ước lượng sự bất biến topo "lượng tử " như là những đa thức Jones và HOMFLY.