Vì sao máy tính lượng tử vẫn chưa thể phân tích 21 thành thừa số nguyên tố

• Sau khi phân tích 15 thành thừa số nguyên tố bằng máy tính lượng tử vào năm 2001, hiện tượng tưởng như không có tiến triển nào được giải thích
• Mạch để phân tích 21 thành thừa số nguyên tố cần nhiều cổng vướng víu hơn 100 lần so với khi phân tích 15
• Sự khác biệt này đến từ độ phức tạp của phép nhân modulo có điều kiện và các tối ưu hóa đặc biệt chỉ áp dụng cho 15
• Sửa lỗi lượng tử và giới hạn phần cứng cũng làm rào cản để tiến tới phân tích 21 càng cao hơn
• Phần lớn các báo cáo về việc phân tích 21 cho đến nay đều dùng mẹo mà không thực hiện phép nhân theo đúng nghĩa thực sự

---

Vì sao máy tính lượng tử vẫn chưa thể phân tích 21 thành thừa số nguyên tố

Vì sao sau khi phân tích 15 thành thừa số nguyên tố vẫn chưa xuất hiện việc phân tích 21

• Năm 2001 đã có thí nghiệm dùng máy tính lượng tử để phân tích 15 thành thừa số nguyên tố
• Đến năm 2025 vẫn chưa có trường hợp thành công nào với phân tích 21 thành thừa số nguyên tố
• Từ điểm này, đã lan truyền nhận thức rằng máy tính lượng tử hoàn toàn không có tiến bộ nào
• Tuy nhiên, khi so sánh mạch phân tích 15 và 21 thành thừa số nguyên tố, có một lý do còn đáng kinh ngạc hơn nhiều

Khác biệt về cấu trúc giữa mạch phân tích 15 và mạch phân tích 21

• Mạch phân tích 15 thành thừa số nguyên tố được triển khai chỉ với 21 cổng lượng tử (21 cổng vướng víu)
  • Gồm 6 cổng vướng víu qubit (các cổng CNOT và CPHASE) và
  • 2 cổng Toffoli (mỗi cổng được phân rã thành 6 cổng vướng víu), tổng cộng thành 21 cổng vướng víu
• Mạch phân tích 21 thành thừa số nguyên tố cần 191 CNOT, 369 Toffoli, tổng cộng 2405 cổng vướng víu
  • Tạo ra gánh nặng số cổng vướng víu lớn hơn 115 lần so với khi phân tích 15
  • Kích thước mạch không chỉ tăng 25% hay gấp đôi, mà đắt hơn hơn 100 lần
• Ngay cả khi tính đến mức độ tối ưu hóa mạch, chênh lệch đến 500 lần cũng có vẻ hoàn toàn khả thi trong thực tế

Vì sao lại xuất hiện khác biệt lớn như vậy

• Trong mạch phân tích thừa số lượng tử (thuật toán Shor), chi phí chi phối là phép nhân modulo có điều kiện
  • Với số N có n bit, cần nhiều lần thực hiện phép nhân modulo lên bộ tích lũy theo điều kiện
  • Trong trường hợp 15, trong 8 phép nhân có điều kiện thì 6 phép có thể xử lý như nhân với 1 (không phải làm gì)
    • Phép nhân đầu tiên có thể triển khai gần như miễn phí vì đầu vào là 1
    • Phép còn lại thứ hai cũng có thể xử lý rẻ bằng hai CSWAP
    • Kết quả là thực tế chỉ cần trả chi phí cho 2 phép
    • Cấu trúc này là tính chất đặc biệt chỉ có ở 15, nơi có nhiều phép nhân gần như với 1 nên gánh nặng giảm đi rõ rệt
• Nhưng với 21 thì tất cả các phép nhân đều không phải 1 và giá trị cũng đa dạng nên phép nào cũng phát sinh chi phí
  • Cả 8 phép nhân đều tốn chi phí, khiến mức tăng không chỉ là 4~5 lần mà thành 20~100 lần
  • Các phép nhân như nhân 4 hay 16 không có cấu trúc có thể triển khai bằng CSWAP (hoán đổi có điều kiện)
  • Độ phức tạp của phép nhân khác nhau theo từng phép, và không dễ tối ưu hóa

Giới hạn thực tế của phần cứng và sửa lỗi

• Việc phân tích 15 thành thừa số nguyên tố trong quá khứ (2001) được triển khai bằng máy tính lượng tử NMR, vốn có nhiều giới hạn về khả năng mở rộng
• Hơn nữa, nhu cầu về sửa lỗi lượng tử cũng tăng lên
  • Nếu số lượng cổng tăng gấp 100 lần thì tỷ lệ lỗi cũng phải thấp hơn 100 lần
  • Trên thực tế, thậm chí còn có thể cần số qubit tăng gấp 100 lần, khiến tổng chi phí tăng tới 10.000 lần

Tranh cãi quanh các nỗ lực phân tích thừa số và những kết quả sai lệch

• Gần đây, một số bài báo tuyên bố đã thành công trong việc phân tích 21 thành thừa số nguyên tố bằng máy tính lượng tử, nhưng
  • trên thực tế, nhiều trường hợp đã lược bỏ phần thực hiện phép nhân của thuật toán hoặc đơn giản hóa mạch vì biết trước kết quả
  • Nếu không thực hiện phép nhân thật sự, thì không thể coi đó là phân tích thừa số
  • Đây là các kết quả mang tính hình thức, bỏ qua khác biệt bản chất giữa việc chỉ "tìm chu kỳ" và phân tích thừa số
• Một số bài báo còn công khai dùng mẹo, và thậm chí đã xuất hiện các bài báo châm biếm về hướng nghiên cứu đó
  • Có nhiều bài báo châm biếm như thí nghiệm tái tạo kỷ lục vô địch phân tích thừa số
  • Các benchmark như Variational factoring vẫn tiếp tục xuất hiện dù không có cơ sở cho khả năng mở rộng quy mô

Chỉ dấu nào mới phản ánh đúng tiến bộ của máy tính lượng tử

• Ở thời điểm hiện tại, phân tích thừa số không phải benchmark chính để đo tiến bộ của máy tính lượng tử
  • Vượt qua 15 là chi phí tăng bùng nổ nên rất khó kiểm chứng theo hướng thực tiễn
• Thay vào đó, việc đưa sửa lỗi lượng tử vào sử dụng (ví dụ: cải tiến surface code) hoặc
  • thay đổi kiến trúc phần cứng để giải quyết bài toán scaling (ví dụ: thay thế liên tục các nguyên tử trung hòa)
  • mới là các điểm quan sát quan trọng hơn để cho thấy tiến bộ thực chất

[GN⁺]

Ý kiến Hacker News

• Nguyên nhân là vì cho đến nay người ta còn chưa từng thực sự phân tích thừa số một số nhỏ hơn theo đúng nghĩa. Nếu chương trình chỉ hoạt động khi quá trình biên dịch đã phải biết sẵn đáp án, thì đó không phải là phân tích thừa số thật sự mà chỉ đơn thuần là "in ra số 3"

• Tôi tò mò cần bao nhiêu quantum gate để thật sự phân tích thừa số một số có ý nghĩa về mặt mật mã. Tôi cũng muốn biết liệu có con đường thực tế nào để trong thế kỷ này xuất hiện một máy tính lượng tử đủ hữu dụng hay không

  • Có thể lấy ví dụ là ước tính trong Bảng 5 của bài báo cho rằng cần khoảng 7 tỷ Toffoli gate để phân tích thừa số RSA 2048 (liên kết bài báo). Cách để đạt đến hàng chục tỷ phép toán chính là sửa lỗi lượng tử, và bài báo cho biết surface code distance 25 là đủ. Trong trường hợp này, 1.400 qubit logic sẽ mở rộng thành khoảng 1 triệu qubit vật lý có nhiễu. Bài nói chuyện của Samuel Jacques tại PQCrypto cũng đáng tham khảo (YouTube). Tôi là tác giả của blog này và của các bài báo liên quan
  • Có hai lý do khiến câu hỏi này khó trả lời. Thứ nhất, không thể vạch ra ranh giới rõ ràng cho khái niệm "có ý nghĩa về mặt mật mã". Thứ hai, kiến trúc của QC có thể thực hiện phép toán này trên thực tế vẫn chưa được biết rõ. Nó hơi giống việc năm 1985 cố ước tính cần bao nhiêu cổng logic truyền thống để tạo ra mạng nơ-ron. Dù vậy, có vẻ chắc chắn sẽ cần từ hàng triệu gate trở lên. Thứ ba nữa là tồn tại đánh đổi trong sửa lỗi lượng tử giữa tỷ lệ lỗi qubit thô thấp hơn và số gate cần để xây dựng các qubit ảo sửa lỗi đáng tin cậy. Hiện giờ chưa ai biết tỷ lệ lỗi của qubit thô rồi sẽ giảm được tới mức nào. Nếu máy tính lượng tử có bước tiến tương tự 75 năm phát triển của máy tính truyền thống, thì có thể tới khoảng năm 2100 mật mã hiện tại sẽ hoàn toàn mất hiệu lực. Trước khi xuất hiện một đổi mới mang tính bước ngoặt như transistor, việc dự đoán là rất khó. Tiến bộ công nghệ lúc nào cũng trông như bất khả thi, cho đến khi ai đó tìm ra cách đầu tiên để làm được. (mô tả UNIVAC I)
  • Cũng có thể tham khảo một tweet gần đây về chủ đề này (liên kết tweet). Từ góc nhìn của người bình thường, con đường đó dường như đang bị che khuất sau nhiều đột phá lớn về khoa học vật liệu
  • Với RSA 4096, ước chừng cần 10^7 qubit với tỷ lệ lỗi 10^-4. Ngay từ khoảng hơn 100 qubit đã có thể làm được các tính toán hóa lượng tử hữu ích, và khi các thuật toán hậu lượng tử dần phổ biến hơn thì động lực phát triển máy tính lượng tử để bẻ khóa mật mã cũng đang giảm đi. Tôi nghĩ điện toán lượng tử sẽ tiến triển nhanh hơn ở những hướng không liên quan đến mật mã
  • Con số mới nhất là cần khoảng 1 triệu qubit ở tỷ lệ lỗi 1e-4 (liên kết bài báo). Số gate được đo khác nhau tùy phép toán thực tế ở cấp độ mã, và với "xung nhịp" 1MHz (thời gian chu kỳ mã), toàn bộ phép tính sẽ mất khoảng một tuần. Đạt được thời gian tính toán còn là chỉ số khó hơn số qubit. Nhờ hiệu ứng gần như kỳ diệu của sửa lỗi lượng tử (tỷ lệ lỗi càng thấp thì số qubit cần càng giảm mạnh), chỉ cần chất lượng qubit tăng thêm một bậc thì số qubit yêu cầu sẽ giảm rất nhiều. Ngược lại, nếu phải chia phép toán ra nhiều hệ thống thì tình hình sẽ xấu đi đáng kể

• Bài báo 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' rất thú vị (đọc bài báo)

• Tôi quan tâm đến kích thước mạch và tính khả thi khi phân tích thừa số các con số có ý nghĩa về mặt mật mã như RSA1024

  • Ước tính chi phí cho RSA1024 không được suy từ việc mở rộng đơn giản các số nhỏ (như 4 bit), mà được tính ra từ thiết kế mạch ở đúng quy mô thực tế. Nói cách khác, vấn đề gián đoạn được nhắc tới trong bài này đã được phản ánh ngầm từ trước. Vì thế bài đăng này không ảnh hưởng đến các ước tính chi phí hiện có
  • (Tham khảo: tối ưu hóa mạch phân tích thừa số 21 có lẽ khó áp dụng khi phân tích các số lớn hơn. So với mạch phân tích thừa số 15, chi phí gấp 500 lần có thể thực tế hơn. Dĩ nhiên, ngay cả mức overhead 100 lần cũng đủ để minh họa luận điểm. Xin đặc biệt cảm ơn Noah Shutty vì đã dùng tìm kiếm tính toán tốn kém để tối ưu hóa mạch đó)
  • Hơi lạc đề một chút, nhưng tôi muốn biết liệu các nhà mật mã học có tin chắc rằng ngay cả những datacenter khổng lồ hiện nay cũng không thể thực tế phân tích thừa số RSA1024 hay không. Hiện tại, ngay cả thuật toán nhanh nhất cũng không thể phân tích trong khung thời gian thực tế. Tuy vậy, tôi tò mò liệu có đồng thuận rằng trong thời gian tới sẽ không có một cải tiến đột phá nào cho thuật toán này hay không

• Tôi tự hỏi liệu một ngày nào đó máy tính lượng tử có thể nhắm tới post-quantum RSA hay không (bài báo liên quan). Cũng có quan điểm cho rằng các phép toán RSA thông thường (tạo khóa, mã hóa, giải mã) có lợi thế bất đối xứng trước thuật toán Shor, nên chỉ cần dùng khóa đủ lớn là được. Điều này tạo ra hiệu ứng hơi giống câu đố Merkle, đồng thời thêm điều kiện rằng kẻ tấn công bắt buộc phải dùng máy tính lượng tử. Tôi từng tạo thử một khóa công khai RSA cỡ gigabit (tệp khóa). Định dạng là: 4 byte little-endian cho số byte của khóa, tiếp theo là khóa, rồi nghịch đảo của khóa (mod theo 256^bytes). Số mũ công khai là 3

  • Post-Quantum RSA là một trò đùa do djb tạo ra để trả lời câu hỏi kiểu "chẳng phải chỉ cần dùng khóa lớn là an toàn sao". Nó được thiết kế để mỗi lần mã hóa với khóa 1TB mất 100 giờ. Ngay cả máy tính lượng tử cũng không phá nổi

• Tôi thấy lỗi chính tả "error corection" khá buồn cười

• Tôi khó hiểu đoạn "chi phí mạch gấp 500 lần so với factor-15". Tác giả đã đưa ra trường hợp 115 lần rồi, vậy tại sao tối ưu hóa thêm lại dẫn tới kết quả tệ hơn?

  • Điều đó có nghĩa là khối lượng công việc tối ưu hóa khổng lồ được đổ vào việc tạo mạch phân tích thừa số cho các số nhỏ là điều không thực tế với các số lớn. Nói cách khác, trực giác hợp lý là khi số cần phân tích lớn lên thì thông thường sẽ cần số gate tăng khoảng 500 lần (chứ không ít như 115 lần)
  • Trên quy mô lớn, hiệu quả tối ưu hóa thực tế sẽ giảm đi, và sẽ không còn lợi nhiều như mạch cho N=21
  • Cách triển khai tối thiểu thì mong manh và khó bảo đảm độ tin cậy. Để phát triển mạch thực dụng cần rất nhiều nghiên cứu nhằm có được các qubit ổn định, và các khái niệm như "decoherence time" cũng được nhắc tới. Vì vậy số qubit buộc phải tăng bùng nổ
  • 115 lần là kết quả của rất nhiều tối ưu hóa (không thực tế)

• Tôi tự hỏi liệu ý chính của bài viết này có phải đang gợi ý rằng nhu cầu mạch Big-O cho phân tích thừa số bằng Schorr là siêu đa thức hay không

  • Theo nội dung bài viết, chi phí gate chủ yếu đến từ O(n) phép nhân modular, và mỗi phép có thể được triển khai bằng O(n^2) gate. Tổng thể, ngay cả trong trường hợp xấu nhất thì độ phức tạp có vẻ vào khoảng bậc ba

• Lý do triển khai công nghệ mật mã PQ (hậu lượng tử) không nhất thiết là vì tin chắc QC sẽ sớm xuất hiện. Thời điểm QC ra đời vẫn bất định tùy theo tốc độ phát triển công nghệ. Mục tiêu của công nghệ mật mã là tìm ra các phương pháp gần như không thể bị phá vỡ ngay cả trên lý thuyết; và nếu một con đường tấn công là khả thi về mặt lý thuyết thì cũng có khả năng khả thi về mặt vật lý, nên phải chuẩn bị trước. ECC và RSA đã có con đường lý thuyết bị tấn công, nên dù chưa có thiết bị thực tế thì vẫn được xem là có thể bị phá. Vì vậy chuẩn bị trước khi chưa có QC là một cách nhìn hoàn toàn hợp lý. Ngược lại, với SHA2, AES, ChaCha... hiện chưa thấy con đường tấn công thực tế, nên chưa có kế hoạch thay thế ngay. Mật mã không phải ứng dụng duy nhất, hay thậm chí quan trọng nhất, của QC. Vẫn có kỳ vọng rằng những đột phá còn chưa biết trước có thể xuất hiện trong nhiều lĩnh vực như hệ vật lý, gấp cuộn protein, machine learning...

  • Tôi cũng tò mò liệu các lĩnh vực như gấp cuộn protein còn có thể tiến xa hơn nữa không (ngay cả sau AlphaFold). (bài viết tham khảo)

  • Với mật mã khóa đối xứng (AES, ChaCha, SHA-2), tấn công lượng tử về thực chất có hiệu ứng làm suy yếu tương đương giảm một nửa độ dài khóa (giống trường hợp 3DES và 2DES). Trên thực tế không thể khẳng định đơn giản là giảm một nửa vì hiệu năng máy tính lượng tử thực tế không tương đương hoặc giống hệt, nhưng chuyển sang AES-256 là đủ nên không có vấn đề gì. Tuy nhiên nơi cần tập trung là Key Exchange. Lý do là Key Exchange được dùng để hai bên thỏa thuận khóa bí mật mà không trực tiếp đưa ra bí mật đó. Nếu có Quantum Computer, thì ngay cả các cuộc hội thoại trong quá khứ đã bị ghi lại cũng có thể bị đọc. Nếu một thuật toán chữ ký bị phá thì bạn không thể quay ngược thời gian để giả chữ ký trong quá khứ, nhưng với Key Exchange, chỉ cần phá được một lần là toàn bộ hội thoại quá khứ cũng bị lộ, nên điều này rất quan trọng. Việc thay thế Key Exchange bằng phương án an toàn là cấp bách nhất.