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?


1 Answer 1


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.

  • $\begingroup$ Thanks.So if I understood correctly, after each measurement, Alice "decrypts" the outcome bit with her random key bits, then $\endgroup$ Nov 10, 2010 at 10:40
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 10, 2010 at 11:08
  • 2
    $\begingroup$ Dan Browne and Hans Briegel wrote an excellent introduction to MBQC (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. $\endgroup$ Nov 10, 2010 at 11:14
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 2, 2010 at 11:42
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 4, 2010 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.