<p>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.</p>

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

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

<p>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.</p>

<p>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.</p>

<p>Hopefully this answers your question.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-01T14:46:54.820Z
Is it also possible to propagate forward the X corrections?
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-12-02T11:42:53.053Z
No, you have to absorb X corrections by flipping the angle of measurement of that qubit. This is because you can think of the XY-plane measurements as a Z-rotation followed by an X measurement. As X anti commutes with Z, this flips the sign of the angle of rotation, and since X commutes with an X measurement, this is all you need to do. This is the reason for the partial time ordering on measurements in MBQC: you need to make sure all qubits which will require the measurement angle to be adapted according to the measurement result of a particular qubit must be measured after that qubit.
Joe Fitzsimons
CC BY-SA 2.5
2010-12-02T15:57:54.373Z
I mean, is it possible to propagate forward the X corrections while keeping Z corrections in place?
If I understand correctly, the same stabilizer generators can be used to obtain stabilizer operators for all Pauli operators.
Obviously it is not possible to propagate forward both X and Z corrections at the same time, unless the algorithm is completely parallelizable.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-12-04T11:10:21.593Z
The short answer is no. In graph states X only appears in standard generators of the stabilizer once for each vertex, making it impossible to multiply generators to cancel out a specific X.So you can't do it in general. Z operators appear multiple times for each vertex, and hence such cancelation is often possible. This gives rise to flow and g-flow. Obviously you could simply apply a Hadamard to every qubit in the graph state, which would interchange Z and X, but I guess this is not what you want. None of this is specific to our protocol but is a common feature of all graph state computation.
Joe Fitzsimons
CC BY-SA 2.5
2010-12-04T23:23:18.397Z
Thanks. Is it still possible to perform computation using XY-plane measurements starting from a state where all qubits have been multiplied by a Hadamard?
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-12-06T20:39:26.733Z
No, not on the same graph.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-10T10:40:23.190Z
Thanks.So if I understood correctly, after each measurement, Alice "decrypts" the outcome bit with her random key bits, then
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-11-10T10:56:25.983Z
- checks whether the result is 0 or 1. If it is 0 she does nothing, otherwise she modifies the measurement angle for the qubits in next columns: one X correction to the qubit in the same row and next column, and one Z correction to all its neighbors (except the ones we have already measured). Is this correct? Are there any examples of transformations of a simple circuit in a UBQC pattern with corresponding execution traces? (I was thinking of coding a simulator)
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-11-10T11:08:53.760Z
@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.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-10T11:14:24.463Z
Dan Browne and Hans Briegel wrote an excellent introduction to MBQC (http://arxiv.org/abs/quant-ph/0603226), which has a far more explicit treatment of these ideas than our paper (which is probably quite mysterious if you haven't used MBQC before). What we do with our 'brickwork' state is just a simple MBQC, which for technical reasons couldn't be done on a square lattice. It might be easiest to implement a straightforward MBQC first, and then add the crypto on top once it is all working.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-10T11:17:55.557Z
Also, feel free to email me if you have questions about any of the details of our protocol, as I may not always see questions posted here (my email address is on my website, linked to from my profile).
Joe Fitzsimons
CC BY-SA 2.5
2010-11-10T03:49:59.573Z
2010-11-10T05:42:40.137Z
2010-11-10T05:42:40.137Z
Joe Fitzsimons
<p>In <a href="http://arxiv.org/abs/0807.4154">Universal Blind Quantum Computation</a> 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.</p>

<p>In the protocol description, the authors mention "dependency sets" associated to each qubit, which are supposed to be calculated by some method described in <a href="http://www.pps.jussieu.fr/~danos/pdf/flow.pdf">Determinism in the one-way model</a></p>

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

<p>Can somebody help to clarify this issue?</p>

<quantum-computing><cr.crypto-security>
Dependent corrections in measurement-based Universal Blind Quantum Computation
Antonio Valerio Miceli-Barone
# Dependent corrections in measurement-based Universal Blind Quantum Computation

(Asked by: username_0 on 2010-11-09)

In [Universal Blind Quantum Computation](http://arxiv.org/abs/0807.4154) 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](http://www.pps.jussieu.fr/~danos/pdf/flow.pdf)

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

Can somebody help to clarify this issue?

**Tags:** quantum-computing, cr.crypto-security


---

## 1 answers

### Answer by username_1 on 2010-11-10. Score: 9 | Accepted answer

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.

Hopefully this answers your question.

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.

> **Comments:**
> **username_0**: Thanks.So if I understood correctly, after each measurement, Alice "decrypts" the outcome bit with her random key bits, then  
> **username_0**: - checks whether the result is 0 or 1. If it is 0 she does nothing, otherwise she modifies the measurement angle for the qubits in next columns: one X correction to the qubit in the same row and next column, and one Z correction to all its neighbors (except the ones we have already measured). Is this correct? Are there any examples of transformations of a simple circuit in a UBQC pattern with corresponding execution traces? (I was thinking of coding a simulator)  
> **username_1**: @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.  
> **username_1**: Dan Browne and Hans Briegel wrote an excellent introduction to MBQC (http://arxiv.org/abs/quant-ph/0603226), which has a far more explicit treatment of these ideas than our paper (which is probably quite mysterious if you haven't used MBQC before). What we do with our 'brickwork' state is just a simple MBQC, which for technical reasons couldn't be done on a square lattice. It might be easiest to implement a straightforward MBQC first, and then add the crypto on top once it is all working.  
> **username_1**: Also, feel free to email me if you have questions about any of the details of our protocol, as I may not always see questions posted here (my email address is on my website, linked to from my profile).  
> **username_0**: Is it also possible to propagate forward the X corrections?  
> **username_1**: No, you have to absorb X corrections by flipping the angle of measurement of that qubit. This is because you can think of the XY-plane measurements as a Z-rotation followed by an X measurement. As X anti commutes with Z, this flips the sign of the angle of rotation, and since X commutes with an X measurement, this is all you need to do. This is the reason for the partial time ordering on measurements in MBQC: you need to make sure all qubits which will require the measurement angle to be adapted according to the measurement result of a particular qubit must be measured after that qubit.  
> **username_0**: I mean, is it possible to propagate forward the X corrections while keeping Z corrections in place? If I understand correctly, the same stabilizer generators can be used to obtain stabilizer operators for all Pauli operators. Obviously it is not possible to propagate forward both X and Z corrections at the same time, unless the algorithm is completely parallelizable.  
> **username_1**: The short answer is no. In graph states X only appears in standard generators of the stabilizer once for each vertex, making it impossible to multiply generators to cancel out a specific X.So you can't do it in general. Z operators appear multiple times for each vertex, and hence such cancelation is often possible. This gives rise to flow and g-flow. Obviously you could simply apply a Hadamard to every qubit in the graph state, which would interchange Z and X, but I guess this is not what you want. None of this is specific to our protocol but is a common feature of all graph state computation.  
> **username_0**: Thanks. Is it still possible to perform computation using XY-plane measurements starting from a state where all qubits have been multiplied by a Hadamard?  
> **username_1**: No, not on the same graph.  

---

