Vào năm 1994, nhà toán học Peter Shor đã tìm ra cách làm cho máy tính lượng tử thực hiện đượ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 của Shor đã khám phá ra rằng, về nguyên tắc, một cỗ máy dựa trên các quy tắc của cơ học lượng tử có thể phân tích một số nguyên lớn thành các thừa số nguyên tố một cách hiệu quả, một công việc vốn quá khó đối với một máy tính cổ điển và chính tính khó này giúp thiết lập cơ sở cho phần lớn tính an toàn của internet ngày nay. Công trình này đã dấy lên sự lạc quan về chủ đề nghiên cứu tính toán lượng tử. Các nhà nghiên cứu nghĩ rằng có lẽ chúng ta sẽ có thể phát minh ra các thuật toán lượng tử giúp giải quyết rất nhiều bài toán khác nhau.
Vinod Vaikuntanathan, giáo sư khoa học máy tính tại Viện Công nghệ Massachusetts (MIT) chia sẻ: “Có một cảm giác phấn khích, rất nhiều người đang suy nghĩ về những điều gì khác còn ở ngoài kia”.
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 biểu diễn cho máy tính lượng tử. Thông thường, họ tưởng tượng ra 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 lý tưởng hóa được gọi là bộ tiên tri (oracles). Oracles giống như các hàm toán học hoặc chương trình 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. Bộ tiên tri có thể có hành vi ngẫu nhiên, đưa ra kết quả “có” nếu đầu vào nằm trong một khoảng ngẫu nhiên nào đó (ví dụ: 12 đến 67) và “không” nếu đầu vào không nằm trong khoảng ngẫu nhiên đó. Hoặc oracles có thể là tuần hoàn, sao cho đầu vào trong khoảng 1 đến 10 trả về “có”, 11 đến 20 trả về “không”, 21 đến 30 trả về “có”,…
Giả sử người dùng có một trong những oracle tuần hoàn này và không hề biết chu kì tuần hoàn của oracle đó. Tất cả những gì người dùng có thể làm là cung cấp cho oracle các con số và xem kết quả oracle trả về. Với những ràng buộc giữa đầu ra và đầu vào của oracle, liệu máy tính có thể tìm thấy chu kỳ nhanh như thế nào? Vào năm 1993, Daniel Simon, khi đó đang làm việc 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 bài toán liên quan chặt chẽ với oracle tuần hoàn ở trên, nhanh hơn theo hàm mũ so với 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ể kỳ vọng tính ưu việt vượt trội của máy tính lượng tử. Nhưng khi Simon gửi bài báo tới một hội nghị hàng đầu, bài báo đã không được chấp thuận. Tuy nhiên, bài báo đã thu hút sự quan tâm của Peter Shor (một thành viên cấp dưới trong ủy ban chương trình của hội nghị), lúc đó đang làm việc tại Phòng thí nghiệm Bell ở New Jersey. Shor tiếp tục phát hiện ra rằng có thể điều chỉnh thuật toán của Simon để tính chu kỳ của một oracle (tất nhiên nếu oracle đó có chu kỳ). Tiếp đó, Shor nhận ra rằng có thể chỉnh sửa thích hợp 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 oracle tuần hoàn: phương trình mô tả bài toán phân tích thừa số nguyên, là tuần hoàn.
Kết quả của Shor mang tính lịch sử. Thuật toán lượng tử mà Shor khám phá ra có thể nhanh chóng phân tích các số lớn thành các thừa số nguyên tố, điều mà không thuật toán cổ điển nào đã biết có thể làm được. Trong những năm sau đó, các nhà nghiên cứu đã tìm ra các thuật toán lượng tử hiệu quả khác, thậm chí còn mang lại lợi thế theo hàm mũ, nhưng không thuật toán nào 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 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, đưa ra một quan sát. Chứng minh về lợi thế lượng tử dường như luôn phụ thuộc vào các oracle mà có một số kiểu cấu trúc không ngẫu nhiên, chẳng hạn như tính tuần hoàn. Vào năm 2009, Aaronson và Ambainis đã phỏng đoán rằng không thể có sự tăng tốc đáng kể đối với các bài toá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 trên đưa ra giới hạn cho sức mạnh của máy tính lượng tử. Nhưng phỏng đoán chỉ nói rằng không có sự tăng tốc đáng kể nào đối với một kiểu bài toán NP phi cấu trúc cụ thể, những bài toán có câu trả lời có hoặc không. Nếu một bài toán liên quan đến việc tìm ra các câu trả lời định lượng hơn, cụ thể hơn, được biết đến là bài toán tìm kiếm, thì phỏng đoán đã không được á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 NTT và Mark Zhandry của Nghiên cứu NTT và Đại học Princeton đã quyết định thử nghiệm một bài toá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 chong chóng gió (weather vane) đều chỉ về cùng một hướng. Đưa cho mỗi chong chóng gió một lực xô đẩy đo được, sau đó để một cơn gió mạnh ảnh hưởng đến hướng của chong chóng gió. Dựa vào hướng cuối cùng của các chong chóng gió, Regev muốn xác định nơi mà tất cả chong chóng gió đã chỉ theo hướng ban đầu. Những bài toán như thế này được gọi là “học với các lỗi (learning with errors)”, bởi vì lực xô đẩy và gió đóng vai trò như một nguồn lỗi ngẫu nhiên theo hướng ban đầu. Có bằng chứng cho thấy bài toán học với các lỗi khó giải đối với cả thuật toán cổ điển và thuật toán lượng tử.
Yamakawa và Zhandry đã điều chỉnh tốt thiết lập. Họ đã sửa đổi độ mạnh của các lực xô đẩy ban đầu, khiến các lực xô đẩy dễ dự đoán hơn. Yamakawa và Zhandry cũng khiến gió được xác định bởi một oracle ngẫu nhiên để nó thậm chí còn ngẫu nhiên hơn trong trường hợp nào đó nhưng hoàn toàn không hoạt động trong trường hợp khác. Với những sửa đổi này, Yamakawa và Zhandry đã phát hiện ra rằng 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 khi áp dụng bất kỳ thuật toán cổ điển nào cũng phải chậm hơn một thừa số hàm mũ so với thuật toán lượng tử. Giống như Shor, sau đó Yamakawa và Zhandry đã điều chỉnh thích hợp thuật toán để giải một phiên bản thực tế của bài toán, vốn thay thế oracle bằng phương trình toán học thực hành.
Các nhà khoa học máy tính vẫn tiếp tục làm việc nhằm hiểu rõ hơn bài toán và độ tin cậy vào bài toán. Vaikuntanathan so sánh dạng bài toán này với một bài toán khác phát sinh khi thực hiện nén dữ liệu: Khi thông tin đang được nén xuống, hai bit có thể tình cờ bị nén vào cùng một vị trí, ghi đè lên vị trí đó. Bài toán dự đoán trước những va chạm bit ở cùng một vị trí, để có thể tránh chúng, có một số điểm tương đồng với bài toán được xem xét bởi Yamakawa và Zhandry. Vaikuntanathan phát biểu: “Đó là một lớp các bài toán về cơ bản giống nhau và có lẽ có thể được giải bằng phương thức lượng tử”.
Có những hy vọng rằng bài toán phi cấu trúc giống bài toán mới ở trên có thể giải được ngay cả trên các thế hệ 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 lời giải. Có suy nghĩ rằng vì tính ngẫu nhiên sẵn có nên các bài toá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. Nhưng cho đến nay, bài toán mới dường như vẫn còn quá phức tạp để giải đối với các máy tính lượng tử hiện có. Aaronson giải thích: “Đó là một bài toán kỳ lạ. Tôi đã không nghĩ đến việc xác định rõ bài toán, nhưng khi nhìn lại, bài toán có một số đặc tính rất hay”.
Kết quả bài báo của Yamakawa và Zhandry đưa ra ví dụ đầu tiên về lợi thế lượng tử nổi bật đối với bài toán NP phi cấu trúc. Điều này cho ta nhiều suy luận hơn để nghĩ về “Liệu có thể có nhiều bài toán khác mà thế giới lượng tử thay đổi từ không giải được về mặt thực hành thành giải được hay không?” O'Donnell nhận xét: “Điều đó đã phần nào đảo ngược niềm tin của chúng ta về các dạng bài toán mà máy tính lượng tử có thể làm tốt”.
