English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

I survey, for a general scientific audience, three decades of research intowhich sorts of problems admit exponential speedups via quantum computers --from the classics (like the algorithms of Simon and Shor), to the breakthroughof Yamakawa and Zhandry from April 2022. I discuss both the quantum circuitmodel, which is what we ultimately care about in practice but where ourknowledge is radically incomplete, and the so-called oracle or black-box orquery complexity model, where we've managed to achieve a much more thoroughunderstanding that then informs our conjectures about the circuit model. Idiscuss the strengths and weaknesses of switching attention to sampling tasks,as was done in the recent quantum supremacy experiments. I make some skepticalremarks about widely-repeated claims of exponential quantum speedups forpractical machine learning and optimization problems. Through many examples, Itry to convey the "law of conservation of weirdness," according to which everyproblem admitting an exponential quantum speedup must have some unusualproperty to allow the amplitude to be concentrated on the unknown rightanswer(s).

How Much Structure Is Needed for Huge Quantum Speedups?