1-way Quantum Finite Automata Example Question

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:

Answer 1

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

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

Answer 2

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.

Answer 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.