Cross-posted from my personal blog.

Since I have a new paper out today in Science, which seems to have attracted the interest of a fair number of non-physicists, I thought I would take the time to explain the paper: what it is we do, and the background behind it.

The paper itself is an experimental implementation of a cryptographic scheme designed to allow a user to run a calculation on a remote computer (server) in such a way that the users input, the operations performed and the output all remain hidden from the server. In our case we care about running a computation where the remote computer is a quantum computer, but the user has access to a much more limited machine. With that in mind, I thought I might first explain the protocol before talking about the experiments themselves.

The current experiments are based on Universal Blind Quantum Computing, a protocol proposed by Anne Broadbent, Elham Kashefi and myself a few years ago (illustrated above).

In quantum computing, the basic unit of information is the quantum bit (or qubit for short). This is exactly the structure you get if you take a classical bit, which can be 0 or 1, and try to represent it as a quantum system. Quantum mechanics allows for a systems to exist in superposition. This is essentially a class of non-classical states which exists in between classical states. This means that the qubit can exist in various superpositions of 0 and 1 at the same time. Each quantum state is can be described in terms of classical states, associating two numbers with each: an absolute amplitude (between 0 and 1) which when squared gives you the probability of finding obtaining that classical state when you measure the system, and a complex phase which governs interference effects. As it turns out, this means that we can represent the state of an (unentangled) qubit very simply, as simply the point on the surface of a sphere, known as a Bloch sphere (see below).

The classical states 0 and 1 are the top point and bottom point of the sphere, while the other states are in superposition. The lower down you go, the higher the probability of obtaining a 1 instead of a 0, with the points around the equator representing states where there is an equal probability of measuring 0 or 1.

Since we imagine this in 3 dimensional space, it makes sense to assign an X, Y and Z axis to the ball. By convention, we take the Z axis to pass through both 0 and 1, and to put the point (0,0,0) at the centre of the ball. This gives us a very easy way to visualise the basic operations of quantum computing which can be performed on a single qubit: they are simply rotations of the ball, and indeed it turns out that it is enough to consider rotations about only the X, Y and Z axes. If you can do these, you can make any more complex operation as a sequence of (3) rotations about these axes. These operations are basically a generalisation of the NOT operation a classical computer can perform, which takes 0 to 1 and 1 to 0.

As with a classical computer, we also need some way to affect one qubit dependent on the state of another qubit. As it turns out, an operation called a CZ gate is sufficient for this. The CZ gate rotates one qubit 180 degrees about the Z axis if the other qubit is in state 1, and does nothing if it is in state 0. Conveniently, this gate is symmetric, so it has exactly the same net effect independent of which qubit you designate to be rotated.

The way our protocol works is based heavily on a result which says that you can perform any computation (classical or quantum) in the following way:

1. Prepare a sufficiently large number of qubits in the state which lies on the equator of the Bloch sphere (which specifies its absolute amplitudes) and has phase +1. I will refer to this as the + state, since in the notation most physicists use it is written as \[\frac{1}{\sqrt{2}}\mid 0 \rangle + \frac{1}{\sqrt{2}}\mid 1 \rangle\]
2. Arrange the qubits into a regular 2D lattice (such as a square grid).
3. For every qubit i in order:

• Rotate i about the Z axis by some angle which depends on exactly which gate you want to perform. Note that this angle can depend on the previous measurement result.
• Rotate i 90 degrees about the Y axis.
• Measure whether i is 0 or 1.

We noticed that if Z rotations before and after the CZ operations have exactly the same effect, and that a Z rotation before the CZ is identical to simply preparing some other state chosen from the equator of the Bloch sphere. The idea is then to get the server to do all off the hard parts: applying the CZ gates, doing the Z rotations and making measurements, while the client only does the easy parts: computing the angle for the measurement in each round, and preparing single qubits (this last part may seem like a physically hard operation to perform, but in fact the client needs little more than a very weak laser and a pair of 3D glasses from the cinema to accomplish this if the server is sufficiently powerful).

If you look at the list of operations that the server is expected to perform, only the Z rotations actually depend on the computation being performed. This is because it is possible to choose a fixed arrangement for the qubits (the lattice referred to earlier) which will work for any computation you may wish to perform. The lattice has only 2 parameters, length and breadth, which are analogous to the time and memory the computation uses. As these parameters can be artificially inflated, they are not revealing anything particularly useful about the computation. So only the Z rotation reveals information about the computation. However, if the user prepares the initial qubits in random states on the equator of the Bloch sphere, the net rotation the server needs to perform must incorporate both the undoing of this initial random rotation and rotate by the appropriate angle required to correctly implement the desired calculation. This means that, depending on the initial random state chose (of which he is not aware), for any fixed angle required to implement the users computation, the server is equally likely to be asked to perform a Z rotation through any angle. Thus the angle he is told is completely independent of the users calculation.

So none of the classical messages the user send reveal any information about the calculation, but what about the qubits? Can’t they be measured to reveal information about their random rotation? If so, then the entire computation could be infered by the server from a combination of the classical and quantum messages sent by the user. Fortunately for us, the quantum mechanics come to the rescue. Suppose instead of choosing the inital state of the qubit and the angle sent to the server in such a way that the exactly implement the correct angle required to implement their desired computation, suppose they choose them randomly to either add up to the correct angle or add up to the correct angle + 180 degrees. What would happen then? Well, this would be the same as randomly choosing on of two opposing points on the Bloch sphere. No matter what two points you pick, it is impossible to determine either of them by making a measurement on such a system. This is because no matter what axis you pick to make a measurement along, you always have an equal chance of obtaining a 1 or a 0, independent o the choice of points. So if the user sends such randomized states to the server, together with measurement angles, there is nothing to be learned by any measurement of the system. Thus everything is perfectly hidden from a malicious server, even if they deviate from the protocol.

But doesn’t this randomization mess up the computation, resulting in nonsense? As it turns out, no, it doesn’t. This is because this extra rotation through 180 degrees is identical to flipping the measurement result the server gets when they measure the qubit. Since the measurement results are randomly flipped, the server can’t learn anything about the computation. However, the user knows whether or not the result has been flipped, and so can unflip it when they receive the result from the server. As long as they base their actions on these corrected results, the outcome of the computation is identical to if they had never occurred at all. Since the measurement results the server obtains are flipped, even for the last qubits to be measured, they have no knowledge of the outcome of the computation, though it can be trivially read by the user.

Since the server doesn’t know what computations are being performed, it is possible to set up traps to detect if the server deviates from the protocol, but this isn’t necessary to ensure blindness, and is beyond the scope of this blog post.

Now that I’ve explained the explained the theory, I’ll tell you a little about the experiment. To actually see our protocol become something real, we spent much of the last two years working with experimentalists Stefanie Barz, Philip Walther and Anton Zeilinger to find a way to implement the protocol using photons. Photons make perfect qubits, since they have two polarizations which can be used to encode a single qubit. In practical terms they would be ideal for a mature implementation of blind quantum computation, since photons can be relatively easily be transferred over large distances, allowing the user to be hundreds or thousands of kilometers distant from the server. Additionally, the group already had significant success in implementing the measurement based model of quantum computing on which our protocol is based.

The final set-up used (see above), like every other first demonstration, makes some compromises most notably in giving the client something a little more sophisticated than a pocket laser and 3d glasses, since this allowed us to simplify the server somewhat. None the less, it is a pretty faithful implementation of our original idea. With the 4 photonic qubits we had, we were able to hide all of the basic building blocks for a larger scale computation, meaning that we were able to demonstrate blind single and 2 qubit gates, which are sufficient to build an arbitrary computation out of. We were also able to hide instances of two quantum algorithms: the Deutsch-Josza algorithm and Grover’s algorithm.

Lastly, and most importantly, we were able to show that virtually no information could have been leaked by the apparatus. Although we have a theoretical proof, as outlined above, actual experimental apparatus aren’t as well behaved as our theoretical models, and so we need to show that our apparatus isn’t leaking information by introducing some subtle error on the quantum states. This may sound impossible, since how do you prove a negative? By running the experiment many times over for each and every possible choice user could make, we were able to use measurements made on different runs to infer the real state received by the server. This was possible because we knew exactly what the users choice of randomness was in each case, and so weren’t subject to the blindness which affects the server. With all of these measurements made, and the true states inferred, we applied a result known as Holevo’s theorem to calculate a maximum amount of information that could be extracted by a malicious server had they knowledge of the exact peculiarities of our experimental set-up. Philip and Stefanie are so good at their jobs, the system is pretty accurate, an the amount of information which could possibly have been leaked was no more than 0.169 of a bit. Even if the server could somehow learn something about the user’s desired calculation or random choices, the amount he could learn from measurements on the quantum state rises only slightly to 0.185 of a bit. In the case of these experiments, we were using 8 different initial states (i.e. 3 bits) for each blind qubit which is sufficient for any calculation, and so the amount of leakage is tiny. Not too bad for a first attempt, I think!