measurement order in cluster states
I should have included a link to this paper by Michael Nielsen in my previous post. It's a more introductory paper, perhaps easier to follow. It also includes a review of the quantum circuit model that's good.
I wanted to discuss measurement order more in the last post, but it had gotten too long. Somewhere in your cluster state are qubits that are your "output" qubits. If you've simply followed the most straightforward method of mapping your circuit to the cluster state, they will be on the right-hand edge.
A fascinating fact: your output qubits are among the first to be measured! They go down in the first round, and you get back the answer to your computation. Viola! Done in one time step!
Well, not quite. The numbers you got back are related to the answer you want, but you don't yet know how they are related. Essentially, what you have is the answer, but encrypted. As you perform other measurements, you learn more information. You keep that data, and perform various bit flips on that data based on measurement outcomes. Eventually, your answer is "decrypted".
I wonder, idly, if you could use this as a form of quantum network security. Start with a big cluster state, send half to your partner. Now neither of you can do anything without the other. Probably theoretically possible, but not practically interesting.