Blind quantum computing: An introduction

January 20th, 2012

Blind quantum computing - as illustrated by my lovely wife Liu Jia
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 Bloch sphere

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.

Optical setup

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!

New Year’s eve in Singapore

January 1st, 2012

newyears.jpg

TCS Community Blog

July 21st, 2011

The CSTheory StackExchange site has now given rise to a community blog. Myself and Aaron Sterling have agreed to have agreed to act as editors for the blog. The first post announcing the blog went up earlier in the week, but we now have the first technical post, from Artem Kaznatcheev on Quantum Query Complexity. The blog will mix happenings on the CSTheory site (interesting questions or answers that have caught our eye, etc.), with contributed posts including technical introductions to various areas of theoretical computer science and discussion of recent interesting results. We are actively soliciting contributions from the community active on the CSTheory site, so if anyone has an idea for an interesting post please feel free to contact me or Aaron.

Fukushima: A nuclear physics primer

March 12th, 2011

As I am sure everyone has heard by now, there has been an enormous earthquake off the coast of North-East Japan, which (together with the tsunami caused by the quake) has lead to widespread distruction and loss of life. At the moment, however, there is concern over trouble at two nuclear power station. The amount of information coming out through the media is quite limited, and of course isn’t easy to decrypt what experts are saying if you don’t know what the terminology means.

Caveat: Although I am a physicist, I am the wrong type of physicist to be paricularly expert on nuclear safety. I am writing this simply so this to try to help non-physicists decipher what is going on at the moment in Fukushima.

The first thing you need to know is what a nuclear power plant actually does, and what radiation is. All atoms are composed of a cloud of electrons which surround a nucleous composed of neutrons and protons. The stability of the nucleus is what determines radioactivity, and is determined by the number of protons and neutrons contained in the nucleus. The interaction between these particles determine how tightly they are bound together.

The above diagram shows the relative stability of different atomic elements, running from lighter to heavier elements. As you can see, iron (Fe) has the highest binding energy (meaning that its nucleons are the most tightly bound). Nuclear reactions in which larger nuclei split apart are known as fission reactions (moving towards iron from the right), while reactions where smaller nuclei are combined to form a larger nucleus are called fusion reactions (moving towards iron from the left). All commercial reactors are at present fission reactors. These work by capturing the energy released by large nuclei splitting, usually using uranium as fuel. The reactors at Fukushima are boiling water reactors, which capture this energy by using it to boil water to produce steam used to drive a turbine, which in turn generates an electric current (producing electricity).

Different nuclei come apart in different ways, depending on their composition. Which element a nucleus is is governed by the total number of protons only, and this determines it’s chemical properties. The nuclei of the same element can have different numbers of neutrons, and these different varieties are known as isotopes. The chart I showed above is of the most stable isotope for each element. How a particular radioactive element comes apart depends not on only on which element it is, but rather which isotope of that element. Below is a diagram showing how different nuclei decay.

Here the important unexplained types of decay are

  1. β- corresponding to the emission of an electron (this is a neutron changing into a proton in the nucleus),
  2. β+ corresponding to the emission of an positron, which is a positively charged version of an electron (this is a proton changing into a neutron in the nucleus)
  3. α which corresponds to the emission of a group of helium nucleus (2 protons and 2 neutrons tightly bound together), and happens because of the huge spike in binding energy for helium nuclei which can be seen in the first diagram.
  4. Fission, where the nucleus splits into several large parts

These ejected byproducts (together with γ-rays which can also be emitted) are what is usually what nuclear radiation is used to refer to. This what is known as ionising radiation, particles sufficiently energetic to knock electrons free from other atoms and molecules, which can in turn lead to chemical changes. Such radiation is dangerous for humans primarily because it can cause chemical changes within our body which can lead to any number of problems. In general ingestion or inhalation is much more dangerous than other types of exposure.

As I mentioned earlier, both Fukushima I and II user boiling water reactors. They use what is called ‘light water’ which simply means they use purified water to cool the fission reactions. The word ‘light’ is used to distinguish them from ‘heavy water’ reactors which use water where the hydrogen is replaced by a heavier isotope called deuterium (which can be used to regulate reactions in some reactor designs).

At Fukushima I, it appears that when the earthquake struck some problem occured with the cooling system for one of the reactors failed. The nuclear reactions produce a lot of heat, and needs to be kept cool by adding water. Unfortunately, even though you can slow down the fission reaction, some byproducts of the decay of uranium are themselves radioactive, and (according to one expert who just appeared on the BBC) can contribute as much as 10% of the energy produced in the reactor, which is essentially impossible to stop. Without the cooling system working, there is a build-up of steam. It is also possible for the fuel to react with the water to produce hydrogen. These gases have to be vented in order for the pressure inside the reactor to be kept within safe limits (so that the reactor doesn’t come apart). As long as the reactor is intack, the amount of radiation released should be low. Hydrogen is not radioactive, even if it absorbs a neutron (producing deuterium), the nucleus is stable. Tritium would be bad, but I can’t see anyway for that to have been produced. However, Nitrogen 16 will also have been produced, which is extremely radioactive. This may sound bad, but it is infact so radioactive that it decays very quickly, meaning that it doesn’t pose a danger any distance from the plant. The half-life is 7 seconds, meaning that 7 seconds after production half of the radioactive nitrogen has converted to safe oxygen. So after after 11 minutes there is on millionth the radiation. Give that wind speeds are relatively slow, the nitrogen will decay before it can cause much trouble (except perhaps for people actually in the plant). This is why we are hearing about high radiation levels in the control room, but little additional radiation right outside the perimeter.

There has also been an explosion at the plant which is causing significant, since it is not entirely clear what has happened. It sounds like this was probably caused by the hydrogen igniting, which has damaged the building, but it seems like the reactor core is still intact. If this is true, and they can keep the reactor cool enough that the fuel does not all melt (a meltdown, which makes it much harder to cool, and which would likely result in the release of much more nasty isotopes) then the amount of radiation released shouldn’t pose to much of a health risk. Fortunately the wind seems to be blowing out to see, which also improves the situation.

The latest I have heard is that the authorities are considering using sea water to cool the reactor core, which they will be reluctant to do since it will make the reactor unusable in future, but which should cool the reactor core. Apparently the incident is currently rated as 4 (”Accident with local consequences”) on the International Nuclear Event Scale, which is still one level below the Three Mile Island incident in the US, and 3 levels below the maximum level which corresponds to a Chernobyl-like event.

If anyone has any further information they would like to contribute, or any corrections to what I have written above (as I say, I am the wrong type of physicist), then please let me know, wither in the comments or by email.

Theoretical Physics Q and A site progress

November 24th, 2010

The proposed Theoretical Physics stack exchange site has finished its definition phase and has now entered a commitment phase. What this means is that we need as many physicists as possible to agree (by signing up here) to participate in the beta and hopefully ask or answer 10 questions in the first 3 months. This shouldn’t be a huge time commitment, but it is really important to get as many research physicists as possible early on. The reason for this is that the democratic nature of Stack Exchange sites means that the direction of the site is set by the participants. Obviously there are a lot more people interested in some aspect of theoretical physics than there are people who have some level of expertise in the field, and so it is important to get as many TP grad students, postdocs and faculty involved at an early stage to insure that the site becomes a TP version of MathOverflow and CSTheory, rather than becoming a site for people to post their pet crackpot theories or discuss pop science topics.

To help convince you to sign up, below are a list of the top 5 examples of both on-topic and off-topic questions chosen during the definition phase.

On-topic:

  1. Are there entangled states which do not violate any Bell inequality?
  2. Are XXZ spinchains with uniform couplings exactly solvable?
  3. Has [specific toy model] been studied in the literature?
  4. What are the justifying foundations of statistical mechanics without appealing to the ergodic hypothesis?
  5. Within Twistor String Theory (ala Within), what is currently seen as the significance of the superconformal algebra realized on supertwistor space?

Off-topic:

  1. Why is the sky blue during the day, red during sunrise and sunset and black at night?
  2. I have found an error in general relativity/quantum mechanics/the second law of thermodynamics. Can someone help me work out the maths?
  3. Is Dr. Quantum’s Double Slit Experiment video scientifically accurate?
  4. Why do hot things glow?
  5. What is the current thinking about Lisi’s “Exceptionally Simple Theory of Everything”?

A Theoretical Physics Q and A site

November 13th, 2010

I’ve become totally enamored with the CSTheory stack exchange site. It’s proving very addictive, but in exchange for the time I spend on the site I am finding that I am learning a lot of new things, and a few new tricks.

I had hoped that the Physics stack exchange site might become a similar resource for physicists (and I still very much self-identify as a physicist). Unfortunately this has turned out not to be the case. There was never a policy dictating that questions should be research level (as there was both for CSTheory and MathOverflow), and this has led to the majority of questions either being basic undergrad type questions or pop-sci question. As a result, there are also very many poor answers which contain common misconceptions, but which get up-voted. Consequently, I don’t think the site is likely to be an attractive propositions for active researchers.

However, I don’t want to just complain and not offer a solution, so I have set up a proposal for a Theoretical Physics stack exchange site. The aim of the site would be to provide a question and answers site aimed at research level questions only, akin to the CSTheory stack exchange site and MathOverflow. Personally I find both sites to be phenomenal resources, and I think it’s high time we physicists had something similar.

I proposed the site as being for theoretical and mathematical physics and not physics in general only because I think that spanning both theory and experiment might make the scope of the site too broad, making it harder to get good answers to specific questions in any one area. Experimentalists with theory questions (or better yet, theory answers) are of course encouraged to participate.

The process of defining the site is entirely democratic, so you don’t need to worry about whether you trust my judgement or not. If the site reaches beta temporary moderators are elected by the community. This is also why it is important to have a solid group of physicists early on, to set the level and tone of the site.

So, if you are a physicist and this sounds like something that might interest you, why not visit and help shape the scope and level of the site by submitting sample questions or voting on whether you think the questions submitted by others would be consistent with such a site?

CS Theory Q&A site in beta

August 23rd, 2010

The mathoverflow-like site for theoretical computer science which I blogged about earlier is about to go into public beta. The site aims to allow users to ask and answer research level questions in TCS, and I must say that my experience with the private beta has been excellent. I have received excellent answers to the 2 questions I asked, and have been able to give reasonable answers to 8 questions so far. It really is an excellent resource. Anyway, if you have an interest in TCS it is well worth participating in the site. It needs as many users as possible to make it a success.

To join the public beta, simply visit http://cstheory.stackexchange.com

P vs NP finally resolved?

August 9th, 2010

A new paper has appeared from Vinay Deolalikar in HP Labs claiming to prove P is not equal to NP (in fact P≠NP is the title). Normally I ignore the constant stream of papers on the subject, but this work looks like a serious attempt and is being taken seriously by a number of people I respect, so it has jumped straight to the top of my reading list.

For more details see posts by the Pontiff, Greg Baker, and R J Lipton.

I really hadn’t expected to see this proved within my life time, so I am of course skeptical. Still, even if there is an error, perhaps it opens up a new approach.

TheoryOverflow

July 2nd, 2010

If you’re a physicist, mathematician or computer scientist and haven’t already seen MathOverflow then stop reading this post and go check it out. It is one of the best resources for research level math I have ever seen. It is absolutely shocking the speed and quality of responses to potentially very technical questions.

So, if you are still reading, I will presume you actually know the site. So why do I bring it up? Well, there is currently a proposal for a TheoryOverflow, aimed at Theoretical Computer Science, on the StackExchange site. Basically the way this works is that the people that produce the engine that powers the MathOverflow and StackOverflow websites are looking to produce similar sites in different areas. First an idea is proposed and fleshed out (Stage 1), once this is done it moves to a commitment stage where potential users are asked to commit to using the new site initially if it were made (Stage 2), either posting questions or answers. Finally it moves to a Beta (Stage 3). TheoryOverflow is currently in stage 2, and so needs support.

Rep, if you don’t know, is basically reputation, and so people who have contributed to other such sites carry more weight than users who haven’t. Different users have different amounts of rep depending on their level of contribution to StackOverflow and sister sites. Unfortunately more users seem to be necessary than usual, because most potential users committing to it seem to either be new or are coming from MathOverflow, and the StackExchange site doesn’t care about your MathOverflow rep (though it does about StackOverflow rep).

So basically, TheoryOverflow needs more support. If it turns out even a tiny fraction as useful as MathOverflow, then it will be a fantastic resource. So please help make it happen. You can sign up here.

Quantum Country

April 18th, 2010

Nice article (and a pretty cool photo) in The Record about my dear friend and collaborator Anne Broadbent.