杏吧原创

PERHAPS we should have recognised the power of weaving long ago. After all, it was a weaver who wrote the world鈥檚 first ever computer program. In 1801, Frenchman Joseph Jacquard created an automated loom that could weave complex designs into cloth according to the pattern of holes in a series of punched cards that he fed into the machine 鈥� and it was nothing short of revolutionary. By 1812, there were 11,000 of Jacquard鈥檚 looms in service, and they changed the face of the textile industry.

Now there鈥檚 another weaving revolution waiting in the wings, and this time it鈥檚 computing, not the rag trade, that will reap the benefits. The twists and turns of weaving are promising a new breed of high-performance computer that will be able to solve problems so complex they would take today鈥檚 fastest processors longer than the age of the universe. This is no ordinary weaving, mind you. We鈥檙e talking about weaving in the quantum world, the realm of subatomic particles.

The idea of using the quantum world to perform calculations began with the late physicist Richard Feynman. He wanted to simulate the complexities of the universe in a computer and, realising that no conventional computer was up to the job, dreamed up the 鈥渜uantum computer鈥�. He pointed out that some computations boil down to solving equations that also describe situations in quantum physics 鈥� for example, what happens when two electrons bounce off one another. Many of these computations are what mathematicians call 鈥淣P-hard鈥�: the number of computational steps needed to find a solution grows exponentially with the number of variables involved, quickly rendering them unsolvable on conventional computers.

Feynman suggested a quicker route: do the quantum experiment 鈥� bounce two electrons off each other, say 鈥� and work out a way to read the result. In other words, find a physical situation where the maths governing the physics mirrors the maths you are trying to solve. An added attraction of this approach is that once you can solve one NP-hard problem, many other NP-hard problems succumb to exactly the same kind of solution.

It was a brilliant idea, and a few years later, David Deutsch of the University of Oxford turned Feynman鈥檚 sketch into a detailed blueprint, showing how to encode a computation in a quantum system and thus perform NP-hard computations. Almost immediately, researchers began coming up with applications for the machine. Among the most notorious is in code-breaking.

The security of many of the world鈥檚 encryption technologies depends on the intractability of one particular NP-hard problem: finding the factors of large numbers. A classical computer would take hundreds of millions of years to factorise a number just 300 digits long, and so encryption techniques such as the popular 鈥淩SA鈥� method have used the hidden factors of these numbers as a basis for establishing secure codes. But in 1994 Peter Shor of AT&T鈥檚 Bell Labs showed how an array of quantum logic gates 鈥� a quantum computer鈥檚 equivalent of the standard logic gates of computation 鈥� could find the factors and crack such codes in seconds.

However, no one has succeeded in developing a useful quantum computer, although there are a number of prototypes in development. Most aim to process quantum bits, or 鈥渜ubits鈥� of information encoded in the states of particles such as trapped ions or atoms held inside silicon chips. But the machines all face one big problem. They have to be carefully shielded to protect them from 鈥渄ecoherence鈥� 鈥� any disturbance can allow information to leak out, ruining the computation.

This is where quantum weaving comes in, potentially eliminating the problem altogether. This solution to the quantum computer鈥檚 problems is nearly as old as the idea of a quantum computer itself. In 1987 Vaughan Jones, a professor of mathematics at the University of California, Berkeley, published an extraordinary discovery. He showed that certain abstract structures called von Neumann algebras 鈥� which enable mathematicians to handle quantum mechanical variables such as energy, position and momentum 鈥� are related to the mathematical theory of knots, and provide a way to tell very complicated knots apart. Jones won the Fields Medal for this insight, the highest accolade in maths.

Jones鈥檚 work also proved that knots can store information 鈥� any given knot can be specified in terms of an array of 0s and 1s, determined by the knot鈥檚 twists and turns. Tie that knot and you have effectively stored those numbers. And since the logic gates used by computers can all be expressed as matrices of 1s and 0s, tying a knot can also encode the logic operations necessary for computation.

The string theorist Edward Witten, based at the Institute for Advanced Study in Princeton, was the first to connect Jones鈥檚 work with its consequences in the physical world. Witten showed that you can move quantum particles around one another to form a braid 鈥� one that exists in space and time, a sort of plait whose strands are the histories of the individual particles. Doing this should affect the quantum states of the particles in a way that is directly related to the properties of the braid you create. In other words, performing measurements on a braided system of quantum particles can be equivalent to performing the computation that a particular knot encodes.

The beauty of this is that the maths behind these braids, like the computations Feynman wanted to perform, is NP-hard: as the knots get more complicated, the equivalent computations that they encode correspond to problems of rapidly increasing difficulty.

With Witten鈥檚 insight, published in 1989, it seemed that Feynman鈥檚 idea had become reality: the properties of quantum particles could indeed give answers to previously intractable problems. But no one knew of a real quantum system that would do the job Witten had outlined. It was eight years before Caltech computer scientist Alexei Kitaev found one.

Kitaev showed how Witten鈥檚 topological interpretation of quantum theory can indeed form the basis for a computer (Annals of Physics, vol 303, p 2). Using quantum particles with just the right properties, braiding can efficiently carry out any quantum computation in super-fast time. And while traditional qubits are prone to decoherence, Kitaev鈥檚 calculator is robust: just as a passing gust of wind may ruffle your shoelaces but won鈥檛 untie them, data stored on a quantum braid can survive all kinds of disturbance.

It was at this point that another Fields medallist, Michael Freedman of Microsoft Research in Redmond, Washington, came onto the scene. Freedman, an expert in topology, had been fascinated by Witten鈥檚 work, but couldn鈥檛 find a way to take it forward. When he saw Kitaev鈥檚 paper, he got in touch, and the pair have been working together ever since.

Freedman and Kitaev (who is now also at Microsoft Research), together with Michael Larson and Zhenghan Wang, both at Indiana University in Bloomington, have now shown how to build a 鈥渢opological quantum computer鈥� using technology that is available today (). It seems to be the one machine that could get useful quantum computers off the drawing board.

So how does it work? The trick is to think of space and time as a unified four-dimensional entity. Even particles that are static in space are hurtling through time, tracing out a long thin 鈥渨orld line鈥� in this 4D space-time. So by moving particles about you can weave their world-lines around each other and tie knots that encode information 鈥� numbers and computations. 鈥淵ou reach in and start braiding the particles around each other, like someone braiding hair,鈥� Freedman says.

So far, so good. But measuring how a handful of identical subatomic particles have been braided round each other is impossible, at least for everyday subatomic particles such as electrons and protons. That鈥檚 because braiding doesn鈥檛 affect the observable properties of most particles, which means you can鈥檛 tell anything about the braid 鈥� and thus the computation 鈥� from examining them.

The way round this is an altogether different type of particle, called a 鈥渘on-Abelian anyon鈥�. Actually, it isn鈥檛 strictly a particle: anyons are blobs of subatomic particles that behave as if they were a single particle, and have one-third the electrical charge of the electron.

Non-Abelian anyons occur in pairs, n much the same way that pairs of particles and antiparticles bubble up from the vacuum of empty space. Each one in a newly created pair carries equal and opposite amounts of a quantity called topological charge. This is not charge in electrical terms but, like the strangeness or charm that quarks can carry, simply a label that describes a basic property of the particles and tells different types apart. The topological charge serves to distinguish one anyon from another as they are braided.

Unlike the fragile qubits in other quantum-computing systems, the information encoded in anyons is robust. That鈥檚 because topological charge, like electrical charge, can only be cancelled out by an equal and opposite charge. 鈥淭he state of the quantum computer is stored in the conserved charges that the anyons carry,鈥� says John Preskill of Caltech. 鈥淓ven if you hit an anyon with a hammer, you can鈥檛 change that charge, so the state stored in the computer is quite robust.鈥�

To perform a computation, you arrange the anyons in a row and then literally grab pairs of particles and swap their positions to create a braid in their space-time world lines (see Diagram). By carefully choosing your particular braiding pattern you can encode the quantum logic operations of the computation you wish to perform.

That correspondence between logic operations and braid designs is complicated 鈥� even Freedman admits he can鈥檛 visualise it as anything other than abstract mathematics. 鈥淚t鈥檚 sort of the end of a long calculation,鈥� he says. However, the actual process of braiding is not so complex. It could well be possible to do it with a device similar to a scanning tunnelling microscope.

Once braiding is complete, it simply remains to press the 鈥渆quals鈥� key. You do this by bringing together the pairs of adjacent anyons in the row. Pairs that have equal and opposite topological charges annihilate, while pairs with unbalanced charges fuse to form a new anyon. The final output of the computation is then a string of 0s and 1s 鈥� a 0 for each pair that disappears and a 1 for each pair that does not. And these could be read out using a probe that looks for the presence of anyons.

That鈥檚 not quite the end of the story, however. The quantum nature of the topological charge means that it doesn鈥檛 actually have a definite value. Although there is a value that is the most probable outcome of a measurement, there is also a chance of getting a range of other values from the measurement. So on one run of a computation, bringing together a particular pair of anyons might lead to their annihilation, giving a 0. Yet on the next run, there is a chance they might fuse to create a single anyon, giving a 1. 鈥淭he answer to the computation is phrased in terms of this probability,鈥� Freedman says. 鈥淏y doing the computation many times we can approximate what that probability is, and that鈥檚 the information we want to know.鈥�

The number of times the computation has to be repeated is in linear proportion to the accuracy you want, or at worst in proportion to its square. So if you needed to know the result to an accuracy of, say, +/鈭� 10 per cent, then you might have to do the experiment 100 times.

It sounds time consuming, but it鈥檚 not. 鈥淭hese anyons are very small and very close to each other,鈥� says Freedman. 鈥淏raiding them around each other involves very small movements and these can be done in nanoseconds.鈥� By comparison, the time taken to perform a calculation on today鈥檚 classical processors typically increases exponentially with the required accuracy.

So why aren鈥檛 Microsoft rushing a topological quantum computer onto the market 鈥� what鈥檚 the hitch? Well, it鈥檚 a big one: no one is certain that non-Abelian anyons actually exist. Ordinary anyons certainly do: they are created in a semiconductor phenomenon called the fractional quantum Hall effect (see 鈥淲here do anyons come from?鈥�). But no one has ever seen the non-Abelian variety. The good news is that everything in quantum theory says they should exist, and that they can be made. 鈥淢athematically we know [they] are out there 鈥� we see them in our models,鈥� Freedman says. 鈥淚f quantum theory is correct, then it鈥檚 certain we鈥檒l make them.鈥�

Chetan Nayak, a quantum computation researcher at the University of California, Los Angeles, agrees and even suggests that the particles may have been produced already. 鈥淚t is quite likely that a particular type of non-Abelian anyon exists in one of the observed fractional quantum Hall states,鈥� he says.

Others are trying new methods: Lev Ioffe, a condensed-matter physicist at Rutgers university in New Jersey, is experimenting with arrays of superconducting junctions. He hopes to make anyons by the end of this year, and believes the same approach will yield the non-Abelian variety. 鈥淚 think non-Abelian anyons will eventually be possible,鈥� he says.

So despite the practical hurdles ahead, many researchers are cautiously optimistic about the prospect of topological quantum computers. 鈥淭he obstacles are daunting but, eventually, I think they will work,鈥� says Preskill.

If these machines can be built, the range of potential applications is unlimited. They might be bad news for security and encryption, but they will also perform lightning-fast searches through large databases, and run simulations of the birth and evolution of the Universe in unprecedented detail. Yet Freedman believes those are peanuts compared with the possibility of a 鈥渧irtual lab鈥�. 鈥淚 think the most important application of quantum computers will be to predict the behaviour of materials without making them,鈥� he says.

At present, engineers largely resort to experiment to determine a material鈥檚 properties, such as its strength or flexibility. Although certain calculations can help, these properties are ultimately determined by quantum physics, so quantum computers are the natural machines to model them. This could allow engineers to tailor-make the materials they need 鈥� and that includes making new semiconductors, the very materials that could give rise to non-Abelian anyons. 鈥淚n a sense one of the applications of quantum computers will be to build more quantum computers,鈥� says Freedman.

And then what? No one knows, but one thing is clear. Ever since the Jacquard loom people have never failed to find innovative and unexpected uses for the increasing computing power at their disposal. Why should the power of quantum weaving prove any different?