Năm 1994, một nhà toán học đã tìm ra cách làm cho máy tính lượng tử làm được điều mà không máy tính cổ điển thông thường nào có thể làm được. Công trình tiết lộ rằng, về nguyên tắc, một cỗ máy dựa trên các quy tắc cơ học lượng tử có thể phân tích một cách hiệu quả một số lượng lớn thành thừa số nguyên tố của nó – một nhiệm vụ khó khăn đến mức đối với một máy tính cổ điển đến nỗi nó tạo thành nền tảng cho phần lớn bảo mật internet ngày nay.
Một sự lạc quan dâng lên theo sau. Có lẽ, các nhà nghiên cứu nghĩ rằng, chúng ta sẽ có thể phát minh ra các thuật toán lượng tử có thể giải quyết một loạt các vấn đề khác nhau.
Nhưng tiến độ bị đình trệ. “Đó là một quỹ đạo hơi tồi tệ,” nói Ryan O'Donnell của Đại học Carnegie Mellon. “Mọi người nói, 'Điều này thật tuyệt vời, tôi chắc chắn rằng chúng ta sẽ có được tất cả các loại thuật toán tuyệt vời khác.' Không." Các nhà khoa học đã phát hiện ra những tốc độ đáng kinh ngạc chỉ đối với một nhóm vấn đề hẹp, duy nhất từ trong một bộ tiêu chuẩn gọi là NP, nghĩa là họ đã có các giải pháp hiệu quả có thể kiểm chứng - chẳng hạn như bao thanh toán.
Đó là trường hợp của gần ba thập kỷ. Sau đó vào tháng XNUMX, các nhà nghiên cứu phát minh một dạng vấn đề mới về cơ bản mà một máy tính lượng tử có thể giải nhanh hơn theo cấp số nhân so với một dạng bài toán cổ điển. Nó liên quan đến việc tính toán các đầu vào cho một quá trình toán học phức tạp, chỉ dựa trên các đầu ra lộn xộn của nó. Cho dù vấn đề là đơn lẻ hay là vấn đề đầu tiên trong một biên giới mới của nhiều người khác vẫn chưa được xác định.
“Có một cảm giác phấn khích,” nói Vinod Vaikuntanathan, một nhà khoa học máy tính tại Viện Công nghệ Massachusetts. "Rất nhiều người đang nghĩ về những gì khác ngoài đó."
Các nhà khoa học máy tính cố gắng hiểu những gì máy tính lượng tử làm tốt hơn bằng cách nghiên cứu các mô hình toán học đại diện cho chúng. Thông thường, họ tưởng tượng một mô hình máy tính lượng tử hoặc máy tính cổ điển được ghép nối với một máy tính toán lý tưởng được gọi là nhà tiên tri. Oracles giống như các hàm toán học hoặc chương trình máy tính đơn giản, nhận một đầu vào và đưa ra một đầu ra được xác định trước. Chúng có thể có một hành vi ngẫu nhiên, xuất ra “có” nếu đầu vào nằm trong một phạm vi ngẫu nhiên nhất định (giả sử, từ 12 đến 67) và “không” nếu không. Hoặc chúng có thể là định kỳ, do đó đầu vào từ 1 đến 10 trả về “có”, 11 đến 20 trả về “không”, 21 đến 30 trả về “có” một lần nữa, v.v.
Giả sử bạn có một trong những phép lạ định kỳ này và bạn không biết chu kỳ. Tất cả những gì bạn có thể làm là cung cấp các con số cho nó và xem những gì nó xuất ra. Với những hạn chế đó, máy tính có thể tìm thấy chu kỳ nhanh đến mức nào? Năm 1993, Daniel Simon, khi đó tại Đại học Montreal, phát hiện ra rằng một thuật toán lượng tử có thể tính toán câu trả lời cho một vấn đề liên quan chặt chẽ theo cấp số nhân nhanh hơn bất kỳ thuật toán cổ điển nào.
Kết quả cho phép Simon xác định một trong những gợi ý đầu tiên về nơi có thể mong đợi sự vượt trội đáng kể đối với máy tính lượng tử. Nhưng khi ông gửi bài báo của mình cho một hội nghị hàng đầu, nó đã bị từ chối. Tuy nhiên, bài báo đã làm cho một thành viên cấp dưới của ủy ban chương trình của hội nghị quan tâm - Peter Shor, lúc đó đang ở Phòng thí nghiệm Bell ở New Jersey. Shor tiếp tục phát hiện ra rằng anh có thể điều chỉnh thuật toán của Simon để tính toán chu kỳ của một lời tiên tri, nếu nó có. Sau đó, anh nhận ra rằng anh có thể điều chỉnh lại thuật toán một lần nữa, để giải một phương trình hoạt động tương tự như một nhà tiên tri tuần hoàn: phương trình mô tả việc bao thanh toán, là phương trình tuần hoàn.
Kết quả của Shor là lịch sử. Thuật toán lượng tử mà ông khám phá ra có thể nhanh chóng giảm các số khổng lồ thành các thừa số nguyên tố cấu thành của chúng, điều mà không một thuật toán cổ điển nào có thể làm được. Trong những năm sau đó, các nhà nghiên cứu đã khám phá ra các thuật toán lượng tử hiệu quả khác. Một số trong số chúng, như thuật toán của Shor, thậm chí còn cung cấp lợi thế theo cấp số nhân, nhưng không ai có thể chứng minh lợi thế lượng tử đáng kể đối với bất kỳ bài toán NP nào không tuần hoàn.
Sự thiếu hụt tiến bộ này đã khiến hai nhà khoa học máy tính, Scott Aaronson của Đại học Texas, Austin, và Andris Ambainis của Đại học Latvia, để thực hiện một quan sát. Các bằng chứng về lợi thế lượng tử dường như luôn phụ thuộc vào các ma thuật có một số loại cấu trúc phi nguyên tử, chẳng hạn như tính tuần hoàn. Năm 2009, họ phỏng đoán rằng không thể có sự tăng tốc đáng kể đối với các vấn đề NP ngẫu nhiên hoặc không có cấu trúc. Không ai có thể tìm thấy một ngoại lệ.
Phỏng đoán của họ đã đặt ra ràng buộc đối với sức mạnh của máy tính lượng tử. Nhưng nó chỉ nói rằng không có sự tăng tốc đáng kể nào đối với một loại vấn đề NP phi cấu trúc cụ thể - những vấn đề có hoặc không có câu trả lời. Nếu một vấn đề liên quan đến việc tìm ra các câu trả lời định lượng, cụ thể hơn, được gọi là bài toán tìm kiếm, thì phỏng đoán sẽ không áp dụng.
Với suy nghĩ đó, các nhà nghiên cứu Takashi Yamakawa của Phòng thí nghiệm Tin học Xã hội NTT và Mark Zhandry của NTT Research và Đại học Princeton đã quyết định thử nghiệm với một vấn đề tìm kiếm cụ thể, được giới thiệu vào năm 2005 bởi Oded Regev.
Hãy tưởng tượng một tập hợp các cánh gạt thời tiết đều hướng về cùng một hướng. Cung cấp cho mỗi người trong số họ một cái xô đã đo được, sau đó để một cơn gió mạnh ảnh hưởng đến hướng của họ. Regev muốn xác định, dựa trên hướng cuối cùng của họ, nơi mà tất cả họ đều chỉ ra ban đầu. Những vấn đề như thế này được gọi là "học với sai sót", bởi vì sự xô đẩy và gió hoạt động giống như một nguồn gây ra lỗi ngẫu nhiên theo hướng ban đầu. Có bằng chứng cho thấy rằng nó khó có thể giải được cho cả thuật toán cổ điển và lượng tử.
Yamakawa và Zhandry đã chỉnh sửa thiết lập. Họ đã sửa đổi sức mạnh của những lần xô đẩy bắt đầu đó, khiến chúng dễ dự đoán hơn. Họ cũng khiến cơn gió được xác định bởi một tiên tri ngẫu nhiên để nó thậm chí còn ngẫu nhiên hơn trong một số trường hợp nhất định nhưng hoàn toàn không hoạt động trong những trường hợp khác.
Với những sửa đổi này, các nhà nghiên cứu phát hiện ra rằng một thuật toán lượng tử có thể tìm ra hướng ban đầu một cách hiệu quả. Họ cũng chứng minh rằng bất kỳ thuật toán cổ điển nào cũng phải chậm hơn theo hệ số mũ. Giống như Shor, sau đó họ đã điều chỉnh thuật toán của mình để giải một phiên bản trong thế giới thực của vấn đề, thay thế lời tiên tri bằng một phương trình toán học thực tế.
Các nhà khoa học máy tính vẫn đang làm việc để hiểu và xây dựng vấn đề. Vaikuntanathan so sánh nó với một điều khác nảy sinh khi nén dữ liệu: Khi thông tin đang được nén xuống, hai bit có thể vô tình bị ép vào cùng một nơi, ghi đè lên chúng. Vấn đề dự đoán trước những va chạm đó, để bạn có thể tránh chúng, mang một số điểm tương đồng. “Đó là một loại vấn đề về cơ bản trông giống như thế này,” ông nói. "Có thể những vấn đề này có thể được giải quyết theo cách lượng tử."
Đã có hy vọng rằng một vấn đề phi cấu trúc như vấn đề mới có thể giải quyết được ngay cả trên các phiên bản máy tính lượng tử non trẻ ngày nay, do đó cung cấp một phương tiện để kiểm tra chúng. Suy nghĩ cho rằng các vấn đề phi cấu trúc có thể tốn ít tài nguyên hơn để lập trình, hoặc ít nhạy cảm hơn với nhiễu, vì chúng đã là ngẫu nhiên. Nhưng cho đến nay, vấn đề mới vẫn còn quá cao đối với các máy tính lượng tử hiện có để giải quyết. “Đó là một vấn đề kỳ lạ. Tôi đã không nghĩ để xác định nó, ”Aaronson nói. "Nhưng nhìn lại, nó có một số tính năng rất hay."
Kết quả cung cấp ví dụ đầu tiên về lợi thế lượng tử đáng kể trong bài toán NP không có cấu trúc. Có thể có nhiều vấn đề khác mà thế giới lượng tử thay đổi từ thực tế không thể giải quyết được thành có thể giải quyết được? Bây giờ có nhiều lý do hơn để nghĩ như vậy.
O'Donnell nói: “Nó phần nào làm đảo lộn niềm tin của chúng tôi về những loại vấn đề mà máy tính lượng tử có thể giải quyết.
