We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, can not avoid the notion of halting to be probabilistic in Quantum Turing Machine. Our result suggests that halting scheme of Quantum Turing Machine and quantum complexity theory based upon the existing halting scheme sholud be reexamined. PACS numbers: 03.67.Lx In [1] Myers pointed out that there exists a problem in case different branches of quantum computation on a Quantum Turing Machine (QTM) take different numbers of steps to complete their calculation. That is, observation of halting qubit may spoil the computation since it selects a branch of computation and the quantum interference is destroyed after the selection. Subsequently several papers [2] [3] [4] on the halting process of QTM were published. In [2] Ozawa proposed a possible solution by means of quantum nondemolition measurement. He showed that if one considers a restricted class of QTMs such that the halting qubit and data slots are not changed after the branch falls into the halting state, the probability to obtain each outcome by a given time does not depend upon the fact whether one employed the halting protocol or not. However there still remains a problem. Even if one employs the protocol proposed, the notion of halting is still probabilistic. That is, a QTM with an input sometimes halts and sometimes does not halt. If one can not get rid of the possibility of such a probabilistic halting, one can not tell anything certain for one experiment since one can not say whether an event of halting or non-halting occured with probability one or just by accident, say with probability 10 −40 . Bernstein and Vazirani [5] deals only with QTMs whose branches halt at a same time or none of them halt. If one restrict QTMs to such a class, one does not have the problem anymore. We will show, in the present letter, the restriction is not realistic. That is, we address the following question: for an arbitrarily given QTM and an input, can we tell whether the halting is probabilistic or not? We prove that the answer is negative. It means that there exists no necessary and sufficient condition to prescribe non-probabilistic halting QTMs. Thus our result suggests that the probabilistic halting cannot be avoided and appears naturally. A QTM [5] consists of a head, a processor and an infinite two-way tape with data slots and other (working) slots. Thus the total Hilbert space is spanned by a complete orthonormalized system {|x ⊗|ξ ⊗|q j }, where x is an infinite sequence of the alphabets {B, 0, 1} (B is called as blank) with the condition that the number of nonblank cells is finite and ξ ∈ Z represents the head position and q j ∈ {q 0 , q 1 , · · · , q N , q f } is an internal state. Here q 0 denotes an initial state and q f a halting state. A QTM is constructed by assigning complex probability amplitudes (components of a unitary matrix) which satisfy local rule condition. That is, only transitions between locally different configurations are allowed. According to [5] , the components are assumed to be computable complex number, since otherwise we can not construct the QTM. In QTM, the halting scheme is slightly different from classical Turing machine due to the reduction of wave packet [6] . For each step, we observe whether the internal state is q f or not, in other words, we perform the meaurement of the operator |q f q f |. When the outcome is 1, we measure the data slots in the tape and recognize the computation result. When the the outcome is 0, we do not observe anything and proceed the computation. All the ever known effective computation shemes [7, 8] halt with probability one at a certatin time and never halt before then. However for an arbitrarily constructed QTM, the different branches of computation can have different numbers of computation steps in general. In such a case the halting process or the notion of halting itself has the problem as described above. One way to avoid such a difficulty is considering only special type of QTMs and inputs. We call a pair of a QTM Q and its input x nonprobabilistic halting iff one of the following conditions is satisfied. i) There exists a t 0 ∈ {1, 2, · · ·} such that at step t 0 , Q under x halts with probability one and for s < t 0 it halts with probability zero. ii) For all the steps, Q under x halts with probability zero. A pair of Q and x is called probabilistic halting when it is not non-probabilistic. We ask whether there exists an algorithm to judge whether a QTM and an input is probabilistic or not [9] . To answer the above question, we assuume the existence of such an algorithm, (classical) Turing Machine (TM) T 0 . Then we can show contradiction. TM T 0 works so as to read input Q, x where Q is a QTM and x ∈ {0, 1} * is an input and determine whether Q under the input x is probabilistic halting or not. For reversible TMs, T 1 and T 2 , let us define a special 1
• Miyadera and Ohya REF discuss the notion of probabilistic halting.
On Halting Process of Quantum Turing Machine
Open Systems and Information Dynamics, Vol.12, No.3 261-264 (2005).
Computer Science Physics Mathematics