[anatta]

Computer Lượng Tử có thể 'xử lý' bài toán không giải được

Nhà khoa học Australia gốc Việt, Kiều Tiến Dũng đã có một khám phá có thể làm cho nền toán học và khoa học computer của thế kỷ trước vượt qua được giới hạn của chính nó: Những bài toán từng được coi là "không giải được" hoặc "không tính được" có thể sẽ giải được bằng cách sử dụng những tính chất bí ẩn của cơ học lượng tử.

Công trình này hiện thu hút sự chú ý của nhiều nhà khoa học trên thế giới.

Hoàn toàn độc lập với Kiều Tiến Dũng, hai nhà khoa học New Zealand là Christian Calude và Boris Pavlov cũng đi đến những kết luận tương tự. Tạp chí New Scientist, một tạp chí tiên phong trong việc giới thiệu những tư tưởng mới trong khoa học, bình luận: Đó là một cuộc tấn công táo bạo vào chính những giới hạn của toán học, nhờ đó có thể lấy lại những kho báu mà chúng ta tưởng rằng vĩnh viễn sẽ nằm ở phía bên kia tầm với.

1- Giới hạn tính toán bằng computer

Alan Turing.

Mặc dù computer ngày nay làm được biết bao nhiêu điều kỳ diệu, nhưng nó có những hạn chế nội tại không thể vượt qua. Người có công khám phá ra điều này là Alan Turing (1912-1954), nhà toán học xuất sắc người Anh, chuyên gia giải mã kỳ tài của Anh trong Chiến tranh thế giới thứ II, được coi là một trong những cha đẻ của khoa học computer ngày nay.

Ngay từ năm 1936, Turing đã phác thảo ra thiết kế của một chiếc máy tính hoạt động theo chương trình, được gọi là máy Turing (Turing Machine). Về nguyên tắc, đó chính là cái mà bây giờ chúng ta gọi là computer. Sau chiến tranh ông dồn hết nỗ lực vào việc tìm nguyên lý hoạt động cho chiếc máy tưởng tượng của mình. Năm 1954, ông tự sát vì bị kết tội đồng tính luyến ái, để lại cho đời một tác phẩm bất hủ, được liệt vào danh sách 10 công trình khoa học tuyệt tác của thế kỷ 20: "On the Computability of Numbers" (Về khả năng có thể tính toán bằng số). Nội dung cơ bản của công trình này chỉ rõ khi nào một bài toán có thể giải được (bằng số) và khi nào thì không.

Gần như đồng thời, Alonzo Church, một nhà logic toán học nổi tiếng tại Đại học Princeton cũng cho công bố một bài báo nhan đề "Một bài toán không giải được của lý thuyết số sơ cấp" (An Unsolvable Problem of Elementary Numbertheory), trong đó chỉ ra rằng có những bài toán không thể giải được bằng thuật toán. Ngay lập tức, Turing chứng minh rằng kết luận của Church tương đương với kết luận của chính ông. Kết luận đó đã đi vào lịch sử của khoa học tính toán như một nguyên lý nền tảng về khả năng giải được hoặc không giải được của một bài toán, được gọi là Luận đề Turing-Church (Turing-Church Thesis) với nội dung cơ bản như sau:

Nếu một bài toán có thể giải được bằng cách sử dụng một tập hợp các quy tắc rõ ràng trong một số bước hữu hạn, thì bài toán đó có thể giải được bằng một chương trình trên computer, và ngược lại.

Thiết kế sơ bộ của máy Turing.

Nói một cách đơn giản: Một bài toán được coi là giải được nếu có thể tìm được một thuật toán hữu hạn để giải nó. Nếu không, bài toán là không giải được. Thực chất luận đề này là sự tổng quát hóa nguyên tắc lập trình cho computer hiện đại. Nó đã trở thành nền tảng, "sách gối đầu giường", một định nghĩa bất khả kháng của khoa học tính toán.

Sau khi khẳng định nguyên lý hoạt động cho chiếc máy của mình, Turing đặt vấn đề: Phải chăng có những bài toán đòi hỏi một thời gian vô hạn để giải? Và ông đã tìm ra một bài toán cụ thể thuộc loại đó - bài toán Tính dừng - SCTM (The Halting Problem) nổi tiếng. Nội dung cụ thể là:

Liệu có thể tiên đoán một chương trình cho trước sẽ ngừng hoặc chạy vòng quanh mãi mãi hay không? Turing trả lời: Không, không thể tiên đoán được. Do đó không thể khắc phục được sự cố này.

Trong khi sử dụng computer, ai cũng có thể gặp SCTM. Gặp sự cố này chúng ta chỉ có cách kiên trì chờ đợi hoặc bấm nút "restart" (khởi động lại). Các nhà khoa học computer sau này cũng tiếp tục xác nhận rằng không có ngôn ngữ chương trình nào (Pascal, BASIC, Prolog, C,...) có thể có được một công cụ cho phép khám phá ra mọi sai hỏng (bugs) dẫn tới ngưng hoạt động hoặc gây ra những vòng xử lý (processing loops) kéo dài vô tận.

Tính dừng là bài toán điển hình về hạn chế của computer. Sau này các nhà khoa học computer còn xác định được nhiều bài toán hạn chế khác như bài toán virus, bài toán tìm chương trình tối ưu cho một hoạt động định trước. Các nhà toán học cho rằng cơ sở logic của tính hạn chế này là Định lý bất toàn của Kurt Godel: Bất kỳ một hệ logic hình thức nào cũng không đủ mạnh để tự nó chứng minh nó phi mâu thuẫn, suy ra computer cũng không thể khắc phục được những sai hỏng trong những bài toán mà nó phải tự "xử lý" nó. Gregory Chaitin tại IBM còn cho rằng nguyên nhân của những hạn chế đó là ở chỗ tính ngẫu nhiên không phải chỉ tác động trong vật lý (như trong cơ học lượng tử), mà tác động ngay cả trong toán học. Chẳng hạn, số nguyên tố là hiện tượng mang tính ngẫu nhiên mà toán học không thể tìm ra những quy tắc xác định thống trị chúng. Tóm lại các hệ logic cũng chứa đựng tiềm ẩn tính bất định!

Với tất cả những lý lẽ đó, khoa học computer dựa trên Luận đề Turing-Church đã tự đặt ra một giới hạn không thể vượt qua. Đó là một kết luận mang ý nghĩa như một "chân lý không thể thay đổi", một nguyên lý "bất di bất dịch", một cột mốc "vĩnh viễn ở phía bên kia tầm với", một bức tường "bất khả xâm phạm".
Trong suốt hơn nửa thế kỷ qua, không ai dám vượt qua bức tường giới hạn đó.

2-Computer lượng tử sẽ cho phép vượt qua giới hạn

Kiều Tiến Dũng.

Năm 1984, sau khi đỗ bằng cử nhân toán - lý xuất sắc tại Đại học Queensland, Australia, Kiều Tiến Dũng nhận được học bổng làm luận án tiến sĩ tại Đại học Edinburgh ở Anh. Hoàn thành luận án năm 1988, ông trở thành giáo sư Đại học Edinburgh và Đại học Oxford. Năm 1991, ông trở về làm giáo sư Đại học Melbourne, đồng thời cộng tác nghiên cứu với các đại học danh tiếng nhất của Mỹ như Đại học Princeton, Đại học Columbia, Đại học MIT. Hiện ông là lãnh đạo nhóm nghiên cứu của CSIRO - Cơ quan nghiên cứu quốc gia của Australia, kiêm giáo sư vật lý lý thuyết tại Đại học Swinburne thuộc thành phố Melbourne.

Trong một công trình nghiên cứu ứng dụng các nguyên lý của cơ học lượng tử vào khoa học tính toán được gửi tới Viện nghiên cứu quốc gia Mỹ ở Los Alamos gần đây, giáo sư Kiều Tiến Dũng đã đưa ra một kết luận hết sức quan trọng: "Chúng tôi bác bỏ Luận đề Turing-Church bằng cách chỉ ra rằng tồn tại những bài toán không giải được theo nguyên lý Turing, nhưng có thể giải được bằng cách thực hiện những quy trình cơ học lượng tử xác định rõ ràng". Nói cách khác, giáo sư Dũng đã khám phá ra rằng những bài toán không giải được bằng computer hiện nay thực ra có thể giải được bằng computer lượng tử - computer dựa trên nguyên lý mã hóa lượng tử.

Theo NewsFctor, công trình của giáo sư Kiều có thể bắn một phát đạn trúng hai đích: Bài toán số 10 của David Hilbert và SCTM của Alan Turing.
Năm 1900, trong Hội nghị toán học thế giới họp tại Paris, Hilbert, một trong những nhà toán học lớn nhất thời đó, nêu lên 23 bài toán chưa giải được như một thách thức đối với toán học thế kỷ 20. Bài toán số 10 có nội dung như sau: "Hãy tìm một phương pháp để xác định xem liệu một phương trình Diophantine có giải được hay không?".

Phương trình Diophantine là phương trình đại số dạng đa thức nhiều biến với hệ số nguyên, nghiệm nguyên. Thí dụ Định lý Pythagoras hoặc Định lý cuối cùng của Fermat là những thí dụ cụ thể của phương trình Diophantine. Có thể phát biểu lại bài toán số 10 như sau: Liệu có thể tìm được một thuật toán hoặc một chương trình computer để tìm nghiệm nguyên của một phương trình đại số dạng đa thức nhiều biến với hệ số nguyên hay không?

Năm 1970, bài toán số 10 được các nhà khoa học computer chứng minh rằng nó tương đương với bài toán "Xác định xem liệu một chương trình computer định trước có thể giải được những phương trình đại số đa thức hay không, hay sẽ bị treo hoặc dừng?". Từ đó thấy rằng bài toán số 10 của Hilbert tương đương với SCTM của Turing - một bài toán không giải được.

Giáo sư Kiều Tiến Dũng tuyên bố ông có thể giải được cả hai bài toán trên. Ông giải thích, với cơ học lượng tử, chúng ta có thể sử dụng một "thuật toán lượng tử" để tìm kiếm một số vô hạn lời giải khả dĩ thích hợp với phương trình trong một khoảng thời gian hữu hạn. Đây là đặc điểm quan trọng nhất của computer lượng tử - yếu tố hơn hẳn và khác biệt hẳn của computer lượng tử so với computer thông thường hiện nay.

David Hilbert.

Nếu có thể xem xét tất cả các lời giải có thể có thì đương nhiên sẽ biết phương trình có thể giải được bằng thuật toán của chúng ta hay không, và cũng sẽ biết computer lượng tử có bị treo hay không, tức là cùng một lúc có thể giải được cả bài toán số 10 của Hilbert lẫn SCTM của Turing.

Giáo sư Dũng nhấn mạnh: "Thuật toán lượng tử của chúng tôi, thực ra, được xem như một cuộc tìm kiếm vô hạn các số nguyên trong một khoảng thời gian hữu hạn - kiểu tìm kiếm cần thiết để giải bài toán Tính dừng của Turing".

Nhưng tại sao computer lượng tử lại có khả năng phi thường đến như thế? Câu trả lời phụ thuộc vào cơ sở vật lý của computer lượng tử - những nguyên lý kỳ lạ của thế giới lượng tử mà thế giới thông thường không có.

3. Cơ sở vật lý trong khám phá của giáo sư Kiều Tiến Dũng

Ngôn ngữ cơ bản của computer là hệ nhị phân - dãy chữ số gồm 1 và 0. Số 1 tương ứng với trạng thái mạch điện đóng và ngược lại, số 0 tương ứng với trạng thái mạch điện mở và ngược lại quan hệ tương ứng này là 1-1. Nói cách khác, mỗi trạng thái vật lý của mạch điện tương ứng với một thông tin duy nhất và ngược lại. Trong computer lượng tử, tình hình diễn ra hoàn toàn khác: Các hạt lượng tử, chẳng hạn electron và protons, cùng một lúc có thể tồn tại trong những trạng thái lượng tử khác nhau.

Các nhà khoa học mô tả đó là sự tồn tại trong một "siêu vị thế trạng thái" (superposition of states). Tính chất này đến nay vẫn là một đặc trưng bí ẩn của thế giới lượng tử mà bản chất của nó chưa ai có thể giải thích rõ ràng chính xác. Một số người mô tả nó như một biểu hiện "rối lượng tử" (quantum entanglement), một số khác coi đó như một trong các biểu hiện bất định. Chẳng hạn, điều rất kỳ lạ là trong cùng một lúc các hạt lượng tử có thể đồng thời quay quanh trục (spining) theo chiều thuận kim đồng hồ lẫn chiều ngược kim đồng hồ, hoặc cùng một lúc có thể đồng thời đạt những mức năng lượng khác nhau. Nhưng dù chưa giải thích được bản chất của hiện tượng siêu trạng thái, các nhà nghiên cứu computer lượng tử vẫn đang tìm cách lợi dụng tính chất bí ẩn đó để xây dựng một thế hệ computer hoàn toàn mới - computer lượng tử - trong đó tại mỗi thời điểm computer có thể đồng thời có hàng nghìn trạng thái khác nhau, tức là tại mỗi thời điểm computer có thể đồng thời thực hiện hàng nghìn phép toán khác nhau.

Điều này dẫn tới kết quả computer lượng tử có thể xử lý một lượng thông tin vô hạn trong một thời gian hữu hạn. Đó chính là cơ sở vật lý của khám phá của Kiều Tiến Dũng, Christian Calude và Boris Pavlov.

Với khám phá này, không phải chỉ có bài toán số 10 của Hilbert hoặc SCTM của Turing sẽ được giải, mà sẽ có hẳn một lớp các bài toán không giải được sẽ được giải, với công cụ mới là computer lượng tử. Giả thuyết Golbach (Golbach' s Conjecture) có thể sẽ là một trong lớp đó. Giả thuyết này nói rằng mọi số chẵn đều là tổng của hai số nguyên tố. Giả sử bạn có thể viết được một chương trình cho computer lượng tử để, trong một thời gian hữu hạn, kiểm tra một số lượng vô hạn các thí dụ cụ thể (điều mà computer thông thường không thể làm vì đòi hỏi thời gian vô hạn). Nếu bạn tìm thấy một trường hợp sai, tức là Giả thuyết Golbach sai, bài toán chấm dứt. Nếu chương trình chạy trên máy hoàn thành mà không phát hiện thấy trường hợp sai, suy ra giả thuyết đúng. Một bài toán khác trong lớp đó có thể sẽ là Giả thuyết Riemann (Riemann's Hypothesis), một "chướng ngại lớn" của toán học đang được treo một giải thưởng trị giá 1 triệu USD cho ai giải được, có thể cũng sẽ được computer lượng tử trong tương lai giải quyết. Và nếu quả thật lớp những bài toán "ghê gớm" này đều được giải quyết hết thì không còn gì có thể so sánh nổi với tầm vóc vĩ đại của computer lượng tử nữa. Khi đó khó mà dự đoán khoa học sẽ còn tiến bộ vượt bậc đến đâu nữa và tạo ra những huyền thoại gì. Và tất nhiên khi đó chúng ta sẽ có dịp nhìn nhận lại rằng ai là người đã tiên đoán được khả năng siêu phàm của computer lượng tử như thế, và đã tiên đoán vào lúc nào.

4. Kết luận và nhận định bước đầu

Sẽ là quá sớm để đưa ra một kết luận khẳng định chung cuộc vào lúc này về công trình nghiên cứu của Kiều Tiến Dũng và của các nhà khoa học New Zealand nói trên. Bởi vì hiện nay computer lượng tử chưa ra đời, chúng đang được thai nghén trong các dự án nghiên cứu. Bất cứ khám phá nào, dù trên lý thuyết đúng 100%, cũng chỉ có thể được coi là một chân lý sau khi đã được thực nghiệm kiểm chứng. Tuy nhiên, về mặt lý thuyết, công trình nghiên cứu của Kiều Tiến Dũng được nhiều nhà vật lý - toán học và khoa học computer đánh giá cao, và đang nằm trong sự chú ý của giới khoa học computer trên toàn thế giới.

Tiến sĩ Richard Gomez, giáo sư Đại học George Mason ở Mỹ, một chuyên gia có uy tín lớn trong khoa học computer hiện nay nhận định: "Tôi đã đọc các công trình của giáo sư Kiều Tiến Dũng và nhận thấy chúng đó hoàn toàn phù hợp với những khám phá của các nhà nghiên cứu khác trong lĩnh vực tính toán lượng tử và vật lý lượng tử. Không còn nghi ngờ gì nữa, hiện nay đã có một sự chấp nhận rộng rãi rằng thông tin mang tính chất vật lý, và vật lý lượng tử cung cấp những quy luật của sự ứng xử vật lý đó". Ông nói tiếp: "Đặc trưng kỳ lạ của cơ học lượng tử cho phép chúng ta làm việc với toàn bộ thông tin theo những cung cách hoàn toàn mới. Đơn giản là giáo sư Kiều đã biết lợi dụng những quy luật của vật lý lượng tử để đạt tới những kết quả mà trong thế giới của vật lý cổ điển không thể đạt tới được".

Nếu lý thuyết của các nhà khoa học này được thực nghiệm trong tương lai sắp tới xác nhận, thì đây có thể sẽ là những thành tựu sánh ngang với những công trình bất hủ nhất của khoa học tính toán trong thế kỷ 20. Sự đánh giá này sẽ được kiểm nghiệm nhanh hay chậm tùy thuộc vào tốc độ phát triển của công nghệ computer lượng tử.

Bản thân giáo sư Kiều Tiến Dũng cho rằng khoảng vài ba chục năm nữa computer lượng tử sẽ biến thành hiện thực.


Theo VnExpress.net
Computer lượng tử có thể Xử Lý bài toán không giải được