Measurement-Based Quantum Turing Machines and their Universality

Abstract

Quantum measurement is universal for quantum computation. This universality allows alternative schemes to the traditional three-step organisation of quantum computation: initial state preparation, unitary transformation, measurement. In order to formalize these other forms of computation, while pointing out the role and the necessity of classical control in measurement-based computation, and for establishing a new upper bound of the minimal resources needed to quantum universality, a formal model is introduced by means of Measurement-based Quantum Turing Machines.

13 pages, based upon quant-ph/0402156 with significant improvements

References in corpus (8)

• Measurement-based quantum computation with cluster states
• Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state
• Computation by measurements: a unifying picture
• State Transfer instead of Teleportation in Measurement-based Quantum Computation
• Computable functions, quantum measurements, and quantum dynamics
• Two-qubit Projective Measurements are Universal for Quantum Computation
• Measurement-Based Quantum Turing Machines and Questions of Universalities
• Measurability and Computability

Cited by in corpus (11)

• Measurement-based quantum computation
• Cluster-state quantum computation
• Unified derivations of measurement-based schemes for quantum computation
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
• Measurement-Based Quantum Computation
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Phase map decompositions for unitaries
• The Measurement Calculus
• Quantum Iterative Deepening with an application to the Halting problem
• A local model of quantum Turing machines