Sunnyvale, California - Ngày 26 tháng 2022 năm XNUMX - Nghiên cứu NTT thông báo rằng một nhà khoa học từ Phòng thí nghiệm Mật mã và Bảo mật Thông tin (CIS) và một đồng nghiệp từ Phòng thí nghiệm Tin học Xã hội NTT (SIL) đã viết một bài báo đột phá về lợi thế lượng tử. Bài báo đã được chọn để trình bày tại Hội nghị chuyên đề IEEE hàng năm về Cơ sở Khoa học Máy tính (FOCS), diễn ra từ ngày 31 tháng 3 đến ngày XNUMX tháng XNUMX. XNUMX ở Denver.
Các đồng tác giả của bài báo, có tiêu đề “Lợi thế lượng tử có thể xác minh được mà không cần cấu trúc, ”Là Tiến sĩ Takashi Yamakawa, nhà nghiên cứu xuất sắc tại NTT SIL và Tiến sĩ Mark Zhandry, nhà khoa học cấp cao trong Nghiên cứu NTT Phòng thí nghiệm CIS. Công trình được thực hiện một phần tại Đại học Princeton, nơi Tiến sĩ Yamakawa là học giả nghiên cứu thỉnh giảng và Tiến sĩ Zhandry cũng là trợ lý giáo sư khoa học máy tính.
Chủ đề về lợi thế lượng tử (hay tăng tốc lượng tử) liên quan đến các loại vấn đề mà máy tính lượng tử có thể giải quyết nhanh hơn máy tính cổ điển, hoặc phi lượng tử và chúng nhanh hơn bao nhiêu. Các vấn đề được đề cập thường được mô tả dưới dạng lớp đa thức thời gian (NP) không xác định. Có bao nhiêu lợi thế có thể thay đổi ở một mức độ lớn. Một máy tính lượng tử có thể giải quyết một vấn đề cụ thể trong một phút hoặc một giây mà máy tính cổ điển phải mất một tuần, hoặc có thể là một khoảng thời gian theo cấp số nhân không thể đoán được. Trong bài báo này, các tác giả đề cập đến thách thức trong việc xác minh tính ưu việt này và làm như vậy một cách hiệu quả. Cho đến nay, các minh chứng về lợi thế lượng tử đã liên quan đến “cấu trúc” quan trọng hoặc giao tiếp qua lại giữa hai hoặc nhiều bên. Bước đột phá của bài báo Yamakawa và Zhandry là chứng minh một bài toán khó NP trong đó việc xác minh có thể thực hiện được mà không cần cấu trúc.
“Đây là lần đầu tiên chúng tôi thấy tốc độ lượng tử theo cấp số nhân cho một bài toán tìm kiếm NP, chỉ yêu cầu một lời tiên tri ngẫu nhiên,” Giáo sư Khoa học Máy tính, Tiến sĩ Scott Aaronson của Đại học Texas tại Austin, người đã nhận xét về phiên bản đầu tiên. của bài báo trong một hội thảo vào ngày 13 tháng 2022 năm XNUMX, tại Viện Lý thuyết Máy tính Simons. Bằng cách chỉ yêu cầu một nhà tiên tri ngẫu nhiên, tức là một hộp đen lý thuyết tạo ra các phản hồi ngẫu nhiên cho mỗi truy vấn, Yamakawa và Zhandry đã xây dựng vấn đề của họ dựa trên các giả định tính toán không có cấu trúc. Do đó, vấn đề của họ sắp xếp chặt chẽ hơn với các hàm một chiều thay vì các hàm có cấu trúc, chẳng hạn như các hàm được tìm thấy trong mật mã khóa công khai. Sự liên kết một chiều đó tạo điều kiện xác minh hiệu quả.
Kazuhiro Gomi cho biết: “Thật thú vị khi thấy các nhà mật mã liên kết với NTT hợp tác trong nghiên cứu một lần nữa xứng đáng với nhãn hiệu 'đột phá', đặc biệt là trong một bài báo làm phong phú thêm hiểu biết của chúng tôi về điện toán lượng tử, một lĩnh vực trọng tâm khác của chúng tôi tại NTT Research. , Chủ tịch và Giám đốc điều hành của NTT Research. “Xin chúc mừng và gửi lời chúc tốt đẹp nhất đến tất cả những người tham gia hội nghị IEEE uy tín này.”
Bài toán tìm kiếm NP mà Yamakawa và Zhandry nghĩ ra là một bài toán hai trong một đòi hỏi việc tìm kiếm 1) một chuỗi ký hiệu n là một từ mã của một mã sửa lỗi nhất định và 2) một chuỗi ký hiệu n trong đó mỗi biểu tượng được ánh xạ đến số XNUMX trong lời tiên tri ngẫu nhiên. Mỗi vấn đề riêng biệt là dễ dàng. Nhưng để tìm một chuỗi ký hiệu vừa là từ mã vừa ánh xạ về XNUMX thì khó hơn nhiều, ít nhất là về mặt cổ điển. Tiến sĩ Zhandry nói: “Nếu bạn là lượng tử, bạn có thể giải quyết vấn đề này trong thời gian đa thức, nhưng nếu bạn là người cổ điển, ít nhất nếu bạn đang ở trong mô hình hộp đen này, bạn cần thời gian theo cấp số nhân.” Mặt khác, với một giải pháp tiềm năng, thật đơn giản để xác minh nó bằng cách kiểm tra xem nó có giải quyết riêng biệt từng vấn đề trong hai vấn đề hay không. Lưu ý rằng, vì phù hợp với một bài báo cho FOCS, công việc này là cơ bản hoặc nền tảng. Như đã chỉ ra trong bài nói chuyện của Tiến sĩ Aaronson tại Viện Simons (được thảo luận trong Nghiên cứu NTT này bài viết trên blog), đối số Yamakawa-Zhandry thuộc loại tốc độ có thể dễ dàng kiểm tra bằng toán học, nhưng không sớm được chứng minh bằng máy tính lượng tử thực tế. Tuy nhiên, ngoài sơ đồ xác minh mang tính đột phá, bài báo cũng chỉ ra một điều gì đó mới mẻ liên quan đến mức độ tăng tốc lượng tử.
“Trước khi làm việc, chúng tôi đã có các ví dụ về lợi thế lượng tử cho các bài toán NP, như bao thanh toán hoặc, trong thiết lập hộp đen, tìm chu kỳ. Nhưng nó chỉ ra rằng thuật toán lượng tử cơ bản của tất cả các ví dụ này về cơ bản là tìm kiếm theo chu kỳ - mặc dù việc chỉ ra cách áp dụng tính năng tìm kiếm theo chu kỳ cho những ví dụ này thường không hề nhỏ, ”Tiến sĩ Zhandry nói. “Bài báo của chúng tôi cho thấy có ít nhất một trường hợp thứ hai. Bạn có thể giải thích một cách lạc quan điều đó vì nói rằng có hy vọng rằng lợi thế lượng tử phổ biến hơn có thể chúng ta nghĩ trước đây ”.
Được tài trợ bởi Ủy ban Kỹ thuật của Hiệp hội Máy tính IEEE về Cơ sở Toán học của Máy tính (TCMF), FOCS là hội nghị hàng đầu trong lĩnh vực khoa học máy tính lý thuyết. Việc kêu gọi các bài báo cho FOCS 2022, cuộc họp thường niên lần thứ 63, đã liệt kê điện toán lượng tử là một trong 17 lĩnh vực chung được quan tâm. Bài báo của Yamakawa-Zhandry dự kiến sẽ được trình bày vào ngày 31 tháng 2022 năm 10, lúc 15:XNUMX sáng MT. Để tìm hiểu thêm về và đăng ký sự kiện này, hãy truy cập TRỌNG TÂM 2022 trang web.
