Quantum Turing machine

2020 Mathematics Subject Classification: Primary: 68Q05 Secondary: 03D10 [MSN][ZBL]

The quantum Turing machine (QTM) is the quantum analogon of a Turing machine (TM). For many aspects, a close analogy to the classical counterpart exists. Though a quantum Turing machine can be defined more or less canonically, several conceptional problems associated with it and concerning the notion of 'quantum computation' exist and are still unsolved. Other properties of the quantum Turing machine like the question, whether universality does hold or not, are unknown as well.

Quantum Aspects of Computation

Church-Turing Thesis

The Church-Turing thesis defines an 'algorithm' as a description of a calculation. But is this the whole story? A calculation is not only a platonic object, usually it is intended to execute the actual calculation in one way or the other. Put in other words, the calculation should be realized physically. Then, the device executing the calculation has to be considered as physical system. A calculation is the execution of a physical experiment, and its result is provided by the observation of the experiment.

Today, many devices executing calculations are known. They are not limited to digital computers. Other types are e.g. analogous computers, soap-bubble based computers, the DNA-computing approach, and the Antikythera mechanism. This leads to the question, whether the restriction to classical models of computation like Turing machines is really adequate.

Church-Turing-Deutsch Thesis

The idea of the Turing machine dates back to the year 1936. At this time, the physical world seemed to be dominated by mechanical forces; correspondingly, the definition of a Turing machine is based on the ideas of classical mechanics. And though the physical realization of a Turing machine, the digital computer, actually uses quantum mechanics, its construction principles aims at the suppression of any effect associated with the quantum world. With ever-tighter package density, however, this is not achievable anymore in a perfect way. The effects of quantum theory may begin to have an influence on the outcome of the calculation.

Considered from another perspective, computations executed by humans are mental processes. In this way, the Church-Turing thesis is also a statement about the human mind. The Platonic world (including computations) is a mental construction. The brain, which is generating the Platonic world, is a physical system in turn; and at the microscopic level, this system has a quantum mechanical nature.

Consequently it seems to be questionable whether the Turing machine provides a 'natural' model of computation. Searching for alternatives and taking the quantum nature of the world into consideration, Feynman has the idea of quantum computation in 1982. As model executing such a quantum computation, he proposes the quantum Turing machine as quantum theoretical analogon to the Turing machine. Similar ideas were developed independently by Yuri Manin in 1980. Accordingly, David Deutsch generalized the Church-Turing thesis to the Church-Turing-Deutsch thesis in 1985, which states that every computation, which can be realized physically, can be executed using a quantum Turing machine.

Quantum Measurements

This section summarizes basic properties of quantum measurements. They are the necessary prerequisite for the discussion of quantum Turing machines. In order to simplify the following considerations, we will make two assumptions.

• The eigenspaces are not degenerated
• The operators associated with measurements have a discrete spectrum

These assumptions help us to concentrate on the foundations instead of technicalities.

Let us now consider a measurement executed by applying an observable $\hat O=|\psi_i \rangle\langle \psi_i |$ having an Eigenvalue $a_i$ with a corresponding Eigenvector $| \psi_i\rangle$. The probability $p$ of measuring the Eigenvalue $a_i$ in a state $| \psi\rangle=\sum_l \alpha_l | \psi_l\rangle \in\mathcal{H}$ is given by $p=|\langle \psi_i |\psi\rangle|^2= |\alpha_i|^2$. When measuring the Eigenvalue $a_i$, the original state $| \psi\rangle$ is changed to the corresponding Eigenvector $| \psi_i\rangle\in\mathcal{H}$ as new quantum state.

Quantum theory would not be probabilistical without measurements. The probabilistic nature could be explained as a result of an interaction between the measurement system and the quantum system, which leads to an entanglement of states. Consequently, the quantum system does not evolve independent from the outside world anymore, its future state is influenced by the measurement system.

Example: Qubits

A Qubit represents a quantum state $Q$ having 2 ground states $\{0,1\}$. Accordingly, $Q$ is given by $$ Q= \alpha | 0\rangle + \beta | 1\rangle.$$ This leads to a 2-dimensional Hilbert-space $\mathcal{H}\cong \mathbb{C}^2$. The probabilities of measuring the ground states are equal to $|\alpha|^2$ and $|\beta|^2$. It holds $ |\alpha|^2 + |\beta|^2 = 1 $, i.e. for example $$Q=\frac{1}{\sqrt{2}}| 0\rangle - \frac{1}{\sqrt{2}}| 1\rangle.$$

The situation described here is not identical with a random bit having values $\{0,1\}$ and probabilities $|\alpha|^2 $, $|\beta|^2$. Whereas a total of 4 different transformations can explain all possible transformations of a random bit, a Qubit can be transformed in infinitely many ways. The possible transformations applied on a Qubit can be represented by rotations of a so-called Bloch sphere.

Definition of a Quantum-Turing-Machine

From Classical to Quantum Dynamics

The basic construction of a quantum Turing machine resembles the classical Turing machine. We assume an infinite tape and the existence of a read/write head. With exception of the transition function $\delta$, all other components of the definition can be reformulated canonically.

• $Q=\{q_i\}_i$, finite state set
• $\Sigma=\{\sigma_j\}_j$, finite input alphabet
• $\Gamma=\{\gamma_k\}_k$, finite tape alphabet
• $\sqcup\in \Gamma$, blank symbol with $\sqcup \notin \Sigma$
• $q_0\in Q$, start state
• $F \subseteq Q$, set of end states

Lance Fortnow (2003) has developed a formalism, which unifies the definitions of a classical Turing machine, a nondeterministic Turing machine, a probabilistic Turing machine, and a quantum Turing machine. His formalism addresses the aspects of the dynamics, which can not be canonically translated to the quantum level. The problem is that the transition function $\delta$ of a Turing machine has the form $\delta\colon Q\times\Sigma\to Q\times\Sigma \times \{L,R,N\}$, wherein the expression $\{L,R,N\}$ does not represent a set of states but a set of head actions. As a way-out, Fortnow proposes a representation of $\delta$ as transition matrix in the space $(q,B,i)\in Q\times \Gamma^\ast \times \mathbb{Z}=:C$ of configurations. The actual configuration, which consists of the (local) state of the Turing machine, the content of its tape, and the position of its head on the tape, provides some kind of global state of the Turing machine. Accordingly, the set $C=\{c_i\}_{i\in I}$ of configurations is used for representing the ground states of the physical system. Assuming $c_i=(\ldots,0,1,0,\ldots)^t$, $\delta\colon c_i\mapsto c_j$ becomes a transition function operating on $C$ representable as a matrix $U$: $$U_{ji} := \begin{cases} 1 & \text{$c_i \buildrel \delta\over\longrightarrow c_j$}\\ 0 & \text{otherwise} \end{cases} $$ The permutation property $U \cdot c_i = c_j$ resembles the (classical) Turing machine. If instead of $U_{ij}\in\{0,1\}$ a probability matrix with $U_{ij}\in \mathbb{R}$ is used, the case of a probabilistic Turing machine is resembled. For the case of a quantum Turing machine $M$, a unitary matrix $U$ is chosen with $U_{ij}\in \mathbb{C}$. The matrix $U$ represents an operator $\hat U$ describing the quantum dynamics of $M$. Due to the property of unitarity, the dynamics must be reversible. It determines the 'program' of $M$. A computation step of $M$ has the form $| \psi(n+1)\rangle=\hat U | \psi(n)\rangle= \hat U^{n+1}| \psi(0)\rangle$. According to its construction, $\hat U$ changes the content of the quantum 'tape' only at the position $i$ of the head. Furthermore, $\hat U$ moves the head at most one step to the right or to the left. Due to $U_{ij}\in \mathbb{C}$, interference is possible with amplification and extinction. The notion of superposition becomes relevant, leading to interdependences between states.

David Deutsch (1985) completed the construction of a quantum Turing machine using the results of Lance Fortnow. In the quantum analogon, a configuration $\psi=(q,B,i)\in C$ is interpreted as (ground) state $| \psi\rangle =|q\rangle|B\rangle|i\rangle$. This gives the countable base of the corresponding Hilbert space. For an input $x$, the start configuration $c_{{\mathrm{init}}(x)}$ of the quantum Turing machine is represented by $| \psi(0)\rangle= | q_0\rangle | x\rangle| 1\rangle$ and with exception of $x$, the tape is empty.

Observables of a quantum Turing machine

After the halt of the machine, one has to execute measurements for determining the symbols at the tape positions. For the set $Q=\{q_0, \ldots, q_r\}$ of states and the set $\Gamma=\{\gamma_1,\ldots,\gamma_s\}$ of tape symbols the observables are

• $\hat q =\sum\limits_{l=0}^r l |q_l\rangle\langle q_l|$ for the actual state.
• $\hat B(m) =\sum\limits_{l=0}^s l |\gamma_l\rangle\langle \gamma_l|$ with $m\in\mathbb{Z}$ for the actual tape symbol at the tape position $m$. Since we assume a computation of finite length, we have to measure only the contents of a finite number of $m\in\mathbb{Z}$.
• $\hat \zeta =\sum\limits_{\zeta\in\mathbb{Z}} \zeta |\zeta\rangle\langle \zeta|$ for the actual head position.

The Input of a quantum Turing machine is a classical state and thus reproducable. Furthermore, the dynamics of a QTM is deterministical; thus the computation steps of quantum Turing machines can be reproduced as well. Reading out the result of the computation, which is realized by executing a measurement, is probabilistic in the contrary. Given the input $x$, the probability of reaching a specific accepting configuration $c_{\mathrm{accept}}$ after $n$ computation steps is equal to $| {{\langle {c_{{\mathrm{accept}}}}|}U^n| c_{{\mathrm{init}}(x)}\rangle}|^2$. Despite of randomized measurement results, one can control the correctness of the result in the case of $P$('correct' result) $=1/2+\varepsilon$, $\varepsilon > 0$, due to the determinism of the dynamics. 'Wrong' results can not be excluded, however.

References

[A2005]	Scott Aaronson, "Quantum computing, postselection, and probabilistic polynomial-time", Proceedings of the Royal Society A461(2005)3473-3482
[A2013]	Scott Aaronson, "The Ghost in the Quantum Turing Machine", arXiv:1306.0159v2 [quant-ph]
[BC2006]	D.P. Bovet, P. Crescenzi, "Introduction to the theory of complexity", Lecture Notes, unpublished 2006
[CC2010]	Goong Chen, David A. Church, Berthold-Georg Englert, Carsten Henkel, Bernd Rohwedder, Marlan O. Scully, M. Suhail Zubairy, "Quantum Computing Devices: Principles, Designs, and Analysis", CRC Press 2010
[D1985]	David Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer", Proceedings of the Royal Society of London A400(1985)97-117
[F2003]	Lance Fortnow, "One Complexity Theorist's View of Quantum Computing", Theoretical Computer Science 292(3)(2003)597-610
[F2007]	Willem Fouché, Johannes Heidema, Glyn Jones, Petrus H. Potgieter, "Deutsch's Universal Quantum Turing Machine (Revisited)", arXiv:0701108v1 [quant-ph]
[H1997]	Mika Hirvensalo, "On Quantum Computation", Licentiate's thesis, University of Turku 1997
[M1980]	Yuri Manin, "Vychislimoe i nevychislimoe", Sov.Radio. 1980
[MN1994]	Takashi Mihara, Tetsuro Nishino, "On a Method of Solving NP-Complete Problems in Polynomial Time Using the Quantum Turing Machine", in Maruoka, Akira (editor), "Computational complexity theory", Proceedings of a symposium held at Kyoto 1994, in RIMS Kokyuroku 871(1994)30-36
[M2012]	Jaroslaw Miszczak, "High-Level Structures for Quantum Computing", Morgan & Claypool Publishers 2012
[MO2002]	Takayuki Miyadera, Masanori Ohya, "Designing Quantum Turing Machine is uncomputable", in Proceeedings of the Erato Workshop on Quantum Information Science 2002
[MO2005]	Takayuki Miyadera, Masanori Ohya, "On Halting Process of Quantum Turing Machine", Open Systems and Information Dynamics, 12(3)(2005)261-265
[M2007]	Markus Müller, "Quantum Kolmogorov Complexity and the Quantum Turing Machine", PhD Thesis, Technischen Universität Berlin 2007
[ON2000]	Masanao Ozawa, Harumichi Nishimura, "Local Transition Functions of Quantum Turing Machines", Theoret. Informatics and Appl. 34(2000)379-402
[P2011]	Simon Perdrix, "Partial Observation of Quantum Turing Machine and Weaker Well-Formedness Condition", Electronic Notes in Theoretical Computer Science 270, Issue 1, (2011) pp. 99-111, also in B. Coecke, I. Mackie, P. Panangaden, P. Selinger (editors), Proceedings of the Joint 5th International Workshop on Quantum Physics and Logic and 4th Workshop on Developments in Computational Models QPL/DCM 2008
[P2006]	P. Prashant, "The Church-Turing-Deutsch Principle in Quantum Computation", in Hamid R. Arabnia, Mark Murgin (Eds.), Proceedings of the 2006 International Conference on Foundations of Computer Science, Las Vegas 2006, CSREA Press 2006, pp. 141-148
[S2000]	A. Stern, "Quantum Theoretic Machines: What is thought from the point of view of Physics?", Elsevier 2000
[Y1993]	Andrew Yao, "Quantum circuit complexity", Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 352-361