# Dependent corrections in measurement-based Universal Blind Quantum Computation

In Universal Blind Quantum Computation the autors describe a measurement-based protocol which allows an almost classical user to perform arbitrary computations on a quantum server without revealing almost anything about the content of the computation.

In the protocol description, the authors mention "dependency sets" associated to each qubit, which are supposed to be calculated by some method described in Determinism in the one-way model

However, it's not clear to me from reading the paper how these set are computed.

Can somebody help to clarify this issue?

Sure. The dependency sets arise from 'flow', which is indeed described in the paper you link to. This is, however, perhaps overkill for what we need.

The idea behind the corrections is to insure that the same effective operator is applied independent of which branch you find yourself in after making a measurement. To do this in principle is fairly simple. Since all the measurements we make are in the XY plane, obtaining a 1 as the measurement outcome for a particular qubit $q$ of state $| \psi \rangle$ yields the same final state as as obtaining a 0 for the same measurement of the same qubit on a state $Z_q | \psi \rangle$. Thus to correct for obtaining a 1 rather than a 0 it is sufficient to find an operator $C$ on the output state such that $Z_q \otimes C | \psi \rangle = | \psi \rangle$.

Now, this implies that $Z_q \otimes C$ is a stabilizer of the initial state. A stabilizer for a state is simply an operator which has that state as an eigenvector with corresponding eigenvalue $+1$.

As it turns out, it is extremely easy to enumerate the generators of the stabilizer group for any graph: For every vertex $v$ in graph $G$ the operator $X_v \prod_{i\in\mbox{nbgh{v}}} Z_i$ is a stabilizer of the graph state, where $\mbox{nbgh{v}}$ denotes neighbours of $v$ in $G$. Thus in order to find the correction for the measured qubit it we can simply pick the stabilizer corresponding to a qubit neighbouring $q$ and multiply it by $Z_q$. This gives a set of $X$ and $Z$ corrections which, when applied to the output state, yield a state equal to the output of the process had the measurement result been inverted.

We need one further requirement, which is that the correction set be in the future of $q$ (i.e. have not yet been measured). This obviously places restrictions on which neighbour of $q$ we choose. In the case of the brickwork state we introduce, this is satisfied uniquely by choosing $v$ to be neighbour of $q$ which is in the same row as $q$ but the next column on. This may sound arbitrary,but as it turns out, this is the unique choice satisfying the conditions I mentioned.

EDITED TO NOTE: You can propagate forward $Z$ corrections by applying the above procedure recursively, so that corrections on any qubit which is to be measured will be $X$ corrections. Whether or not an $X$ correction needs to be made to a particular qubit will then depend on the parity of the measurements for all qubits for which the correcting operator contains an $X$ at this location. To work out this set it is easiest to work the other way around: Simply calculate the correction operators for each vertex propagating all the $Z$ operators to the output qubits, and then once you have these operators work out which measurements alter the measurement at a given site.
• @user1749: For measurement based computation this is essentially correct, though often people like to shift all the $Z$ operators to the output, which entails using $X$ operators on more than one qubit. In our protocol, Alice doesn't actually apply an $X$ correction, but rather modifies the angle of measurement of the qubit (which is equivalent). Rather than coding up a full blind QC simulator straight off, it might be better to simulating a simple measurement based computation first. There is really nothing unique about our use of flow. Nov 10 '10 at 11:08