Aaronson: Quantum speedups require choreographing destructive interference for wrong answers
Scott Aaronson · Scott Aaronson on Computational Complexity Theory and Quantum Computers · Y Combinator · Jun 29, 2018 · at 5:23
Scott Aaronson, computer science professor at UT Austin, explains the theoretical mechanism required to obtain computational advantages from quantum computers.
0:00 / 0:27exact quote · 27.1s
▶ Watch the full episode on YouTube → 720p mp4 · rendered on demand · StarZero watermark
“The entire hope of getting a speed advantage from a quantum computer is to exploit the way that amplitudes work differently. It's to try to choreograph a pattern of interference Where for each wrong answer to your computational problem, like some of the paths leading there have positive amplitude, some have negative amplitude, so they cancel each other out. Whereas for the right answer, you want all the contributions to it to reinforce each other.”
quote is from the automated transcript, cleaned for reading: filler sounds and stutters are removed, nothing is rephrased. names can be misheard (the analysis reads context, assessments check outside sources). how →
More from Scott Aaronson
Aaronson: Human stupidity is a bigger near-term threat than superintelligent AI
“When I think about, like, the future of civilization, you know, let's say the next 20 years, the next 50 years, I tend to worry less about super intelligence than I do about super stupidity. You know, I tend to worry about, you know, killing ourselves off or y…”
Aaronson: Quantum error correction turned scaling into an engineering challenge
“What changed everything for most of us in the nineties was the discovery of quantum error correction, right? And quantum fault tolerance. The upshot of which was if you want to build a scalable quantum computer, you don't need to get perfect qubits. That are p…”
Aaronson: Certified randomness may be quantum computing's first near-term application
“As far as I can see, may be the first application of quantum computing that people could actually be able to realize with, like, near-term devices with 50 or 60 or 70 qubits. And this application is to generate cryptographically secure random bits.”
Aaronson: Differential privacy and quantum shadow tomography share a mathematical connection
“There's a, you know, precise mathematical connection between these two problems. You can prove it. You know, it goes in both directions, and then we were actually able to use it to, you know, take work that's been done in differential privacy by people who don…”