1-way Quantum Finite Automata Example Question 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 (this alternative link 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



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:
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. 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$.
  
  
  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.
  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.)
  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$.