Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Độ phức tạp tính toán lượng tử

Nâng caokhoảng 60 giờ6 bước

Các lớp BQP và QMA, mô hình truy vấn và oracle, giới hạn của máy tính lượng tử, và lập luận về ưu thế lượng tử (lấy mẫu mạch ngẫu nhiên, lấy mẫu boson): điều gì máy tính lượng tử làm được nhanh hơn và điều gì không (tham chiếu MIT 8.371 và Scott Aaronson).

Bắt đầu học

Bạn sẽ học được gì

  • Định nghĩa P, NP, BPP, PSPACE, BQP, QMA và đặt các thuật toán lượng tử đã học vào đúng lớp
  • Chứng minh phác thảo BPP ⊆ BQP ⊆ PP ⊆ PSPACE và phân biệt rõ kết quả đã chứng minh với giả thuyết được tin là đúng
  • Áp dụng phương pháp đa thức và phương pháp đối thủ để chứng minh cận dưới truy vấn, gồm cận √N cho tìm kiếm
  • Giải thích ý nghĩa của tách biệt tương đối với oracle và vì sao chúng không phải chứng minh vô điều kiện
  • Phát biểu bài toán Hamiltonian cục bộ, tính QMA-đầy đủ của nó và hệ quả với mô phỏng hóa học lượng tử
  • Phân tích một thí nghiệm ưu thế lượng tử: bài toán, lập luận độ phức tạp, vai trò của nhiễu và các mô phỏng cổ điển phản bác

Nên học trước

Giới thiệu

Độ phức tạp tính toán lượng tử hỏi câu hỏi mà mọi kỹ sư lượng tử cần một câu trả lời trung thực: máy tính lượng tử về nguyên tắc làm được gì mà máy cổ điển không làm được hiệu quả, và không làm được gì? Chủ đề đặt các thuật toán đã học vào bản đồ các lớp độ phức tạp, học cách chứng minh cận dưới, và xem xét các thí nghiệm "ưu thế lượng tử" với con mắt phê phán. Nội dung theo MIT 8.371 (phần độ phức tạp) và sách Quantum Computing since Democritus của Scott Aaronson.

Bản đồ các lớp

Ôn trước các lớp cổ điển: P (giải được trong thời gian đa thức), NP (kiểm tra được lời giải trong thời gian đa thức), BPP (thuật toán ngẫu nhiên đúng với xác suất ít nhất 2/3), PSPACE (bộ nhớ đa thức). Lớp lượng tử trung tâm là BQP: bài toán giải được bởi họ mạch lượng tử kích thước đa thức (sinh ra đều) với xác suất đúng ít nhất 2/3.

Điều đã chứng minh: BPP ⊆ BQP ⊆ PP ⊆ PSPACE. Chiều cuối đến từ ý tưởng tổng theo mọi đường đi của Feynman: biên độ cuối là tổng của rất nhiều số hạng, mỗi số hạng tính được với bộ nhớ nhỏ. Phân tích thừa số nằm trong BQP (Shor).

Điều chỉ là niềm tin, chưa chứng minh:

  • BQP chứa bài toán không thuộc BPP — tức máy lượng tử thật sự mạnh hơn. Chứng minh điều này sẽ kéo theo P khác PSPACE, một câu hỏi mở lớn.
  • NP không nằm trong BQP — tức máy lượng tử không giải hiệu quả được bài toán NP-đầy đủ. Bằng chứng: cận dưới √N của tìm kiếm không cấu trúc và việc chưa ai tìm được thuật toán như vậy.
  • Phân tích thừa số không thuộc BPP.

Với oracle, người ta chứng minh được các tách biệt: có oracle tương đối với nó BQP chứa bài toán nằm ngoài cả hệ phân cấp đa thức PH (Raz và Tal, 2018). Kết quả tương đối hóa như vậy là bằng chứng, không phải chứng minh cho thế giới không có oracle.

Cận dưới truy vấn

Trong mô hình truy vấn ta chứng minh được giới hạn chắc chắn. Phương pháp đa thức dựa trên quan sát: sau T truy vấn, xác suất chấp nhận là đa thức bậc tối đa 2T theo các biến đầu vào; phương pháp đối thủ đo tiến bộ mà mỗi truy vấn có thể tạo ra. Hai phương pháp cho cận dưới √N của tìm kiếm, ∛N của bài toán va chạm, và cho thấy máy lượng tử không tăng tốc được hàm mũ trên hàm tổng quát không có cấu trúc.

QMA: phiên bản lượng tử của NP

QMA gồm các bài toán mà lời khai là một trạng thái lượng tử có thể được kiểm tra bởi máy lượng tử đa thức. Kitaev chứng minh bài toán Hamiltonian cục bộ là QMA-đầy đủ — tương tự lượng tử của định lý Cook–Levin. Hệ quả thực tế: tìm năng lượng trạng thái cơ bản của một Hamiltonian cục bộ tổng quát là khó ngay cả với máy tính lượng tử (theo các giả thiết độ phức tạp chuẩn), nên các thuật toán hóa học lượng tử phải khai thác cấu trúc của bài toán cụ thể hoặc cần trạng thái ban đầu tốt.

Ưu thế lượng tử: đọc thí nghiệm thế nào

Năm 2019, nhóm Google chạy lấy mẫu mạch ngẫu nhiên trên chip 53 qubit và ước lượng máy cổ điển cần hàng nghìn năm; sau đó các phương pháp mạng tensor và các siêu máy tính đã rút ngắn con số đó rất nhiều. Các thí nghiệm lấy mẫu boson bằng photon (Jiuzhang, 2020) và các máy siêu dẫn lớn hơn tiếp tục cuộc đua. Lập luận độ phức tạp đằng sau (Aaronson – Arkhipov và các công trình sau) cho thấy lấy mẫu chính xác là khó với máy cổ điển nếu hệ phân cấp đa thức không sụp đổ; với lấy mẫu có nhiễu như trên phần cứng thật, cơ sở lý thuyết yếu hơn. Năm 2024–2025 Google công bố lấy mẫu mạch ngẫu nhiên trên chip Willow và một phép đo "tiếng vọng lượng tử" được giới thiệu là kiểm chứng được; hãy đọc chúng với cùng các câu hỏi đó. Bài học cho kỹ sư: phân biệt "khó mô phỏng" với "hữu ích", và chờ các kiểm chứng độc lập.

Nên học thế nào

  • Sách chính là Quantum Computing since Democritus (văn phong như bài giảng, chặt chẽ nhưng dí dỏm); phần độ phức tạp truy vấn trong ghi chép của Andrew Childs; chuyên khảo của Kitaev, Shen và Vyalyi cho định nghĩa hình thức và QMA.
  • Ôn độ phức tạp cổ điển trước: khóa Lý thuyết tính toán trên trang đủ cho P, NP, quy dẫn và độ đầy đủ.
  • Viết lại mỗi kết quả kèm giả thiết: "đã chứng minh", "đúng tương đối với oracle", hay "được tin là đúng".

Chủ đề cần Thuật toán lượng tử và lý thuyết tính toán.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Có phíTrung bìnhTiếng Anh370 trang

Vì sao chọn: Sách của Scott Aaronson (Cambridge University Press) phát triển từ loạt bài giảng: từ tính toán được và độ phức tạp cổ điển tới BQP, chứng minh lượng tử, kích thước trạng thái lượng tử, các lập luận hoài nghi và học. Chọn làm sách chính vì trình bày độ phức tạp lượng tử sinh động mà vẫn chặt chẽ. Sách trả phí.

Nên đọc: Chương 5–7, 9–10, 13–17

Classical and Quantum Computation

A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi · 2002

Có phíNâng caoTiếng Anh257 trang

Chuyên khảo ngắn mà sâu của Kitaev, Shen và Vyalyi (American Mathematical Society): độ phức tạp cổ điển, mô hình mạch lượng tử, lớp BQP và lớp BQNP (nay thường gọi là QMA) với chứng minh bài toán Hamiltonian cục bộ là đầy đủ. Mục được dẫn theo tiêu đề. Sách trả phí.

Nên đọc: Các mục Boolean circuits; The class NP; BPP; Definition of quantum computation; BQNP

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Ôn độ phức tạp cổ điển: P, NP, BPP và mạch Boole

    khoảng 10 giờ

    Ôn máy Turing, P, NP, quy dẫn, NP-đầy đủ, thuật toán ngẫu nhiên và BPP, mạch Boole và PSPACE; có thể dùng khóa Lý thuyết tính toán trên trang. Bài tập: chứng minh BPP không đổi khi thay ngưỡng 2/3 bằng 1 − 2⁻ⁿ (lặp lại và bất đẳng thức Chernoff); quy dẫn 3-SAT về bài toán tập độc lập; giải thích vì sao ta tin P khác NP nhưng chưa chứng minh được.

  2. Bước 2: BQP và vị trí của nó

    khoảng 10 giờ

    Học định nghĩa BQP qua họ mạch sinh ra đều, khuếch đại xác suất đúng, BPP ⊆ BQP và BQP ⊆ PP ⊆ PSPACE qua tổng theo đường đi. Bài tập: viết chương trình tính một biên độ đầu ra của mạch H và Toffoli bằng tổng theo đường đi, so với mô phỏng vectơ trạng thái, và so bộ nhớ – thời gian của hai cách; lập bảng mỗi thuật toán đã học (Deutsch–Jozsa, Simon, Shor, Grover) với mô hình chi phí và kết quả so sánh là đã chứng minh hay chỉ so với thuật toán tốt nhất đã biết.

  3. Bước 3: Độ phức tạp truy vấn và cận dưới

    khoảng 10 giờ

    Học mô hình truy vấn, phương pháp đa thức, bài toán va chạm và phương pháp đối thủ. Bài tập: chứng minh cận dưới √N cho hàm OR bằng phương pháp đa thức (đối xứng hóa, bất đẳng thức Markov) và bằng phương pháp đối thủ; giải thích vì sao cận ∛N cho bài toán va chạm có nghĩa là máy tính lượng tử không phá được hàm băm chỉ bằng truy vấn nhanh hơn mức đó.

    • Đọc: Chương 21 Query complexity and the polynomial method; Chương 22 The collision problem; Chương 23 The quantum adversary method — Lecture Notes on Quantum Algorithms
  4. Bước 4: QMA và bài toán Hamiltonian cục bộ

    khoảng 10 giờ

    Học QMA (trong sách của Kitaev gọi là BQNP), kiểm tra lời khai lượng tử, cấu trúc chứng minh QMA-đầy đủ của bài toán Hamiltonian cục bộ (Hamiltonian lịch sử của Feynman – Kitaev) và kích thước của trạng thái lượng tử. Bài tập: dựng Hamiltonian lịch sử cho một mạch 2 bước trên 1 qubit, tính phổ bằng NumPy và nhận ra trạng thái cơ bản mã hóa toàn bộ phép tính; viết một trang giải thích vì sao kết quả này không mâu thuẫn với việc dùng máy lượng tử cho hóa học.

  5. Bước 5: Ưu thế lượng tử và các tranh luận

    khoảng 10 giờ

    Đọc các lập luận hoài nghi về máy tính lượng tử và cách trả lời, rồi đọc bài báo thí nghiệm lấy mẫu mạch ngẫu nhiên năm 2019 của Google (Nature), bài lấy mẫu boson Jiuzhang năm 2020 (Science) và ít nhất một công trình mô phỏng cổ điển phản bác. Bài tập: lập bảng cho mỗi thí nghiệm: bài toán, kích thước, độ trung thực, thời gian lượng tử, ước lượng cổ điển ban đầu và ước lượng sau này; mô phỏng lấy mẫu mạch ngẫu nhiên 12 qubit và tính đại lượng cross-entropy benchmarking với mẫu lý tưởng và mẫu có nhiễu khử phân cực.

  6. Bước 6: Học, chứng minh tương tác và giới hạn: bài luận tổng kết

    khoảng 10 giờ

    Đọc về học trạng thái lượng tử, chứng minh tương tác và cận dưới mạch; tìm hiểu vì sao kiểm chứng một phép tính lượng tử bằng máy cổ điển là bài toán nghiên cứu riêng. Bài luận ba trang: chọn một tuyên bố gần đây về lợi thế lượng tử (tối ưu hóa, học máy hoặc mô phỏng), phân loại từng khẳng định thành đã chứng minh, đúng tương đối với oracle, dựa trên giả thuyết hay chỉ là thực nghiệm, và nêu thí nghiệm hoặc định lý nào sẽ thay đổi kết luận.

Khái niệm chính

BQP
Lớp bài toán quyết định giải được bởi họ mạch lượng tử kích thước đa thức sinh ra đều, với xác suất trả lời đúng ít nhất 2/3 trên mọi đầu vào; ngưỡng 2/3 có thể nâng gần 1 bằng lặp lại và lấy đa số.
BPP ⊆ BQP ⊆ PP ⊆ PSPACE
Các bao hàm đã chứng minh: máy lượng tử mô phỏng được thuật toán ngẫu nhiên, và máy cổ điển mô phỏng được máy lượng tử với bộ nhớ đa thức (tổng theo đường đi) dù có thể mất thời gian hàm mũ. Chưa bao hàm nào được chứng minh là chặt.
BQP và NP
Quan hệ giữa hai lớp chưa biết. Giới nghiên cứu tin rằng các bài toán NP-đầy đủ không thuộc BQP, dựa trên cận dưới √N của tìm kiếm không cấu trúc và việc thiếu thuật toán; đây là giả thuyết, không phải định lý.
Tách biệt tương đối với oracle
Kết quả chứng minh hai lớp khác nhau khi cả hai được truy cập cùng một hộp đen, ví dụ tồn tại oracle mà BQP chứa bài toán ngoài PH (Raz và Tal, 2018); là bằng chứng mạnh nhưng không suy ra được tách biệt vô điều kiện.
Phương pháp đa thức
Sau T truy vấn, xác suất chấp nhận của thuật toán lượng tử là đa thức bậc tối đa 2T theo các bit đầu vào; cận dưới bậc xấp xỉ của hàm cần tính cho cận dưới số truy vấn, ví dụ √N với hàm OR.
Phương pháp đối thủ
Kỹ thuật chứng minh cận dưới truy vấn bằng cách đo mức độ mà mỗi truy vấn có thể làm các trạng thái ứng với những đầu vào khó phân biệt tách rời nhau; phiên bản tổng quát cho cận gần như chặt với mọi hàm.
QMA
Tương tự lượng tử của NP: lời khai là trạng thái lượng tử đa thức qubit, người kiểm tra là mạch lượng tử đa thức, chấp nhận lời khai đúng với xác suất ít nhất 2/3 và không bị lừa quá 1/3.
Bài toán Hamiltonian cục bộ
Cho Hamiltonian là tổng các số hạng tác động lên ít qubit, quyết định năng lượng trạng thái cơ bản dưới ngưỡng a hay trên ngưỡng b; Kitaev chứng minh bài toán là QMA-đầy đủ, nên trong trường hợp tổng quát nó khó cả với máy tính lượng tử.
Hệ phân cấp đa thức (PH)
Chuỗi các lớp mở rộng NP bằng lượng từ tồn tại và với mọi xen kẽ; giả thuyết PH không sụp đổ là nền của nhiều lập luận khó cho máy cổ điển, gồm lập luận cho lấy mẫu boson và lấy mẫu mạch ngẫu nhiên.
Lấy mẫu mạch ngẫu nhiên
Bài toán tạo mẫu từ phân bố đầu ra của một mạch lượng tử ngẫu nhiên; dùng trong thí nghiệm ưu thế lượng tử năm 2019 với đại lượng kiểm tra cross-entropy benchmarking, và bị thách thức bởi các mô phỏng mạng tensor sau đó.
Lấy mẫu boson
Bài toán lấy mẫu vị trí của các photon không phân biệt được sau một mạng giao thoa tuyến tính; xác suất liên quan tới permanent của ma trận, đại lượng khó tính cổ điển, nên lấy mẫu chính xác được cho là khó nếu PH không sụp đổ.
Ưu thế lượng tử
Trình diễn một thiết bị lượng tử giải một bài toán xác định nhanh hơn mọi máy cổ điển hiện có; tuyên bố gắn với thời điểm, bài toán có thể không hữu ích, và có thể bị thu hẹp khi thuật toán cổ điển tiến bộ.

Học xong để làm gì

  • Thẩm định tuyên bố tăng tốc hay ưu thế lượng tử của doanh nghiệp, bài báo và báo chí
  • Chọn bài toán ứng dụng có khả năng hưởng lợi thật từ máy tính lượng tử và loại bỏ bài toán không có hy vọng
  • Hiểu cơ sở độ khó của mật mã hậu lượng tử (vì sao tin rằng bài toán mạng tinh thể không thuộc BQP)
  • Đánh giá giới hạn của thuật toán hóa học lượng tử qua tính QMA-đầy đủ của bài toán Hamiltonian cục bộ
  • Nền cho nghiên cứu về thuật toán lượng tử và kiểm chứng thiết bị lượng tử

Câu hỏi thường gặp

Có chứng minh được máy tính lượng tử mạnh hơn máy tính cổ điển không?

Chưa, theo nghĩa vô điều kiện. Chứng minh BQP khác BPP sẽ kéo theo P khác PSPACE, một câu hỏi mở lớn của khoa học máy tính. Những gì có là tách biệt trong mô hình truy vấn, tách biệt tương đối với oracle, và các lập luận khó dựa trên giả thuyết như PH không sụp đổ.

Thí nghiệm ưu thế lượng tử có nghĩa là máy lượng tử đã hữu ích?

Không. Các thí nghiệm này chọn bài toán lấy mẫu được thiết kế để khó mô phỏng, không có ứng dụng trực tiếp, và con số thời gian cổ điển thường bị rút ngắn khi có thuật toán mô phỏng mới. Chúng là cột mốc về kiểm soát phần cứng và độ phức tạp, không phải bằng chứng về lợi ích thực tế.

Tôi cần nền độ phức tạp cổ điển đến mức nào?

Cần nắm máy Turing, P, NP, quy dẫn đa thức, NP-đầy đủ, thuật toán ngẫu nhiên và BPP. Chủ đề Theory of Computation của lộ trình Khoa học máy tính và khóa Lý thuyết tính toán trên trang đủ cho phần này.

Có cần mua sách không?

Sách của Aaronson và của Kitaev, Shen, Vyalyi là sách trả phí; ghi chép của Andrew Childs miễn phí. Aaronson cũng công bố miễn phí nhiều ghi chép bài giảng trên trang cá nhân, có thể đọc thay thế một phần.

60 giờ có đủ không?

Đủ để nắm bản đồ các lớp, hai phương pháp cận dưới, QMA và đọc có phê phán các thí nghiệm ưu thế. Một học phần độ phức tạp lượng tử ở bậc cao học cần khoảng 120–150 giờ với nhiều chứng minh.

Chọn nguồn tự học

Cần nền lý thuyết tính toán cổ điển trước; sau đó đọc một cuốn nhập môn độ phức tạp lượng tử viết dễ hiểu, rồi một giáo trình chặt chẽ hơn về các lớp độ phức tạp lượng tử; đọc kèm các bài báo ưu thế lượng tử với con mắt phê phán.