by Jonathan Warneke
MIT Professor Edward Farhi, director of the Center for Theoretical Physics at MIT, has been deemed armed and dangerous by the United States government. His weapon of choice? A quantum computer.
Farhi, who grew up in New York City, knew he wanted to be a physicist by age 12. “I liked words like mass, energy, and atom,” he said, half-jokingly. Farhi began his rigorous science education at the Bronx High School of Science and upon graduating enrolled at Brandeis University as an undergraduate. After getting his PhD in physics from Harvard in 1978, Farhi did two years of post-doctoral work at SLAC, the Stanford Linear Accelerator Center, and one year at the LHC (Large Hadron Collider) in Geneva, Switzerland, with CERN.
Two main reasons lie behind Farhi’s choice to go into theoretical physics rather than experimental physics. First, he always liked challenging math problems, and theoretical physics is much closer to math than experimental physics is. Secondly, experimentalists are tinkerers, people who are comfortable with tools and making things – characteristics that Farhi said do not describe him. “My limit of household repairs – I can change a light bulb,” he said. “I don’t even own a drill. If I need one, I don’t even find a drill. I find a person to drill for me.”
Farhi arrived at MIT in 1981. After some time working on particle physics, astrophysics, and general relativity, in 1997, he turned his attention toward the field of quantum computation. “It was fresh, the main results were new,” he said, which lured him into the field. A particle physicist by training, he knew that he could use his quantum mechanics background effectively to work on speeding up computations. Though a quantum computer has not yet been built, it is certainly theoretically possible, and Farhi’s work focuses on the possibilities of what such a computer might accomplish.
So what are quantum computers? First, it is necessary to understand classical computers, which we use today. Classical computers operate with bits, or a bunch of 0’s and 1’s. This is called a binary system. Classical computers carry out functions by using binary arithmetic: adding or subtracting 0’s and 1’s to get more 0’s and 1’s, which translate to “off” and “on,” respectively. The sequence of “off”s and “on”s tells a computer which functions to execute. However, quantum computers operate using what are called qubits, or quantum bits, which are quantum particles, such as electrons. Recall from high school chemistry that an electron can have two states: spin up or spin down. However, with qubits, superpositions, or states in between up and down, can be created, no longer restricting operations simply to a 0 or a 1. These superpositions can be thought of as linear combinations of “spin up” and “spin down” electrons. This allows for much more computational freedom and power.
When computers solve a problem, they follow a certain number of steps, each with a certain clock speed, which is how fast the step is completed. Quantum computers actually have slower clock speeds than classical computers, but they dramatically decrease the number of steps necessary to solve a problem. Because of this, the net time a quantum computer takes to solve certain problems is actually far less than the time in which a classical computer can solve those problems. This concept of taking far fewer steps, even if the individual steps themselves may be slower than those of classical computers, is called algorithmic speedup.
This makes quantum computers extremely powerful. “Exactly how powerful?” you ask. Dangerously powerful. This is why Farhi’s research is funded generously by many top-secret government agencies. “I couldn’t even tell you what they are,” he says, because even he doesn’t know their names. Farhi is funded in this way because he’s deemed “armed and dangerous” by the United States government; theoretically, he could build a quantum computer with the ability to crack government security encryptions. Government agencies give him money to do his research because if he does ever build such a device, they want to be the first to know about it. And Farhi’s power would not be limited to this; banks, Facebook—anything with an encryption—could potentially be cracked by a quantum computer.
These encryption systems assume that extremely large numbers, say, a thousand-digit-long number, cannot easily be factored into prime numbers. A prime number is a number with only two distinct factors: one and itself. Each number has only one unique prime factorization, for instance, 24=23∙3. So to make an encryption, one can pick lots of prime numbers at random and multiply them all together to get a really big number. To break the encryption, one would have to be able to produce the prime factorization of this really big number. Finding a solution to this problem is not difficult – the problem is finding a practical one. The simplest solution is just to take the number (#119873#) and try dividing it by the prime numbers: 2, 3, 5, 7, 9, and so on until you get to (#119873#). However it’s even less difficult than that. A better solution notes that it’s only necessary to try primes up to √ N because if (#119909#) is a factor of (#119873#) less than or equal to , its corresponding factor (the number (#119910#) such that (#119909#)(#119910#)=(#119873#)) is greater than or equal to √ N. Despite this simplification, it would take an outrageous amount of time to factor a thousand-digit-long number, for example, even with many powerful classic computers working in tandem. However, a quantum computer could theoretically do this in a timely fashion. Why? Because it could do the problem in far fewer steps than √ N.
In reality, quantum computing is not a new discipline, but rather a new application of disciplines. It combines the ideas of computer science, early 20th century mathematics, and quantum mechanics to solve a problem. There are many promising implications and applications of quantum computing, including quantum money and the traveling salesman problem.
Quantum money introduced the idea of using quantum computing as a tool in the world of finance. A curious principle of quantum mechanics is that if a person “looks” at a particle (or measures a property of it), he inevitably changes its state. Quantum money takes advantage of this principle to eliminate counterfeiting. A quantum bill couldn’t be copied – once the counterfeiter looked at the bill to measure its worth, she would change what the bill actually was. However, this introduces a new problem. How is it possible to verify that anyone had the money in the first place? Currently, Farhi and other quantum computational theorists are searching for a way to “partially measure” the value of a bill so that it can be verified. But, in turn, this means that a counterfeiter may be able to find a way to “partially measure” the bill, too, and copy it. This is why the concept of quantum money could be valuable, but at the same time challenging.
Another problem sought to be solved by quantum-computing hopefuls is the traveling salesman problem. Right now, if one ships a package using overnight air with FedEx, even if it is going to an adjacent state, the package is flown to the FedEx hub in Tennessee and then flown to the airport closest to the destination, which is extremely inefficient. This is because, like everyone else, FedEx has no solution to the traveling salesman problem. The problem is this: if a salesman has to stop at N cities, and he knows the distance between any two cities, which is the shortest possible route he can take that permits him to visit each city exactly once? Just as with the prime factorization problem, there is an obvious solution: check each route, and see which one is the shortest. However, if you are given (#119873#) cities, there are (#119873#)! routes, where (#119873#)!=(#119873#) ∙ ((#119873#)−1)⋯ 3 ∙ 2 ∙ 1, because there are (#119873#) options for the first city to visit, ((#119873#)−1) options for the next city, and so on, until there is only one city left. So for large values of (#119873#), a classical computer could never compute the distance of each route in any of our lifetimes. (To give you an idea, if (#119873#)=10, then (#119873#)!=3,628,800: over 3.5 million routes! And presumably, there would be many more cities than 10.) However, there is widespread optimism that a quantum computer may be able to crack this problem one day by using far fewer steps than the (#119873#)! a classical computer would take.
Farhi doesn’t think that people will see actual quantum computers in use for at least another twenty years. Further, he predicts that they won’t be used in a home-computer setting, but rather by the government, at least at first. This is because quantum computers work with algorithmic speedup but slower clock speed, which solves different types of problems from those solved by classical computers. For simple tasks like checking email or word processing, it is more efficient to use faster clock speed with slower algorithms. Therefore, Farhi suspects that classical computers will likely remain the best option for the general public, which seeks general purpose computers.
On floor three of Building 6 at MIT, Farhi still ponders the possibilities of quantum computing behind the glass double-doors that guard his office. Although he admittedly tends to focus intensely on one subject at a time, he still pays close attention to what goes on at the Large Hadron Collider. He eagerly awaited results confirming the existence of the Higgs-Boson particle, which further supports the Standard Model, keeping his roots as a particle physicist. Every day, with physics on the mind and chalk in hand, Farhi takes to the blackboard, scribbling down what might be the next quantum leap in the field of computing. “It’s only a hope, though,” he says. But based on his track record, it would be no surprise if it turned out to be much more than just a hope.
Source:
Farhi, Edward. Personal Interview, Nov. 1, 2011.
Jonathan Warneke is a member of the class of 2015 at MIT, where he is studying theoretical mathematics and physics. He enjoys playing golf, among other sports, along with pool, chess, and thinking puzzles in his spare time.