Knotty calculations: a quantum version of braids could lay the groundwork for tomorrow's computers.
When you learned to tie knots as a child, you probably thought their main use was for making bows on birthday presents or keeping your shoes on your feet. However, if a small band of mathematicians and physicists has its way, knots will form the basis for an entirely new kind of computer, one whose power vastly outstrips that of the machines at our disposal today. In its first century, the mathematical study of knots belonged squarely to the realm of pure mathematics, seemingly divorced from any practical applications. In the past decade, however, mathematicians have turned knot theory knot theory
Mathematical theory of closed curves in three-dimensional space. The number of times and the manner in which a curve crosses itself distinguish different knots. into a bridge between two seemingly unconnected subjects: computer science and quantum mechanics quantum mechanics: see quantum theory.
Branch of mathematical physics that deals with atomic and subatomic systems. It is concerned with phenomena that are so small-scale that they cannot be described in classical terms, and it is , the branch of physics that deals with the ultrasmall scale of atoms and subatomic particles.
In a paper published last month, researchers propose that this connection between the two fields might finally enable physicists to reach a decades-long goal: to exploit quantum physics quantum physics
n. (used with a sing. verb)
The branch of physics that uses quantum theory to describe and predict the properties of a physical system.
See quantum mechanics. to build a computer whose performance would far surpass that of computers based on the classical physics of Isaac Newton. A quantum computer (computer) quantum computer - A type of computer which uses the ability of quantum systems, such as a collection of atoms, to be in many different states at once. In theory, such superpositions allow the computer to perform many different computations simultaneously. , if it is ever built, will have the power to crack the cryptographic schemes that safeguard Internet transactions and to create incredibly detailed simulations of the behavior of the universe at the tiniest scale.
The knots that mathematicians have been studying have a slight quirk: After the theoretical knot is tied, the ends of the string are joined together so the knot can't untie. The same knot can appear in many guises, since pulling and twisting the strings can make the knot look completely different. The basic question of knot theory is, Given two knots that look very different, is there a way tell whether they are knotted in the same way (SN: 12/8/01, p. 360)?
To distinguish between knots, mathematicians look for numerical characteristics of a knot, such as the number of times the knot's shadow crosses itself. Some other characteristics, called knot invariants, don't change when the knot is pulled and twisted about. If two knots have different invariants, they must be different knots.
At the heart of the connection between computer science and quantum physics is a knot invariant called the Jones polynomial In the mathematical field of knot theory, the Jones polynomial is a knot polynomial discovered by Vaughan Jones in 1983. Specifically, it is an invariant of an oriented knot or link given by a Laurent polynomial in the variable , which associates a given knot with an array of numbers. The Jones polynomial involves a complex mathematical formula, and although calculating it is easy for simple knots, it is enormously difficult for messy, tangled knots. In fact, mathematicians have found compelling evidence suggesting that as knots get more and more complicated, the difficulty of computing their Jones polynomials rises exponentially. Calculating the Jones polynomial for complicated knots is considered beyond the reach of even the fastest computers.
That seems like bad news. A connection to quantum physics, however, has turned this apparent liability into a decided advantage by offering a new approach. In the late 19808, physicist Edward Witten Edward Witten (born August 26, 1951) is an American theoretical physicist and professor at the Institute for Advanced Study. He is one of the world's leading researchers in superstring theory. , a major figure in string theory (SN: 2/27/93, p. 136), described a physical system that should calculate information about the Jones polynomial during the course of its regularly scheduled activities--just as when a ball is hurled into the air, nature instantly solves the complicated equations that govern its motion.
Now, mathematician Michael Freedman Michael Hartley Freedman (born 21 April 1951 in Los Angeles, California, U.S.) is a mathematician at Microsoft Station Q. In 1986, he was awarded a Fields Medal for his work on the Poincaré conjecture, one of the most famous problems of the 20th century. of Microsoft Research Microsoft Research (MSR) is a division of Microsoft created in 1991 for researching various computer science topics and issues. Overview
Microsoft Research (MSR) is one of the top research centers worldwide, currently employing Turing Award winners, C.A.R. in Redmond, Wash., and physicist Alexei Kitaev of the California Institute of Technology California Institute of Technology, at Pasadena, Calif.; originally for men, became coeducational in 1970; founded 1891 as Throop Polytechnic Institute; called Throop College of Technology, 1913–20. in Pasadena are pursuing a daring idea: If Witten's physical system somehow does calculations beyond the reach of computers, could this system be harnessed to build a completely new kind of computer?
NATURE AS COMPUTER The idea of a physical system calculating something about knots or other loops may sound strange, but in fact examples of such systems abound, even in basic physics. In an electrical transformer, for instance, two loops of wire are coiled around an iron core. An electric current passing through one of the wires generates a voltage in the other wire that's proportional to the number of times the second wire twists around the core. Thus, even if you couldn't see the wire, you could figure out its number of twists simply by measuring the voltage. Witten proposed that in the same way, it should be possible to obtain information about the Jones polynomial of a knot by taking appropriate measurements in a more complicated physical system.
The connections between the Jones polynomial and both computers and quantum physics caught Freedman's eye in the late 1980s. Freedman freed·man
A man who has been freed from slavery.
pl -men History a man freed from slavery
Noun 1. was on his home turf when it came to knots--in 1986, he was awarded a Fields Medal (the mathematical equivalent of the Nobel prize Nobel Prize, award given for outstanding achievement in physics, chemistry, physiology or medicine, peace, or literature. The awards were established by the will of Alfred Nobel, who left a fund to provide annual prizes in the five areas listed above. ) for his work in topology, the mathematical field to which knot theory belongs. However, he knew less about the challenges of building an actual physical system like Witten's theoretical system. Physicists "said Witten's physics was so abstract it wasn't related to the real world, and that we'd never be able to build such a computer in our universe," Freedman recalls. Discouraged, he put the project on the back burner Noun 1. back burner - reduced priority; "dozens of cases were put on the back burner"
precedence, precedency, priority - status established in order of importance or urgency; "... .
As Freedman gradually learned more physics, however, he became convinced that certain extremely cold electron seas called quantum Hall fluids might offer the right physics to do the job. Then in 1997, working independently, Kitaev described a concrete model for how such a computer might work. "Kitaev's paper was stunningly original," says John Preskill John Phillip Preskill (born 19 January, 1953) is an American theoretical physicist and a professor at the California Institute of Technology (Caltech).
Preskill was born in Highland Park, Illinois. After earning an B.A. , who studies quantum computation at the California Institute of Technology in Pasadena. "It's a beautiful and potentially quite significant idea."
In the past several years, Freedman and Kitaev have joined forces to explore the promise of their model for what they call a topological quantum computer A topological quantum computer is a theoretical quantum computer that employs two-dimensional quasiparticles called anyons, whose world lines cross over one another to form braids in a three-dimensional spacetime (i.e., one temporal plus two spatial dimensions). . Such a computer would encode information not in the conventional zeros and ones but in the configurations of different braids, which are similar to knots but consist of several different threads intertwined around each other. The computer would physically weave braids in space-time, and then according to according to
1. As stated or indicated by; on the authority of: according to historians.
2. In keeping with: according to instructions.
3. Witten's theory, nature would take over the hard work, carrying out complex Jones polynomial calculations in the blink of an eye.
POLYNOMIAL polynomial, mathematical expression which is a finite sum, each term being a constant times a product of one or more variables raised to powers. With only one variable the general form of a polynomial is a0xn+a POWER A computer specially geared to calculate the value of some obscure knot invariant might not seem particularly useful. However, in the late 1980s, mathematicians showed that computing the Jones polynomial belongs to the famous family of what they call NP-hard problems. If someone could find a fast way to calculate the Jones polynomial, the numerical output of the calculation could then be used to solve a host of other difficult problems. These include the traveling salesman problem (spelling) traveling salesman problem - US spelling of travelling salesman problem. , which looks for the most efficient route for a salesman who must pass through many cities. "There's an impressive amount of information stored in the Jones polynomial," Freedman says.
Kitaev and Freedman's model computer wouldn't provide the exact value of the Jones polynomial, only indicate whether its value lies within a certain range. However, even that is enough to solve many important problems. Last year, Freedman and Kitaev, together with mathematicians Zhenghan Wang and Michael Larsen
Both types of computers are expected to have the power to crack cryptographic schemes, such as the RSA (1) (Rural Service Area) See MSA.
(2) (Rivest-Shamir-Adleman) A highly secure cryptography method by RSA Security, Inc., Bedford, MA (www.rsa.com), a division of EMC Corporation since 2006. It uses a two-part key. algorithm commonly used in Internet security ''This article or section is being rewritten at
Internet security is the process of protecting data and privacy of devices connected to internet from information robbery, hacking, malware infection and unwanted software. , including credit card transactions. "A lot of people belonging to agencies with three letters in their name will be very interested if someone is able to build these computers," says Seth Lloyd Seth Lloyd is a Professor of mechanical engineering at MIT. He refers to himself as a "quantum mechanic".
Lloyd was born on August 2, 1960, received his AB from Harvard College in 1982, his Math.Cert. and M.Phil. from Cambridge University in 1983 and 1984, and his Ph.D. , who studies quantum computation at the Massachusetts Institute of Technology Massachusetts Institute of Technology, at Cambridge; coeducational; chartered 1861, opened 1865 in Boston, moved 1916. It has long been recognized as an outstanding technological institute and its Sloan School of Management has notable programs in business, .
Although researchers have been thinking about how to build qubit quantum computers for decades, so far they languish on the drawing board. The main difficulty is that in a qubit computer, each bit of information is typically encoded in the state of a single particle, such as an electron or photon. This makes the information vulnerable: If a tiny disturbance in the environment changes the state of the particle, the information is lost forever. Physicists call this problem decoherence. "Decoherenee is the number one enemy of quantum computation," Preskill says.
By encoding information in braids instead of single particles, a topological quantum computer neatly sidesteps this problem. A small disruption from the environment might disturb the threads of a knot slightly but is extremely unlikely to change its overall knottedness--just as a breeze might make your shoelaces flutter Flutter (aeronautics)
An aeroelastic self-excited vibration with a sustained or divergent amplitude, which occurs when a structure is placed in a flow of sufficiently high velocity. Flutter is an instability that can be extremely violent. but not untie. Thus, the topological quantum computer has a built-in defense against decoherence. "I think it's the right way to go in the long run, if you want to build a quantum computer," Preskill says. "It's a made-to-order solution to the problem of decoherence and errors.
Topological quantum computation's stability might eventually give it the edge over qubit computers, Lloyd says. "Topological quantum computation is far away from realization now, but it has such appealing features that it wouldn't take me by surprise if it turned into the dominant paradigm," he says. "It's such an elegant idea to use what nature gives you to build quantum computers that are intrinsically reliable."
COMPUTATION, ANYON? For building a topological quantum computer, one system that Freedman and Kitaev are considering is an exotic form of matter called a fractional quantum Hall fluid. It arises when electrons at the flat interface of two semiconductors are subjected to a powerful magnetic field and cooled to temperatures close to absolute zero. The electrons on the flat surface form a disorganized dis·or·gan·ize
tr.v. dis·or·gan·ized, dis·or·gan·iz·ing, dis·or·gan·iz·es
To destroy the organization, systematic arrangement, or unity of. liquid sea of electrons, and if some extra electrons are then added, strange quasi-particles called anyons emerge. Unlike electrons, which each have a single negative charge, or protons, which have a single positive charge, anyons can have a charge that is a fraction of a whole number--something never before seen in physics.
Anyons have a strange property that may make them the key to topological quantum computation. If you slide a bunch of pennies around on a table along paths that return the pennies to their original spots at the end, then after the motion is over there is no way to tell what paths the pennies followed (unless you have a very dusty table). When anyons are moved around each other, however, they remember--in a specific physical sense--the knottedness of the paths they followed.
Imagine several anyons on a surface, and suppose they move around along complicated paths, ending up where they started. On the surface, the paths may cross each other in many spots. However, in space-time--in which there is one snapshot of the surface for each moment in time--the paths don't pass directly through each other, but simply braid around each other.
Anyons come in a variety of types, and if two different anyons bump into each other, they either annihilate an·ni·hi·late
v. an·ni·hi·lat·ed, an·ni·hi·lat·ing, an·ni·hi·lates
a. To destroy completely: The naval force was annihilated during the attack. each other or fuse into a single particle. When anyons move around each other along braided braid·ed
a. Produced by or as if by braiding.
b. Having braids.
2. Decorated with braid.
3. paths, the motion changes the pattern of the anyons' interactions with each other--a change physicists call a unitary transformation A unitary transformation is an isomorphism between two Hilbert spaces. In other words, a unitary transformation is a bijective function
where . This transformation alters what will happen if two anyons collide, so by bumping anyons into each other it's possible to tell that they have moved.
What's more, different braids lead to different transformations, so one can figure out something about the particular braid the anyons traversed by measuring what happens when the anyons collide. The fractional quantum Hall fluid has effectively calculated numerical properties of the braid, and measuring the anyons gives information about the result of this calculation.
Quantum Hall fluids come in many flavors, depending on the fractional charge of the anyons. Different fluids have different unitary transformations and so carry out different calculations. If the transformations in a particular fluid aren't very complicated, then the corresponding calculations aren't very interesting. So, the task now is to find an anyonic system with complex enough transformations--called nonabelian transformations--to carry out Jones polynomial calculations. So far, the few quantum Hall systems that have been studied thoroughly aren't powerful enough to do the job, but Freedman is optimistic that the right systems exist. "Nonabelian anyons are not obscure mathematically--they're rather simple, and there's no overriding physical law that has to be broken to make them," he says. "I feel confident that they're out there, but there's no way of knowing right now whether they'll be easy or hard to put together."
Although quantum Hall fluids are the only known systems that contain anyons, many other anyonic systems probably await discovery, suggests physicist Chetan Nayak of the University of California, Los Angeles UCLA comprises the College of Letters and Science (the primary undergraduate college), seven professional schools, and five professional Health Science schools. Since 2001, UCLA has enrolled over 33,000 total students, and that number is steadily rising. . "With quantum Hall fluids, we stumbled by experiment into a new category of matter, and we've just scratched the surface in terms of new possibilities," Nayak says. He has teamed up with Freedman to explore the possibility of creating nonabelian anyons in systems consisting of many thin layers of magnets. Kitaev, meanwhile, is investigating the possibility of building memory for a quantum computer from a system in which electrons spinning on the corners of a hexagonal hex·ag·o·nal
1. Having six sides.
2. Containing a hexagon or shaped like one.
3. Mineralogy grid give rise to anyons.
Freedman is reluctant to put a time frame on the construction of a topological quantum computer, but he is confident that it will happen. "If the physical world is the way we think it is, it's only a matter of time," he says.
If a quantum computer is built, its uses will go far beyond cracking cryptographic schemes. A quantum computer could simulate the interactions of individual molecules and atoms, rapidly carrying out enormous computations that today's computers do agonizingly slowly. It's hard to guess ahead of time just how engineers and physicists will employ such a vast increase in computing capacity, says Daniel Gottesman Daniel Gottesman is a computer scientist, known for his work regarding quantum error correction. References
1. ^ Daniel Gottesman's resume
Waterloo is a city in Ontario, Canada. It is the smallest of the three cities in the Regional Municipality of Waterloo, and is adjacent to the larger city of Kitchener. . "When classical computers were invented, no one imagined that engineers would someday use them to test the design of airplanes or bridges," he says. With engineers turning their attention to designing single-molecule drugs, robots, and machines, it would be useful to have a quantum computer to probe matter on this tiny scale, Gottesman says.
For Freedman, though, there's a motivation even more compelling than the possibility of creating a powerful new computer. I'm working on this because the mathematics is so beautiful," he says. "It's an excuse to think about the two most interesting things in the world: topology and theoretical physics."