Trong những trường hợp cụ thể nào thì máy tính lượng tử vượt qua các đối tác cổ điển của chúng? Đó là một câu hỏi khó trả lời, một phần vì máy tính lượng tử ngày nay là những thứ phức tạp, đầy lỗi có thể chồng chất và làm hỏng các tính toán của chúng.
Tất nhiên, theo một biện pháp nào đó, họ đã làm được điều đó. Năm 2019, các nhà vật lý tại Google công bố rằng họ đã sử dụng máy 53 qubit để đạt được tối cao lượng tử, một cột mốc mang tính biểu tượng đánh dấu thời điểm mà máy tính lượng tử làm được điều gì đó ngoài tầm với của bất kỳ thuật toán cổ điển thực tế nào. Tương tự cuộc biểu tình bởi các nhà vật lý tại Đại học Khoa học và Công nghệ Trung Quốc ngay sau đó.
Nhưng thay vì tập trung vào kết quả thử nghiệm cho một máy cụ thể, các nhà khoa học máy tính muốn biết liệu các thuật toán cổ điển có thể theo kịp khi máy tính lượng tử ngày càng lớn hơn hay không. “Hy vọng là cuối cùng khía cạnh lượng tử sẽ hoàn toàn rút lui cho đến khi không còn sự cạnh tranh nữa,” nói Scott Aaronson, một nhà khoa học máy tính tại Đại học Texas, Austin.
Câu hỏi chung đó vẫn khó trả lời, một phần nữa là do những lỗi khó chịu đó. (Các máy lượng tử trong tương lai sẽ bù đắp cho sự không hoàn hảo của chúng bằng một kỹ thuật gọi là sửa lỗi lượng tử, nhưng khả năng đó vẫn còn xa.) Liệu có thể có được lợi thế lượng tử chạy trốn được hy vọng ngay cả với các lỗi chưa được sửa chữa?
Hầu hết các nhà nghiên cứu nghi ngờ câu trả lời là không, nhưng họ không thể chứng minh điều đó cho mọi trường hợp. Bây giờ, trong một giấy được đăng lên máy chủ in sẵn arxiv.org, một nhóm các nhà khoa học máy tính đã thực hiện một bước quan trọng hướng tới bằng chứng toàn diện rằng việc sửa lỗi là cần thiết để có được lợi thế lượng tử lâu dài trong lấy mẫu mạch ngẫu nhiên — vấn đề đặt trước mà Google đã sử dụng để thể hiện uy quyền lượng tử. Họ đã làm như vậy bằng cách phát triển một thuật toán cổ điển có thể mô phỏng các thí nghiệm lấy mẫu mạch ngẫu nhiên khi có lỗi.
“Đó là một kết quả lý thuyết tuyệt vời,” Aaronson nói trong khi nhấn mạnh rằng thuật toán mới thực tế không hữu ích cho việc mô phỏng các thử nghiệm thực tế như của Google.
Trong các thí nghiệm lấy mẫu mạch ngẫu nhiên, các nhà nghiên cứu bắt đầu với một mảng qubit hoặc bit lượng tử. Sau đó, họ điều khiển ngẫu nhiên các qubit này bằng các hoạt động được gọi là cổng lượng tử. Một số cổng khiến các cặp qubit trở nên vướng víu, nghĩa là chúng chia sẻ trạng thái lượng tử và không thể mô tả riêng rẽ. Các lớp cổng lặp đi lặp lại đưa các qubit vào trạng thái vướng víu phức tạp hơn.
Để tìm hiểu về trạng thái lượng tử đó, các nhà nghiên cứu sau đó đo tất cả các qubit trong mảng. Điều này làm cho trạng thái lượng tử chung của chúng co lại thành một chuỗi ngẫu nhiên gồm các bit thông thường — 0 và 1. Số lượng các kết quả có thể xảy ra tăng nhanh với số lượng qubit trong mảng: Với 53 qubit, như trong thử nghiệm của Google, nó là gần 10 triệu triệu. Và không phải tất cả các chuỗi đều có khả năng như nhau. Lấy mẫu từ một mạch ngẫu nhiên có nghĩa là lặp lại các phép đo như vậy nhiều lần để xây dựng một bức tranh về phân bố xác suất làm cơ sở cho các kết quả.
Câu hỏi về lợi thế lượng tử chỉ đơn giản là: Có khó để bắt chước phân bố xác suất đó không với một thuật toán cổ điển mà không sử dụng bất kỳ vướng mắc?
Trong 2019, các nhà nghiên cứu chứng minh rằng câu trả lời là có đối với các mạch lượng tử không có lỗi: Thực sự rất khó để mô phỏng một cách cổ điển một thí nghiệm lấy mẫu mạch ngẫu nhiên khi không có lỗi. Các nhà nghiên cứu đã làm việc trong khuôn khổ lý thuyết về độ phức tạp tính toán, lý thuyết phân loại độ khó tương đối của các vấn đề khác nhau. Trong lĩnh vực này, các nhà nghiên cứu không coi số lượng qubit là một số cố định, chẳng hạn như 53. “Hãy nghĩ về nó như n, đó là một số con số sẽ tăng lên,” nói Aram bừa, một nhà vật lý tại Viện Công nghệ Massachusetts. “Sau đó, bạn muốn hỏi: Có phải chúng ta đang làm những việc mà nỗ lực theo cấp số nhân? n hoặc đa thức trong n?” Đây là cách ưu tiên để phân loại thời gian chạy của thuật toán — khi n phát triển đủ lớn, một thuật toán theo cấp số nhân trong n thua xa bất kỳ thuật toán nào đa thức trong n. Khi các nhà lý thuyết nói về một vấn đề khó đối với máy tính cổ điển nhưng lại dễ dàng đối với máy tính lượng tử, họ đang đề cập đến sự khác biệt này: Thuật toán cổ điển tốt nhất cần thời gian theo cấp số nhân, trong khi máy tính lượng tử có thể giải quyết vấn đề trong thời gian đa thức.
Tuy nhiên, bài báo năm 2019 đó đã bỏ qua ảnh hưởng của lỗi do các cổng không hoàn hảo gây ra. Điều này để ngỏ trường hợp lợi thế lượng tử cho việc lấy mẫu mạch ngẫu nhiên mà không cần sửa lỗi.
Nếu bạn tưởng tượng việc liên tục tăng số lượng qubit như các nhà lý thuyết về độ phức tạp vẫn làm và bạn cũng muốn tính đến lỗi, thì bạn cần quyết định xem bạn có tiếp tục thêm nhiều lớp cổng hơn hay không — tăng độ sâu của mạch, như các nhà nghiên cứu cho biết. Giả sử bạn giữ độ sâu của mạch không đổi ở ba lớp tương đối nông, khi bạn tăng số lượng qubit. Bạn sẽ không gặp nhiều vướng víu và đầu ra vẫn có thể tuân theo mô phỏng cổ điển. Mặt khác, nếu bạn tăng độ sâu mạch để theo kịp với số lượng qubit ngày càng tăng, các tác động tích lũy của lỗi cổng sẽ loại bỏ sự vướng víu và đầu ra sẽ lại trở nên dễ dàng mô phỏng theo kiểu cổ điển.
Nhưng ở giữa là một vùng Goldilocks. Trước bài báo mới, vẫn có khả năng lợi thế lượng tử có thể tồn tại ở đây, ngay cả khi số lượng qubit tăng lên. Trong trường hợp độ sâu trung bình này, bạn tăng độ sâu mạch cực kỳ chậm khi số lượng qubit tăng lên: Mặc dù đầu ra sẽ dần bị suy giảm do lỗi, nhưng vẫn có thể khó mô phỏng theo cách cổ điển ở mỗi bước.
Bài báo mới đóng lỗ hổng này. Các tác giả đã rút ra một thuật toán cổ điển để mô phỏng lấy mẫu mạch ngẫu nhiên và chứng minh rằng thời gian chạy của nó là một hàm đa thức của thời gian cần thiết để chạy thí nghiệm lượng tử tương ứng. Kết quả tạo nên mối liên hệ lý thuyết chặt chẽ giữa tốc độ của các phương pháp tiếp cận cổ điển và lượng tử đối với việc lấy mẫu mạch ngẫu nhiên.
Thuật toán mới hoạt động đối với một loại chính của các mạch có độ sâu trung bình, nhưng các giả định cơ bản của nó bị phá vỡ đối với một số mạch nông hơn, để lại một khoảng trống nhỏ nơi các phương pháp mô phỏng cổ điển hiệu quả chưa được biết đến. Nhưng một số nhà nghiên cứu đang nuôi hy vọng rằng việc lấy mẫu mạch ngẫu nhiên sẽ khó mô phỏng theo cách cổ điển trong cửa sổ mỏng còn lại này. Tôi cho rằng tỷ lệ cược khá nhỏ, anh nói Bill Fefferman, một nhà khoa học máy tính tại Đại học Chicago và là một trong những tác giả của bài báo lý thuyết năm 2019.
Kết quả cho thấy rằng việc lấy mẫu mạch ngẫu nhiên sẽ không mang lại lợi thế lượng tử theo các tiêu chuẩn nghiêm ngặt của lý thuyết độ phức tạp tính toán. Đồng thời, nó minh họa thực tế rằng các thuật toán đa thức, mà các nhà lý thuyết về độ phức tạp gọi một cách bừa bãi là hiệu quả, không nhất thiết phải nhanh trong thực tế. Thuật toán cổ điển mới ngày càng chậm hơn khi tỷ lệ lỗi giảm và ở tỷ lệ lỗi thấp đạt được trong các thí nghiệm về uy quyền lượng tử, nó quá chậm để có thể thực hiện được. Không có lỗi, nó bị hỏng hoàn toàn, vì vậy kết quả này không mâu thuẫn với bất kỳ điều gì mà các nhà nghiên cứu đã biết về mức độ khó để mô phỏng lấy mẫu mạch ngẫu nhiên một cách cổ điển trong trường hợp lý tưởng, không có lỗi. Sergio Boixo, nhà vật lý dẫn đầu nghiên cứu về uy quyền lượng tử của Google, cho biết ông coi bài báo này “giống như một xác nhận tốt về việc lấy mẫu mạch ngẫu nhiên hơn bất kỳ thứ gì khác.”
Ở một điểm, tất cả các nhà nghiên cứu đều đồng ý: Thuật toán mới nhấn mạnh tầm quan trọng của việc sửa lỗi lượng tử đối với sự thành công lâu dài của điện toán lượng tử. “Cuối cùng thì đó là giải pháp,” Fefferman nói.
