Máy Turing lượng tử

Một máy Turing lượng tử (MTLT), cũng là một máy tính lượng tử vạn năng, là một máy trừu tượng được sử dụng để mô hình hóa hiệu ứng của máy tính lượng tử. Nó cung cấp một mô hình rất đơn giản, nắm bắt tất cả sức mạnh của tính toán lượng tử. Bất kỳ thuật toán lượng tử nào cũng có thể được biểu diễn chính thức như một máy Turing lượng tử cụ thể. Những máy Turing như vậy lần đầu tiên được đề xuất trong một bài báo năm 1985 được viết bởi nhà vật lý David Đại học Oxford, cho rằng cổng lượng tử có thể hoạt động theo kiểu tương tự như cổng logic nhị phân điện toán kỹ thuật số truyền thống.^[1]

Máy lượng tử Turing không phải lúc nào cũng được sử dụng để phân tích tính toán lượng tử; mạch lượng tử là một mô hình phổ biến hơn.^{[2] :2} Những mô hình này là tương đương tính toán.

Máy Turing lượng tử có thể liên quan đến máy Turing cổ điển và xác suất trong một khung dựa trên ma trận chuyển tiếp,   được hiển thị bởi Lance Fortnow.^[3]

Iriyama, Ohya và Volovich đã phát triển một mô hình của máy Turing lượng tử tuyến tính (LQTM). Đây là một khái quát của QTM cổ điển có các trạng thái hỗn hợp và cho phép các chức năng chuyển tiếp không thể đảo ngược. Những thứ này cho phép biểu diễn các phép đo lượng tử mà không có kết quả cổ điển.^[4]

Một máy Turing lượng tử có postelection được xác định bởi Scott Aaronson, người đã chỉ ra rằng lớp thời gian đa thức trên một máy như vậy (PostBQP) bằng với lớp PP phức tạp cổ điển.^[5]

Tài liệu tham khảo

1. Deutsch, David (tháng 7 năm 1985). “Quantum theory, the Church-Turing principle and the universal quantum computer” (PDF). Proceedings of the Royal Society A. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. Bản gốc (PDF) lưu trữ ngày 23 tháng 11 năm 2008.
2. Abel Molina; John Watrous (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arΧiv:1808.01701 [cs.CC]. 
3. Fortnow, Lance (2003). “One Complexity Theorist's View of Quantum Computing”. Theoretical Computer Science. 292 (3): 597–610. doi:10.1016/S0304-3975(01)00377-2.
4. Simon Perdrix; Philippe Jorrand (ngày 4 tháng 4 năm 2007). “Classically-Controlled Quantum Computation”. Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). “Classically-Controlled Quantum Computation” (PDF). Math. Struct. In Comp. Science. 16 (4): 601–620. CiteSeerX 10.1.1.252.1823. doi:10.1017/S096012950600538X.
5. Aaronson, Scott (2005). “Quantum computing, postselection, and probabilistic polynomial-time”. Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. Preprint available at [1]

đọc thêm

• Molina, Abel; Watrous, John (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arΧiv:1808.01701 [cs.CC]. 
• Iriyama, Satoshi; Ohya, Masanori (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arΧiv:quant-ph/0405191. 
• Deutsch, D. (1985). “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer”. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. JSTOR 2397601.
• Máy tính lượng tử - lịch sử