The Computational Power of Observed Quantum Turing Machines

Slides

The quantum Turing machine (QTM) has been introduced by Deutsch [Deu85] as the very first model of quantum computation. Roughly speaking, a quantum Turing machine can be seen as a generalisation of a probabilistic Turing machine where the probabilities which are associated with any transition are replaced by amplitudes i.e., complex numbers. The use of complex numbers leads to model fundamental phenomena of quantum mechanics like interferences and entanglement.

A probabilistic Turing machine is submitted to well-formedness conditions ensuring that for any configuration, the probabilities of all the possible evolutions sums to one (or at most one). A quantum Turing machine is submitted to similar well-formedness conditions. These well-formedness conditions ensures that the evolution of a quantum Turing machine (i) does not violate the law of quantum mechanics; (ii) is reversible. This later condition can be rephrased in more physical terms as an isolation of the quantum Turing machine from its environment during the computation.

The reversibility assumption of quantum Turing machines is questionable for several reasons, including for instance the emergence of quantum computing models based on non reversible evolutions, like the one-way model [RBB02] or more generally the measurement-based quantum computations [Nie03], which point out that a quantum computation is not necessary reversible. Moreover, the isolation assumption leads to technical issues like the impossibility to know whether a running computation is terminated or not i.e., whether the halting state is reached or not. Finally, due to the isolation assumption, quantum Turing machines are the natural quantum versions of reversible Turing machines. But the natural embedding of any reversible Turing machine into a quantum Turing machine cannot be extended to non-reversible and probabilistic Turing machines.

We present a weakening of the well-formedness condition of QTM leading to Observable Quantum Turing Machines (OQTM) [Per08]. No more isolated, an OQTM can be seen as a QTM which is able to interact with its environment. Modelling environment behaviour is a key issue. Indeed, we point out that some naive modelling of environment increases drastically the computational power of the machine. Finally, we show that the environment can be modelled such that QTM and OQTM have the same computational power.

References

[Deu85]

D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 400:97–117, 1985.

[Nie03]

M. A. Nielsen. Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state. Phys. Rev. A, 308:96–100, 2003.

[Per08]

S. Perdrix. Partial observation of quantum Turing machine and weaker well-formedness condition. In proceedings of Joint Quantum Physics and Logic and Development of Computational Models (Joint 5th QPL and 4th DCM), 2008.

[RBB02]

R. Raussendorf, D. E. Browne, and H. J. Briegel. The one-way quantum computer - a non-network model of quantum computation. Journal of Modern Optics, 49:1299, 2002.

This document was translated from L^AT_EX by H^EV^EA.