Giới thiệu về tính toán lượng tử. Máy tính điện tử giúp giải phóng sức lao động trí óc của con người, giúp con người đạt đến một tầm cao mới – kỷ nguyên của tự động hóa. Theo định luật Moore, cứ mỗi 18 tháng tốc độ máy tính lại tăng lên gấp đôi. Với sự thay đổi chóng mặt của khoa học máy tính và công nghệ thông tin thì các bài toán, các vấn đề của cuộc sống, của khoa học kỹ thuật ngày càng trở nên dễ dàng hơn. Tuy vậy, vẫn còn tồn tại rất nhiều bài toán của tự nhiên chưa có cách thức giải bằng máy tính và những bài toán có độ phức tạp lớn (các bài toán NP đầy đủ). Những bài toán như vậy có ý nghĩa rất lớn trong thực tế. Đặc biệt là những bài toán NP đầy đủ sử dụng trong các thuật toán mã hóa phi đối xứng như: bài toán phân tích số nguyên tố, bài toán logarit rời rạc,… Với máy tính cổ điển thì việc giải các bài toán này cho đến nay chưa đạt hiệu quả mong muốn – hay nói cách khác những hệ mật dựa trên những bài toán này tương đối an toàn đối với sức mạnh tính toán cổ điển.
Tuy vậy, dưới quan điểm rằng: “Có thể chế tạo được các cỗ máy tính toán đơn thuần dựa trên các hiện tượng vật lý”, R.P. Feynman đã đề xuất mô hình tính toán hoàn toàn mới “mô hình máy tính lượng tử” dựa trên lý thuyết cơ học lượng tử. Các máy tính cổ điển dựa trên các khái niệm vật lý cổ điển, nhưng như đã chứng minh trong vật lý, về bản chất vật lý cổ điển không thể mô tả toàn bộ các hiện tượng trong thế giới thực. Do đó tiềm năng của việc nghiên cứu sức mạnh và giới hạn của tính toán lượng tử là cần thiết.
Điểm khác biệt căn bản nhất của máy tính lượng tử và máy tính cổ điển là bản chất vật lý dựa trên các tính chất của cơ học lượng tử mà ở đây được thể hiện bằng việc lưu trữ và xử lý thông tin dưới dạng các qubit, ở đó mỗi qubit không chỉ tồn tại trạng thái 0 và 1 mà còn tồn tại ở các trạng thái chồng chập giữa 0 và 1. Điều này làm cho máy tính lượng tử có khả năng lưu trữ vượt trội đồng thời có tốc độ tính toán nhanh hơn rất nhiều lần so với máy tính cổ điển. Do giới hạn về mặt vật lý của việc mở rộng tốc độ tính toán của các máy tính điện tử dựa trên định luật Moore khi các thiết bị điện tử không thể vượt qua giới hạn về kích thước hạ nguyên tử, thì việc mở rộng về tốc độ tính toán của các hệ thống vi xử lý là có giới hạn. Vì vậy, tính toán lượng tử mở ra một triển vọng phát triển mở rộng cho việc nâng cấp sức mạnh tính toán và tăng tốc độ xử lý cho nhiều thuật toán cổ điển.
Bên cạnh đó, trong nhiều trường hợp máy tính lượng tử không chỉ đơn thuần tăng hiệu năng xử lý tính toán mà còn giảm độ phức tạp tính toán nhằm giải quyết những bài toán có độ phức tạp tính toán cao. Một ví dụ kinh điển là thuật toán phân tích hợp số có độ phức tạp đa thức của Shor trên máy tính lượng tử. Trên máy tính cổ điển, phương pháp tốt nhất để phân tích một số nguyên dương có độ phức tạp mũ và khi muốn phân tích một số nguyên dương có 300 chữ số cần tiêu tốn thời gian hàng ngàn năm (ngay cả với siêu máy tính mạnh nhất hiện nay), trong khi thuật toán lượng tử của Shor thời gian cần thiết là chưa đầy một giây.
Tuy nhiên, với những rào cản về mặt vật liệu và kỹ thuật, cho tới nay thì việc xây dựng được máy tính lượng tử thay thế cho máy tính cổ điển vẫn không phải là vấn đề dễ dàng. Mặc dù vậy, qua hơn ba thập kỷ nghiên cứu và phát triển, đã có rất nhiều các công trình và kết quả quan trọng về mặt lý thuyết lẫn thực nghiệm trong lĩnh vực tính toán và truyền thông lượng tử. Sự phát triển của máy tính lượng tử diễn ra rất mạnh mẽ từ đầu những năm 80, cho đến nay các nhà khoa học trên thế giới đã xây dựng được những mô hình và lý thuyết quan trọng cho phép đưa máy tính lượng tử vào sử dụng trong thực tế. Các cột mốc đáng chú ý có thể kể đến như:
- Năm 1980 Paul Benioff là người đầu tiên nhận ra khả năng liên kết giữa mô hình lý thuyết tính toán và cơ học lượng tử. Ông chỉ ra phép biến đổi Unita khả nghịch có thể mô tả toán học cho sức mạnh của một máy Turing.
- Năm 1982 Richard Feynman chỉ ra độ khó khi mô phỏng một hệ cơ học lượng tử trên mô hình máy tính cổ điển có độ phức tạp mũ, đồng thời đưa ra khả năng sử dụng một máy tính dựa trên nguyên lý cơ học lượng tử để vượt qua vấn đề này.
- Năm 1985 David Deutsch định nghĩa các máy Turing lượng tử, một mô hình lý thuyết cho tính toán lượng tử, đồng thời tìm ra nguyên lý song song lượng tử, công cụ quan trọng trong tính toán lượng tử.
- Năm 1992 Deutsch và Jozsa xem xét bài toàn sau: Cho một hàm \(f :\{0,1,\ldots,N\}\rightarrow\{0,1\} \) , xác định xem liệu \(f \) là hàm hằng với mọi đầu vào hay \(f \) là cân bằng (có giá trị bằng 1 với chính xác một nửa đầu vào nhận được và bằng 0 với chính xác nửa còn lại). Hai tác giả đã đề xuất ra một thuật toán lượng tử trên mô hình máy Turing lượng tử, cho phép giải quyết nhanh hơn gấp nhiều lần so với thuật toán cổ điển nhanh nhất có thể có cho bài toán này.
- Năm 1993 Bernstein và Vazirani chỉ ra rằng, tồn tại một máy Turing lượng tử phổ quát có khả năng mô phỏng máy Turing lượng tử trong thời gian đa thức.
- Năm 1994 Peter Shor phát triển một thuật toán lượng tử để giải quyết bài toán phân tích hợp số – một bài toán vô cùng quan trọng trong hệ mật mã khóa công khai. Thuật toán này nhanh hơn cấp độ mũ so với bất kỳ một thuật toán cổ điển nào có thể có nhằm giải quyết bài toán phân tích hợp số. Khi đó, các hệ mật khóa công khai dựa trên bài toán phân tích hợp số như RSA hoàn toàn có thể bị phá vỡ trong thời gian chấp nhận được. Đây là kết quả nghiên cứu mang tính đột phá, nó khẳng định sức mạnh của tính toán lượng tử so với tính toán cổ điển. Nếu máy tính lượng tử được xây dựng thành công thì các hệ mật liên quan đến bài toán phân tích hợp số như RSA, DSA, ECDSA… sẽ hoàn toàn bị phá vỡ!
- Năm 1996, Lov Grover tại Bells Lab đã đưa ra thuật toán để giải bài toán tìm kiếm trên một danh sách không sắp xếp với tốc độ cực nhanh.
- Tháng 3 năm 2000, nhóm nghiên cứu của IBM, do Isac Chung lãnh đạo đã xây dựng thành công máy tính lượng tử với bộ xử lý 7-qubit. Mặc dù trên thực tế, số lượng bảy qubit vẫn còn quá ít, nhưng đây là kết quả đánh dấu một ý nghĩa quan trọng rằng máy tính lượng tử hoàn toàn có khả năng ứng dụng được trong thực tiễn và việc xây dựng các máy tính lượng tử có khả năng giải quyết các bài toán thực tế là hoàn toàn khả thi trong tương lai không xa.
- Tháng 2 năm 2007, máy tính lượng tử 15 qubit được tuyên bố chế tạo thành công.
- Tháng 4 năm 2014, nhóm các nhà nghiên cứu tại đại học Havard do tiến sĩ Mikhail Lukin đứng đầu đã chế tạo thành công một thiết bị ngắt mạch lượng tử có khả năng bật và tắt bằng cách sử dụng một photon duy nhất. Đây được xem là một thành tựu công nghệ đột phá có thể mở đường cho việc tạo nên các mạng máy tính lượng tử bảo mật với độ bảo mật vô cùng cao trong tương lai.
- Và gần đây tháng 9/2019, các nhà khoa học của Google đã tuyên bố vượt qua giới hạn lượng tử để giải bài toán mà trước đây ngay cả các siêu máy tính phải mất hàng ngàn năm để giải thì nay với máy tính lượng tử do họ tạo ra trong phòng thí nghiệm chỉ còn mất vài phút.
Mikhail Lukin và máy tính lượng tử
Chính vì tính thời sự và ưu việt của tính toán lượng tử cũng như tính khả thi trong việc ứng dụng tính toán lượng tử trong tương lai không xa, tek.vn giới thiệu đến bạn chuỗi bài viết “Giới thiệu về tính toán lượng tử” nhắm đến mục tiêu xây dựng cái nhìn tổng quan về máy tính lượng tử, các thuật toán lượng tử và các ứng dụng của thuật toán lượng tử trong thực tế như thế nào.
Nội dung chuỗi bài viết bao gồm:
Bài 1. Mô hình tính toán cổ điển và luận đề Church – Turing
Bài 2. Cơ sở toán học của tính toán lượng tử
Bài 3. Qbuit và thanh ghi lượng tử
Bài 4. Cổng và mạch lượng tử
Bài 5. Phép đo lượng tử và các nguyên lý trong tính toán lượng tử
Bài 6. Máy tính lượng tử là gì?
Bài 7. Thuật toán lượng tử, xương sống của máy tính lượng tử
Bài 8. Thuật toán Deutsch – Jozsa
Bài 9. Thuật toán Simon
Bài 10. Thuật toán tìm kiếm Grover
Bài 11. Các phép biến đổi tích phân lượng tử
Bài 12. Thuật toán ước lượng pha
Bài 13. Thuật toán tìm bậc Modulo N
Bài 14. Phá mã các hệ mật khóa công khai bằng máy tính lượng tử
Bài 15. Mật mã hậu lượng tử (Post-quantum cryptography)
Bài 16. Mật mã lượng tử
Hãy cùng theo dõi chuỗi bài viết “Giới thiệu về tính toán lượng tử” này và để lại bình luận bên dưới nhé!
