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
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.