In 2010, a Canadian company called D-Wave announced that it had begun production of what it called the world’s first commercial quantum computer, which was based on theoretical work done at MIT. Quantum computers promise to solve some problems significantly faster than classical computers — and in at least one case, exponentially faster. In 2013, a consortium including Google and NASA bought one of D-Wave’s machines.
Over the years, critics have argued that it’s unclear whether the D-Wave machine is actually harnessing quantum phenomena to perform its calculations, and if it is, whether it offers any advantages over classical computers. But this week, a group of Google researchers released a paper claiming that in their experiments, a quantum algorithm running on their D-Wave machine was 100 million times faster than a comparable classical algorithm.
Scott Aaronson, an associate professor of electrical engineering and computer science at MIT, has been following the D-Wave story for years. MIT News asked him to help make sense of the Google researchers’ new paper.
Q: The Google researchers’ paper focused on two algorithms: simulated annealing and quantum annealing. What are they?
A: Simulated annealing is one of the premier optimization methods that’s used today. It was invented in the early 1980s by direct analogy with what happens when people anneal metals, which is a 7,000-year-old technology. You heat the metal up, the atoms are all jiggling around randomly, and as you slowly cool it down, the atoms are more and more likely to go somewhere that will decrease the total energy.
In the case of an algorithm, you have a whole bunch of bits that start flipping between 1 and 0 willy-nilly, regardless of what that does to the solution quality. And then as you lower the “temperature,” a bit becomes more and more unwilling to flip in a way that would make the solution worse, until at the end, when the temperature is zero, a bit will only go to the value that keeps the solution going straight downhill — toward better solutions.
The main problem with simulated annealing, or for that matter with any other local-search method, is that you can get stuck in local optima. If you’re trying to reach the lowest point in some energy landscape, you can get stuck in a crevice that is locally the best, but you don’t realize that there’s a much lower valley somewhere else, if you would only go up and search. Simulated annealing tries to deal with that already: When the temperature is high, then you’re willing to move up the hill sometimes. But if there’s a really tall hill, even if it’s a very, very narrow hill — just imagine it’s a big spike sticking out of the ground — it could take you an exponential amount of time until you happen to flip so many bits that you happen to get over that spike.
In quantum mechanics, we know that particles can tunnel through barriers. (This is the language that the physicists use, which is a little bit misleading.) There’s an important 2002 paper by Farhi, Goldstone, and Gutmann, all of whom are here at MIT, and what they showed is that if your barrier really is a tall thin spike, then quantum annealing can give you an exponential speedup over classical simulated annealing. Classical annealing is going to get stuck at the base of that spike for exponential time, and quantum annealing is going to tunnel over it and get down to the global minimum in polynomial time.
Page 1 of 3
Suggested Items
Real Time with… IPC APEX EXPO 2024: Automation in North American PCB Shops
05/17/2024 | Real Time with...IPC APEX EXPOBenmayor Group has entered the North American market's automation landscape with their Technosystem division. In this interview, Eduardo Benmayor highlights this underinvestment and current efforts to catch up and address challenges related to strategic planning. Eduardo shares Technosystem's automation journey, from simple equipment to robotic arms, stressing the importance of machine communication and data analysis. He also offers advice on implementing automation in older facilities.
TactoTek Licenses IMSE Technology to Polestar for Sustainable Electronics Design Innovation
05/15/2024 | TactoTekPolestar, the Swedish electric performance car brand, and Finnish smart surface pioneer TactoTek, have entered a collaboration to explore integration of Injection Molded Structural Electronics (IMSE) technology into Polestar’s vehicle programs.
Using AI to Redefine Productivity
05/15/2024 | Nolan Johnson, SMT007 MagazinePlato Systems, a machine perception company spun out of Stanford University, employs AI and video data to analyze and optimize the human component in manufacturing. Initially focused on semiconductors, Plato Systems has expanded into EMS manufacturing. Co-founder and CEO Amin Arbabian, along with product advisor Anders Holden and head of growth Luis Vidal, discuss their approach to changeover optimization and its impact on productivity in the industry. They’ve also included customer Raj Vora in the conversation.
Real Time with… IPC APEX EXPO 2024: Saki America's Inspection Solutions and Market Expansion
05/15/2024 | Real Time with...IPC APEX EXPOCraig Brown, GM of Saki America, speaks with Editor Marcy LaRont about Saki's comprehensive inspection solutions, metrology, quality control, and software integration. He also touches on the company's recent X-ray machine award, the 3Di-LS3 machine, and their growing presence in the US and Mexico markets.
Saki Set to Highlight Cutting-Edge Inspection Technology at SMTConnect 2024
05/15/2024 | Saki CorporationSaki Corporation, an innovator in the field of automated optical and X-ray inspection equipment, will be exhibiting at SMTConnect 2024 in Nuremberg, Germany from June 11-13. As a key highlight of the Selecs booth #235 in Hall 4, Saki will be showcasing its unique range of automated inspection solutions including the award-winning X-ray Automated Inspection System (AXI) and innovative ‘One Programming’ and AI Solutions Features.