kiến thức Giới hạn của máy tính cổ điển. Máy tính lượng tử có ưu việt hơn máy tính cổ điển không?

bribnt · 7/7/26

Gần đây thấy máy tính lượng tử được hype quá nhiều nên rảnh rỗi viết bài này.

Đây là box lập trình nên nội dung sẽ là "phần mềm" chứ không phải "phần cứng". Nên đối tượng bàn đến là những máy tính lượng tử hoàn hảo lý tưởng (vốn vẫn có rất xa mới thành hiện thực).

Nhiều người không tìm hiểu kỹ nên có những tưởng tượng quá đà về nó, coi như là một thiết bị ma thuật sẽ làm thay đổi hoàn toàn tương lai ngành tính toán. Hy vọng các bác đọc xong sẽ bớt thần thánh hóa nó lại, hoặc nếu có bạn sinh viên nào tự nhiên hứng thú muốn đi theo nghiên cứu mảng này thì quá tốt.

Các khái niệm trong bài này chỉ là trình bày lại theo cách hiểu của mình, không phải là định nghĩa chính quy, vì như vậy sẽ rất dài và phức tạp so với phạm vi của bài viết. Chủ yếu là nhắc lại, vì những ai học CS rồi đều đã quá quen thuộc với những khái niệm này.

Máy tính cổ điển làm được những gì? Hiệu quả ra sao?

Để hiểu về khả năng của máy tính lượng tử thì trước hết phải hiểu về khả năng của máy tính cổ điển.

TL;DR cho người đã biết:

Máy tính cổ điển có thể tính toán được tất cả các thuật toán mà con người có thể nghĩ được,
Máy tính cổ điển hiệu quả ngang với một máy Turing: có thể giải các bài toán lớp P trong thời gian đa thức O(n^k),
Vẫn chưa biết liệu máy tính cổ điển có thể giải được bài toán lớp NP trong thời gian đa thức hay không. Phần lớn tin là không.

Theo Mệnh đề Church - Turing:

Bất kỳ bài toán hay hàm toán học nào có thể giải được bằng một thuật toán trực quan (phương pháp cơ học) thì đều có thể tính toán được bằng một Máy Turing.

Về cơ bản mệnh đề cho rằng một máy Turing có thể tính toán được bất kỳ hàm toán học hay là một thuật toán bao gồm hữu hạn các bước tính toán xác định theo quy tắc cho trước nào đó.
Với phạm vi bài viết này, bạn không cần phải biết máy Turing là cái gì, chỉ cần hiểu nó là một mô hình lý thuyết có thể tính toán được mọi hàm số hoặc thuật toán.

Một mô hình tính toán được gọi là Turing hoàn chỉnh nếu nó có thể mô phỏng được hoạt động của máy Turing, tức là cũng sẽ có khả năng y hệt như máy Turing.

Có thể chứng minh được rằng mọi ngôn ngữ lập trình và kiến trúc máy tính thông dụng gần như (*) là Turing hoàn chỉnh. Điều này có nghĩa là mọi máy tính cổ điển có thể làm được mọi thứ mà máy Turing làm được.

(*) gọi là "gần như" là vì máy Turing yêu cầu một băng nhớ vô hạn, điều mà nhiều ngôn ngữ lập trình hiện nay không cung cấp. Tức là những ngôn ngữ này chính xác tương đương với một Automat tuyến tính giới nội (Linear bound automata - LBA) - một phiên bản yếu hơn của máy Turing, nhưng thực tế thì người ta thường bỏ qua yếu tố bộ nhớ khi xét đến tính chất Turing hoàn chỉnh.

Vậy có cái gì mà máy tính cổ điển không làm được? Có, những gì không tồn tại thuật toán thì nó không tính được. Bài toán tiêu biểu nhất là bài toán dừng: kiểm tra xem một máy Turing sẽ có thể dừng (sau hữu hạn các bước) hay không. Có thể chứng minh được là không tồn tại thuật toán nào để giải bài toán này.
Một số hệ quả của việc không thể giải bài toán dừng mà dân dev gặp thường ngày:

Chức năng phát hiện / xóa deadcode trên các IDE hoạt động không chính xác. Bởi vì không tồn tại một thuật toán nào để có thể biết được chắc chắn chương trình sẽ nhảy vào đoạn code đó hay không,
Trên một số trình dịch của ngôn ngữ như C hay C++, việc quên viết return ở ngoài mệnh đề if/else trong một hàm không phải void không được coi là lỗi mà chỉ là warning. Bởi vì cũng không tồn tại thuật toán nào để xác định chính xác hàm sẽ không 100% return ở trong các nhánh if/else đó. Nên chuẩn của ngôn ngữ không thể ép trình dịch làm theo.

Tính hiệu quả
Trong lý thuyết độ phức tạp tính toán thì một thuật toán được gọi là nhanh/hiệu quả/khả thi nếu nó có thể được thực hiện trong thời gian đa thức O(n^k) (có nghĩa là O(n) hay O(n^100000) thì đều hiệu quả).
Một mô hình tính toán nếu có thể mô phỏng một mô hình tính toán khác mà chỉ làm chậm và tốn bộ nhớ hơn ở theo hàm đa thức thì sự mô phỏng này được gọi là hiệu quả. Vì đa thức x đa thức = đa thức bậc cao hơn, thời gian thực hiện cuối cùng vẫn là đa thức.

Ví dụ: Để thực hiện một thuật toán trên máy Turing mất O(n) thời gian và không gian, nếu dùng một ngôn ngữ A mô phỏng máy Turing để thực hiện đúng thuật toán đó mà chậm và tốn bộ nhớ hơn O(n^3) thì A vẫn được coi là hiệu quả dù lúc này phải mất đến O(n^4) thời gian.

Tất cả máy tính và ngôn ngữ phổ biến hiện nay đều có thể mô phỏng hiệu quả máy Turing. Ngược lại máy Turing cũng có thể mô phỏng hiệu quả các máy tính và ngôn ngữ lập trình.

Kết luận: máy tính cổ điển hiểu quả như máy Turing.

Các lớp độ phức tạp
Ở đây chỉ giới thiệu hai lớp quan trọng nhất

P (Polynomial): gồm các bài toán quyết định (là bài toán chỉ có hai kết quả đúng/sai) có thể giải bằng máy Turing trong thời gian đa thức.
Ví dụ: tính tổng n số, nhân hai ma trận, giải hệ phương trình tuyến tính (chú ý phải phát biểu dưới dạng bài toán quyết định), kiểm tra tính nguyên tố (thuật toán AKS),

NP (Nondeterministic Polynomial): có hai định nghĩa tương đương

gồm các bài toán quyết định có thể kiểm chứng trong thời gian đa thức. Ví dụ bài toán TSP dạng quyết định: liệu có tồn tại đường đi tổng độ dài nhỏ hơn k hay không. Nếu có tồn tại đường đi x như vậy thì rõ ràng có thể kiểm chứng trong thời gian đa thức,
gồm các bài toán quyết định có thể giải bằng máy Turing không tất định (Nondeterministic Turing machine - NTM) trong thời gian đa thức.

Ở đây ta có khái niệm mới NTM - "máy Turing không tất định", về cơ bản là một biến thể của máy Turing trong đó ở mỗi bước có thể chọn để thực hiện nhiều hành động khác nhau. Tức là NTM có thể tạo ra nhiều nhánh tính toán khác nhau và thực hiện chúng cùng lúc và kết thúc thuật toán khi có một trong các nhánh đó hoàn thành.

Hình: máy Turing thực hiện từng bước theo một nhánh duy nhất. Máy Turing không tất định có thể phân ra nhiều nhánh ở mỗi bước, từng nhánh đó lại phân ra thành các nhánh con, ... Tổng số nhánh có thể tăng đến hàm mũ O(k^n).

Dựa vào mô tả thì có vẻ như NTM là một mô hình ưu việt hơn hẳn máy Turing thông thường (hay máy Turing tất định - DTM), gần như viễn tưởng, giống như là tính toán trên các vũ trụ song song. Vậy NTM có thật sự hiệu quả hơn DTM hay không?

Câu trả lời khá bất ngờ: không ai biết. Rõ ràng có thể mô phỏng DTM bằng NTM trong thời gian đa thức (vì DTM cũng chỉ là một trường hợp suy biến của NTM), và cũng có thể mô phỏng NTM bằng DTM trong thời gian hàm mũ bằng cách thử hết tất cả các nhánh. Nhưng vấn đề là không ai biết liệu có còn cách khác để mô phỏng NTM mà chỉ cần thời gian đa thức hay không.

Đây chính là bài toán P ?= NP nổi tiếng. Nếu P = NP thì có nghĩa là có thể dùng DTM (cũng có nghĩa là máy tính cổ điển) để mô phỏng NTM trong thời gian đa thức, nếu P ⊂ NP nghĩa là không có cách nào. Hiện nay phần lớn mọi người tin rằng P ⊂ NP, cũng có nghĩa là tin rằng máy tính cổ điển kém hiệu quả hơn NTM.

Tổng kết lại, khả năng của máy tính cổ điển:

có thể tính toán được tất cả các thuật toán mà con người có thể nghĩ được,
hiệu quả ngang với một máy Turing tất định: có thể giải các bài toán lớp P trong thời gian đa thức O(n^k),
Vẫn chưa biết liệu máy tính cổ điển có thể giải được bài toán lớp NP trong thời gian đa thức hay không. Phần lớn tin là không.

Khả năng của máy tính lượng tử

Tất cả các máy tính lượng tử đang phát triển hiện nay đều tương đương với máy Turing lượng tử - Quantum Turing Machine - QTM. Đây là một biến thể khác của máy Turing trong đó trạng thái cổ điển được thay bằng các trang thái trong không gian Hilbert và quy tắc chuyển đổi tất định thay bằng các phép biến đổi unitary.

Sức mạnh của máy tính lượng tử có thể được mô tả bằng quan hệ (nghi ngờ) giữa các lớp thuật toán như sau:

(

BQP - Bounded-error quantum polynomial: bài toán quyết định có thể giải quyết trong thời gian đa thức trên một QTM với sai số <= 1/3. Chú ý là 1/3 ở đây là chọn bất kỳ một số < 1/2, vì có thể tăng độ chính xác lên tùy ý bằng việc lặp lại quá trình nhiều lần
PSPACE: bài toán quyết định cần bộ nhớ tăng theo hàm đa thức.

)

BQP lớn hơn P => máy tính lượng tử giải được hiệu quả một số bài toán mà máy tính cổ điển sẽ mất nhiều thời gian hơn. Một trong số đó là bài toán số phân tích thừa số nguyên tố, có thể giải bằng thuật toán Shor O(n^3) trên máy tính lượng tử,
BQP không giao với NP complete => máy tính lượng tử không giải được hiệu quả các bài toán NP complete (bao gồm các bài kinh điển như TSP, Knapsack, SAT 3, ...),
BQP không nằm hoàn toàn trong NP => tồn tại những bài toán có thể giải được hiệu quả với máy tính lượng tử nhưng ngay cả máy Turing không tất định NTM cũng không giải hiệu quả được, tức là còn không thể kiểm chứng được kết quả trong thời gian đa thức. Một trong số đó là bài toán mô phỏng hệ lượng tử.

Có hai điều cần chú ý:

Tất cả các quan hệ của các lớp thuật toán như trên đều chưa được chứng minh, tất cả chỉ là niềm tin hiện tại của đa số. Tức là những ưu thế của máy tính lượng tử không phải là điều chắc chắn về lý thuyết mà chỉ là chưa tìm được thuật toán hiệu quả với máy tính cổ điển,
Để đạt được thời gian đa thức cần phải chấp nhận một sai số (có thể chọn được).

Ưu thế lượng tử
Trên lý thuyết máy tính lượng tử chưa được chứng minh là ưu việt hơn máy tính cổ điển ở bất kỳ một bài toán nào. Về mặt trực quan thì khó mà tưởng tượng được P = NP = BQP, nên phần lớn vẫn tin rằng ưu thế lượng tử là có thật.

Một số bài toán nổi bật nằm trong BQP nhưng được cho là không nằm trong P có thể kể đến:

Phân tích thừa số nguyên tố. Thuật toán Shor trên máy tính lượng tử có thể thực hiện trong O(n^3) bước, còn các thuật toán trên máy cổ điển tốt nhất hiện nay đều mất thời gian hàm mũ.
Ứng dụng: phá mã hóa RSA, ECC, trao đổi khóa Diffie - Hellman
Tìm trị riêng khi biết vector riêng của một ma trận Unitary: (tìm λ sao cho Uλ = Uv, v là vector riêng). Thuật toán cổ điển tốt nhất hiện nay mất thời gian đa thức đối với kích thước vector, tức là hàm mũ đối với số bit để biểu diễn vector. Còn thuật toán QPE (Quantum Phase Estimation) trên máy tính lượng tử chỉ mất O(N^4) (N là số qbit).
Ứng dụng:
- Là một bước của thuật toán Shor
- Nếu đặt U = exp(-i H t ) với H là Hamintonian của một hệ lượng tử và chạy QPE nhiều lần thì có thể tìm được mức năng lượng thấp nhất của hệ, bởi vì H là toán tử năng lượng. Có thể ứng dụng trong ngành hóa lượng tử để dự đoán được kết quả của phản ứng hóa học như sau:
  - Với các chất đầu vào, chuẩn bị kịch bản về các chuỗi phản ứng hóa học có thể xảy ra. Mô hình hóa, tìm Hamiltonian của các chất trung gian và kết quả,
  - Dùng QPE để xác định mức năng lượng thấp nhất của các hệ trước, giữa và sau phản ứng,
  - Theo nguyên tắc vật lý, nếu mức năng lượng của bước sau thấp hơn bước trước thì phản ứng này có thể xảy ra.
Giải hệ phương trình tuyến tính: Phương pháp cổ điển như khử Gauss mất O(n^3) số phép tính, tức là O(2^(3N)) với N là số bit. Thuật toán HHL trên máy tính lượng tử có thể giải bài toán với thời gian đa thức theo N. Tuy nhiên kết quả sẽ bị mã hóa theo một cách mà không thể đọc được toàn bộ các thành phần của nghiệm trong thời gian đa thức. Cho nên nó chỉ có tác dụng khi việc giải hệ phương trình chỉ là một bước trung gian của một thuật toán khác, hoặc khi không cần toàn bộ thông tin.
Hệ phương trình tuyến tính có mối liên hệ mật thiết với học máy, tuy nhiên do các hạn chế của nó nên không thể chỉ đơn giản là lắp HHL vào thay thế các thuật toán cũ. Hiện nay người ta đang thiết kế các mô hình học máy riêng để tận dụng tốc độ của HHL.

Tổng kết

Máy tính lượng tử chắc chắn không yếu hơn máy tính cổ điển. Hiện nay cũng chưa chứng minh được nó thực sự vượt trội hơn, mặc dù đây là khả năng rất cao.

Tuy vậy vấn đề lớn nhất vẫn là có quá ít bài toán mà máy tính lượng tử được cho là nhanh hơn hẳn máy tính cổ điển. Mà kể cả với những bài toán này thì vẫn có rất nhiều hạn chế chứ không phải là một sự thay thế hoàn hảo.
Nó cũng không (chưa) thể giúp tăng tốc giải các bài toán NP-hoàn chỉnh kinh điển vốn gặp rất nhiều trong đời sống.

Do vậy kể cả với tương lai tích cực nhất, máy tính lượng tử cũng sẽ không thay thế hoàn hoàn máy tính cổ điển mà sẽ đóng vai trò tương tự như GPU, dùng để tối ưu tăng tốc một số phép tính nhất định.

lakad312 · 9/7/26

uầy vch em đọc mà k hiểu gì luôn các bác ạ .... có cần phải học về cái gì đó liên quan tới máy tính như khoa học máy tính mới hiểu đc k vậy các bác :ops:

bribnt · 9/7/26

lakad312 đã nói:
uầy vch em đọc mà k hiểu gì luôn các bác ạ .... có cần phải học về cái gì đó liên quan tới máy tính như khoa học máy tính mới hiểu đc k vậy các bác

Có nhé.

Phải hiểu lý thuyết về độ phức tạp tính toán trước đã.

Konstante · 9/7/26

bribnt đã nói:
....
Các khái niệm trong bài này chỉ là trình bày lại theo cách hiểu của mình, không phải là định nghĩa chính quy, vì như vậy sẽ rất dài và phức tạp so với phạm vi của bài viết. Chủ yếu là nhắc lại, vì những ai học CS rồi đều đã quá quen thuộc với những khái niệm này.

Máy tính cổ điển làm được những gì? Hiệu quả ra sao?

Để hiểu về khả năng của máy tính lượng tử thì trước hết phải hiểu về khả năng của máy tính cổ điển.

TL;DR cho người đã biết:

Máy tính cổ điển có thể tính toán được tất cả các thuật toán mà con người có thể nghĩ được,

Máy tính cổ điển hiệu quả ngang với một máy Turing: có thể giải các bài toán lớp P trong thời gian đa thức O(n^k),

Vẫn chưa biết liệu máy tính cổ điển có thể giải được bài toán lớp NP trong thời gian đa thức hay không. Phần lớn tin là không.

Theo Mệnh đề Church - Turing:

Về cơ bản mệnh đề cho rằng một máy Turing có thể tính toán được bất kỳ hàm toán học hay là một thuật toán bao gồm hữu hạn các bước tính toán xác định theo quy tắc cho trước nào đó.
...

Đoạn này cần hết sức thận trọng.

Vì khái niệm "thuật toán" cần được định nghĩa bằng chính máy Turing (là cái mà ta có thể định nghĩa được chính xác), nếu nói "máy Turing có thể tính toán được mọi thuật toán" thì người ta sẽ lại hỏi "thế định nghĩa thế nào là thuật toán ?". Thực ra nên nói là "thuật toán là bất cứ thủ tục tính toán nào có thể mô tả được bởi một máy Turing".

Có cực kỳ nhiều (mạnh hơn nữa là tuyệt đại đa số) các hàm Toán học đều không thể tính được bằng một máy Turing. Điều này có thể chứng minh được một cách rất đơn giản bằng lập luận đường chéo của Cantor: tập các hàm tính được bởi máy Turing là tập đếm được, còn tập các hàm Toán học là không đếm được.

bribnt · 9/7/26

Konstante đã nói:
Đoạn này cần hết sức thận trọng.

Vì khái niệm "thuật toán" cần được định nghĩa bằng chính máy Turing (là cái mà ta có thể định nghĩa được chính xác), nếu nói "máy Turing có thể tính toán được mọi thuật toán" thì người ta sẽ lại hỏi "thế định nghĩa thế nào là thuật toán ?". Thực ra nên nói là "thuật toán là bất cứ thủ tục tính toán nào có thể mô tả được bởi một máy Turing".

Có cực kỳ nhiều (mạnh hơn nữa là tuyệt đại đa số) các hàm Toán học đều không thể tính được bằng một máy Turing. Điều này có thể chứng minh được một cách rất đơn giản bằng lập luận đường chéo của Cantor: tập các hàm tính được bởi máy Turing là tập đếm được, còn tập các hàm Toán học là không đếm được.

Uhm, đúng là chỗ này mình dùng từ "thuật toán" là gọi tắt thôi, chứ vẫn phải là nói về "các thủ tục tính toán" để không bị định nghĩa vòng. Chỗ hàm toán học cũng phải thêm điều kiện "đầu vào số nguyên" mới đúng.

Konstante · 9/7/26

bribnt đã nói:
....
Vậy có cái gì mà máy tính cổ điển không làm được? Có, những gì không tồn tại thuật toán thì nó không tính được. Bài toán tiêu biểu nhất là bài toán dừng: kiểm tra xem một máy Turing sẽ có thể dừng (sau hữu hạn các bước) hay không. Có thể chứng minh được là không tồn tại thuật toán nào để giải bài toán này.
Một số hệ quả của việc không thể giải bài toán dừng mà dân dev gặp thường ngày:

Chức năng phát hiện / xóa deadcode trên các IDE hoạt động không chính xác. Bởi vì không tồn tại một thuật toán nào để có thể biết được chắc chắn chương trình sẽ nhảy vào đoạn code đó hay không,

Trên một số trình dịch của ngôn ngữ như C hay C++, việc quên viết return ở ngoài mệnh đề if/else trong một hàm không phải void không được coi là lỗi mà chỉ là warning. Bởi vì cũng không tồn tại thuật toán nào để xác định chính xác hàm sẽ không 100% return ở trong các nhánh if/else đó. Nên chuẩn của ngôn ngữ không thể ép trình dịch làm theo.

...

Đoạn này cũng cần thận trọng.

Vì cả hai ví dụ đều không quá liên quan đến "bài toán dừng" (halting problem), mà chúng liên quan đến tính "không quyết định được" (undecidability) nói chung của static analysis.

Ví dụ thứ nhất, chức năng phát hiện/xóa deadcode chính là một thủ tục static analysis trên mã nguồn của chương trình.

Ví dụ thứ hai có thể nói là nhầm lẫn (nếu compiler đã warning được, nghĩa là nó đã phát hiện được). Ngôn ngữ C đơn giản là cho phép có lệnh return ở mọi nơi, và trình biên dịch tuân theo điều đó.

Konstante · 9/7/26

bribnt đã nói:
Uhm, đúng là chỗ này mình dùng từ "thuật toán" là gọi tắt thôi, chứ vẫn phải là nói về "các thủ tục tính toán" để không bị định nghĩa vòng. Chỗ hàm toán học cũng phải thêm điều kiện "đầu vào số nguyên" mới đúng.

Thực ra đầu vào số nguyên vẫn không thể được, vì tập các hàm từ N -> N sẽ có lực lượng N^N (N mũ N), tập này là không đếm được.

bribnt · 10/7/26

Konstante đã nói:
Đoạn này cũng cần thận trọng.

Vì cả hai ví dụ đều không quá liên quan đến "bài toán dừng" (halting problem), mà chúng liên quan đến tính "không quyết định được" (undecidability) nói chung của static analysis.

Ví dụ thứ nhất, chức năng phát hiện/xóa deadcode chính là một thủ tục static analysis trên mã nguồn của chương trình.

Ví dụ thứ hai có thể nói là nhầm lẫn (nếu compiler đã warning được, nghĩa là nó đã phát hiện được). Ngôn ngữ C đơn giản là cho phép có lệnh return ở mọi nơi, và trình biên dịch tuân theo điều đó.

Cả hai ví dụ này đều có thể chứng minh là undecidable bằng định lý Rice, vốn cũng suy ra từ bài toán dừng.

1. Đây không hẳn là về vấn đề của static analysis. Vì deadcode theo định nghĩa là code chắc chắn sẽ không được thực thi, bất kể đầu vào là gì đi nữa.

Ví dụ:

Python:

def f(x):
    if isnan(x):
        return

    if Complex_Condition(x):
        Code_If()
    else:
        Code_Else()

Nếu Complex_Condition(x) := sin(x)^2 + cos(x)^2 == 1 thì
case else chắc chắn sẽ không được nhảy vào dù x là gì đi nữa, nó chính là deadcode.
Nhưng bỏ if isNan(x) ở trên thì đoạn đó lại vẫn có thể nhảy vào trong trường hợp x là NaN, lúc này thì lại không phải là deadcode.

Một thuật toán DeadcodeDetect() hoàn hảo sẽ phải xác định xem Complex_Condition(x) có luôn trả về true hoặc luôn trả về false với mọi x không để suy ra có dead code hay không. Điều này là không thể theo định lý Rice.

2. Cũng tương tự y hệt phần trên:

Python:

def g(x):
    If Complex_Condition_1(x):
         return
    Elif Complex_Condition_2(x):
        return

Để xác định chính xác liệu hàm có luôn return hay không thì cần phải xác định được Complex_Condition_1(x) OR Complex_Condition_2(x) có luôn true hay không. Mà điều này cũng không thể do định lý Rice.

Thực ra nếu một ngôn ngữ chặt (kiểu như Java) thì nó sẽ bắt buộc phải có return ở cuối hàm, bất kể trên đó là gì, kiểu thà giết lầm còn hơn bỏ sót. Còn C/C++ thì tư tưởng tự do nên chỉ warning thôi.

Compiler Explorer - C++ (x86-64 gcc 16.1)

int f(int a, int b) { if ( (a+b) * (a+b) == a*a + b*b + 2*a*b ) { return 1; } } int g(int a, int b) { if ( (a+b) * (a+b) == a*a + b*b + 2*a*b ) { return 1; } else { return 0; } } int main(int argc, char *argv[]) { int a = argv[0][0], b =...

godbolt.org

Screenshot_20260710_014629_org.mozilla.firefox.webp

Compiler Explorer - Java (jdk 25.0.1)

class A{ int f(int a, int b) { if ( (a+b) * (a+b) == a*a + b*b + 2*a*b ) { return 1; } } int g(int a, int b) { if ( (a+b) * (a+b) == a*a + b*b + 2*a*b ) { return 1; } else { return 0; } } }

godbolt.org

Screenshot_20260710_014301_org.mozilla.firefox.webp

Mấy cái warning hay error đều là heuristic hoặc là pattern có sẵn chứ không phải là đã có thuật toán generic để xử lý. Kiểu như là nếu nó thấy có cấu trúc if/else mà không có return ở tất cả các case và thiếu return cuối hàm thì sẽ báo. Mặc dù những lúc này dev đã chắc chắn nó sẽ return do hiểu logic.

Konstante · 10/7/26

Mình biết, mình hiểu rất rõ mấy cái này. Nhưng trong ngữ cảnh của removing dead code, thì nó chính là static analysis. Và mọi phương pháp static analysis đều chịu sự chi phối của định lý Rice. Một trong những nhiệm vụ của static analysis chính là remove dead code (và trong trường hợp tổng quát thì là undecidable).

Ví dụ 2 thì bạn nhầm lẫn, và bạn đã nhận ra rồi nên mình không cần nói thêm. Chỉ lưu ý răng các thông báo của trình biên dịch không phải là heuristic đâu, nó là kết quả của sound but incomplete static analysis.

bribnt · 10/7/26

Konstante đã nói:
Mình biết, mình hiểu rất rõ mấy cái này. Nhưng trong ngữ cảnh của removing dead code, thì nó chính là static analysis. Và mọi phương pháp static analysis đều chịu sự chi phối của định lý Rice. Một trong những nhiệm vụ của static analysis chính là remove dead code (và trong trường hợp tổng quát thì là undecidable).

Ví dụ 2 thì bạn nhầm lẫn, và bạn đã nhận ra rồi nên mình không cần nói thêm. Chỉ lưu ý răng các thông báo của trình biên dịch không phải là heuristic đâu, nó là kết quả của sound but incomplete static analysis.

Thì ý ban đầu là vậy mà. Định lý Rice đặt một giới hạn lên các tool static analysis, mà bản thân định lý Rice cũng là hệ quả của việc Halting là undecidable. Nên việc các tool đó không bao giờ có thể hoạt động hoàn hảo cũng là do Halting.

Còn vụ return thì nếu nhìn theo quan điểm của người thiết kế ngôn ngữ: nếu thực sự có cách để xác định chính xác hàm sẽ return hay không thì nó sẽ trở thành rule của ngôn ngữ. Nhưng vì không thể nên các ngôn ngữ chỉ có thể check syntactic thay vì sematic, mà vì syntax thì không phải là chính xác nên có những ngôn ngữ chỉ warning, có ngôn ngữ cấm hẳn.

lienxo · 12/7/26

các bạn dùng nhiều kiến thức tóan học để giải trình phân biệt máy tính cổ điển và luợng tử.
hiểu đơn giản nó thế này : máy tính cổ điển xử lý dữ liệu theo cách tuần tựnghĩa là kết quả của phép tính truớc sẽ là đầu vào cho phép tính tiếp theo, bộ xử lỹ cpu họat động theo nguyên tác này. còn máy tính luợng tử chính là xử lý dữ liệu song song, qbit có bao nhiêu trạng thái thì chính là số luợng tính tóan cùng lúc . để máy tính cổ điển xử lý đuợc song song thì nó dùng cơ chế interupp ^ngẮt*.

Konstante · 14/7/26

bribnt đã nói:
....
Ưu thế lượng tử
Trên lý thuyết máy tính lượng tử chưa được chứng minh là ưu việt hơn máy tính cổ điển ở bất kỳ một bài toán nào. Về mặt trực quan thì khó mà tưởng tượng được P = NP = BQP, nên phần lớn vẫn tin rằng ưu thế lượng tử là có thật.

Một số bài toán nổi bật nằm trong BQP nhưng được cho là không nằm trong P có thể kể đến:

Phân tích thừa số nguyên tố. Thuật toán Shor trên máy tính lượng tử có thể thực hiện trong O(n^3) bước, còn các thuật toán trên máy cổ điển tốt nhất hiện nay đều mất thời gian hàm mũ.
Ứng dụng: phá mã hóa RSA, ECC, trao đổi khóa Diffie - Hellman

Tìm trị riêng khi biết vector riêng của một ma trận Unitary: (tìm λ sao cho Uλ = Uv, v là vector riêng). Thuật toán cổ điển tốt nhất hiện nay mất thời gian đa thức đối với kích thước vector, tức là hàm mũ đối với số bit để biểu diễn vector. Còn thuật toán QPE (Quantum Phase Estimation) trên máy tính lượng tử chỉ mất O(N^4) (N là số qbit).
Ứng dụng:

Là một bước của thuật toán Shor

Nếu đặt U = exp(-i H t ) với H là Hamintonian của một hệ lượng tử và chạy QPE nhiều lần thì có thể tìm được mức năng lượng thấp nhất của hệ, bởi vì H là toán tử năng lượng. Có thể ứng dụng trong ngành hóa lượng tửđể dự đoán được kết quả của phản ứng hóa học như sau:

Với các chất đầu vào, chuẩn bị kịch bản về các chuỗi phản ứng hóa học có thể xảy ra. Mô hình hóa, tìm Hamiltonian của các chất trung gian và kết quả,

Dùng QPE để xác định mức năng lượng thấp nhất của các hệ trước, giữa và sau phản ứng,

Theo nguyên tắc vật lý, nếu mức năng lượng của bước sau thấp hơn bước trước thì phản ứng này có thể xảy ra.

Giải hệ phương trình tuyến tính: Phương pháp cổ điển như khử Gauss mất O(n^3) số phép tính, tức là O(2^(3N)) với N là số bit. Thuật toán HHL trên máy tính lượng tử có thể giải bài toán với thời gian đa thức theo N. Tuy nhiên kết quả sẽ bị mã hóa theo một cách mà không thể đọc được toàn bộ các thành phần của nghiệm trong thời gian đa thức. Cho nên nó chỉ có tác dụng khi việc giải hệ phương trình chỉ là một bước trung gian của một thuật toán khác, hoặc khi không cần toàn bộ thông tin.
Hệ phương trình tuyến tính có mối liên hệ mật thiết với học máy, tuy nhiên do các hạn chế của nó nên không thể chỉ đơn giản là lắp HHL vào thay thế các thuật toán cũ. Hiện nay người ta đang thiết kế các mô hình học máy riêng để tận dụng tốc độ của HHL.

Tổng kết

Máy tính lượng tử chắc chắn không yếu hơn máy tính cổ điển. Hiện nay cũng chưa chứng minh được nó thực sự vượt trội hơn, mặc dù đây là khả năng rất cao.

Tuy vậy vấn đề lớn nhất vẫn là có quá ít bài toán mà máy tính lượng tử được cho là nhanh hơn hẳn máy tính cổ điển. Mà kể cả với những bài toán này thì vẫn có rất nhiều hạn chế chứ không phải là một sự thay thế hoàn hảo.
Nó cũng không (chưa) thể giúp tăng tốc giải các bài toán NP-hoàn chỉnh kinh điển vốn gặp rất nhiều trong đời sống.

Do vậy kể cả với tương lai tích cực nhất, máy tính lượng tử cũng sẽ không thay thế hoàn hoàn máy tính cổ điển mà sẽ đóng vai trò tương tự như GPU, dùng để tối ưu tăng tốc một số phép tính nhất định.

Gần đây mình có thấy kết quả này "Separating QMA from QCMA with a classical oracle" (ArXiv), bài này là best paper của STOC năm nay.

Đọc giải thích dành cho đại chúng trên quantamagazine mà không hiểu gì luôn, đại loại hiểu lơ mơ là bài báo chứng minh được một kết quả rất quan trọng về sức mạnh của quantum algorithm, nhưng vẫn chưa chứng minh được rằng máy tính lượng tử là ưu việt hơn.

zZ_K.I.A_Zz · 16/7/26

Quantum computer giờ chắc chỉ dùng để gen số ngẫu nhiên :shame:

bribnt · 18/7/26

zZ_K.I.A_Zz đã nói:
Quantum computer giờ chắc chỉ dùng để gen số ngẫu nhiên

Cái đó thì còn chẳng cần quantum computer.
Chỉ cần dùng một quá trình nào đó có bản chất quantum là đủ, đơn giản nhất như là như đo chuyển động trung bình của các hạt phân tử không khí cũng được.

Konstante đã nói:
Gần đây mình có thấy kết quả này "Separating QMA from QCMA with a classical oracle" (ArXiv), bài này là best paper của STOC năm nay.

Đọc giải thích dành cho đại chúng trên quantamagazine mà không hiểu gì luôn, đại loại hiểu lơ mơ là bài báo chứng minh được một kết quả rất quan trọng về sức mạnh của quantum algorithm, nhưng vẫn chưa chứng minh được rằng máy tính lượng tử là ưu việt hơn.

Mấy cái mà chứng mình máy tính lượng tử ưu việt hơn hiện giờ đều là dựa trên một cái "oracle" nào đó. Kiểu như nếu coi cả quantum lẫn classical đều có quyền access vào cái oracle đó với thời gian O(1) thì quantum sẽ nhanh hơn.

lienxo đã nói:
các bạn dùng nhiều kiến thức tóan học để giải trình phân biệt máy tính cổ điển và luợng tử.
hiểu đơn giản nó thế này : máy tính cổ điển xử lý dữ liệu theo cách tuần tựnghĩa là kết quả của phép tính truớc sẽ là đầu vào cho phép tính tiếp theo, bộ xử lỹ cpu họat động theo nguyên tác này. còn máy tính luợng tử chính là xử lý dữ liệu song song, qbit có bao nhiêu trạng thái thì chính là số luợng tính tóan cùng lúc . để máy tính cổ điển xử lý đuợc song song thì nó dùng cơ chế interupp ^ngẮt*.

Gọi là song song cũng được, nói chung cái này phụ thuộc vào cách diễn giải của cơ học lượng tử, hiện nay chưa thống nhất.
Nhưng vấn đề lớn nhất là cho dù có song song thì ta cũng không thể tự dưng mà lấy được tất cả các kết quả đó.

Ví dụ: cho một hàm f(x), với x ∈ {1, 2, ..., 2^n}, máy tính lượng tử có thể tính hết f(1), f(2), ... f(2^n) trong một bước chỉ với n qubit. Nhưng mà không có cách nào để trích ra được các kết quả đó, mà chỉ có thể lấy được một trạng thái ngẫu nhiên theo một xác suất có thể tính trước.

Nên là muốn tận dụng tính chất này thì phải có cách để biến đổi sao cái mà mình cần có xác suất lớn nhất. Nói chung là rất khó, cho nên là đến tận bây giờ người ta vẫn chưa chứng minh chặt chẽ được là máy tính lượng tử thực sự ưu việt hơn.

Konstante · 18/7/26

Hỏi cái này sợ không đúng chỗ, nhưng mình cứ mạnh dạn hỏi.

Thím đánh giá về FHE (Fully Homomorphic Encryption) thế nào? Các sơ đồ cho FHE hiện tại đều dựa vào LWE (Learning With Error) là post-quantum cryptographic algorithm. Nhược điểm của FHE hiện tại là cực chậm.

Hiện tại đang thương mại hóa FHE có Zama. Nhưng Zama có vẻ như có mỗi hướng là theo blockchain (cái này về quan điểm cá nhân mình thấy không ổn lắm, nhưng đương nhiên là họ có lý do).

quocdat · 22/7/26

Có thể tóm gọn lại như sau:

Bộ xử lý lượng tử hoạt động theo nguyên lý khác với bộ xử lý máy tính thông thường.
Bộ xử lý lượng tử chỉ có ưu thế trong một số tình huống đặc biệt và cần thuật giải đặc biệt.
Các máy tính thông thường hiện tại đang xử lý hầu hết các tình huống mà loài người đang cần.
Do đó máy tính lượng tử không phải là thiết bị thay thế máy tính thông thường mà nó là máy tính có bộ xử lý lượng tử sẽ đóng vai trò như một bộ đồng xử lý (co-processor), tức là một bộ xử lý phụ.
Máy tính lượng tử sẽ bao gồm máy tính thông thường (Turing CPU) và bộ đồng xử lý lượng tử (Quantum CPU). Trong đó Turing CPU sẽ xử lý các tác vụ thông thường của giải thuật, đến khi cần thuật toán đặc biệt của Quantum CPU thì nó sẽ chuyển dữ liệu sang Quantum CPU xử lý. Kết quả thu về sẽ được Turing CPU xử lý và thể hiện với giao diện người dùng.

kiến thức Giới hạn của máy tính cổ điển. Máy tính lượng tử có ưu việt hơn máy tính cổ điển không?

bribnt

Đã tốn tiền

lakad312

Senior Member

bribnt

Đã tốn tiền

Konstante

Senior Member

bribnt

Đã tốn tiền

Konstante

Senior Member

Konstante

Senior Member

bribnt

Đã tốn tiền

Compiler Explorer - C++ (x86-64 gcc 16.1)

Compiler Explorer - Java (jdk 25.0.1)

Tệp đính kèm

Konstante

Senior Member

bribnt

Đã tốn tiền

lienxo

Senior Member

Konstante

Senior Member

zZ_K.I.A_Zz

Senior Member

bribnt

Đã tốn tiền

Konstante

Senior Member

quocdat

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này