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.
Nhưng sự tiến bộ trong hướng nghiên cứu này bị đình trệ. Giáo sư Ryan O'Donnell của Đại học Carnegie Mellon nhận xét: “Đó là một quỹ đạo hơi thất vọng” và “Kiểu như là, ‘điều này thật đáng kinh ngạc, tôi chắc chắn rằng chúng ta sẽ nhận được tất cả các kiểu thuật toán đáng kinh ngạc khác’. Tuy nhiên câu trả lời là Không!”. Các nhà khoa học đã phát hiện ra khả năng tăng tốc đáng kể chỉ dành cho một lớp bài toán hẹp, đơn lẻ từ bên trong một tập tiêu chuẩn có tên là “lớp bài toán NP”, nghĩa là lớp bài toán có các lời giải có thể kiểm tra hiệu quả - chẳng hạn như bài toán phân tích thừa số nguyên. Đây chính là bối cảnh nghiên cứu trong gần ba thập kỷ qua. Phải đến tháng 4/2022, các nhà nghiên cứu Takashi Yamakawa, Mark Zhandry [1] đã phát minh một dạng bài toán mới mà máy tính lượng tử có thể giải nhanh hơn theo hàm mũ so với máy tính cổ điển. Bài toán mới này liên quan đến việc tính toán các đầu vào cho một quy trình toán học phức tạp, chỉ dựa trên các đầu ra được xáo trộn. Liệu bài toán là độc lập hay là bài toán đầu tiên trong một biên giới mới của nhiều bài toán khác vẫn còn chưa được xác định.
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”.
Tài liệu tham khảo: Takashi Yamakawa, Mark Zhandry. “Verifiable Quantum Advantage without Structure”, arXiv:2204.02063. |
Đỗ Đại Chí (Tổng hợp)
14:00 | 25/03/2024
11:00 | 29/07/2023
09:00 | 01/08/2023
09:00 | 17/10/2023
08:00 | 20/08/2020
09:00 | 21/08/2018
10:00 | 29/03/2024
Chiều ngày 28/3, tại Hà Nội, Khối thi đua 4 hệ Cơ yếu: Quân đội, Công an, Ngoại giao, Đảng - Chính quyền tổ chức Lễ phát động thi đua và ký giao ước thi đua năm 2024. Đồng chí Nguyễn Hữu Hùng, Phó Trưởng ban Ban Cơ yếu Chính phủ tới dự và phát biểu chỉ đạo.
10:00 | 19/03/2024
Làn sóng khởi nghiệp về Trí tuệ nhân tạo (AI) đang dần nóng lên trong cuộc chiến giành nhân tài ở châu Âu, khiến các công ty như Google DeepMind phải đưa ra lựa chọn giữa việc trả mức lương hấp dẫn hoặc đánh mất những bộ óc giỏi nhất của công ty mình.
09:00 | 06/03/2024
Hội thảo Quốc gia lần thứ XXVII "Một số vấn đề chọn lọc về Công nghệ thông tin và Truyền thông" – VNICT 2024 do Viện Công nghệ thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam và Trường Đại học Nha Trang đồng tổ chức tại Nha Trang - Khánh Hòa vào các ngày 11-12/10/2024. Hội thảo có sự tham gia phối hợp của Câu lạc bộ các Khoa-Trường-Viện CNTT-TT Việt Nam (FISU) và Tạp chí An toàn thông tin.
14:00 | 23/02/2024
Nhóm tin tặc mã độc tống tiền BlackCat đã bắt đầu lạm dụng các quy tắc báo cáo sự cố mạng của Ủy ban Chứng khoán và Giao dịch Mỹ (SEC) để gây áp lực lên các tổ chức từ chối đàm phán thanh toán tiền chuộc. Những kẻ tấn công đã nộp đơn khiếu nại lên SEC đối với một nạn nhân, trong một động thái có thể sẽ trở thành thông lệ sau khi các quy định mới đã có hiệu lực vào giữa tháng 12.
Khoảng giữa năm 1995, cơ quan An ninh Quốc gia Mỹ (National Security Agency - NSA) bắt đầu công bố hàng nghìn thông điệp được giải mật từ dự án VENONA. Đó là các thông điệp được truyền trong hoạt động ngoại giao và hoạt động tình báo của Liên Xô được trao đổi từ năm 1940. Trong đó, có chứa các thông tin liên quan đến Cơ quan tình báo trung ương Liên Xô (Komitet Gosudarstvennoy Bezopasnosti - KGB), Cơ quan Tình báo Quân đội Nga (Glavnoye Razvedyvatel’noye Upravleniye - GRU), Cơ quan Dân ủy Nội vụ (Narodnyy Komissariat Vnutrennikh Del - NKVD)…. Đây là kết quả hợp tác truyền thông tình báo của Mỹ, Anh và một số nước đồng minh. Bài viết dưới đây trình bày khái quát các kết quả chính và nguyên nhân thám mã thành công của dự án VENONA.
15:00 | 30/12/2018
Hội nghị quốc tế lần thứ 12 Lãnh đạo cấp cao phụ trách an ninh được tổ chức dựa trên sự cần thiết vì nó mở ra cơ hội để trao đổi kinh nghiệm, tìm kiếm những cách tiếp cận mới và các giải pháp tổng hợp chung cho các vấn đề cấp bách về an ninh khu vực và toàn cầu.
09:00 | 28/04/2024
Hướng tới kỷ niệm 80 năm Ngày truyền thống ngành Cơ yếu Việt Nam (12/9/1945 - 12/9/2025), Ban Cơ yếu Chính phủ đã ban hành Kế hoạch phát động Cuộc thi sáng tác nghệ thuật thơ, ca khúc về Ngành Cơ yếu Việt Nam.
10:00 | 16/04/2024