Computing with a Quantum Walk

Ben: -  Researchers from Bristol University reported on a development in quantum computing that could bring this revolutionary technology closer, by up to twenty years. I met up with Jonathan Matthews to find out how their device works, but first Jeremy O'Brien, the Director of the Centre for Quantum Photonics, explained why quantum computers are so appealing...

Jeremy: -   People have been trying to develop a quantum computer for at least a decade in a serious way, and for a couple of decades people have known that such a device could be incredibly powerful for computation for particular tasks.  So there's been a big worldwide effort to realise a quantum computer.  Even at this stage it's anticipated to be decades away though, and the reason for that is that you need to be able to control single quantum systems - so that could mean single particles of light, single photons or single electrons, or single atoms.  You need to be able to couple them together in complex ways to control them and manipulate them and read out the state that they are in.  So it's an incredible quantum engineering challenge, if you like, to be able to make such a device.  There's tasks that we know that we can do with a quantum computer exponentially faster than we can do with a conventional computer.  So that means we can do problems that are intractable on a conventional computer and they are ones in which the time taken to do the computation grows exponentially with the problem size.  For a quantum computer we don't have that - they are linked in a sensible way with one another - the size of the problem and the time taken.

Ben: -   So rather than an evolution of the existing computer we are looking at a revolution of the sorts of technology we use?

Jeremy: -   That's exactly right.  So it's a completely different way of doing computation.  The idea here is to harness uniquely quantum mechanical effects.  So quantum mechanics is the theory that explains how the world works at its most fundamental level - how single photons, single atoms and single molecules, and so on, behave and interact with one another - and it's surprisingly different to the way the world works in our every day experience.  For example, it tells us that an object can be in two places or more places indeed, simultaneously, that two objects can be inextricably linked with one another, no matter how far apart they are, such that a measurement on one will instantaneously affect the other one.  We call these effects "superposition" and "entanglement" but that's essentially what they are.

Ben: -   Jonathan, if I could bring you in here, what physically is this device that you've developed?

Jonathan: -   This device is an integrated optical chip.  It uses what we call "wave guides" to guide light through a monolithic structure - a fixed structure, and these wave guides work very much like optical fibres - like pipes for light if you will.  And what we do is we pattern several of these wave guides close together so that the photons can actually tunnel directly between neighbouring wave guides, or neighbouring pipes, and this allows us to see these superposition patterns that we call "quantum walks."

Ben: -   What is a quantum walk and how would it differ from a classical walk?

Jonathan: -   Perhaps I can start with a classical walk.  A classical walk - you can realise by dropping a marble and giving it a series of choices by going left or right as it hits a bunch of pins arranged in a grid pattern, and this will give you a normal distribution at the bottom - a bell curve.  So that's based on the marble being given a choice of going left or right, based on probability.  But if you give the marble the possibility of going left and right, it has the possibility of interfering with itself, and you get at the end a very different statistical outcome.  These statistical outcomes include features such as propagating much faster - the distribution propagates much quicker than in the classical case.  It's this kind of behaviour that can be really harnessed in quantum technologies.

Ben: -   So, a quantum object will give you a very different likelihood of landing in any particular place from this walk, and that's when you put one photon through.  Your work is working on putting more than one through to see how that works out.  What's the advantage of doing that?

Jonathan: -   A key thing is you need the two photons to be exactly the same in every single property, but they quantum interfere with each other, and the fact that there are two photons, gives you a different statistical output than if you put in one photon and then put another photon in, and compare the two results.

Ben: -  So in terms of quantum computing, why is this an advantage?

Jonathan: -    Well this allows us to simulate more complicated structures.  So quantum walks move around an environment that mathematicians call graphs, and these environments essentially become exponentially more complicated as you linearly increase the number of photons.  So if I have one photon, it's moving through a system of let's say, 20 wave guides, then my system is of size 20, whereas if I stick two photons into the device, then I'm simulating a structure that's of the order of 20 squared.

Ben: -   So Jeremy, coming back to you, what do we hope to use these quantum computers for?

Jeremy: -   So these particular types of computers based on quantum walks are in principle able to realise an universal quantum computer, so there's an exciting and important theoretical result to show that quantum walks are able to perform any type of quantum computation.  But in the nearer term we expect to be able to simulate important quantum systems using these quantum walks in a sort of direct way.  The types of things that we might be interested in simulating are complex molecules that might be relevant to designing new pharmaceuticals or new materials. And it turns out that if we have a molecule with in the order of thirty atoms in it, that's the limit  of what we can reliably calculate using a conventional computer, even using a super computer today. And the reason is that the description of that system grows exponentially in the same way that Jonathan described the exponential growth of the quantum walk as we add more particles to it.  Other applications include understanding natural processes such as photosynthesis which rely on quantum coherent effects for their operation.

Ben: -   So by how much do you think your work has bought forward the reality of quantum computing?

Jeremy: -    So I think it's fair to say that the majority of people working in the field of quantum information science and quantum computing specifically, believe that an universal quantum computer is decades away.  But we're optimistic that using this quantum walk-type technique, we'll be able to make a device that's able to do things that can't be done on a conventional computer within a 5-year timescale.

Ben: -   That was Jeremy O'Brien and before him, Jonathan Matthew, explaining how the phenomenon of quantum walk could help to lead to a revolution in computing.  Their paper was published this week in the journal Science.