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
Testimonial
"Our marketing partnership with I-Connect007 is already delivering. Just a day after our press release went live, we received a direct inquiry about our updated products!"
Rachael Temple - AlltematedSuggested Items
Driving Innovation: Inner Layer Alignment Methods in PCB Production
08/06/2025 | Kurt Palmer -- Column: Driving InnovationIn PCB manufacturing, precision is a fundamental requirement. Among many complex processes, the accurate registration of inner layers before lamination is one of the most critical. Much like a child's game where rings must be perfectly stacked onto a single pin, PCB manufacturers align multiple conductive and insulating layers to form a cohesive, functional board. This alignment directly affects PCB precision; tighter layer alignment results in smaller "annular rings," superior performance, and higher yields.
Smarter Machines Use AOI to Transform PCB Inspections
06/30/2025 | Marcy LaRont, PCB007 MagazineAs automated optical inspection (AOI) evolves from traditional end-of-process inspections to proactive, in-line solutions, the integration of AI and machine learning is revolutionizing defect reduction and enhancing yields, marking a pivotal shift in how quality is managed in manufacturing.
Technica USA Announces New Strategic Partnership with I.T.C. Intercircuit Production GmbH
06/24/2025 | Technica USATechnica USA is pleased to announce a new distribution and representative agreement with I.T.C. Intercircuit Production GmbH, a globally recognized manufacturer of advanced equipment for the PCB manufacturing industry.
Smart Automation: The Power of Data Integration in Electronics Manufacturing
06/24/2025 | Josh Casper -- Column: Smart AutomationAs EMS companies adopt automation, machine data collection and integration are among the biggest challenges. It’s now commonplace for equipment to collect and output vast amounts of data, sometimes more than a manufacturer knows what to do with. While many OEM equipment vendors offer full-line solutions, most EMS companies still take a vendor-agnostic approach, selecting the equipment companies that best serve their needs rather than a single-vendor solution.
Sierra Circuits Boosts High Precision PCB Manufacturing with Schmoll Technology
06/16/2025 | Schmoll MaschinenSierra Circuits has seen increased success in production of multilayer HDI boards and high-speed signal architectures through the integration of a range of Schmoll Maschinen systems. The company’s current setup includes four MXY-6 drilling machines, two LM2 routing models, and a semi-automatic Optiflex II innerlayer punch.