3Q: Scott Aaronson on Google’s New Quantum-Computing Paper
December 15, 2015 | MITEstimated reading time: 7 minutes
A: In the current model of the D-Wave chip, there are 1,000 or so qubits [quantum bits], but they’re organized into clusters of eight qubits each. The qubits within each cluster are very tightly connected to each other, and between clusters there are only weaker connections. I think that this is the best evidence we’ve had so far for quantum tunneling behavior, at least at the level of the eight-bit clusters.
The main way that they got an advantage over simulated annealing in these results was by taking advantage of the fact that quantum tunneling — or anything that correlates all the qubits within the cluster — can flip all the bits within each cluster at the same time, whereas simulated annealing is going to try flipping the bits one by one, then see that that’s not a good idea, then flip them all back, and not realize that by flipping all eight of them, you could get something better.
The case has now clearly been made that whatever the D-Wave device is doing, it’s something that can tunnel past this eight-qubit barrier. Of course, that still doesn’t mean that you’re doing anything faster than you could do it classically.
Q: What does it mean, then?
A: In computer science, normally we care about asymptotic speedup: We care about, “What is your running time as a function of the size of the problem? Does it grow linearly? Does it grow quadratically?” The constant that’s in front — Does it take 5N steps? Does it take 10N steps? — we don’t care that much about. We just care that it’s linear in N.
In the Google paper, they discuss two classical algorithms that do match the asymptotic performance — and one of them beats the real-world performance — of the D-Wave machine. So besides simulated annealing, there are two more classical algorithms that are actors in this story. One of them is quantum Monte Carlo, which is actually a classical optimization method, but it’s one that’s inspired by quantum mechanics.
In this new Google paper, they say that even though quantum Monte Carlo has the same asymptotic performance, the constant is way, way better for the D-Wave machine. The constant is about 100 million times better.
There are two huge issues that I would have with that. The first issue is that the problem instances where the comparison is being done are basically for the problem of simulating the D-Wave machine itself. There were $150 million dollars that went into designing this special-purpose hardware for this D-Wave machine and making it as fast possible. So in some sense, it’s no surprise that this special-purpose hardware could get a constant-factor speedup over a classical computer for the problem of simulating itself.
Page 2 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.