AI chứng minh giả thuyết Aaronson-Ambainis, Aaronson xác nhận tin được

Ngày 06/11/2026, Physical Superintelligence (PSI) công bố hệ thống AI của họ đã chứng minh xong giả thuyết Aaronson-Ambainis, bài toán mở từ 2008 về độ phức tạp truy vấn lượng tử. Hai ngày sau, Scott Aaronson lên blog nói ông tin chứng minh này đúng, dù thừa nhận mình chưa tự hiểu hết chứng minh. Mình đọc kỹ vì tin này khác hẳn mấy tin AI toán học ồn ào.

Tóm tắt nhanh: PSI công bố 06/11/2026, model Anthropic chưa công khai, chứng minh đầy đủ ngày thứ 3, paper 60 trang, code Lean công khai, Aaronson đăng blog 08/11/2026 lúc 15:44 nói tin chứng minh đúng.

Giả thuyết Aaronson-Ambainis hỏi gì về dữ liệu ngẫu nhiên

Trước khi bàn AI giỏi tới đâu, anh em cần biết giả thuyết hỏi cái gì đã, vì nhiều tít giật gân đang viết lệch câu hỏi gốc. Câu hỏi gốc hình như bắt đầu từ Lance Fortnow khoảng 1999.

Ở Banff 2008, Aaronson nhận ra đáp án nằm ở một tuyên bố về đa thức. Bài gốc lên arXiv ngày 05/11/2009, đăng tạp chí Theory of Computing 2014, tập 10, trang 133-166. Aaronson thừa nhận ông chưa bao giờ tự giải trực tiếp câu hỏi này, và chứng minh mới trả lời câu hỏi Fortnow và Rogers từ 1998, ở dạng tương đối với random oracle.

Đa thức bậc 2 trên 4 bit, 16 đỉnh là 16 đầu vào, sơ đồ gốc trang PSI.

Bức tường công tắc đèn giải thích influence của một bit

Ví dụ này của The Neuron, newsletter ngày 09/11/2026. Anh em tưởng tượng bức tường đầy công tắc đèn. Influence của một bit là khả năng gạt công tắc đó làm đổi đáp án cuối cùng. Dữ liệu ngẫu nhiên là dãy công tắc bật tắt lung tung, hầu như không có mẫu ẩn để bám vào. Trò 20 câu hỏi cũng vậy thôi.

Không có câu nào chốt được cả cục thì đành hỏi lần lượt từng công tắc.

Shor 1994 nhanh nhờ cấu trúc tuần hoàn

Máy lượng tử nhanh vượt trội khi bài toán có cấu trúc. Ví dụ quen nhất là thuật toán Shor phân tích thừa số 1994. Shor nhanh nhờ khai thác tính tuần hoàn ẩn trong dữ liệu, tức một mẫu lặp mà máy lượng tử nhìn ra rồi bám vào đi tắt.

Còn giả thuyết này hỏi lợi thế đó còn không khi đầu vào ngẫu nhiên, không có cấu trúc ẩn nào để bám, nghe đơn giản mà khó, anh em ạ.

Beals 1998 biến tốc độ thành đa thức

Beals và cộng sự 1998 cho ra kết quả để Aaronson và Ambainis đưa câu hỏi tốc độ về một tuyên bố về đa thức. Kết quả này nói xác suất thuật toán lượng tử trả lời yes sau T lần đọc đầu vào là một đa thức bậc tối đa 2T, giá trị luôn từ 0 đến 1.

Thế là hai ông chuyển bài toán thành việc kiểm tra xem mọi đa thức như vậy, miễn là thay đổi đáng kể, có luôn một biến ảnh hưởng lớn hay không, anh em ạ.

Aaronson tin chứng minh dù chưa hiểu hết

Tin này đáng đọc vì người đặt ra giả thuyết đã lên tiếng, thừa nhận chưa hiểu hết chứng minh mà vẫn tin nó đúng, và hai lý do ông đưa ra mới là chỗ đáng tiền, anh em ạ.

Hai cột sáng đỡ dầm ngang, gợi hai lý do Aaronson tin. Hình này do mình vẽ.

Chứng chỉ Lean khiến Aaronson tin chứng minh đúng

Aaronson viết trên blog ngày 08/11/2026:

“I haven’t yet understood the proof, although I hope to. In the meantime, though, I believe the proof is correct for two reasons. Firstly, there’s a Lean certificate, and secondly, human experts (I’m no longer an expert on my own conjecture!) have already gone over it and understood it.”

Dịch ý thì ông tin vì chứng chỉ Lean và các chuyên gia đã đọc hiểu chứng minh. Lean chỉ chấp nhận chứng minh khi kernel xác nhận mọi bước đều suy ra đúng. Tin được là một chuyện, hiểu hết lại là chuyện khác.

Nhóm Blanc và Stanford đọc hiểu chứng minh

Lý do thứ hai là bản diễn giải của Guy Blanc ở MIT theo blog Aaronson, cùng Jordan Docter, Carmen Strassle, Li-Yang Tan ở Stanford. Nhóm này đã giải trường hợp đặc biệt ngày 19/08/2026, được chấp nhận tại FOCS 2026.

Họ khen qua PSI: “This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way.” Lời khen này tới công chúng qua PSI, chưa có tuyên bố độc lập trên kênh của nhóm tính đến 07/11.

Ba cảm xúc của Aaronson sau 18 năm chờ đợi

Aaronson kể ba cảm xúc, thứ nhất là hài lòng vì giả thuyết hóa ra đúng sau cùng: “Satisfied that our conjecture turned out to be true after all (it’s nice to be 100% correct about something from time to time!)” Thứ hai là thất vọng vì robot giành trước con người: “Disappointed that humans didn’t get to snag this conjecture before the robots did (with some more years, I think it’s exceedingly likely that they would have)”

Thứ ba là mệt mỏi trước buffet bài toán mở cứ cuồn cuộn đến: “Fatigued by the endless wonders from Aladdin’s Cave, the neverending buffet of solutions to longstanding open problems, wondering when if ever we’ll have time to digest it all”. Ông vừa vui vừa tiếc.

Lean kiểm chứng 648 định lý của PSI

Lean không khen hay, chỉ kiểm tra từng bước logic, và con số kiểm chứng đủ để anh em tự đối chiếu, đó là chỗ tin này khác mấy tin AI toán học ồn ào.

Screenshot repo GitHub aaronson-ambainis: 58 sao, 1 commit, giấy phép Apache 2.0, chụp 09/11/2026.

Repo Lean PSI: 84 file, 648 định lý, 0 sorry

Repo Lean của PSI có 84 file, 761 khai báo, trong đó 648 là định lý, gồm 4 định lý cuối, 0 sorry, 0 tiên đề thêm ngoài 3 tiên đề chuẩn của Lean. Định nghĩa chính PrintedConjecture chỉ dài 20 dòng, in đủ trong README, chạy kiểm chứng trên Lean 4.33.0 với Mathlib v4.33.0.

Exponent cải thiện từ 22 xuống 11 rồi 7

Bản đầu tiên ngày thứ 3 chỉ đạt exponent 22, sau đó hệ thống cải thiện xuống 11 rồi 7, mỗi bản đều được Lean kiểm tra lại. Exponent nhỏ dần thì kết quả mạnh dần.

Bound cuối cùng: influence của bit i ít nhất bằng c nhân v mũ 5/2 chia d mũ 6, mà vế này vẫn lớn hơn hoặc bằng (v/d) mũ 7. Hằng số c bằng 8 nhân căn 15 chia 125 nhân pi mũ 4, khoảng 0,0025, v là phương sai còn d là bậc.

Chứng minh đi theo kế hoạch Lovett và Zhang, thay bất đẳng thức họ để lại bằng một bất đẳng thức mới, chứng minh bằng cách ghép cặp một-một các cấu hình đầu vào qua định thức, mở rộng Butterfly Lemma của David Reimer. Paper cũng chỉ ra một tuyên bố của Lovett và Zhang không đúng ở dạng tổng quát đã nêu.

leanchecker, lean4lean và nanoda chạy lại chứng minh

Ba checker độc lập đã chạy lại chứng minh. leanchecker chạy qua Lean kernel, lean4lean là bản cài đặt độc lập của Lean type checker, còn nanoda là checker viết bằng Rust, chạy lại 4 định lý cuối qua Comparator.

Năm 2019, chứng minh của Keller và Klein sụp đổ vì một bổ đề sai ở Lemma 5.3 mà Paata Ivanisvili phát hiện ra. PSI tuyên bố ngày 06/11/2026: “The Aaronson-Ambainis conjecture is now a theorem.” Đây mới là tuyên bố của PSI, chưa phải kết luận của tạp chí sau peer review. Cùng ngày 06/11, DeepMind cũng dùng AI tấn công RSA 1024-bit trong working paper kiểm tra đại số bằng Lean 4.

Peer review, Ambainis, bản diễn giải Stanford chưa xong

Lean chấp nhận là tin tốt, nhưng Lean chỉ bảo đảm định lý như được viết trong Lean là đúng, phần còn lại vẫn chờ người đọc, chờ tạp chí, chờ những người liên quan lên tiếng, tin được, nhưng chưa xong.

Ba mảnh ghép đã khớp, một mảnh chỉ có đường viền. Mình vẽ tay.

Chưa peer review, chưa rõ PSI có nộp paper không

Chứng minh chưa qua peer review, cũng chưa rõ PSI có nộp paper 60 trang đi tạp chí hay không. Paper viết cho người đọc thì không được máy kiểm chứng, nên đừng đọc paper như định lý đã được tạp chí duyệt.

Andris Ambainis chưa lên tiếng tính đến 09/11/2026

Andris Ambainis là đồng tác giả giả thuyết. Tính đến 09/11/2026 ông hình như chưa lên tiếng công khai, nên anh em đừng suy đoán hộ ông hay bịa phát ngôn cho ông.

Định nghĩa PrintedConjecture 20 dòng chờ chuyên gia xác nhận

Định nghĩa PrintedConjecture có đúng là giả thuyết gốc hay không, README của PSI ghi rõ đó là việc người đọc phải xác nhận. Định nghĩa chính chỉ dài khoảng 20 dòng và in đầy đủ trong README. Một trong 4 định lý phụ thuộc kết quả của Agarwal và Ben-David chưa được formal hóa, nhưng định lý chính mang tên aaronson_ambainis không cần nó.

Model Anthropic chưa công khai nên không ai chạy lại

Model Anthropic chưa công khai, tên tạm chưa công bố, hệ thống PSI thì nội bộ, Anthropic cũng chưa bình luận gì.

Người ngoài không chạy lại được quá trình tìm chứng minh trong 3 ngày, mà chỉ kiểm tra lại được chứng minh Lean đã công khai. Bản diễn giải của nhóm Stanford chưa xuất hiện công khai. The Neuron cảnh báo phản hồi của nhóm này mới chỉ là nhận xét từ những người trong cuộc, chưa phải kết luận của toàn giới chuyên môn.

AI tìm chứng minh, con người kiểm tra

Nói AI chứng minh xong giả thuyết thì dễ, nhưng muốn nói cho đúng thì phải tách phần máy làm và phần người làm, tài liệu PSI cũng không hề viết AI thay nhà toán học.

Mạng mạch xanh gặp nét vẽ hổ phách, gợi việc AI và con người. Ảnh tự vẽ.

Model Anthropic tìm kiếm, đề xuất, kiểm tra ý tưởng

Hệ thống do PSI tự phát triển và chạy trên hạ tầng của họ, với các bản sao model Anthropic chưa công khai. Các bản sao này tìm kiếm tài liệu, đề xuất ý tưởng mới, kết hợp và kiểm tra các ý tưởng.

Hệ thống có chứng minh đầy đủ vào ngày thứ 3, sau đó cải thiện thêm 2 lần. PSI ra mắt ngày 01/09/2026, gọi được vòng seed 58 triệu USD, rồi ngày 23/10/2026 đã công bố kết quả trên 5 bài toán mở.

David Turturean xây hệ thống, chịu trách nhiệm kiểm tra

David Turturean là tác giả duy nhất paper 60 trang, ông là người xây hệ thống, định phạm vi bài toán, chạy hệ thống, yêu cầu model đóng gói kết quả thành bản thảo, xem lại rồi chịu trách nhiệm về tính đúng đắn của nó.

Jim Halverson audit chứng minh, Phiala Shanahan nhận xét Lean

Jim Halverson là người audit chứng minh, còn Phiala Shanahan nhận xét phần Lean. PSI đã báo trước cho Aaronson vài tuần trước khi công bố. Aaronson thừa nhận ông không biết harness của PSI đóng góp bao nhiêu so với model Claude nội bộ.

Aaronson-Ambainis không giết chết quantum supremacy

Độc giả lướt mạng xã hội sẽ gặp hiểu lầm này nhiều nhất, và Aaronson cũng phản bác nó mạnh nhất trên blog của ông.

Sóng tuần hoàn và đám chấm rời rạc, gợi dữ liệu có cấu trúc và ngẫu nhiên. Hình vẽ tay.

Post X của Pedro Domingos: quantum supremacy đã chết

Pedro Domingos ở Đại học Washington đăng post X nói giấc mơ quantum supremacy đã chết, nguyên văn theo lời Aaronson trích lại là “the dream of quantum supremacy is dead.” Đăng cho 137.000 người theo dõi, nguồn là post X Aaronson trích lại trên blog ngày 08/11/2026.

Aaronson phản bác: chứng minh chỉ loại trừ một loại supremacy

Aaronson phản bác, chứng minh chỉ loại trừ một loại supremacy cụ thể. Nguyên văn ông viết:

“It rules out one particular type of quantum supremacy (namely, for yes-or-no problems relative to random oracles) that we’d already conjectured didn’t exist anyway. It doesn’t undermine any form of quantum supremacy that we did conjecture to exist!”

Dịch ý thì chứng minh này chỉ loại trừ đúng loại supremacy mà mọi người vốn đã đoán là không có. Aaronson gọi cách viết đó là thiếu trung thực về mặt trí tuệ.

Shor, mô phỏng lượng tử, Yamakawa-Zhandry đứng ngoài

Chứng minh không ảnh hưởng tới Shor vì Shor dùng oracle tuần hoàn chứ không ngẫu nhiên, cũng không ảnh hưởng tới mô phỏng vật lý hóa học lượng tử. Đột phá Yamakawa-Zhandry 2022 cho thấy chuyển sang NP search problem thì tốc độ tăng hàm mũ vẫn có thể xảy ra.

Định lý chỉ đếm số lần đọc đầu vào, không đếm tổng thời gian tính toán, chỉ đúng cho hầu hết đầu vào ngẫu nhiên với sai số cho trước.

Máy thường muốn bắt chước thì phải biết trước công thức đa thức, mà số lần đọc thêm tuy tăng theo lũy thừa cố định vẫn có thể rất lớn khi đòi độ chính xác cao. Cảnh báo nhỏ: đây không phải P bằng NP lượng tử, vì câu hỏi P có bằng BQP hay không vẫn mở.

Ba mốc cần theo dõi trước khi xong vụ này

Đọc xong bài này, anh em chỉ cần chờ ba mốc cụ thể dưới đây, mốc nào tới trước mình cập nhật bài thêm một dòng, đừng vội coi vụ này là xong.

Con đường dẫn tới ba điểm sáng xa, gợi ba mốc đang chờ. Mình vẽ lại.

Không chạy lại model, chỉ kiểm tra code Lean

Anh em đừng vội mong chạy lại được quá trình tìm chứng minh vì model không công khai, hệ thống PSI là nội bộ, mình chỉ kiểm tra được code Lean công khai trên GitHub. Repo là github.com/physical-superintelligence/aaronson-ambainis, mình mở ra kiểm chứng ngày 09/11/2026 thì thấy repo public, 58 sao, 1 commit, giấy phép Apache 2.0.

Ba mốc cần theo dõi: Stanford, Ambainis và peer review

Ba mốc đó là bản diễn giải nhóm Stanford, phản hồi công khai của Andris Ambainis, và peer review cùng việc PSI có nộp paper đi tạp chí không, tính đến 09/11/2026 thì cả ba đều chưa tới.

Bài cùng chuỗi AI toán học tháng 11

Bài này nằm trong đợt AI toán học dày đặc tháng 10 và 11 năm 2026. OpenAI công bố 722 bản thảo toán do AI viết tháng 10/2026 rồi rút 3 bài sau 1 ngày. Cùng tháng 10, OpenAI và Anthropic cũng bác bỏ giả thuyết ETH trong bài về thuật toán điểm 3-SAT đổi thời gian mũ.

Giả thuyết 18 năm thành định lý, peer review chờ

Bình minh trên biển với khối lập phương phát sáng mờ. Tự vẽ tay.

Giả thuyết mở từ 2008, bài gốc lên arXiv năm 2009, chứng minh đầy đủ có vào ngày thứ 3, exponent cải thiện từ 22 xuống 11 rồi 7, Lean kiểm chứng 648 định lý, Aaronson tin vì Lean và các chuyên gia đã đọc hiểu.

Nhưng chứng minh này không giết chết quantum supremacy, không chạm tới Shor hay mô phỏng vật lý hóa học. Peer review, phản hồi của Ambainis cùng bản diễn giải Stanford vẫn chưa xong, nên anh em cứ theo dõi đúng ba mốc đó.

Làm theo ngay: anh em mở repo GitHub ở trên, đọc README, rồi đọc định nghĩa PrintedConjecture dài khoảng 20 dòng trong file Conjecture.lean, đối chiếu với problem_statement.md.

Trong repo, thư mục verification lưu lại các lần kiểm tra bằng leanchecker, lean4lean và nanoda. Chỗ nào chưa hiểu thì cứ để lại bình luận, mình cập nhật bài ngay khi có mốc mới.

Nguồn tham khảo

• PSI, trang công bố Aaronson-Ambainis: https://psi.inc/research/aaronson-ambainis/
• Blog Shtetl-Optimized của Scott Aaronson, 08/11/2026: https://scottaaronson.blog/?p=10295
• madrobot.blog, 06/11/2026: https://madrobot.blog/2026/11/06/anthropic-model-proves-aaronson-ambainis-quantum-conjecture/
• The Quantum Insider, 06/11/2026: https://thequantuminsider.com/2026/11/06/ai-assisted-proof-settles-longstanding-question-about-quantum-speedups/
• The Neuron newsletter, 09/11/2026: https://www.theneuron.ai/newsletter/anthropic-s-ai-cracks-a-puzzle/
• Quantum Zeitgeist: https://quantumzeitgeist.com/an-ai-system-running-an-anthropic-model-settled-an-almost-20-year-old-conjecture-with-implications-for-quantum-speedup/
• MACCUS: https://maccus.fr/en/aaronson-ambainis-conjecture/
• Business Insider qua dnyuz, 07/11/2026: https://dnyuz.com/2026/11/07/an-unreleased-anthropic-model-just-helped-solve-a-major-quantum-computing-question/
• DearMyAI forum: https://dearmyai.com/forum/ai-proves-aaronson-ambainis-quantum-conjecture
• Quentir.ai: https://www.quentir.ai/blog/2026/psi-lean-4-proof-aaronson-ambainis-conjecture-anthropic-model-quantum-speedups-6-november-2026
• XenoSpectrum: https://xenospectrum.com/en/aaronson-ambainis-conjecture-proof-quantum-query-complexity/
• DigestAI: https://digestai.news/story/psi-proves-aaronson-ambainis-conjecture-using-anthropics-non-public-mo
• RuntimeWire: https://runtimewire.com/article/physical-superintelligence-aaronson-ambainis-proof
• Blog Aaronson về Keller và Klein năm 2019: https://scottaaronson.blog/?p=4414
• OfficeChai: https://officechai.com/ai/us-startup-physical-superintelligence-proves-aaronson-ambainis-conjecture-a-key-open-problem-in-quantum-computing/
• VectorWire: https://vectorwire.ai/article/psi-claims-ai-system-proved-quantum-computing-conjecture-open-since-2008-1c949d