Các Mô hình Tính toán Lượng tử

Tính toán lượng tử thay thế các bit cổ điển bằng các trạng thái lượng tử có thể được chồng chập và vướng víu, định nghĩa các mô hình như mạch lượng tử và lớp phức tạp BQP dường như giải quyết một số vấn đề nhanh hơn bất kỳ phương pháp cổ điển nào.

Definition

Một mô hình tính toán lượng tử xử lý thông tin được lưu trữ trong các qubit có trạng thái là các vectơ đơn vị trong một không gian phức hợp; tính toán áp dụng các cổng lượng tử thuận nghịch để tạo ra sự chồng chập và vướng víu, và một phép đo cuối cùng mang lại một kết quả cổ điển với xác suất được đặt bởi trạng thái lượng tử.

Scope

Chủ đề này bao gồm các qubit và cổng lượng tử, mô hình mạch lượng tử và sự tương đương của nó với máy Turing lượng tử, lớp phức tạp BQP của tính toán lượng tử hiệu quả và mối quan hệ của nó với các lớp cổ điển, các thuật toán cơ bản như phân tích thừa số của Shor và tìm kiếm của Grover, và vai trò của phép đo và sự mất kết hợp trong việc định nghĩa mô hình.

Core questions

• Sự chồng chập và vướng víu thay đổi khả năng của một phép tính như thế nào?
• Mối quan hệ giữa lớp lượng tử hiệu quả BQP và các lớp cổ điển là gì?
• Đối với những vấn đề nào thì các thuật toán lượng tử mang lại sự tăng tốc có thể chứng minh được hoặc rõ ràng?
• Phép đo và nguyên lý không sao chép hạn chế tính toán lượng tử như thế nào?

Key theories

Mô hình mạch lượng tử và BQP

Tính toán lượng tử hiệu quả được nắm bắt bởi các mạch lượng tử kích thước đa thức trên một tập hợp cổng phổ quát, định nghĩa lớp BQP, chứa P và được cho là mở rộng nó trong khi vẫn nằm trong PSPACE.

Tăng tốc lượng tử

Thuật toán của Shor phân tích các số nguyên trong thời gian đa thức và thuật toán của Grover tìm kiếm một không gian không có cấu trúc với sự tăng tốc bậc hai, chứng minh những lợi thế cụ thể của mô hình lượng tử cho các nhiệm vụ cụ thể.

Clinical relevance

Các mô hình lượng tử hướng dẫn thiết kế phần cứng và thuật toán lượng tử; thuật toán phân tích thừa số của Shor đe dọa các hệ thống mật mã khóa công khai mà tính bảo mật của chúng dựa trên độ khó của việc phân tích thừa số, thúc đẩy sự phát triển của mật mã hậu lượng tử, trong khi mô phỏng lượng tử hứa hẹn những tiến bộ trong hóa học và khoa học vật liệu.

History

Feynman đề xuất sử dụng các hệ thống lượng tử để mô phỏng vật lý vào năm 1982, và Deutsch đã chính thức hóa máy Turing lượng tử vào năm 1985. Thuật toán phân tích thừa số của Shor năm 1994 và thuật toán tìm kiếm của Grover năm 1996 đã cho thấy những cải tiến tốc độ cụ thể, biến tính toán lượng tử thành một nhánh chính của lý thuyết phức tạp và là động lực của nỗ lực thực nghiệm.

Debates

Lợi thế lượng tử lớn đến mức nào, và liệu nó có thể thực hiện được về mặt vật lý ở quy mô lớn không?

Máy tính lượng tử tính toán các hàm giống như máy tính cổ điển, vì vậy vấn đề là hiệu quả. Mối quan hệ chính xác giữa BQP và các lớp cổ điển vẫn chưa được giải quyết, và liệu các máy tính lượng tử chịu lỗi lớn có thể được xây dựng bất chấp sự mất kết hợp vẫn là một câu hỏi khoa học và kỹ thuật mở.

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

Máy tính lượng tử có tính toán được những thứ mà máy tính cổ điển không thể không?

Không. Máy tính lượng tử giải quyết chính xác cùng một lớp vấn đề như máy tính cổ điển; sự khác biệt là tốc độ. Đối với một số vấn đề nhất định, chẳng hạn như phân tích thừa số các số lớn, mô hình lượng tử dường như nhanh hơn đáng kể, nhưng nó không mở rộng ranh giới của những gì có thể tính toán được về nguyên tắc.

Tại sao tính toán lượng tử lại quan trọng đối với mật mã?

Thuật toán của Shor sẽ cho phép một máy tính lượng tử lớn phân tích các số nguyên lớn và tính toán logarit rời rạc một cách hiệu quả, phá vỡ các hệ thống khóa công khai bảo mật phần lớn thông tin liên lạc ngày nay. Triển vọng này đã thúc đẩy việc tìm kiếm các lược đồ hậu lượng tử dựa trên các vấn đề được cho là khó ngay cả đối với máy lượng tử.