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
Europlacer Presents New Range of iineo SMT Placement Machines.
05/01/2024 | EuroplacerFor more than 15 years, the Europlacer iineo placement machines have made their mark on the SMT industry with unique features and unrivalled flexibility. Today, Europlacer announces the launch of the second generation iineo.
Real Time with... IPC APEX EXPO 2024: Factory Insights: A Customizable Data Collection Solution
05/01/2024 | Real Time with...IPCEditor Nolan Johnson and Julie Cliche-Dubois, product manager for Cogiscan, focus on Factory Insights, a new product that emphasizes customization. With years of experience in data collection from various machines and factories, the Factory Insights product offers dashboards and KPI customization, striking a balance between out-of-the-box solutions and customization, ultimately bringing contextualization to machine data.
Real Time with... IPC APEX EXPO 2024: Industrial Quality Solutions from Zeiss
04/23/2024 | Real Time with...IPC APEX EXPOEditor Nolan Johnson and Herminso Gomez of Zeiss Group discuss the company's industrial quality solutions, with a focus on X-ray technology. Zeiss provides a range of microscopy options and Herminso highlights the advantages of X-ray technology for aerospace, medical, and consumer electronics sectors.
VDMA: Machine Vision Navigating Through Uncertain Times
04/18/2024 | VDMAFor over a decade, the European machine vision industry has reported steady growth, with turnover increasing by an average of 9 percent annually between 2012 and 2022. Despite a temporary setback in 2020 (minus 4 percent) due to the Covid-19 pandemic, the industry rebounded strongly in 2021 (plus 17 percent) and 2022 (plus 11 percent).
IPC Bestows Posthumous Hall of Fame Award to Industry Icon Michael Ford
04/18/2024 | IPCIPC honored the late Michael Ford, Aegis Software, for his extraordinary contributions to the global electronics manufacturing industry with the IPC Raymond E. Pritchard Hall of Fame Award at IPC APEX EXPO 2024. IPC’s most prestigious honor, the Hall of Fame Award is given to individuals who have provided exceptional service and advancement to IPC and the electronics industry. Ford, an industry leader and valued IPC volunteer, died suddenly in January 2024.