Lược sử máy tính lượng tử kì 2: Những người tiên phong

Bài viết kì trước:

Mặc dù tính toán lượng tử là một ngành khoa học non trẻ, nhưng số lượng bài báo nghiên cứu về nó cũng không thua kém bất kỳ ngành nào khác. Do đó, tôi không thể tóm tắt tất cả mà chỉ giới thiệu nội dung về một số bài báo quan trọng đã thúc đẩy nghiên cứu về máy tính lượng tử mạnh mẽ.

Mô hình máy tính lượng tử vẫn dựa trên những ý tưởng từ khoa học máy tính, vật lý và toán học, và hầu hết các bài báo được viết bởi những nhà khoa học thông thạo trong cả ba lĩnh vực.

Richard Feynman là người đầu tiên đề xuất rằng máy tính lượng tử có thể mạnh hơn các máy tính cổ điển trong một bài nói chuyện vào năm 1981. Bài giảng này được tái bản trên tạp chí “The International Journal of Theoretical Physics” năm 1982.

Feynman đưa ra vấn đề là loại máy tính nào có thể mô phỏng hiện tượng vật lý và sau đó lập luận rằng chỉ có máy tính lượng tử mới có thể mô phỏng chính vật lý lượng tử hiệu quả. Ông tập trung vào vật lý lượng tử hơn là vật lý cổ điển bởi vì như ông diễn giải: “Thiên nhiên không tuân theo vật lý cổ điển, nếu chúng ta muốn tạo ra một trình mô phỏng về tự nhiên, tốt hơn là sử dụng cơ học lượng tử và thật thú vị, đó là một vấn đề tuyệt vời bởi vì nó không dễ dàng chút nào.”

Cùng thời gian đó, trong “Quantum mechanical models of Turing machines that dissipate no energy” năm 1982 và các bài báo liên quan, Paul Benioff đã chứng minh rằng có tồn tại máy Turing lượng tử.

David Deutsch đã trả lời câu hỏi này và hơn thế nữa trong bài báo năm 1985 của ông với tựa đề “Quantum theory, the Church-Turing principle and the universal quantum computer”. Đầu tiên, ông giới thiệu các phiên bản lượng tử tương ứng cho cả máy Turing và máy Turing vạn năng. Sau đó, ông chứng minh rằng máy Turing lượng tử vạn năng có thể làm những điều mà máy Turing vạn năng không thể, bao gồm việc tạo số thực sự ngẫu nhiên, tính toán song song trên một thanh ghi và mô phỏng hoàn hảo hệ thống vật lý hữu hạn chiều.

Năm 1989, trong công trình “Quantum computational networks”, Deutsch đã mô tả mô hình thứ hai cho tính toán lượng tử: mạch lượng tử. Ông đã chứng minh rằng các cổng lượng tử có thể kết hợp như các cổng Boolean cổ điển (NOT, OR, AND, ...). Sau đó, ông chỉ ra rằng các mạch lượng tử có thể tính toán bất cứ thứ gì mà máy tính lượng tử tổng quát có thể tính toán được, và ngược lại.

Andrew Chi-Chih Yao tiếp tục nghiên cứu của Deutsch và đề xuất khái niệm về độ phức tạp của tính toán lượng tử trong bài báo năm 1993, “Quantum circuit complexity”. Cụ thể, ông đã chỉ ra rằng bất kỳ hàm nào có thể tính trong thời gian đa thức bằng máy Turing lượng tử cũng có thể được tính bằng mạch lượng tử. Phát hiện này cho phép các nhà nghiên cứu tập trung vào mạch lượng tử, vốn dễ thiết kế và phân tích hơn so với máy Turing lượng tử.

Cũng trong năm 1993, Ethan Bernstein và Umesh Vazirani đã trình bày “Quantum complexity theory”, trong đó mô tả máy Turing lượng tử tổng quát có thể mô phỏng hiệu quả bất kỳ máy Turing lượng tử nào.

Năm 1995, một nhóm các bài báo đã kiểm tra xem bộ cổng lượng tử nào là đủ để tính toán lượng tử - nghĩa là đủ để tạo ra mạch lượng tử bất kỳ (như bộ cổng cổ điển AND - OR - NOT hoặc NAND). Trong số này, bài báo được trích dẫn nhiều nhất là “Elementary gates for quantum computation” của Barenco và cộng sự. Trong công trình này, các nhà nghiên cứu đã cho thấy rằng bất kỳ mạch lượng tử nào cũng có thể xây dựng bằng cách sử dụng cổng lượng tử 1 qubit và các cổng Control-OR 2 qubit. Mặc dù được cho là có ảnh hưởng nhất, các bài báo khác cũng rất quan trọng, bao gồm " Two-bit gates are universal for quantum computation", trong đó David Di Vincenzo đã chứng minh cổng lượng tử 2qubit là đủ; “Conditional quantum dynamics and logic gates” (Barenco, Deutsch, Ekert, và Jozsa) chỉ ra rằng cổng controlled - NOT và cổng 1qubit là phù hợp; và “Almost any quantum logic gate is universal” (Lloyd) chứng minh hầu hết cổng lượng tử tác động trên hai hoặc nhiều qubit là tổng quát (tức là tự nó là đủ).

Năm 1992, David Deutsch và Richard Jozsa ra mắt “Rapid solution of problems by quantum computation”, trong đó họ trình bày một thuật toán xác định hàm f là hàm hằng hay hàm cân bằng. Deutsch – Jozsa là thuật toán lượng tử đầu tiên chạy nhanh hơn trong mọi trường hợp so với thuật toán cổ điển trong việc cùng giải quyết một vấn đề nào đó. Mặc dù phức tạp, nhưng thuật toán này rất đáng chú ý và đáng đọc.

Trong “Quantum complexity theory” (1993), Bernstein và Vazirani là những người đầu tiên xác định một số vấn đề có thể giải trong thời gian đa thức bằng thuật toán lượng tử. Năm sau, Daniel R. Simon đưa ra một bài toán cụ thể. Nghiên cứu của ông đã truyền cảm hứng cho Peter W. Shor, người sau đó đã phát minh ra hai thuật toán lượng tử vượt trội, tìm thừa số nguyên tố trong thời gian đa thức và logarit rời rạc. Simon và Shor đều đã trình bày những khám phá của họ tại Hội nghị IEEE năm 1994 về Nền tảng của Khoa học Máy tính trong bài báo “On the power of quantum computation”, Simon và “Algorithms for quantum computation: Discrete logarithms and factoring”, Shor.

Đặc biệt, thuật toán Shor đã gây chấn động và tạo ra sự lo lắng về sức mạnh của tính toán lượng tử. Cụ thể, nó đã gây ảnh hưởng đến hệ mật mã RSA (Rivest, Shamir và Adleman đã mô tả hệ thống mật mã này vào năm 1978 trong bài báo “A method for obtaining digital signatures and public-key cryptosystems). Tất nhiên, để điều này biến thành hiện thực, thuật toán của Shor phải được triển khai trên máy tính lượng tử có đủ số lượng qubit. Isaac L. Chuang và nhóm nghiên cứu của ông đã phân tích được 15 = 3 * 5 trên máy tính lượng tử 7 qubit vào năm 2001 trong bài báo “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance”.

Một thuật toán lượng tử có ảnh hưởng khác là thuật toán của Lov K. Grover để tìm kiếm phần tử trong dãy chưa được sắp xếp, được mô tả trong “A fast quantum mechanical algorithm for database search năm 1996 và “Quantum mechanics helps in searching for a needle in a haystack”, 1997. Không giống như thuật toán của Shor, thuật toán của Grover chỉ nhanh hơn bậc hai chứ không vượt bậc so với thuật toán cổ điển. Isaac L. Chuang đã ở vị trí tiên phong trong thử nghiệm. Vào năm 1998, ông, Neil Gershenfeld và Mark Kubinec đã báo cáo về việc triển khai thuật toán của Grover trong " Experimental implementation of fast quantum searching“.

Có nhiều thuật toán lượng tử. Tuy nhiên, số lượng mà các nhà nghiên cứu kỳ vọng sẽ không đạt được do nghiên cứu về thuật toán lượng tử không theo kịp với các khía cạnh khác trong máy tính lượng tử. Vào năm 2003, Peter W. Shor giải quyết tình trạng này trong một bài báo ngắn có tên "Why haven’t more quantum algorithms been found? Shor đã giải thích lý do rằng các nhà khoa học máy tính vẫn chưa khai thác hết bản chất lượng tử (tuy nhiên điều này cũng không dễ để khắc phục).

Như đã đề cập trước đây, thuật toán của Shor vẫn chưa được triển khai thực tế. Nhưng nếu việc phân tích trên số lớn trở nên khả thi, mật mã RSA sẽ bị thay thế bằng một mật mã mới. May mắn là nó đã tồn tại, trên thực tế được phát triển trước khi Shor phát minh ra thuật toán của mình. Mật mã được đề cập là phân phối khóa lượng tử, được Charles H. Bennett và Gilles Brassard giới thiệu vào năm 1984 trong “Quantum cryptography: Public key distribution and coin tossing” (BB84). Ngắn gọn, phân phối khóa lượng tử an toàn không phải vì thông điệp được mã hóa theo cách khó giải mà là vì khi bắt các thông điệp thì sẽ bị phát hiện. Mặc dù phân phối khóa lượng tử là ứng dụng về mật mã nổi tiếng nhất của cơ học lượng tử, nhưng nó không phải là ứng dụng duy nhất và cũng không phải là ứng dụng đầu tiên. Vào những năm 1960, Stephen Wiesner đã hình thành hai ứng dụng: một cách để gửi hai tin nhắn, chỉ một trong số đó có thể đọc được, và một cách để thiết kế tiền không thể làm giả. Ý tưởng của ông hầu chỉ được biết đến cho đến năm 1983, khi ông mô tả chúng trong một bài báo “Conjugate coding” (Wiesner, 1983). Ngoài ra, một nhóm các mật mã khác có khả năng chống lại sự tấn công đến từ máy tính lượng tử, được gọi là mật mã hậu lượng tử (post quantum cryptography) cũng rất mạnh mẽ, như McEliece (1978), RLCE (2016), …

Bảo mật quan trọng, nhưng không phải quan trọng nhất trong việc truyền dẫn thông tin. Các chủ đề khác bao gồm sửa lỗi lượng tử, nén lượng tử và dịch chuyển lượng tử.

Peter W. Shor, đi đầu không chỉ về thuật toán lượng tử mà còn về sửa lỗi lượng tử là người đầu tiên mô tả phương pháp sửa lỗi lượng tử. Trong bài báo năm 1995, “Scheme for reducing decoherence in quantum computer memory”, ông đã chứng minh rằng việc mã hóa mỗi qubit thành 9 qubit có thể là một giải pháp. Gần như cùng thời điểm, Andrew M. Steane đã viết “Error correcting codes in quantum theory” và cũng đạt kết quả tương tự. Rất nhanh sau đó, Shor và A.R. Calderbank đã trình bày phương pháp tiên tiến hơn trong “Good quantum error-correcting codes exist”. Vào cuối những năm 1990, khi nghiên cứu về sửa lỗi lượng tử nổi lên, Shor, Steane và Calderbank vẫn nằm trong số những người đóng góp lớn.

Lỗi không phải là điều duy nhất mà các nhà lý thuyết thông tin cố gắng giảm thiểu, họ cũng tìm cách giảm không gian lưu trữ thông tin. Bài báo mang tính bước ngoặt về cách biểu diễn và nén dữ liệu cổ điển là “A mathematical theory of communication” của Claude E. Shannon (1948), cha đẻ của lý thuyết thông tin. Trong bài báo này, Shannon đã chỉ ra rằng có thể nén mà không làm mất thông tin ở một giới hạn cụ thể.

Gần 50 năm sau, Benjamin Schumacher đã phát triển phiên bản lượng tử tương ứng trong “Quantum coding” nộp năm 1993, nhưng đến mãi năm 1995 mới được xuất bản. Tiếc là trong khoảng thời gian 1993 - 1995, ông và Richard Jozsa đã xuất bản “A new proof of the quantum noiseless coding theorem” năm 1994, đưa ra chứng minh đơn giản hơn bài báo gốc.

Không phải mọi thứ trong lý thuyết thông tin lượng tử đều tương ứng trong lý thuyết thông tin cổ điển. Năm 1993, Charles H. Bennett đã làm giới khoa học kinh ngạc và khi chứng minh rằng dịch chuyển lượng tử là có thể. Trong “Teleporting an unknown quantum state via dual classical and Einstein – Podolsky - Rosen channels” đã mô tả cách một cặp hạt vướng víu từ trước, được tách ra xa nhau và tái tạo lại một cách hoàn hảo trong tại một địa điểm khác. Điều này đã được thực nghiệm đầu tiên trong báo cáo năm 1997 của Bouwmeester, “Experimental quantum teleportation”. Năm 2016, dịch chuyển lượng tử đã được thực hiện lại ở khoảng cách 6 km bởi các nhà nghiên cứu ở Canada và Trung Quốc.

Máy tính lượng tử vẫn tiếp tục được nghiên cứu và phát triển bởi các nhà khoa học hàng đầu trong nhiều lĩnh vực, những người chắc chắn sẽ tiếp tục đặt ra những câu hỏi đầy thách thức, khám phá các giải pháp sáng tạo và thanh lịch. Những bài báo gần đây đã đạt kết quả đáng kinh ngạc hơn nữa về thực nghiệm và kỹ thuật, nhân loại đang dần có những bước tiến lớn trong việc tạo ra một máy tính lượng tử hoàn chỉnh.

Tham khảo: