The Equivalence of Sampling and Searching

DOI10.1007/978-3-642-20712-9_1zbMath1319.68152arXiv1009.5104OpenAlexW1589227882MaRDI QIDQ3007612

Scott Aaronson

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum algorithms and complexity in the theory of computing (68Q12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The computational complexity of linear optics
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: The Equivalence of Sampling and Searching