Một máy tính lượng tử là một máy Turing. Nó khác với các máy tính truyền thống không phải bằng cách thoát khỏi các giới hạn của khả năng tính toán, mà bằng cách nó xử lý thông tin. Nó vẫn bị giới hạn trong thế giới Church–Turing. Nó không thể giải quyết Vấn đề Dừng, cũng như không thể tính toán.