<p>For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V_a$. Yet, it is not really <strong>meaningful</strong> to compute the <em>amplitudes</em> of the state to be measured over $|q_{0}⟩$ and $|q_{1}⟩$ and to put them on the diagram, for the automata does <em>neot</em> measure the projectors $|q_{0}⟩\langle q_{0}|$, and $|q_{1}⟩\langle q_{1}|$. In other words, this numbers do not represent probabilities, they do not correspond to outcomes of the measurement to be performed. Therefore, labeling the arrows of the diagram with this numbers would give a potentially-misleading illustration of how the measurement process is working. </p>

<p>Although I might say things you already know, let us elaborate on the topic a bit to clarify the meaning of the transition diagrams you depicted. It is important to highlight that after reading a symbol $a$ and applying $V_a$, the automata does <em>not</em> perform a measurement in the standard computational basis: $$\{|q_0⟩,|q_1⟩,|q_{acc}⟩,|q_{rej}⟩\}$$ Instead, the automata measures this complete set of orthogonal projectors:</p>

<ul>
<li>$P_{acc}=|q_{acc}⟩\langle q_{acc}|$</li>
<li>$P_{rej}=|q_{rej}⟩\langle q_{rej}|$</li>
<li>$P_{non}= |q_{0}⟩\langle q_{0}|+|q_{1}⟩\langle q_{1}|$</li>
</ul>

<p>In other words, the measurement has three possible outcomes: (<em>acc</em>) the automata measures an accepting state and halts; (<em>rej</em>) the automata measures a rejecting state and halts; (<em>non</em>) the automate measures something else, does not halt, and reads next symbol (non states for non-halting). </p>

<p>Now, this is a problem I see in your diagrams: if you had a state $(|q_{0}⟩+|q_{1}⟩)/2$ before some measurement, and you happened to obtain the outcome (non), the state would remain <strong>invariant</strong> after the measurement (just apply $P_{non}$ and check). Therefore, depicting the probability of transition to either $|q_{0}⟩$ or $|q_{1}⟩$ creates confusion.</p>

<p>Taking all said into account it is easy to follow the calculation given in your <a href="http://arxiv.org/abs/quant-ph/9802062" rel="nofollow">main reference</a>. In order to illustrate everything said, and, for completeness, I will quote it with here with some minor comments (though I added some modifications, I do not know whether this type of quoting is acceptable;  if its is <em>not</em>, please, let me know or edit the answer yourself):</p>

<blockquote>
  <p>The automaton starts in $|q_0\rangle$.</p>
  
  <ol>
  <li><p><strong>Read "a"</strong>.  $V_a$ is applied,
  giving $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle+
\frac{1}{\sqrt{2}} |q_{rej}\rangle$.
  This is observed. Two outcomes are possible. With probability
  $(1/\sqrt{2})^2=1/2$, a rejecting state is observed.
  Then, the superposition collapses to $|q_{rej}\rangle$,
  the word is rejected and the computation terminates.
  Otherwise (with probability $1/2$), a non-halting state is observed and the
  superposition collapses to $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$.
  In this case, the computation continues.</p></li>
  <li><p><strong>Read "a" again</strong>. A simple computation (we leave the details out) 
  shows that $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$ is mapped
  to itself by $V_a$.
  After that, a non-halting state is observed. (There are no
  accepting or rejecting states in this superposition.)</p></li>
  <li><p><strong>Read final symbol \$</strong>. The transformation $V_{\$}$ corresponding
  to the right endmarker $\$$ is done. It maps
  the superposition to $\frac{1}{2} |q_{rej}\rangle+\frac{1}{2} |q_{acc}\rangle$.
  This is observed. With probability $(1/2)^2=1/4$, the rejecting state $q_{rej}$
  is observed. With probability $1/4$, the accepting state $q_{acc}$ is observed.</p></li>
  </ol>
  
  <p>The total probability of accepting is $1/4$, the probability
  of rejecting is $1/2+1/4=3/4$.</p>
</blockquote>

CC BY-SA 3.0
2012-04-07T21:54:39.310Z
Ah terrific answer, thank you so much for taking the time to write it out in more explicit terms. Also, on a side note, is there any obvious way or perhaps previous reference that depicts a visual representation in a more accurate and non-misleading way? It seems that perhaps laying out the evolution in some type of a tree-like structure would allow a better illustration of the branching that occurs throughout the execution of the automata. Thanks again for your help.
Vincent Russo
CC BY-SA 3.0
2012-04-08T14:41:42.047Z
@VincentRusso: you can't really describe it in a tree-based manner. The very point is that there can be destructive interference between amplitudes on the various finite automaton 'states'; this being the principal difference between stochastic and quantum computation. The graphical depiction of the automaton isn't really misleading if you take quite seriously that it is describing amplitudes for vectors, rather than probabilistic transitions. Of course, for both quantum or stochastic automata, the model is actually about linear transformations, so the picture is mostly beside the point.
Niel de Beaudrap
CC BY-SA 3.0
2012-04-09T18:47:48.170Z
At the beginning of chapter 6 of [Kaye, Laflamme, Mosca's](http://www.amazon.com/Introduction-Quantum-Computing-Phillip-Kaye/dp/019857049X) there is a nice discussion about the differences between classical-probabilistic and quantum computation; the authors  illustrate the text with state-diagrams. They actually discuss that these diagrams are not entirely adequate to describe quantum-interference --as Niel de Beaudrap has pointed out and nicely explained--. I personally recommend this reference for further reading.
Juan Bermejo Vega
CC BY-SA 3.0
2012-04-04T12:21:53.573Z
2012-04-09T20:10:51.180Z
2012-04-09T20:10:51.180Z
Juan Bermejo Vega
<p>Juan Bermejo Vega has given an accurate summary of what is said in the original paper. I will give you a higher-level description.</p>

<p>I will recommend, in your case, to avoid thinking of the amplitudes as probabilities altogether. They are related to probabilities, but this is not especially helpful to think about for these finite automata. I suspect that things will be much clearer if you think of this as a slightly abstract recipe for transforming complex-valued vectors instead.</p>

<p>What vectors are we transforming? Well: suppose you have a finite automaton with <em>n</em> states. The automaton represents a (yes, probabilistic) model for transforming vectors, which at any time step may give rise to an accepting or rejecting decision.</p>

<ul>
<li>Define <em>n</em> axes (coefficients of the vectors being transformed). Label each axis with one of the labels of the states. In particular, there is an <strong>accept</strong> axis and a <strong>reject</strong> axis. Call this vector space $\mathcal H$. The vectors we will be transforming are unit vectors in $\mathcal H$, and the only probabilities we will ever consider have to do with the coefficients of the vectors along the accept or reject axes. </li>
<li>We have a collection of transformations $V_q : \mathcal H \to \mathcal H$ for each state <em>q</em>, such that $V_q^\dagger V_q = I$ (<em>i.e.</em>&nbsp;they are <strong>unitary</strong>). We also have an initial transformation $V_c$ (neglected in the example you describe; we have $V_c = I$ in that case) and a final transformation $V_\$$ which are also unitary.</li>
<li>We start with a vector $V_c\,\mathbf{\hat e}_1$, where $V_c$ is the initial transformation and $\mathbf{\hat e}_1$ is the unit vector in the direction of the axis of the first state ($q_0$ in your example). We then perform the following transformations for each letter:<br><br>
<ol>
<li>If the next letter to be read is $a$, we perform the transformation $V_a$ on the vector.</li>
<li>The resulting vector $\mathbf v$ might have coefficients $u_A$ along the accept axis, and $u_R$ along the reject axis. If so, we immediately accept with probability $|u_A|^2$ and reject with probability $|u_R|^2$.</li>
<li>If some of the other coefficients are non-zero, there is a probability that the computation continues; if it does so, we multiply the vector by a factor of $(1 - |u_A|^2 - |u_R|^2)^{-1/2}$, and  set the accept and reject coefficients to zero.</li>
<li>Proceed for the next letter.<br></li>
</ol></li>
<li>We perform these transformations for each letter of the word, and also for a terminating symbol \$ which we append to the end.</li>
</ul>

<p><em>The only time probabilities come into play is with the accepting and rejecting axis</em>. While this model of computation is obviously inspired by finite automata, it is simple not useful to interpret any of the other coefficients of the vector, at any point in time (even at the end!), as being probabilities.</p>

<p>Note that the accept and reject probabilities at each timestep are <em>conditional</em> probabilities, <em>i.e.</em>&nbsp;they depend on the computation not having yet halted; if you want to compute the total probability of acceptance/rejection, you can most easily do this by dispensing with the "renormalization" step in the evolution (the part where we multiply by the inverse-square-root value; but still setting the accept/reject coefficients to zero if the computation continues), and simply sum all of the probabilistic contributions to accepting/rejecting that arise along the way.</p>

CC BY-SA 3.0
2012-04-08T18:26:34.580Z
Niel, thank you again for your comment as well. It was very helpful to get a more intuitive picture of how this computation takes place. Thank you very much for taking the time to explain, it's much clearer to me now.
Vincent Russo
CC BY-SA 3.0
2012-04-04T15:41:46.960Z
2012-04-04T15:46:48.280Z
2012-04-04T15:46:48.280Z
Niel de Beaudrap
<p>You are incorrectly assuming that the state collapses fully (to a computational basis state) after reading each symbol. The measurement at each stage is only partial.</p>

CC BY-SA 3.0
2012-03-31T04:52:59.880Z
I was under the impression that since this is utilizing the "measure many" model that a measurement is performed on each step of the computation, which collapses the superposition to a definite probabilistic value.
Vincent Russo
CC BY-SA 3.0
2012-03-31T06:10:11.577Z
@Vincent Russo You are right that the state is measured for each symbol that is read.
funkstar
CC BY-SA 3.0
2012-04-02T09:05:06.333Z
I think that a QFA where the state of the automaton is measured after each step would be completely equivalent to a Markov Chain. So what would be the motivation to study them?
Shitikanth
CC BY-SA 3.0
2012-04-02T09:12:46.307Z
I had a look at the paper. The measurement that is done in each step is a partial measurement which only checks if the state is accepted, rejected or in a non-final state. So the state does not collapse fully. (The measurement is defined by the projectors $|q_{acc} \rangle \langle q_{acc}|,|q_{rej} \rangle \langle q_{rej}|, I - |q_{acc} \rangle \langle q_{acc}|-|q_{rej} \rangle \langle q_{rej}|$.)
Shitikanth
CC BY-SA 3.0
2012-04-02T14:58:01.540Z
Right, I understand the the partial measurement is only checking whether it is in an accepting, rejecting, or non-halting state now. I'm still a bit confused on what happens when the second $a$ is read, I'm not quite sure I see that the resulting superposition after reading the first $a$ ($\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$) is mapped to itself after reading the second (see my comment in the above post for further details on this). I'm sure I'm just messing up something fundamental here.
Vincent Russo
CC BY-SA 3.0
2012-04-03T23:47:28.333Z
First of all the state after reading the first $a$ with probability 1/2 will be $(\frac{1}{\sqrt 2} |q_0\rangle + \frac{1}{\sqrt 2} |q_1\rangle)$.
Shitikanth
CC BY-SA 3.0
2012-04-03T23:49:22.920Z
You can easily find the result of $V_a$ on $(\frac{1}{\sqrt 2} |q_0\rangle + \frac{1}{\sqrt 2} |q_1\rangle)$ by using the linearity of $V_a$. $V_a(\frac{1}{\sqrt 2} |q_0\rangle + \frac{1}{\sqrt 2} |q_1\rangle) = (\frac{1}{\sqrt 2} V_a|q_0\rangle + \frac{1}{\sqrt 2} V_a|q_1\rangle)$. Hope this settles your doubts.
Shitikanth
CC BY-SA 3.0
2012-04-04T14:54:01.493Z
I think this answer can create confusion as it is written. Whatever measurement scheme you use, there are always states that do not "collapse": in the case of a computational basis measurement, product-states do not collapse. What it is relevant here is that after reading every symbol and performing an unitary the automata *does* perform a measurement, and the quantum state may perfectly collapse.
Juan Bermejo Vega
CC BY-SA 3.0
2012-04-04T14:58:42.217Z
I only wanted to show why his "reworked automaton model" does not accurately describe the QFA system. This is, in fact, because the automaton does not fully collapse in the computational basis at each step.
Shitikanth
CC BY-SA 3.0
2012-04-04T15:01:38.467Z
In any case, I think that the question has already been answered sufficiently clearly. Let's not get lost in technicalities.
Shitikanth
CC BY-SA 3.0
2012-04-04T15:13:26.787Z
I totally agree with your last comments.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-30T21:12:04.033Z
2012-04-04T15:49:50.113Z
2012-04-04T15:49:50.113Z
Shitikanth
<p>I'm attempting to clarify my understanding in the example presented in Section 2.2 of <a href="http://arxiv.org/abs/quant-ph/9802062" rel="noreferrer">1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations</a> (this <a href="http://arxiv.org/abs/quant-ph/9904066" rel="noreferrer">alternative link</a> may also be useful). This example provides a very stripped down example of a 1-QFA with the following transition rules:</p>

<p>$V_a|q_0\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle$,</p>

<p>$V_a|q_1\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle$,</p>

<p>$V_{\$}|q_0\rangle = |q_{rej}\rangle$,</p>

<p>$V_{\$}|q_1\rangle = |q_{acc}\rangle$</p>

<p>For instance, if I'm in $q_0$ and I process an $a$ as input, I apply the first rule. My understanding is that I would have a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of staying in state $|q_0\rangle$, a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of progressing to state $|q_1\rangle$ and a $||\frac{1}{\sqrt 2}||^2 = \frac{1}{2}$ chance of ending the computation and rejecting the string.</p>

<p>I would imagine the automata for this to look like the following image</p>

<p><img src="https://i.sstatic.net/E2HKZ.png" alt="enter image description here"></p>

<p>I'm not entirely sure if that is correct however. The probabilities mentioned in the paper for acceptance of the string $aa$ is $\frac{1}{4}$ while the probability of rejection is $\frac{3}{4}$. Just wondering if someone could either point out a flaw or validate what I have conceptually in mind for the example.</p>

<p>Thanks. </p>

<p>Reworked automata model to more accurately reflect the probabilities:
<img src="https://i.sstatic.net/pkjmC.png" alt="enter image description here"></p>

CC BY-SA 3.0
2012-03-30T19:52:24.853Z
I suggest you look up "quantum superposition". It looks like you are interpreting it purely probabilisticly, which ignores the possibility of interference, which is central in quantum computing.
funkstar
CC BY-SA 3.0
2012-03-31T05:12:45.393Z
Well, I'm considering the state to be in a superposition upon each input. Given the input to the automata, it progresses to the next state based on the collapse of the superposition from measurement. This collapsed value obtained from the previous superposition serves as the weight for transition. For instance in step one, the probability to transition from $q_0$ to $q_{rej}$ is $||\frac{1}{\sqrt 2}||^2$. Each step of the computation induces a measurement.
Vincent Russo
CC BY-SA 3.0
2012-03-31T07:25:05.440Z
Note that the measurement is partial - it doesn't give you an exact state unless it is a final state. That way, you can do a (partial) measurement after applying a unitary transform corresponding to some symbol, and if it doesn't collapse to a final state then it will still be in a proper superposition, which leaves the possibility of interference open.
funkstar
CC BY-SA 3.0
2012-03-31T19:16:54.993Z
So just to be sure I understand:

1.)-- Read first $a$:
Reject string with probability $\frac{1}{2}$, otherwise state can be either in $q_0$ or $q_1$ and the superposition collapses to $\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$.

2.)-- For the second $a$ I'm a little unsure:

Since the state could be in either $|q_0\rangle$ or $|q_1\rangle$, both rules are applied to the current superposition I would assume as:
Vincent Russo
CC BY-SA 3.0
2012-03-31T19:17:33.917Z
$(\frac{1}{2}\langle q_0| + \frac{1}{2}\langle q_1|) (\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle) ((\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle))$
$ = (\frac{1}{4}\langle q_0 | q_0 \rangle + \frac{1}{4} \langle q_1 | q_1 \rangle) (\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle)$
$ = \frac{1}{8}|q_0\rangle + \frac{1}{8}|q_1\rangle $
Vincent Russo
CC BY-SA 3.0
2012-03-31T19:17:40.780Z
However, I think I'm missing something fundamental as this process should instead map to $\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$ as stated 
in step 2 of the paper. Thanks again for all of your help by the way, and I apologize for the long string of comments. If it's not clear, I can put it in the main question below if that helps.
Vincent Russo
CC BY-SA 3.0
2012-04-03T14:47:49.720Z
Also, I have another question about the automata visual. I've reworked it to be a bit more correct however I'd still think that the probability weightings are justified. My question is this: You read the first $a$ and you have a $\frac{1}{2}$ probability of rejecting and a $\frac{1}{2}$ probability of staying in a non-halting position (or in other words, $\frac{1}{4}$ chance of staying in $|q_0\rangle$ or $\frac{1}{4}$ chance of staying in $|q_1\rangle$. Since reading any # of a's maps to either non-halting state, the probability for being in either $|q_0\rangle$ or $|q_1\rangle$ is still 1/4
Vincent Russo
CC BY-SA 3.0
2012-04-03T14:51:08.090Z
It now also makes sense that at the end of the computation, accepting the string yields a $\frac{1}{4}$ chance, while rejecting the string yields a $\frac{1}{2}$ chance. The probabilities are basically a reflection of the superposition. I'm not sure if this is the most accurate way to reflect the automata visually however. Any feedback would be most helpful.
Vincent Russo
CC BY-SA 3.0
2012-04-03T18:20:46.620Z
Maybe reading the paper "Quantum complexity theory" by Bernstein and Vazirani answers your confusions. The relevant section is the one on "Quantum Turing Machines", which are just more general than finite automata.
Mahdi Cheraghchi
<fl.formal-languages><quantum-computing><automata-theory><grammars>
1-way Quantum Finite Automata Example Question
Vincent Russo
# 1-way Quantum Finite Automata Example Question

(Asked by: username_0 on 2012-03-30)

I'm attempting to clarify my understanding in the example presented in Section 2.2 of [1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations](http://arxiv.org/abs/quant-ph/9802062) (this [alternative link](http://arxiv.org/abs/quant-ph/9904066) may also be useful). This example provides a very stripped down example of a 1-QFA with the following transition rules:

$V\_a|q\_0\rangle = \frac{1}{2}|q\_0\rangle + \frac{1}{2}|q\_1\rangle + \frac{1}{\sqrt 2}|q\_{rej}\rangle$,

$V\_a|q\_1\rangle = \frac{1}{2}|q\_0\rangle + \frac{1}{2}|q\_1\rangle - \frac{1}{\sqrt 2}|q\_{rej}\rangle$,

$V\_{\$}|q\_0\rangle = |q\_{rej}\rangle$,

$V\_{\$}|q\_1\rangle = |q\_{acc}\rangle$

For instance, if I'm in $q\_0$ and I process an $a$ as input, I apply the first rule. My understanding is that I would have a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of staying in state $|q\_0\rangle$, a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of progressing to state $|q\_1\rangle$ and a $||\frac{1}{\sqrt 2}||^2 = \frac{1}{2}$ chance of ending the computation and rejecting the string.

I would imagine the automata for this to look like the following image

![enter image description here](https://i.sstatic.net/E2HKZ.png)

I'm not entirely sure if that is correct however. The probabilities mentioned in the paper for acceptance of the string $aa$ is $\frac{1}{4}$ while the probability of rejection is $\frac{3}{4}$. Just wondering if someone could either point out a flaw or validate what I have conceptually in mind for the example.

Thanks.

Reworked automata model to more accurately reflect the probabilities:
![enter image description here](https://i.sstatic.net/pkjmC.png)

**Tags:** fl.formal-languages, quantum-computing, automata-theory, grammars
> **Comments:**
> **username_1**: I suggest you look up "quantum superposition". It looks like you are interpreting it purely probabilisticly, which ignores the possibility of interference, which is central in quantum computing.  
> **username_0**: Well, I'm considering the state to be in a superposition upon each input. Given the input to the automata, it progresses to the next state based on the collapse of the superposition from measurement. This collapsed value obtained from the previous superposition serves as the weight for transition. For instance in step one, the probability to transition from $q_0$ to $q_{rej}$ is $||\frac{1}{\sqrt 2}||^2$. Each step of the computation induces a measurement.  
> **username_1**: Note that the measurement is partial - it doesn't give you an exact state unless it is a final state. That way, you can do a (partial) measurement after applying a unitary transform corresponding to some symbol, and if it doesn't collapse to a final state then it will still be in a proper superposition, which leaves the possibility of interference open.  
> **username_0**: So just to be sure I understand:  1.)-- Read first $a$: Reject string with probability $\frac{1}{2}$, otherwise state can be either in $q_0$ or $q_1$ and the superposition collapses to $\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$.  2.)-- For the second $a$ I'm a little unsure:  Since the state could be in either $|q_0\rangle$ or $|q_1\rangle$, both rules are applied to the current superposition I would assume as:  
> **username_0**: $(\frac{1}{2}\langle q_0| + \frac{1}{2}\langle q_1|) (\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle) ((\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle))$ $ = (\frac{1}{4}\langle q_0 | q_0 \rangle + \frac{1}{4} \langle q_1 | q_1 \rangle) (\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle)$ $ = \frac{1}{8}|q_0\rangle + \frac{1}{8}|q_1\rangle $  
> **username_0**: However, I think I'm missing something fundamental as this process should instead map to $\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$ as stated  in step 2 of the paper. Thanks again for all of your help by the way, and I apologize for the long string of comments. If it's not clear, I can put it in the main question below if that helps.  
> **username_0**: Also, I have another question about the automata visual. I've reworked it to be a bit more correct however I'd still think that the probability weightings are justified. My question is this: You read the first $a$ and you have a $\frac{1}{2}$ probability of rejecting and a $\frac{1}{2}$ probability of staying in a non-halting position (or in other words, $\frac{1}{4}$ chance of staying in $|q_0\rangle$ or $\frac{1}{4}$ chance of staying in $|q_1\rangle$. Since reading any # of a's maps to either non-halting state, the probability for being in either $|q_0\rangle$ or $|q_1\rangle$ is still 1/4  
> **username_0**: It now also makes sense that at the end of the computation, accepting the string yields a $\frac{1}{4}$ chance, while rejecting the string yields a $\frac{1}{2}$ chance. The probabilities are basically a reflection of the superposition. I'm not sure if this is the most accurate way to reflect the automata visually however. Any feedback would be most helpful.  
> **username_2**: Maybe reading the paper "Quantum complexity theory" by Bernstein and Vazirani answers your confusions. The relevant section is the one on "Quantum Turing Machines", which are just more general than finite automata.  

---

## 3 answers

### Answer by username_3 on 2012-04-04. Score: 5 | Accepted answer

For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V\_a$. Yet, it is not really **meaningful** to compute the *amplitudes* of the state to be measured over $|q\_{0}⟩$ and $|q\_{1}⟩$ and to put them on the diagram, for the automata does *neot* measure the projectors $|q\_{0}⟩\langle q\_{0}|$, and $|q\_{1}⟩\langle q\_{1}|$. In other words, this numbers do not represent probabilities, they do not correspond to outcomes of the measurement to be performed. Therefore, labeling the arrows of the diagram with this numbers would give a potentially-misleading illustration of how the measurement process is working.

Although I might say things you already know, let us elaborate on the topic a bit to clarify the meaning of the transition diagrams you depicted. It is important to highlight that after reading a symbol $a$ and applying $V\_a$, the automata does *not* perform a measurement in the standard computational basis: $$\{|q\_0⟩,|q\_1⟩,|q\_{acc}⟩,|q\_{rej}⟩\}$$ Instead, the automata measures this complete set of orthogonal projectors:

* $P\_{acc}=|q\_{acc}⟩\langle q\_{acc}|$
* $P\_{rej}=|q\_{rej}⟩\langle q\_{rej}|$
* $P\_{non}= |q\_{0}⟩\langle q\_{0}|+|q\_{1}⟩\langle q\_{1}|$

In other words, the measurement has three possible outcomes: (*acc*) the automata measures an accepting state and halts; (*rej*) the automata measures a rejecting state and halts; (*non*) the automate measures something else, does not halt, and reads next symbol (non states for non-halting).

Now, this is a problem I see in your diagrams: if you had a state $(|q\_{0}⟩+|q\_{1}⟩)/2$ before some measurement, and you happened to obtain the outcome (non), the state would remain **invariant** after the measurement (just apply $P\_{non}$ and check). Therefore, depicting the probability of transition to either $|q\_{0}⟩$ or $|q\_{1}⟩$ creates confusion.

Taking all said into account it is easy to follow the calculation given in your [main reference](http://arxiv.org/abs/quant-ph/9802062). In order to illustrate everything said, and, for completeness, I will quote it with here with some minor comments (though I added some modifications, I do not know whether this type of quoting is acceptable; if its is *not*, please, let me know or edit the answer yourself):

> The automaton starts in $|q\_0\rangle$.
>
> 1. **Read "a"**. $V\_a$ is applied,
>    giving $\frac{1}{2} |q\_0\rangle+\frac{1}{2} |q\_1\rangle+
>    \frac{1}{\sqrt{2}} |q\_{rej}\rangle$.
>    This is observed. Two outcomes are possible. With probability
>    $(1/\sqrt{2})^2=1/2$, a rejecting state is observed.
>    Then, the superposition collapses to $|q\_{rej}\rangle$,
>    the word is rejected and the computation terminates.
>    Otherwise (with probability $1/2$), a non-halting state is observed and the
>    superposition collapses to $\frac{1}{2} |q\_0\rangle+\frac{1}{2} |q\_1\rangle$.
>    In this case, the computation continues.
> 2. **Read "a" again**. A simple computation (we leave the details out)
>    shows that $\frac{1}{2} |q\_0\rangle+\frac{1}{2} |q\_1\rangle$ is mapped
>    to itself by $V\_a$.
>    After that, a non-halting state is observed. (There are no
>    accepting or rejecting states in this superposition.)
> 3. **Read final symbol \$**. The transformation $V\_{\$}$ corresponding
>    to the right endmarker $\$$ is done. It maps
>    the superposition to $\frac{1}{2} |q\_{rej}\rangle+\frac{1}{2} |q\_{acc}\rangle$.
>    This is observed. With probability $(1/2)^2=1/4$, the rejecting state $q\_{rej}$
>    is observed. With probability $1/4$, the accepting state $q\_{acc}$ is observed.
>
> The total probability of accepting is $1/4$, the probability
> of rejecting is $1/2+1/4=3/4$.

> **Comments:**
> **username_0**: Ah terrific answer, thank you so much for taking the time to write it out in more explicit terms. Also, on a side note, is there any obvious way or perhaps previous reference that depicts a visual representation in a more accurate and non-misleading way? It seems that perhaps laying out the evolution in some type of a tree-like structure would allow a better illustration of the branching that occurs throughout the execution of the automata. Thanks again for your help.  
> **username_4**: @VincentRusso: you can't really describe it in a tree-based manner. The very point is that there can be destructive interference between amplitudes on the various finite automaton 'states'; this being the principal difference between stochastic and quantum computation. The graphical depiction of the automaton isn't really misleading if you take quite seriously that it is describing amplitudes for vectors, rather than probabilistic transitions. Of course, for both quantum or stochastic automata, the model is actually about linear transformations, so the picture is mostly beside the point.  
> **username_3**: At the beginning of chapter 6 of [Kaye, Laflamme, Mosca's](http://www.amazon.com/Introduction-Quantum-Computing-Phillip-Kaye/dp/019857049X) there is a nice discussion about the differences between classical-probabilistic and quantum computation; the authors  illustrate the text with state-diagrams. They actually discuss that these diagrams are not entirely adequate to describe quantum-interference --as Niel de Beaudrap has pointed out and nicely explained--. I personally recommend this reference for further reading.  

---

### Answer by username_4 on 2012-04-04. Score: 5

Juan Bermejo Vega has given an accurate summary of what is said in the original paper. I will give you a higher-level description.

I will recommend, in your case, to avoid thinking of the amplitudes as probabilities altogether. They are related to probabilities, but this is not especially helpful to think about for these finite automata. I suspect that things will be much clearer if you think of this as a slightly abstract recipe for transforming complex-valued vectors instead.

What vectors are we transforming? Well: suppose you have a finite automaton with *n* states. The automaton represents a (yes, probabilistic) model for transforming vectors, which at any time step may give rise to an accepting or rejecting decision.

* Define *n* axes (coefficients of the vectors being transformed). Label each axis with one of the labels of the states. In particular, there is an **accept** axis and a **reject** axis. Call this vector space $\mathcal H$. The vectors we will be transforming are unit vectors in $\mathcal H$, and the only probabilities we will ever consider have to do with the coefficients of the vectors along the accept or reject axes.
* We have a collection of transformations $V\_q : \mathcal H \to \mathcal H$ for each state *q*, such that $V\_q^\dagger V\_q = I$ (*i.e.* they are **unitary**). We also have an initial transformation $V\_c$ (neglected in the example you describe; we have $V\_c = I$ in that case) and a final transformation $V\_\$$ which are also unitary.
* We start with a vector $V\_c\,\mathbf{\hat e}\_1$, where $V\_c$ is the initial transformation and $\mathbf{\hat e}\_1$ is the unit vector in the direction of the axis of the first state ($q\_0$ in your example). We then perform the following transformations for each letter:  
    
  1. If the next letter to be read is $a$, we perform the transformation $V\_a$ on the vector.
  2. The resulting vector $\mathbf v$ might have coefficients $u\_A$ along the accept axis, and $u\_R$ along the reject axis. If so, we immediately accept with probability $|u\_A|^2$ and reject with probability $|u\_R|^2$.
  3. If some of the other coefficients are non-zero, there is a probability that the computation continues; if it does so, we multiply the vector by a factor of $(1 - |u\_A|^2 - |u\_R|^2)^{-1/2}$, and set the accept and reject coefficients to zero.
  4. Proceed for the next letter.
* We perform these transformations for each letter of the word, and also for a terminating symbol \$ which we append to the end.

*The only time probabilities come into play is with the accepting and rejecting axis*. While this model of computation is obviously inspired by finite automata, it is simple not useful to interpret any of the other coefficients of the vector, at any point in time (even at the end!), as being probabilities.

Note that the accept and reject probabilities at each timestep are *conditional* probabilities, *i.e.* they depend on the computation not having yet halted; if you want to compute the total probability of acceptance/rejection, you can most easily do this by dispensing with the "renormalization" step in the evolution (the part where we multiply by the inverse-square-root value; but still setting the accept/reject coefficients to zero if the computation continues), and simply sum all of the probabilistic contributions to accepting/rejecting that arise along the way.

> **Comments:**
> **username_0**: Niel, thank you again for your comment as well. It was very helpful to get a more intuitive picture of how this computation takes place. Thank you very much for taking the time to explain, it's much clearer to me now.  

---

### Answer by username_5 on 2012-03-30. Score: 3

You are incorrectly assuming that the state collapses fully (to a computational basis state) after reading each symbol. The measurement at each stage is only partial.

> **Comments:**
> **username_0**: I was under the impression that since this is utilizing the "measure many" model that a measurement is performed on each step of the computation, which collapses the superposition to a definite probabilistic value.  
> **username_1**: @Vincent Russo You are right that the state is measured for each symbol that is read.  
> **username_5**: I think that a QFA where the state of the automaton is measured after each step would be completely equivalent to a Markov Chain. So what would be the motivation to study them?  
> **username_5**: I had a look at the paper. The measurement that is done in each step is a partial measurement which only checks if the state is accepted, rejected or in a non-final state. So the state does not collapse fully. (The measurement is defined by the projectors $|q_{acc} \rangle \langle q_{acc}|,|q_{rej} \rangle \langle q_{rej}|, I - |q_{acc} \rangle \langle q_{acc}|-|q_{rej} \rangle \langle q_{rej}|$.)  
> **username_0**: Right, I understand the the partial measurement is only checking whether it is in an accepting, rejecting, or non-halting state now. I'm still a bit confused on what happens when the second $a$ is read, I'm not quite sure I see that the resulting superposition after reading the first $a$ ($\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$) is mapped to itself after reading the second (see my comment in the above post for further details on this). I'm sure I'm just messing up something fundamental here.  
> **username_5**: First of all the state after reading the first $a$ with probability 1/2 will be $(\frac{1}{\sqrt 2} |q_0\rangle + \frac{1}{\sqrt 2} |q_1\rangle)$.  
> **username_5**: You can easily find the result of $V_a$ on $(\frac{1}{\sqrt 2} |q_0\rangle + \frac{1}{\sqrt 2} |q_1\rangle)$ by using the linearity of $V_a$. $V_a(\frac{1}{\sqrt 2} |q_0\rangle + \frac{1}{\sqrt 2} |q_1\rangle) = (\frac{1}{\sqrt 2} V_a|q_0\rangle + \frac{1}{\sqrt 2} V_a|q_1\rangle)$. Hope this settles your doubts.  
> **username_3**: I think this answer can create confusion as it is written. Whatever measurement scheme you use, there are always states that do not "collapse": in the case of a computational basis measurement, product-states do not collapse. What it is relevant here is that after reading every symbol and performing an unitary the automata *does* perform a measurement, and the quantum state may perfectly collapse.  
> **username_5**: I only wanted to show why his "reworked automaton model" does not accurately describe the QFA system. This is, in fact, because the automaton does not fully collapse in the computational basis at each step.  
> **username_5**: In any case, I think that the question has already been answered sufficiently clearly. Let's not get lost in technicalities.  
> **username_3**: I totally agree with your last comments.  

---

