数理解析研究所講究録1093 巻 1999 年 200-205200

量子有限オートマトンにおける決定不能問題
天野正己 (Masami Amano)

岩間 –雄 (Kazuo Iwama)

京都大学工学部情報学科

京都大学大学院情報学研究科

Abstract
Our model in this paper is a 1.5-way quantum finite
position but
automaton which can move its head$-.1$ position. It is shown that the most fundamental
declslon question, the emptiness problem, is not solvable for this model. Note that the emptiness problem issolvable for push-down automata and even for one-way
nondeterministic stack automata.
$0\mathrm{o}\mathrm{r}+1$

not.

machines, i.e., the built-in parallelism of their computation.
The emptiness problem is probably the easiest one
among popular decision questions such as the equivalence problem and the disjointness problem. The empti[HU79]
ness problem is solvable for push-down
and furthermore for 1-way nondetermlnlstic stack aumay not be linear time. It
tornata (lSA)s) [HU79].
are also
is known that all languages recognized byrecognized by deterministic linear-space TM’s [HU68],
but its proof is not that easy and the difference of power
between these two models is far from trivial. Our uncan accept somesolvability result means that 1.
; itlanguages that cannot be recognized by any
are veryis quite reasonable to conclude that 1.
powerful in some cases.
It should be noted that this does not necessarily mean
are always powerful. We can probablythat 1.
prove that some re.gular languages cannot be recognized
by using the same technique as in [KW97].
by 1.
However, it seems that such adversary languages havesome common properties in their syntax, which can be
avoided if we allow desirable encoding of input strings.
In the proof of unsolvability, it is almost free to use suchencoding techniques, which could make it easier to investigate the inherent power of machines without depending
too much on the syntax of languages.

a.ut.omata$1\mathrm{S}\mathrm{A}’ \mathrm{s}$$1\mathrm{S}\mathrm{A}’ \mathrm{s}$1Introduction

It has become an undoubted fact that the quantum
mechanism gives us a certain kind of computational
power which cannot be achieved by the conventional
mechanism. However, although we have wonderful reports supporting this idea [Gro96, Sho94], there is still
a lot of unclearness about what is real and concrete reason for such a miracle power and how hard it is to enjoy
this power in designing algorithms. In their recent paper[KW97], Kondacs and Watrous gave a good hint against
those questions: They introduced 2-way quantum finite, and proved that a nonregular lanautomata,,$2\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}.(\mathrm{A}1\mathrm{t}\mathrm{h}_{0}\mathrm{u}\mathrm{g}\mathrm{h}\mathrm{e}\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{C}\mathrm{a}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{g}- a^{n}b^{n}n\geq \mathrm{l}\}_{\mathrm{h}\mathrm{t}}\mathrm{C}\mathrm{a}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{a}\mathrm{C}\mathrm{c}_{1\mathrm{g}\mathrm{u}\mathrm{a}}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{e}\mathrm{d}\mathrm{b}\mathrm{y}\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{S}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{n}$$\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{u}\mathrm{a}\mathrm{g}\mathrm{e},$nized by 2-way probabilistic finite automata [Fre81] but
it needs exponential expected time [DS89].) They also(lQFA’s) which they prove can recdefined 1-way
ognize only a proper subset of regular languages. Since
finite automata are much simpler than the general computation model (i.e., Turing machines), it is obviously
easier to undelstand concrete merits and demerits of thequantum mechanism.
More recently, Ambainis and Freivalds studied IQFA’sin mole detail [AF98]. Their results are a.gain interestingfrom the above viewpoint: (i) If the maxlmum error rateis bounded by a small value then lQFA’s cannot surpass
the power of 1-way reversible finite automata and (ii) In
some cases, we can design lQFA’s the number of whosestates is exponentially less than conventional ones. Morethan that, they gave the following observation about the: The definition in [KW97] includes thepower ofhead position into quantum state and hence the numberof quantum states grows unlimitedly with the growing
size of the input. Ambainis and Freivalds suggest t,hat
this could provide QFA’s with unreasonably high power
and at the same time could make the machine more complicated and more difficult to implement.
Their suggestion is probably true: In this paper it iscan actually beshown that the real power ofmuch higher than it seems. Our main result says thatthe emptiness problem, which asks whether a given ma.
chine accepts the empty set, is not solvable for
Moreover, it turns out that we do not need the 2-way
head-move for this result but the 1.5–way head-move (theposition to the right but not-l
head can movein this paper
position) is enough. Since all 1.
does not have a cycle of transitions without moving thehead (called an -cycle), the theorem also holds for such1.
which run obviously in linear time. The idea of
this extension is to exploit the basic nature of quantum)$\mathrm{Q}\mathrm{F}\mathrm{A}$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$1\mathrm{S}\mathrm{A}’ \mathrm{s}$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$\mathrm{s}$$2\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$2\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$2\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$0\mathrm{o}\mathrm{r}+1$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$Definitions

2
2.1

2-way Quantum Finite Automata

Our definitions of)$\mathrm{Q}\mathrm{F}\mathrm{A}$$\mathrm{s}$are exactly the same as,$\mathrm{f}_{Q,)}^{\mathrm{K}\mathrm{w}_{\Sigma\delta,q\mathrm{o},Q}}97].\mathrm{A}2- \mathrm{W}\mathrm{a}\mathrm{y}\mathrm{Q}ac\mathrm{C}’ Q,ei),\mathrm{W}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}Q\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{t}\circ \mathrm{f}s\mathrm{F}\mathrm{A}(2\mathrm{Q}\mathrm{F}\mathrm{A})\mathrm{i}\mathrm{s}\mathrm{g}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{a}\mathrm{S}Mattes=$

is a finite set of input symbols, $q_{0}\in Q$ is the iniand $Q_{rej}\subset Q$ are the setstial state, an. Qacc
of accepting and rejecting states, respectively.
is called the set of non-halting states.
$\Sigma$$\subset Q$$\mathrm{d}$$Q_{\mathrm{n}}on=$$Q-(Q_{a\mathrm{c}c}\cup Q_{fej})$$l\mathrm{a}\mathrm{n}\mathrm{d}\not\in,\Sigma \mathrm{r}=\Sigma\cup\{\emptyset^{d\mathrm{t}}\}11\mathrm{e}\mathrm{d}\mathrm{h}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{o}tapeSyms.\delta \mathrm{a}_{\mathrm{i}_{\mathrm{S}\mathrm{C}\mathrm{a}}}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{e}lefl\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{t}\mathrm{h}\mathrm{e}_{\mathrm{f}b\mathit{0}}\dot{n}gh\{end-m_{l}atkers.\cdot$$Q\mathrm{x}\Gamma\cross Q\cross\{-1,0,1\}\neg C$

function.

$(i,p)$ , isA pair of a head position and a state
on a tapecalled a configuration. Therefore, aof length has $n|Q|$ different configurations, denoted
by $C_{n}=Q\mathrm{x}Z_{n}$ . A superposition of $M$ is any norm
. For each
1 element of the Hilbert space$c\in C_{n},$denotes the unit vector with value 1 at and,elsewhere: For a superposition. For eachis the amplitude of the configuration in$q’\in Q,$
shows
and $d\in\{-1,0,1\},$the amplitude with which $M$ in state and reading
will change to state and move its head position right.
determines the time-evolution operator
Given a tapeas follows
on
$i$

$p,$

$2\mathrm{Q}\mathrm{F}\mathrm{A}M$

$n$

$x$

$\mathcal{H}_{n}=l_{2}(C_{n})$$c$$|c\rangle$$0$$|\psi\rangle$$=\Sigma_{c\in^{c_{n}\alpha}\mathrm{c}}|C\rangle$$c$$\delta(q, \sigma,q’, d)$$\delta\in\Gamma$

$q,$

$q$

$d$

$q’$

$x,$

$U_{\delta}^{x}$$\alpha_{c}$$|\psi\rangle$$\delta$$l_{2}(C_{n})$$\epsilon$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$.

is called the state transition$q’,$ $d)|q’,$$U_{\delta}^{x}|q,$$k \rangle=\sum_{q’1d}\delta(q, X(k),$$k+d(mod|X|))$$\sigma$201

where $x(k)$ is the input symbol at thecell.
is naturally extended toby lineality.
must beunitary and if so, $M$ is said to be $well_{-}f.ormed$ .
The computation of $M$ on begins
superposition. Thenis applied step by step. After each step,
the current superposition is observed. Our observable is. If “accept)’ or “reject)) is observed,
the computation halts. It is said thatis accepted by”$M$ iff
is observed with probability greater than
1/2. $L(M)$ denotes the set of all the tapes accepted by$M$ and is called the language accepted by $M$ .
To design well-formed, we can use the following approach: Suppose that we have designed a linear
operator: $l_{2}(Q)arrow i_{2}(Q)$ for eachand a function $D$ : $Qarrow\{-1,0,1\}$ . Let
denote the coefficient of. Then defille the transit,ion function
inof $M$ as$k\mathrm{t}\mathrm{h}$$U_{\delta}^{x}|q,$$U_{\delta}^{x}|\psi\rangle$$x$$|q_{0},1\rangle$. Suppose that the tape $x=x_{1}x_{2}X_{3}X_{4}(x_{i}\in\{a, b\})$ is$k\rangle$$U_{\delta}^{x}$$\mathrm{m}$$U_{\delta}^{x}$$Q_{acc}\oplus Q_{\mathrm{r}ej}\oplus Q_{non}$$x$$‘(\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}$glven to this QFA. Then one can see that:(i) If $x_{1}=x_{2}$and $x_{3}=x_{4}$ thenhalts inwith probability 0.2,
and if that does not happen thenreaches
Therefore the probability that “accept” isobserved ls 0.8 in total. (ii) If $x_{1}=x_{2}$ andthenthat probability is 0.4. (iii) If
and $x_{3}=x_{4}$ thenit is again 0.4. (iv) If
andthen theprobability is . Thus this QFA accepts the language$x_{1}=x_{2}$ and $x_{3}=x_{4}$ }.
{$\Lambda I_{0}$$q_{3}$$\sqrt{05}|q_{18}\rangle$$M_{0}$$+$$\sqrt{05}|q_{19}\}_{:}$$x_{3}\neq x_{4}$$x_{1}\neq x_{2}$$x_{1}\neq x_{2}$$x_{3}\neq x_{4}$$0$$x_{1}x_{2}x_{3}X_{4}|x_{i}\in\{o_{\rangle}b\},$)$2\mathrm{Q}\mathrm{F}\mathrm{A}$$\mathrm{s}$$\langle q’|V_{\sigma}|q\rangle$$|q’\rangle$

One-Register Machines

2.3$\sigma\in\Gamma$$V_{\sigma}$$V_{\sigma}|q\rangle$$\delta$

To prove the unsolvability, we shall use the unsolvof the halting problem for one-register nlachines.
A-regisler $mac/_{t}ine(RM)$ consists of t,lle finite control with states , . . , $p_{K-1}$ and a single
that
can hold an (albitrarily large) integer. Let be 2 or 3.
For each state, one of the following three instructions is
specified:(1) Multiply the current value, , in the register by
and move to state . This instruction is denoted by(MUL-i, ).
(2) Divide $R$ by and move to , denoted by (DIV$\mathrm{a}\mathrm{b}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}_{}\mathrm{y}$$\mathit{0}?le$,$p_{0}$$\langle q’|V|\sigma q\rangle$$\delta(q, \sigma, q’, d)=\{$$0$

if $D(q’)=d$
if $D(q’)\neq d$ .

$1^{\cdot}\mathrm{e}\mathrm{g}\mathrm{i}\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{r}$

$i$

$R$

It is shown in [KW97] that $M$ is well-forlned if and only
if
1 $q_{1}=q_{2}$$\sum_{q’}\overline{\langle q’|V\sigma|q_{1}\rangle}\langle q|\prime V\sigma|q2\rangle=\{$

$0$

$i$

$p_{j}$$p_{j}$$i$$p_{j}$$i,p_{j})$$q_{1}\neq q_{2}$(3) Test if isby . If so, move toandmove tootherwlse. This instruction is denoted by$R$for each$\sigma\in\Gamma$.

$\mathrm{d}\mathrm{i}.\mathrm{v}\mathrm{i}_{\mathrm{S}}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}$$i$$p_{j_{1}}$$p_{j_{2}}$(TEST-i,).
is always the initial state and $p_{K-1}$ is always the
only one halting state. Without loss of generality, we
can assume that when instruction (2) is executed, thecurrent value $R$ is divisible by . For technical reason
we also assume that the instruction as sociated with theinitial stateis always (MUL-2, ), which again does
not lose generality. The value $R$ does not cha.n ge when(3) is executed. It is known thatare equlvalent to$p_{j_{1}},p_{j_{2}}$$p_{0}$

1.5-way Quantum Finite Automata

2.2

A 1.5-way quantum finite automaton is asuchthat is defined as :, and is de. by a QFA from now on. Namely, QFA’s
notedcannot move their head $-1$ position but can moveor +1 position. A sequence of statesis$1\leq j\leq m,$ $q_{i_{j}}\in Qnon$
called an -cycle if (i) for eachand(and (iii) there is a tapesymbolsuch that the coefficientin
is not zero for all $1<i<m-1$ . If a QFA $M$ does notinclude an -cycle,
clearly halts within a linear
time. Allin this paper do not include e-cycles.
Fig. 1 shows an example of a QFA, denoted by.
This figure gives aso–called state-transition diagram. For
example, the transition from (that is the initial state)$2\mathrm{Q}\mathrm{F}\mathrm{A}$$\delta$$Q\cross \mathrm{r}_{\mathrm{x}Q}\mathrm{X}\{0,1\}arrow C$$\delta$$\mathrm{s}\mathrm{i}\mathrm{m}_{\mathrm{P}^{\mathrm{l}\mathrm{y}}}$$0$$q_{i_{1}},$$q_{i_{2},\cdots,q_{i_{m}}}$$\epsilon$$q_{i_{j}},$$D(q_{i_{\mathrm{j}}})=0,$$q_{i_{1}}=q_{i_{m}}$$\mathrm{i}\mathrm{i}\rangle$$\sigma\in\Gamma$$\mathrm{o}\mathrm{f}|q_{i_{\mathrm{j}+1}}\rangle$$V_{\sigma}|q_{i_{j}}\rangle$$i$$p_{0}$$p_{1}$$\mathrm{R}\mathrm{M}$)$\mathrm{s}$Turing machines:
Proposition 1 [Min66]. The halting .roblem for
RM’s that start their computation with the lnitial
register value one is not solvable.
$\mathrm{p}$$\mathrm{t}\overline{\mathrm{h}}\mathrm{e}\mathrm{n}^{-}M$$\epsilon$)$\mathrm{Q}\mathrm{F}\mathrm{A}$$\mathrm{s}$$M_{\mathrm{Q}}$$q_{0}$

means$V_{\mathit{4}}|q\mathrm{o})=\sqrt{04}|q_{1}\rangle+\sqrt{04}|q2\rangle+\sqrt{02}|q_{3}\rangle$.

Accepting states are. Rejecting states are ,andand. As for the function $D,$ $D(q_{i})=0$ if
is an accepting or a rejecting state and $D(q_{i})=1$ otherwise. Following the practice [KW97, AF98], we leave
many transitions (e.g., transitions from ) undefined.
Those transitions may be arbitrary and it is not hard to
define them so that the resulting operator will be unitary.
$q_{18}$$q_{7)}q_{1}3,$$q_{1}6$$q_{19}$3

Main Theorem

The emptiness problem is to decide whether $L(M)=.\phi$for a given autolnaton $M$ . If the emptiness problem ls
unsolvable for a class of automata, several other problems are also unsolvable for that class of automata including the equivalence problem $(L(M_{1})=L(M_{2})?)$ and$\mathrm{i}\mathrm{m}\mathrm{m}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{C}\circ \mathrm{r}01\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{S}\mathrm{j}_{\mathrm{o}\mathrm{i}\mathrm{b}}\mathrm{n}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{p}\mathrm{r}\circ 1\mathrm{e}_{\mathrm{f}\mathrm{T}\mathrm{s}_{\mathrm{e}}.\mathrm{S}}\mathrm{m}1\mathrm{a}\mathrm{r}\mathrm{y}\circ L(M\mathrm{o}1\mathrm{e}\mathrm{m}1)\cap L(M_{2})\phi?).\mathrm{A}1\mathrm{S}\mathrm{o}\mathrm{a}1\mathrm{i}\mathrm{S}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\overline{\overline{\mathrm{t}}}\mathrm{h}\mathrm{e}\mathrm{e}\mathrm{m}_{\mathrm{P}}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{n}$$q_{3}$$q_{17}$$q_{i}$$q\tau$problem is unsolvable for.
Theorem 1. The emptiness problem for QFA’s is)$2\mathrm{Q}\mathrm{F}\mathrm{A}$unsolvable.
Proof. It is shown that there is an algorithm (a Turing machine that always halts) which translates any RM$X$ into
a QFAsuch that $L(M_{X})=\phi$ iff $X$ startingwith $R=1$ does not halt. Suppose that the given $X$ has
states,. Recall that each state is as$M_{X}$$I\mathrm{s}\mathrm{i}$“”$(\mathrm{i}\mathrm{e}\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\circ \mathrm{s}\mathrm{e}.\mathrm{t}\mathrm{h}.,\mathrm{a}\iota \mathrm{w}\mathrm{e}\circ \mathrm{b}_{\mathrm{S}}\mathrm{e}\mathrm{r}\mathrm{v}\mathrm{e}_{\mathrm{b}\mathrm{s}\mathrm{e}\mathrm{r}}M0_{\mathrm{V}\mathrm{e}\mathrm{d}}\mathrm{a}\mathrm{f}\mathrm{t}\mathrm{e}_{\mathrm{W}}\mathrm{r}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}_{\mathrm{O}}\mathrm{t}\mathrm{s}\mathrm{t}\mathrm{e}_{\mathrm{P},\mathrm{i}1}.\mathrm{T}\mathrm{h}.\mathrm{n}\mathrm{b}\mathrm{y}q_{3})\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{p}\mathrm{r}\mathrm{b}\mathrm{a}\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{y}0^{\mathrm{e}}2$$\mathrm{s}$$p0\mathrm{t}\mathrm{h}_{\mathrm{l}\mathrm{O}}\mathrm{u}\mathrm{g}\mathrm{h}p_{K}-1$$\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}$and if that happens
halts.
is observed withprobability $(\sqrt{04})^{2}+(\sqrt{04})^{2}=0.8$ and if that happens, the amplitude of each state changes fromto. This amplitude does not change until
is reached unlessdrops into ,$q16$ or. If reads $ab$ or $ba$ in the first two steps,”$+\sqrt{05}|q_{9}$then it goes to). If(by ) isobserved (with probability 0.5) thenstops. Otherwise
continues its computation from.
$M_{0}$$\{q_{1}, q_{2}\}$$\sqrt{04}$$\frac{\sqrt{04}}{\sqrt{08}}=\sqrt{05}$$\sqrt{05}|q_{18}\rangle+\sqrt{05}|q_{19}\rangle$$q_{17}$$q_{1\mathrm{s}},$$M_{0}$$q_{7}$$M_{0}$$\sqrt{05}|q_{7}\rangle$($‘ \mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}$$q_{7}$$M_{0}$$M_{0}$$\mathrm{F}_{0\mathrm{s}^{1}}^{05}q_{9}\rangle$$=|q_{9}\rangle$,
and (TEST-3,). Since the translation
itself ls not.plicated, lt wlll be enough to only givea detailed descrlption of the target machine. In thefollowing, we first explain what kind of language
should accept and then describe how to construct
to that goal.
$\mathrm{s}\mathrm{o}\mathrm{c}\mathrm{i}2,pj)\mathrm{a}\mathrm{t},\mathrm{e}\mathrm{d}(\mathrm{M}\mathrm{U}\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{n}\mathrm{e}\circ \mathrm{f}\mathrm{t}\mathrm{L}-3pj))’(\mathrm{D}\mathrm{I}\mathrm{V}- 2,pj),(\mathrm{D}\mathrm{I}\mathrm{V}- pj\mathrm{h}\mathrm{e}\mathrm{f}\circ 11\mathrm{o}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}\mathrm{i}\mathrm{X}\mathrm{i}\mathrm{n}\mathrm{s}_{3,)}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{C}\mathrm{t}\mathrm{i},\mathrm{o}\mathrm{n}(\mathrm{T}\mathrm{s}\mathrm{b}_{\mathrm{s}\mathrm{T}2}\mathrm{M}\mathrm{U}\mathrm{L}--$$p_{\mathrm{j}_{1}},$$p_{j_{2}})$$p_{i1)}p_{jz}$$\mathrm{c}\mathrm{o}\mathrm{m}$$M_{X}$$M_{X}$$M_{X}$

202$\Rightarrow$

Fig. 1

The Language to be accepted by

3.1$M_{X}$

be the following language which is determinedLet, $p_{K-1},p_{K}$ ,by the RM $X$ and whose alphabet is {$p_{K+1},\#,$
states).
through $p_{K-1}$ are(recall thathas to be of the following
A sequence contained inform. Its objective is to show a sequence of configurations that change step by step in the course ofcomput ation:$L_{X}$$p_{0},$$\cdots$$X’ \mathrm{s}$$0\}$$p_{0}$$L_{X}$$z$$X’ \mathrm{s}$,branches into
Remark 1.
; $p_{K-1}$ , respectively. Afby readingof two neighboring blocks,
ter
must
)
, .
that is the same as
two blocks. The existence ofdescribed in (2) above allows us to design this portion ofusing unitary operators.
,
later,
reaches “acceptance”,
As will
wlth
(or
one
probability
with“acceptance is
’
.
), if
probability 0.4 considerlng the whole machine
the tape passes the above test. If does not passwith probability
the test,
can reachroughly $1/N$ or less, as shown later, where we can set $N$.
as an arbitrarily large integer. This is the same for, or represents
One can see that if the tape is inconfigurations, thena proper halting sequence of. That nleans the whole
passes both tests ofandmachinereaches “acceptance” with probability 0.8,
then iti.e., is accepted. If the tape is not indoes not pass at least one of the two tests, which meansreaches “acceptance” with probability at most 0.4+
. Thus, namely is not accepted by$M_{1}(p\mathrm{o}),$$M_{1}$$M_{1}(p_{K}-1)$$p_{0},p_{1},$$M_{1}(p_{1}),$$\cdots$$\cdots$$\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}.\mathrm{t}\mathrm{h}\mathrm{e}.\mathrm{p}\mathrm{r}\mathrm{o}_{\mathrm{P}^{\mathrm{e}}}\mathrm{r}\mathrm{n}\mathrm{e}\mathrm{S}\mathrm{s}$O.

$M_{1}$$\mathrm{r}\mathrm{e}_{\mathrm{J}^{\mathrm{o}\mathrm{i}\mathrm{n}1}}\mathrm{n}.\mathrm{t}$$M_{1}(p_{1})$$M_{1}(p_{0}),$$\mathrm{a}_{M},\sin_{\mathrm{f}}1p_{K1}-$$\mathrm{a}\mathrm{g}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{e}1\mathrm{e}\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{b}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{n}\mathrm{t}\circ \mathrm{x}\mathrm{t}$$p_{i_{1}}$$\mathrm{P}i_{4}$$M_{1}$$M_{1}$$\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{w}\mathrm{n}$$\mathrm{i}_{:}\mathrm{e}.$)’$\mathrm{o}\mathrm{b}_{\mathrm{S}\mathrm{e}}\mathrm{r}\mathrm{V}\mathrm{e}\mathrm{d}$$M_{X}$

tz$=l#p0$0_{pK}\# p100p_{K}+1\#\cdots\#\mathrm{P}i\mathrm{o}\cdots \mathrm{o}_{pj}\#\cdots\# p_{K}-10\cdots 0p_{\mathrm{t}\#\}$

$z$

$z$

$M_{1}$

is called a block.
A subsequence surrounded by two
in each block shows the value $R$ In
The number of
iff the following three
more detail, is in$\#’ \mathrm{s}$$0’ \mathrm{s}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\dot{\mathrm{i}}_{\mathrm{O}}\mathrm{n}\mathrm{s}$$L_{X}$$z$

are met:and(1) The first and second blocks must beand$p_{1}00pK+1$ , respectively, regardless of $X$ , where$p_{K+1}$ are new symbols neither of which appears elsewhere again.
$p_{0}0p_{K}$$p_{K}$$‘(\mathrm{a}\mathrm{C}\mathrm{C}\mathrm{e}_{\mathrm{P}^{\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}’}’$$M_{2}$$L_{X}$$x$$x$$X’ \mathrm{s}$$M_{2}$$M_{1}$$M_{X}$$L_{X}$$x$$x$$M_{X}$$\mathrm{b}1\circ \mathrm{C}(24\mathrm{S}\mathrm{e}\mathrm{X}\mathrm{C}\mathrm{n}\mathrm{t}\mathrm{L}\mathrm{e}\mathrm{t}\#_{\mathrm{e}_{\mathrm{P}^{\mathrm{t}\mathrm{i}\mathrm{g}\mathrm{e}}}}pi_{1}0^{j1}p\#\mathrm{f}\mathrm{i}\mathrm{S}pi0^{j}2p\mathrm{h}^{i}\mathrm{e}^{2}\mathrm{r}^{8}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{d}^{i}\mathrm{t}\# 4\mathrm{g}\mathrm{h}\mathrm{b}\circ \mathrm{r}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\circ \mathrm{n}\mathrm{b}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{y}\mathrm{n}\mathrm{e}\mathrm{i}\mathrm{e}\mathrm{s}.\mathrm{T}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{W}\circ \mathrm{h}\mathrm{n}(\mathrm{i})$$\frac{1}{N}<0.5$, and (ii) the
betweenmust be equal toin these two blocks, and , and thethe numbers ofmust be valid with respect
andrelation between
to the instruction associated with . (if the innstructionandis (MUL-2, ), for example, then must be 2
must be ).
with $p_{K-1}$ , i.e., the only$|\mathrm{c}\mathrm{l}\dot{\mathrm{c}}1\mathrm{l}\mathrm{i}\mathrm{o}\mathrm{n}$$p_{i_{4}}$$p_{i_{1}}$$p_{i_{3}}$$p_{i_{1}}$$p_{i_{1}}$$\cdot j_{1}$$g_{2}$$p_{j}$$p_{j}$$p_{i_{3}}$.

$\circ \mathrm{n}\mathrm{e}4_{\mathrm{a}}^{\mathrm{T}\mathrm{h}\mathrm{e}}(31\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\circ \mathrm{f}\mathrm{t}1\mathrm{a}S\mathrm{t}\mathrm{b}1\mathrm{o}\mathrm{c}\mathrm{k}\mathrm{m}\mathrm{u}\mathrm{S}\mathrm{t}\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{h}\mathrm{e}\mathrm{R}\mathrm{M}x\mathrm{t}$3.3Submachines$M_{1}$

and$M_{X}$$q_{0},$$M_{2}$$M_{X}$$M_{1},$$\mathrm{J}/I_{2}$$\sqrt{0.4},$$q\mathrm{o},r\mathrm{e}j$$\sqrt{04}$$\sqrt{02}$$\ln$$M_{1}$$(2i+1)\mathrm{t}\mathrm{h}$$M_{10}$$(2i+2)\mathrm{t}\mathrm{h}$$M_{1}$$M_{1}(p_{0}),\lambda/_{1}I(p_{1}),$ $\cdots$$(2i)\mathrm{t}\mathrm{h}$$M_{1}$$\Lambda’I_{1}(p_{K-1})$$\Lambda I_{2}$and$M_{10}$$M_{20}$which checks
Fig. 3 illustrates the submachine
the first and second blocks. The machine is easy since all
it has to do is to check whether the beginning portion of
the input is equal to the fixed string. As for the notation,. All rejecting
for allmeans
states but the following exceptions have “ ” in theirandsubscripts. Other rejecting states are. forincludes a split lnto
$1<j\leq N-1$ . Note thatand the quantum Fourier transform
paths from. We actually do not need those gadgets for thefromabove purpose but we introduced them to adjust thatlater.
portion to other parts of’ which one can see
is slmilar to the example in secThe behavior ofbyis not observed and thetion 2.2. If “reaches
beginning portion of is proper, then
. (More precisely speaking, $Mx$
with amplitude
where is some superposition
reaches$M_{10}$$\sigma\not\in\{\oint\}$$V_{\sigma}|q_{0}\rangle$$\mathrm{r}\mathrm{e}\mathrm{j}$$M_{2}$

consists of two major subThe whole machineas shown in Fig. 2. From its
andmachines
and a lejectsplits into
initial state,
and, with amplitudes
ing state,
Fig. 1. Then
respectively, just like the example
tests (i) whether the first two blocks are properand (ii) whether theusing submachineandblocks are proper in the sense of (2)uses submachines
above for each $i\geq 1$ . To do so,
is similar. It checks,.
whether the first block is proper and then whether theandblocks are properly related. Bothandalso check whether the last block includes
thehalting state $p_{K-1}$ .
$M_{1}$.

Submachines$V_{\neg}\{’\}|q_{\mathit{0}})$3.2$M_{X}$$M_{X}$$x$$L_{\lambda}-$$j_{2}$$j_{1}$$\mathrm{O}’ \mathrm{s}$recognizes$s_{1,j}$$t_{1,j}$$M_{10}$$\sqrt{N}$$q_{1,8}$$r_{1,j}$$M_{X}.$$M_{10}$)$\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}?$$q_{0,r\mathrm{e}j}$$M_{10}$$z$$|q_{1,8}\rangle$$\sqrt{05}$$\sqrt{05}|q_{1,8}\rangle$$+|\psi\rangle$$\psi$$(2i+1)\mathrm{t}\mathrm{h}$$\mathrm{s}\mathrm{i}\circ \mathrm{n},\mathrm{w}\mathrm{e}\mathrm{o}\mathrm{f}M_{2^{\mathrm{S}}}’ \mathrm{s}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{V}\mathrm{e}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{S}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}||\mathrm{h}\mathrm{e}\mathrm{a}|\psi\rangle|4^{=}\mathrm{p}\mathrm{o}\mathrm{S}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{s}\mathrm{n}\mathrm{e}\sqrt{05}.\mathrm{I}\mathrm{n}\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{t}\mathrm{s}-$$M_{2}$$X’ \mathrm{s}$important.) Subsequently,$M_{10}$goes through the Fourier

203

Fig. 2transform and one can calculate that it reaches$0|s_{1,1}\rangle$$0|s_{1,2}\rangle+\cdots+0|s1,N-1\rangle+\sqrt{05}|S_{1,N}\rangle=\sqrt{05}|S_{1,N}\rangle$$M_{10}$goes to3.4$\sqrt{05}|q_{1,staf}t\rangle$

Submachines.

$M_{20}’ \mathrm{s}$$M_{1}(p_{x})$$+$. Thenbehavior is similar.

and$M_{2}(p_{x})$i.e., the amplitude ofis very small. Recall that all
through $s_{1N-1}$ are rejecting states.
We can use the same idea to recognize the slightly different language $\{0^{n}10^{n}.|n\geq 1\}$ . Actually, the situation
is better than before slnce we do not need the reverse
move of the head that was mandatory in $M_{KW}$ when
the head crosses the boundary ofand. Namely,$|s_{1,N}\rangle$$s_{1,1}$$a’ \mathrm{s}$If the input string is proper,
reads some,$0\leq x\leq K-1$ , in stateand branches to submachine. Recall thatis associated with oneof the six instructions. Suppose that $p_{x}\neq p_{K-1}$ and the
instruction for is (MUL-2, ) Th\S n the transition ofis as shown in Fig. 4. (Thefor other
five cases are omitted.) If $p_{x}=p_{K-1}$ then $M_{1}(p_{K-1})$
has only to check whether the current block is the lastone, whose transition is given in Fig. 5. In whqt follows,
we overview the case that Fig. 4 applies. All the othel.
cases are quite similar.
Suppose that $Px$ is associated with (MUL-2, ). Here
we can use the idea of thein [KW97], denoted by$M_{KW}$ , which accepts $\{a^{n}b^{n}|n\geq 1\}$ . Reading 4, $M_{KW}$
splits into $N$ paths with amplitude $1/\sqrt{N}$ . Along thepath, $M_{KW}$. operates as follows:
reads , its tapehead remalns stationary for steps and then moves right.
If $M_{KW}$ reads , the head remains stationary for $N-j+1$
teps and then it moves right. Now suppose that $M_{KW}$
given the input. Then it turns out that any
two distinct computation paths will reach the $ symb
at the same time if and only if $n_{1}=n_{2}$ . To check thissimultaneousness, we can use the Fourier. Let
us look at Fig. 3 again: If the machine is in, i.e., if all the $N$ paths reaches
at the same time, then the machine reaches
whose amplitude is 1.0. If only one path reaches,say,
at some time (i.e., the machine is inwheredoes not include,,), thenit reaches
at the next step,$M_{10}$$b’ \mathrm{s}$$p_{x}$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\{0^{n}\mathrm{l}0n|\mathrm{f}\mathrm{u}\mathrm{r}\mathrm{t}\mathrm{h}n\geq \mathrm{l}\}\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{b}\mathrm{e}\Gamma \mathrm{e}\mathrm{c}\mathrm{o}\mathrm{g}\mathrm{n}\mathrm{i}\mathrm{Z}\mathrm{e}_{\mathrm{h}}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{C}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{y}\mathrm{b}\mathrm{a}1.5\mathrm{Q}\mathrm{F}\mathrm{A}.\mathrm{T}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{g}\mathrm{n}\mathrm{i}\mathrm{Z}\mathrm{e}\mathrm{s}$$q_{1,staft}$$M_{1}(p_{x})$$p_{x}$$p_{x}$$p_{y}$$2\mathrm{Q}\mathrm{F}\mathrm{A}$$j\mathrm{t}\mathrm{h}$$\mathrm{i}\mathrm{f}M_{KW}$

$a$

$j$

$b$

$.\mathrm{s}$$a^{n_{1}}b^{n_{2}}$$1\mathrm{S}$$o1$$\mathrm{t}‘ \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{S}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}$$\mathrm{j}_{N}^{1}=|r_{1,1}\rangle$$+$$\frac{1}{\sqrt{N}}|r_{1,2}\rangle+\cdots+\frac{1}{\sqrt{N}}|r_{1,N}\rangle$$r_{1,N}$$|s_{1,N}\rangle$$r_{1,1}$$|\psi\rangle$

.

that

$\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{L}\mathrm{e}\mathrm{t}\mathrm{s}\mathrm{i}\mathrm{n}1\mathrm{u}\mathrm{S}\mathrm{O}\mathrm{o}_{S}\mathrm{k}\mathrm{a}q_{1},tart\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{b}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{t}\mathrm{F}\mathrm{i}\mathrm{g}.4\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{t}\mathrm{a}\mathrm{i}1M_{1}\mathrm{s}\mathrm{t}\mathrm{o}(p_{x}.\int_{\mathrm{b}\mathrm{a}\mathrm{d}}^{\mathrm{i}})\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{m}_{\mathrm{i}}\mathrm{a}\mathrm{C}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{y}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{g}p_{x}\mathrm{e}$$\mathrm{t}\dot{\mathrm{r}}\mathrm{a}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$p_{y}$$\cdots,$$(\mathrm{a}p_{x}.)\mathrm{n}\mathrm{d}$$.$$M_{1}(p_{x})$$r_{1,1},$$\mathrm{i}_{\mathrm{S}\mathrm{e}}\mathrm{a}\mathrm{c}\mathrm{t}1\{0^{n_{\mathrm{X}}}10^{2n}|n\geq 1\}\mathrm{i}\mathrm{S}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\mathrm{f}\mathrm{y}_{\mathrm{W}}\mathrm{h}\mathrm{a}\mathrm{t}\mathrm{w}\mathrm{e}\mathrm{w}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{d}\circ \mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}M_{1}\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{w}\mathrm{a}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{x}\mathrm{e}\mathrm{r}\mathrm{C}\mathrm{i}\mathrm{e},$$\frac{1}{\sqrt{N}}|r_{1,1}\rangle$$|\psi\rangle$$|r_{1,2}\rangle$$\cdots$$+$$|r_{1,N}\rangle$$\frac{1}{N}\exp(\frac{2\pi i}{N}\cdot 1)|S_{1,1}\rangle+\cdots+\frac{1}{N}\exp(\frac{2\pi i}{N}\cdot(N-$$1))|S_{1,N}-1 \rangle+\frac{1}{N}\exp(\frac{2\pi i}{N}\cdot N)|S_{1,N}\rangle+|\psi’\rangle$

and at the same time splits into $N$ paths. Here,$\{p_{*}\}$$\cdot\#.,p_{w}^{K\mathrm{l}},\mathrm{a}\mathrm{n}.\mathrm{a}\mathrm{g}\mathrm{a}\mathrm{n}\{p0,p-\}_{\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{t}}(\mathrm{i}\mathrm{i})\mathrm{T}\mathrm{h}\mathrm{e}0^{\mathrm{n}}’ \mathrm{S}\mathrm{i}M1\iota^{px}\mathrm{i}_{\mathrm{S}}\mathrm{o}\mathrm{r}\mathrm{d}^{\sup_{\mathrm{r}}}\mathrm{e}.\mathrm{s}_{\mathrm{u}}^{\mathrm{o}}\mathrm{p}\mathrm{P}^{\mathrm{o}\mathrm{S}}\mathrm{e})\mathrm{i}\mathrm{S}\mathrm{p}\mathrm{s}\mathrm{e}\mathrm{d}\mathrm{t}\mathrm{o}$$\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{s}0’ \mathrm{s},pu’.,$”that. Then
the numbersof the filst
and the secondin each path by themethod previously explained. In the middle of this action, it falls into rejecting states if. (see (11)in the figure). Note that
may be arbitrary. (iii) Subsequently t.h machine should readagain (otherwise
falls into rejecting states in (15) and leaves, i.e.,
converges toin $(14-a)$ . Note that the $N$ paths are
not converged at this moment yet. In the next step the
Fourier transform is applied in $(16-a)$ (which alreadyappeared in Fig. 3 but is repeated here).
Claim 1. If everything is good, then the $N$ computation paths arrive at
at the same time. Thatmeansreaches. Otherwise, if the numbersof the first
and the second
are not proper for example, then each of the $N$ computation paths arrives at
at all different steps with amplitude $1/N$ each time.
If $p_{w}=p_{K-1}$ and if this $p_{K-1}$ is the proper successorof , then the second block must be the final one. Therefore
goes to a different routine at $(10-b)$ . In
this case, the Fourier transform is applied in $(16-b)$ andif everything is good then it reaches
insteadof. In the next step it reaches,$p_{w}\neq p_{K-1}$$\Lambda/I_{1}(px)‘(\mathrm{C}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{s}$$\mathrm{O}’ \mathrm{s}$$0’ \mathrm{s}$$p_{w}\neq p_{y}$$p_{u}$$\mathrm{e}$$p_{x}$$)$$M_{1}(p_{x})$$|r_{1\mathrm{j}}\rangle$$r_{1,1)}\cdots,$ $r_{1,N}$$\sqrt{05}|S_{1,N}\rangle$$M_{1}$$0’ \mathrm{s}$$\mathrm{O}’ \mathrm{s}$$s_{1,N}$$p_{x}$$M_{1}(p_{x})$$\sqrt{05}|t_{1,N}\rangle$$\sqrt{05}|S_{1,N}\rangle$$\sqrt{05}|q_{1,ac}c\rangle$

204

served for the fastest path or the second fastest path is.
is one of the four accepting states of
wherethat is the counterpart ofin(The others are) )inin $M_{1}(p_{K-}1)$ and, which is almost theWe omit the description of(but of coulse we need new states).
same asThere is one thing we should be caleful for. There are,) and (TEST-3,
two instructions (TEST-2,$M_{X}$$q_{1,acc}$$M_{2}$$q_{2,acc}$$0.5 \frac{N-1}{N^{2}}+(1-0.5\frac{N-1}{N^{2}})0.5(\frac{N.-1}{N^{2}-05(N-1)})=2\cross(0.5\frac{N-1}{N^{2}})$$M_{2_{\backslash }^{(}\mathrm{P}}K-1$$q2_{\}}11,acc$$q1,aCc’ q1,11,a\mathrm{c}\mathrm{c}$$.$$M_{2}(p_{x})$when theNamely, the probability is increased bysecond fastest path arrives. It is not hard to see that thesame amount of probability is also added when the thirdwhenfastest path reaches there and so on. As a “
isthe $N$ paths reach there, the probability thathalts soobserved for at least one path, namely that
far is$M_{1}(p_{x})$$p_{j_{1}},$$05 \frac{N-1}{N^{2}}$$p_{j_{1}}$$p_{j_{2}}$$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{u}\mathrm{l}\mathrm{t}.\rangle$$p_{\{}2)\mathrm{w}\mathrm{h}\mathrm{i}_{\mathrm{C}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{f}}\mathrm{u}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{u}\mathrm{s}\mathrm{t}_{0}\mathrm{c}0\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{V}\mathrm{S}\mathrm{i}1\mathrm{e}\mathrm{b}\mathrm{y}\mathrm{t}_{\mathrm{W}\circ}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{C}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{e},\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{k}\mathrm{W}\mathrm{h}\mathrm{e}\mathrm{t}\mathrm{p}\mathrm{e}\mathrm{t}\mathrm{V}\mathrm{e}1_{\mathrm{V}}.\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{C}\mathrm{k}\mathrm{g}\mathrm{h}\mathrm{e}_{\mathrm{C}}\mathrm{r}_{\mathrm{i}}\mathrm{t}\mathrm{h}\mathrm{e}.\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}_{\mathrm{i}\mathrm{n}}\circ$’if it is divisible by two has no problem but checking if
it is divisible by three needs care. Intuitively, this canand . If thebe done using three states, saynumber is divisible, then the machine will be always in. Otherwise, if not divisible, then the machine may beor ; it is not possible to define transition fronu those
two states to a single state by the same symbol.
$p_{0},$$\mathrm{r}\mathrm{e}_{\mathrm{J}^{\mathrm{e}\mathrm{C}\mathrm{t}}’}$$M_{1}$$p_{2}$$p_{1}$$0.5 \frac{N-1}{N^{2}}\cdot N=0.5\frac{N-1}{\mathit{1}\mathrm{V}}$$p_{0}$

Since “reject” is observed with probability 0.2 before
branches to $M,$ . the overall probability that “reject’) is
observed so far ls$M_{x}$$p_{2}$$p_{1}$

Analysis

3.5.

is theLet $z=\# B_{1}\# B_{2}\# B3\#\cdots\# B_{i}\#\cdots\# B_{2}m\#$ , whereare proper and thatblock. Suppose first that all. Then, for all $1\leq i\leq m-1$ ,does not stop at) after it reads
reachesalwayssubmachine
, and
it
reads
after
reaches. Thenalwaysfinally. Submachinethen reaches
for allalso after it reads
reachesis read by $M_{2}(p_{K1}-)$ , which$i\leq m-1$ and finally
eventually. Thus the probability
reaches $\sqrt{05}|q2,11$
that “acceptance is observed is $(1 -0.2)\cdot((\sqrt{05})^{2}+$$(\sqrt{05})^{2})=0.8$ and. If includes
is accepted byan odd number of blocks, then nothing differs excepting
are switched. As a result,andthat the roles ofthen is accepted by
we can conclude that if is in$0.2+(1-0.2) \cdot 0.5\cdot\frac{N-1}{N}=0.2+0.4\frac{N-1}{N}$ .

$B_{i}$)$B_{i}$$i\mathrm{t}\mathrm{h}$$M_{X}$$\mathrm{s}$If$q0,r\mathrm{e}j$$\sqrt{05}|s_{1,N}$$M_{1}$$B_{2m}$$\sqrt{05}|t_{1,N}\rangle$$M_{1}$$B\circ\sim i$$M_{2}$$\sqrt{05}|q_{1,ac\mathrm{C}}\rangle$$\sqrt{05}|s_{2,N}\rangle$$0\leq$$B_{2\iota+1}$$z$

is sufficiently large, this value is greater than 0.5 andrecognizes
is rejected. Thus we can conclude that$N$

$M_{X}$$L_{X}$.

Finally we should mention how we have designed
reso as to be unital.y. The basic idea is to makeversible everywhere but the portions of the Fourier transform. This concludes the proof of Theorem 1.
$M_{X}$$M_{X}$$B_{2m}$$acc\rangle$)”$M_{X}$$z$$z$$M_{2}$$M_{1}$$z$$L_{X}$$z$.
are proper but
through
Now suppose that
. There are two cases:
is not for(1)
is improper regardless of the number of ; fororor
example, its syntax is different fromis not what is supposed to be. Then one can see thatcan detect that improperness
andat least one ofand all the $N$ paths fall into rejecting states. That means
the overall probability that “reject” is observed is at least$M_{X}$$B_{i-1}$$B_{1}$$B_{i}$$\mathrm{e}_{\mathrm{o}\mathrm{m}\mathrm{e}i}.\geq 1$$0^{)}\mathrm{s}$$B_{i}$$p_{x}0\cdots \mathrm{o}_{p_{y}}$$p_{x}$$p_{y}$$M_{2}$$M_{1}$

Concluding Remarks

4

Our study in this paper would reveal several interesting questions yet to be resolved: (i) Now we know that1.
can accept considerably high-class languages
up to at least those which cannot be accepted by oneway stack automata. Then what is a well-known class oflanguages that can contain all t,he languages accepted by? Furtllermore, does the answer to this questionAdlffer much if 1.5 QFA’s are replaced bymore specific question is whether or not there is a classof one-way linear-time conventional machines (like alter) which is at least as powerful as 1.5
nating off-line
QFA’s without -cycles. (iii) We were not able toin this paper. Our
negative aspects of 1.
cannot be
regulal languages
ture is that thereeven if we allow -cycles. (iv)
accepted by any 1.
Our 1.
in this paper have a quite large error probto reduce it signifability. It, does not appear
beicantly as long as dependillg on the current approach ofcomputing conjunctiveness (see the example in Section$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$1_{:}5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$2\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}?(\mathrm{i}\mathrm{i})$$\mathrm{T}\mathrm{M}\mathrm{s}$$\cdot$$\mathrm{d}\mathrm{i}_{\mathrm{S}\mathrm{C}.\mathrm{u}}\mathrm{s}\mathrm{S}$$\epsilon$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$\mathrm{C}\mathrm{o}\mathrm{n}_{\mathrm{J}^{\mathrm{e}\mathrm{c}-}}$$\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\downarrow$$\mathrm{a}\mathrm{l}\mathrm{e}$$0.2+(2).\mathrm{b}\mathrm{e}1^{\cdot}\mathrm{o}\sqrt{05})_{0’ \mathrm{e}\mathrm{i}}20.6,\mathrm{n}\mathrm{a}\mathrm{m}\mathrm{e}1\mathrm{y},z\mathrm{i}\mathrm{s}\Gamma \mathrm{e}\mathrm{j}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{f}\mathrm{S}\mathrm{a}111\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{e}11\mathrm{t}\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{w}\mathrm{e}\mathrm{e}\mathrm{n}\mathrm{e}=.\mathrm{d}.Bi-1$$5\mathrm{Q}\mathrm{F}\mathrm{A}\mathrm{s}$, which checks, say,or. Then either$B_{x-1}$ and, can detect it as follows. Recall thatand$M_{1}$$B_{i}$$M_{1}$$M_{2}$$M_{1}$$B_{i}$

splits into the $N$ paths each of which has amplitude

at different time.
Recall thatthrough $S_{1,N-1}$ are all rejecting states.
Hence, when the fastest path reaches there, the prob”
ability that)(foris observed is(for(for $s_{1,N-1}$ ))“,$2)|s_{1,2} \rangle+\cdots+\frac{1}{N}\exp(\frac{2\pi i}{N}j\cdot N)|S1,N\rangle)$$s_{11}$$( \sqrt{05}\frac{1}{N})^{2}$$+( \sqrt{05}\frac{1}{N})^{2}$$s_{1,2}$$+ \cdots+(\sqrt{05}\frac{1}{N})^{2}$$s_{1,1}$$=$)$\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}(N-1\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{m}\mathrm{p}1\mathrm{u}\mathrm{d})\cdot(\sqrt{05}\frac{1}{N,\mathrm{i}\mathrm{t}})^{2}=0.5\frac{N-1}{\mathrm{a}^{N^{2}}\mathrm{c}\mathrm{h}}.\mathrm{I}\mathrm{f}$$\mathrm{t}_{\mathrm{c}}\mathrm{o}$$\mathrm{e}_{\mathrm{c}}\tau s\mathrm{y}$2.2).

$\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h},\mathrm{r}\mathrm{e}\mathrm{a}\sqrt{05}/\sqrt{N}.\mathrm{A}\mathrm{s}\mathrm{d}\mathrm{e}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{n}1\mathrm{a}\mathrm{i}\mathrm{m}1,\mathrm{e}_{1}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{s}\sqrt{05}(\frac{\mathrm{i}\mathrm{b}1}{N}\exp(\frac{2\pi i\mathrm{C}}{N}j\cdot 1)|s_{1},\rangle+\frac{\mathrm{a}1}{N}\mathrm{p}l\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{t}\mathrm{h}\exp)(\frac{2\pi i\mathrm{e}j}{N}j\cdot$$‘(\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}$$\epsilon$$5\mathrm{Q}\mathrm{F}\mathrm{A}’ \mathrm{s}$$\mathrm{i}_{\mathrm{S}}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{b}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{V}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{e}\mathrm{d}\mathrm{e}\mathrm{d}$$\mathrm{r}\mathrm{n}\mathrm{e}\mathrm{o}\mathrm{f}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{p}’ \mathrm{a}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{C}\mathrm{t}$Reference[AF98] A. Ambainis and R. Freivalds, “1-way quantum
finite automata: strengths, weaknesses and generalizations,” Proceedings of the 39th IEEE Conference
on Foundations of Computer Science (to appear),1998.

path reaches the same point, the probability that “reject” is observed is thatthe power of[DS89] C. Dwork and L. Stockmeyer,
2-way probabilistic finite automata,” Proceedings ofthe 30th IEEE Conference on Foundations of Computer Science, 480-485, 1989.

.

[Fre81] R. Freivalds, “Probabilistic two-way machines,”
LNCS, 188, 33-45, 1981.

It then follows that the probability that “reject” is ob-[Gro96] L. Grover, “A fast quantum mechanical algorithm for database search,’) Proceedings of the 28th
ACM Symposium on Theory of Computing, 212219, 1996.

by$\sqrt{1-05\neq^{-}NN}^{1}$times. Therefore when the second fastest$(N-1) \cdot(\sqrt{05}\frac{\frac{1}{N}}{\sqrt{1-05\frac{N-1}{N^{2}}}})^{2}=0.5(\frac{N-1}{N^{2}-0.\mathrm{s}(N-1)})$$‘(\mathrm{O}\mathrm{n}$

.

205

[HU79] J. Hopcroft and J. Ullman, An Introductio ?
to Automata Theory, $La?1tj$ ?lages $a?7d$ Computation,
Addison-Wesley, 1979.
$\uparrow$[HU68] J. Hopcroft and J. Uilman,
Deterministic
stack automata and the quotient operator,’) JCSS,
2:1, 1-12, 1968.

$\emptyset\# p_{1}0p_{K}\# p_{2}00pK+1\#\cdots$$$\alpha$$V_{\sqrt}|q_{0}\rangle=\sqrt{04}|q1,0\rangle+\sqrt{04}|q2,0\rangle+\sqrt{02}|q_{0},rej\rangle$$V_{\neg}\mathrm{t}t\}|q_{0}\rangle=|q0,\mathrm{r}\mathrm{e}j\rangle$$V_{\#}|q_{1,0}\rangle=|q_{1,1})$[KW97] A. Kondacs and J. Watrous, (‘On the power ofquantum finite state automata,” Proceedings of the
38th IEEE Conference on Foundations of Computer
Science, 66-75, 1997.

$V_{\neg}|\mathrm{t}\#\}q_{1},0\rangle=|q1,0,rej\rangle$$V_{p_{1}}|q_{1,1}\rangle=|q_{1,2}\rangle$$V_{\neg}\{p_{1}\}|q_{1},1\rangle=|q_{1,1,\Gamma e_{j}}\rangle$$V_{0}|q_{1,2}\rangle=|q_{1,3}\rangle$[Min66] M. Minsky, Computation: Finite and infinite
machines, Prentice-Hall, 1966.
P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” Proceedmgs of the 35th IEEE Symposium on Foundationsof Computer Science, 124-134, 1994.

[Sho94]$V_{\neg}|i^{\mathrm{o}}\}q1,2\rangle=|q_{1,2,r\mathrm{e}j}\rangle$$V_{PK}|q_{1,3}\rangle=|q_{1,4}\rangle$$V_{\neg}|\{q_{1},3\rangle=|q_{1,3_{)}r\mathrm{e}j}\rangle$$V_{\#}|q_{1,4}\rangle=|q_{1},\mathrm{s}\rangle$$V_{\neg}|\{\#\}q_{1,4}\rangle=|q_{1,4,\Gamma \mathrm{e}j}\rangle$$V_{\mathrm{P}2}|q1,\mathrm{s}\rangle=|q_{1,6}\rangle$$V_{\neg}\{p_{2}\}|q_{1},5\rangle=|q1,5,r\mathrm{e}j\rangle$$\emptyset$\cdots$\# p_{x}000p_{\mathrm{s}}\# p_{y}000000_{p_{x}}\#\cdots$or$\emptyset$\cdots$$V_{0}|q1,6\rangle=|q_{1,7}\rangle$$\# Px000P*\# p_{K1}-000000p_{x}$#$$V_{\neg}|\{\mathrm{O}\}q_{1},6\rangle=|q1,6,\Gamma ej)$

$V_{0}|q_{1,7}\rangle=|q_{1,8}\rangle$

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)

$V_{\mathrm{P}x}|q_{1,St\Gamma t} \circ\rangle=\frac{1}{\sqrt{N}}\Sigma_{j=0}^{N}|r1,j,0,p_{x},1\rangle$$V_{\urcorner}|\{0\}q1,7\rangle=|q_{1,7,f\mathrm{e}_{\mathit{3}}}\rangle$$V_{\neg p.\}}|\mathrm{t}q_{1_{S}t},art\rangle=|q_{1,.\iota ar}.t,rej\rangle$$V_{0}|r_{1,j,x}0,p,1)=|r_{1,g,2j,\mathrm{P}x^{1}},\rangle$$V_{\neg}|\{p_{K+1}\}q1,8\rangle=|q1,8,r\mathrm{e}j\rangle$$V_{0}|r_{1_{J^{k}}},,,\mathrm{P}x^{1}’\rangle=|r_{1,j,kp}-1,x’ 1\rangle,$$(14-a)$$(14-b)$(15). $(16-a)$$(16-b)$$(17-a)$$(17-b)$(18)$(19-a)$$(19-b)$$1\leq k\leq 2j$$1\leq j\leq N$$V_{\#}|r_{1,j})= \frac{1}{\sqrt{N}}\Sigma_{l=1}^{N}\exp(\frac{2\pi i}{N}jl)|S_{1},\mathrm{t}\rangle,$$V_{\mathrm{P}}.|r_{1,j},0,\mathrm{p}_{x^{1}},\rangle=|r_{1,j,0_{\mathrm{p}_{x},2}}.\rangle$$V_{\neg}\{\mathfrak{g}\}|\gamma_{1,j}\rangle=|r_{1,j,rGj}\rangle$$V_{\mathrm{P}K+1}|r_{1},j,0,p_{x},1)=|r_{1,j,0,\mathrm{p}_{x^{2}}},\rangle$$V_{\#}|s_{1,N}\rangle=|q1,star\iota)$$V_{\neg}\{0_{p_{K+1^{p}}},,.\}|r_{1},j,0_{p},x’ 1\rangle=|r1,j,0_{\mathrm{P}x},,1,r\mathrm{e}j\rangle$$V_{1}|r_{1,j},0,\mathrm{p}x^{2}’\rangle=|r_{1,j,0_{\mathrm{p}x}},,3\rangle$.

$(10-a)$$(10-b)$

(11)
(12)
(13)

$V_{PK+1}|q_{1},8 \rangle=\frac{1}{\sqrt{N}}\Sigma_{j=1}^{N}|r_{1},j\rangle$$D(q_{1},:)=+1,0\leq i\leq 8$$V_{\neg}|\{\not\in\}r1,j,0,\mathrm{p}_{x^{2}},\rangle=|r_{1,j,\mathrm{p}_{x},r6\mathrm{j}}0,2,\rangle$$V_{\mathrm{P}y}|r_{1,j,0,px},3\rangle=|r_{1,j,0,\mathrm{p}_{x^{4}}},\rangle$(if $p_{y}\neq p_{K-1}$ )(if)$V_{\mathrm{P}K-1}|r_{1,j,0_{\mathrm{p}_{x}},3},\rangle=|r_{1,j,0_{p},\mathrm{s}},\rangle x$$\mathrm{P}y=\mathrm{P}K-1$$V_{\neg}|\{p_{y}\}r1,j,0,\mathrm{P}x^{3}’\rangle=|r_{1,j,,3,fe}0_{\mathrm{p}_{x},j}\rangle$:.

$V_{0}|r_{1,j,x}0_{\mathrm{P}f},,\rangle$$=|r_{1,j,j1,f}N-+p_{x},\rangle$$V_{\mathit{0}}|r_{1},j,\mathrm{k},px’ f\rangle=|r_{1,j,x}k-1,p,j\rangle,$$D(q1,|.,rej)=,$ $0$$D(r_{1,j})=+1,1\leq j\leq N$$D(r_{1_{\mathrm{J}^{r\mathrm{e}}},j},)=0$$D(s_{1,l}.)=0,1\leq l\leq N$, $f=4,5$$1\leq k\leq N-j+1$$D(q1_{S},taf\iota)=+1$$D(q0,rej)=0$$V_{p_{x}}|r_{1,j,0,p4}\rangle x’=|r_{1,j}\rangle$

Fig. 3$V_{p_{x}}|r_{1,j,x^{5}}0,P,\rangle=|r_{1,j,1})$$V_{\neg}\{0.px\}|r1,j,0,\mathrm{p}_{x},f\rangle=|r_{1,j,0,p,f^{\gamma eg}},\cdot\rangle x$$V_{\#}|r_{1,\mathrm{j}} \rangle=\frac{1}{\sqrt{N}}\Sigma_{\mathrm{t}=1}^{N}\exp(\frac{2\pi 1}{N}\hat{J}^{l})|S_{1},\iota\rangle,$$1\leq j\leq N$$V \mathfrak{g}|r1,j,1\rangle=\frac{1}{\sqrt{N}}\Sigma_{l=}^{N}1\exp(\frac{2\pi*}{N}jl)|t_{1,\iota}\rangle,$$t\cdots\# p_{K-}10\cdots 0_{p_{*}}\#$$1\leq j\leq N$$V_{\mathrm{P}K1}|-q1,start\rangle=|q1,9\rangle$$V_{\neg}|\mathrm{t}\#\}1,j\rangle r=|r_{1},j,\mathrm{r}\mathrm{e}j\rangle$$V_{\neg}\{p.\}|q_{1,St}a\mathrm{r}t\rangle=|q_{1}$$V_{\neg}\{\mathrm{t}\}|r1,j,1\rangle=|r1,j,1,r\mathrm{e}j\rangle$,start,$r\mathrm{e}j\rangle$$V_{0}|q_{1},\mathfrak{g}\rangle=|q_{1,9}\rangle$$V_{\#}|s_{1,N}\rangle=|q_{1,\mathit{8}tar\iota\rangle}$$V_{P_{*}}|q1,9\rangle=|q1,10\rangle$$V_{\}|t_{1},N\rangle=|q_{1,acc}\rangle$$V_{\urcorner}\{0,p.\}|q_{1,9}\rangle=|q1,9,r\mathrm{e}j\rangle$$V_{\neg}|\{}t_{1,N}\rangle=|t_{1,rer}\rangle$$V_{\#}|q_{1},10\rangle=|q_{1,11}\rangle$

(20)
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
(31)

$D(r_{1,j},0_{\mathrm{P}},x,m)=+1,1\leq m\leq 5$$D(r_{1,j,\mathit{0},\mathrm{e}j}r)\mathrm{p}_{x},m,=0^{\cdot}$$D(r_{1,j,,m}k_{\mathrm{P}x},)=0,$ $k\neq 0,$$D$$m=1,4,5$$V_{\neg}|\{\#\}q1,10\rangle=|q1,10,r\epsilon j\rangle$$V_{\}|q_{1,11}\rangle=|q1_{\mathfrak{l}}11,acc\rangle$$V_{\neg}|\mathrm{t}}q_{1},11)=|q1,10,r\mathrm{e}j\rangle$( ,start) $=+1$$q_{1}$$i=9,10,11$$t=9,10,11$$D(s_{1,1})=0,1\leq \mathrm{t}\leq N$$D(q_{1},.)=+1,$$D(t_{1,\iota)=+}1,1\leq l\leq N$$D(q_{1},|,rej)=0,$$D(r_{1,j})=+1,1\leq j\leq N$$D(q_{1,11,a\mathrm{c}c})=0$$D(r_{1,j,\mathrm{r}ej})=0$

Fig. 5$D(r_{1,j,1})=+1$$D(r_{1,j,1,\mathrm{r}}\mathrm{e}\mathrm{j})=0$$D(q_{1},aCC)=0$$D(t_{1,f}\mathrm{e}j)=0$

Fig. 4