Quantum Turing Machine (QTM)
A Quantum Turing Machine (QTM) is a theoretical model representing the computational capabilities of a quantum computer. It provides a simple framework to describe all possible quantum algorithms.
Comparison with Classical Turing Machines
A QTM extends the classical Turing Machine (TM) by introducing:
- Hilbert Space: Replacing the discrete states of a TM with a continuous Hilbert space.
- Unitary Transformations: Transition function represented by unitary matrices that map the Hilbert space to itself, allowing for quantum superpositions.
Formal Definition
A three-tape QTM can be defined as a tuple:
(Q, Γ, b, Σ, δ, q0, F)
where:
- Q: Hilbert space of states
- Γ: Hilbert space of tape symbols
- b: Blank symbol in Γ
- Σ: Discrete input and output alphabet
- δ: Collection of unitary matrices that define the transition function
- q0: Initial state in Q
- F: Subspace of Q representing accepting states
Measurement and Output
In a QTM, measurements are typically performed to observe the output. The frequency of measurements affects how writes to the output tape are defined.
History and Developments
- 1980-1982: Paul Benioff proposed the first quantum mechanical models of Turing machines.
- 1985: David Deutsch suggested the concept of quantum gates for quantum computation.
- Iriyama, Ohya, Volovich: Developed the Linear Quantum Turing Machine (LQTM) with mixed states and irreversible transitions.
- Scott Aaronson: Defined the Quantum Turing Machine with postselection (PostBQP), showing its equivalence to the classical complexity class PP.
Technical Language Summary
The quantum Turing machine (QTM) is a theoretical model that extends the capabilities of the classical Turing machine (TM) to the realm of quantum computing. It is a formalization of the computational power of a quantum computer.
Hilbert Space and Unitary Transformations
The QTM introduces a Hilbert space for both the states of the machine and the symbols on its tape. The transition function is defined by a set of unitary transformations that operate on this Hilbert space, enabling quantum superpositions and entanglement.
Quantum Probabilities and Measurement
The unitary transformations in the QTM preserve the total probability, but they induce probability distributions over the possible states of the machine. These probabilities are determined by the superposition and entanglement in the Hilbert space. Measurements are performed to collapse the superposition and obtain a classical outcome.
Generality and Equivalence with Quantum Circuits
The QTM captures all possible quantum algorithms, representing any quantum computation as a formal transition between states in the Hilbert space. While the quantum circuit model is more commonly used for practical implementations, the QTM provides a more abstract and fundamental framework for understanding the computational capabilities of quantum systems.
Computational Complexity with Postselection
The QTM with postselection allows for a restricted form of measurement. PostBQP, the class of problems solvable by a polynomial-time QTM with postselection, has been shown to be equivalent to the classical complexity class PP. This demonstrates the power of quantum computation but also highlights the limitations imposed by the need for postselection.
Extensions and Applications
Extensions to the QTM have been proposed, including the LQTM with mixed states and irreversible transitions. Quantum Turing machines with postselection have been used to characterize the computational capabilities of quantum systems and to study the relationship between quantum and classical complexity classes.