PERHAPS we should have recognised the power of weaving long ago. After all, it was a weaver who wrote the world’s 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’s looms in service, and they changed the face of the textile industry.
Now there’s another weaving revolution waiting in the wings, and this time it’s 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’s fastest processors longer than the age of the universe. This is no ordinary weaving, mind you. We’re 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 “quantum 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 “NP-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.
Advertisement
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’s 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’s 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 “RSA” method have used the hidden factors of these numbers as a basis for establishing secure codes. But in 1994 Peter Shor of AT&T’s Bell Labs showed how an array of quantum logic gates – a quantum computer’s 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 “qubits” 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 “decoherence” – 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’s 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’s 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’s 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’s 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’s insight, published in 1989, it seemed that Feynman’s 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’s 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’s calculator is robust: just as a passing gust of wind may ruffle your shoelaces but won’t 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’s work, but couldn’t find a way to take it forward. When he saw Kitaev’s 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 “topological 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 “world 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. “You 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’s because braiding doesn’t affect the observable properties of most particles, which means you can’t 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 “non-Abelian anyon”. Actually, it isn’t 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’s because topological charge, like electrical charge, can only be cancelled out by an equal and opposite charge. “The state of the quantum computer is stored in the conserved charges that the anyons carry,” says John Preskill of Caltech. “Even if you hit an anyon with a hammer, you can’t 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’t visualise it as anything other than abstract mathematics. “It’s 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 “equals” 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’s not quite the end of the story, however. The quantum nature of the topological charge means that it doesn’t 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. “The answer to the computation is phrased in terms of this probability,” Freedman says. “By doing the computation many times we can approximate what that probability is, and that’s 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’s not. “These anyons are very small and very close to each other,” says Freedman. “Braiding 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’s classical processors typically increases exponentially with the required accuracy.
So why aren’t Microsoft rushing a topological quantum computer onto the market – what’s the hitch? Well, it’s 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 “Where 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. “Mathematically we know [they] are out there – we see them in our models,” Freedman says. “If quantum theory is correct, then it’s certain we’ll 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. “It 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. “I 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. “The 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 “virtual lab”. “I 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’s 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. “In 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?
Where do all the anyons come from?
The signature of anyons was first seen in 1982 at Bell Labs in New Jersey, when researchers were studying the “quantum Hall effect”.
The classical Hall effect is named after Edwin Hall, a graduate student at Johns Hopkins University in Maryland in the late 19th century. Hall found that when a thin sheet of metal with an electrical current flowing through it is placed in a magnetic field, it creates a small voltage across the sheet, at right angles to both the current and the field.
In 1980, German physicist Klaus von Klitzing re-examined the Hall effect, but instead of metal he used a thin sheet of semiconductor at 1 Kelvin. He found that the Hall resistance – the observed voltage divided by the applied current – didn’t vary smoothly as the magnetic field strength changed, as it had done for Hall, but instead changed in discontinuous jumps. The very low temperatures of the experiment had allowed quantum behaviour to come into play. Klitzing found that the size of the jumps was given by a combination of physical constants from quantum theory, including the charge of the electron.
Two years later, a team from Bell Labs repeated the experiment, but this time using the purest semiconductor samples ever made, cooled to less than 300 mK and subjected to a magnetic field nearly a million times as strong as the Earth’s. Again, the Hall resistance varied in jumps, but now there were new steps, above and between those that Klitzing had seen. The distance between the new steps could only be accounted for if the electrical charge of the current-carrying particles had somehow dropped to just one-third the charge of the electron. It was as if the electrons had somehow split into three.
Shortly after this, physicist Robert Laughlin, now at Stanford University in California, constructed a theory that explained the result through the action of a new quantum entity: an anyon.