Skip to content
The methodOpen data
Back to the collection

How Much Structure Is Needed for Huge Quantum Speedups?

Scott Aaronson

2022 · arXiv

PhysicsAlgorithmsScience & research
Read the paper
HN score
0
Mentions
3
Readers
3
Months
3
What’s in a score?

From the abstract

I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit model, which is what we ultimately care about in practice but where our knowledge is radically incomplete, and the so-called oracle or black-box or query complexity model, where we've managed to achieve a much more thorough understanding that then informs our conjectures about the circuit model. I discuss the strengths and weaknesses of switching attention to sampling tasks, as was done in the recent quantum supremacy experiments. I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

3 selected excerpts · 3 total mentions

pred_
Neutral mention · rule
Normally, where I come from anyway, verifiability would refer to the ability to prove to a classical skeptic that the quantum device did what it's supposed to, cf. e.g. Mahadev (https://arxiv.org/abs/1804.01082), Aaronson (https://arxiv.org/abs/2209.06930), in a strong, theoretical, sense. And that's indeed relevant in the context of proving advantage, as the earlier RCS experiments lacked that ability, so “demonstrating verifiable quantum advantage” would be quite the step forward. That doesn't appear to be what they did at all though. Indeed, the paper appears to barely touch on verifiability at all. And – unlike the press release – it doesn't claim to achieve advantage either; only to indicate “a viable path towards” it.
Original comment Willow quantum chip demonstrates verifiable quantum advantage on hardware
civilized
Neutral mention · rule
We don't. Here's a survey paper from quantum computing expert Scott Aaronson, posted to arXiv just a couple months ago: https://arxiv.org/pdf/2209.06930.pdf From the abstract: > I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. [...] I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of…
Read the full comment
weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s). I am very confused at how so many people are absolutely convinced that quantum computing is known to do, or already does, all sorts of things it is not known to do. There's a sister comment here saying exponentially superior quantum computers are available in AWS! It's like an urban legend that circulates among software engineers.
Original comment Quantum winter is coming

Keep following the thread.

More in Physics

More from the same topics.