scientific article; zbMATH DE number 6789291

DOI10.4230/LIPICS.CCC.2016.26MaRDI QIDQ5368760zbMATH OpenFDO

Authors Scott Aaronson, Shalev Ben-David

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1512.04016

zbMATH Keywords

decision-tree complexityquantum computingquery complexitystructural complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The elusive source of quantum speedup
• CONTROLLING THE QUANTUM COMPUTATIONAL SPEED
• The need for structure in quantum speedups
• MAPPING, PROGRAMMABILITY AND SCALABILITY OF PROBLEMS FOR QUANTUM SPEED-UP
• Quantum speedup of Monte Carlo methods
• Toward the first quantum simulation with quantum speedup
• Speeding up quantum dynamics by adding tunable time-dependent Hamiltonians
• Theory of the quantum speed-up
• Estimating quantum speedups for lattice sieves

Cited in

(6)

• CONTROLLING THE QUANTUM COMPUTATIONAL SPEED
• Symmetries, graph properties, and quantum speedups
• On the physical basis for the incomparability of NP and BQP
• Quantum and classical communication complexity of permutation-invariant functions
• On the fine-grained query complexity of symmetric functions
• On the fine-grained query complexity of symmetric functions

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368760)