The equivalence of sampling and searching

DOI10.1007/s00224-013-9527-3zbMath1319.68153OpenAlexW1979231104MaRDI QIDQ2254498

Scott Aaronson

Publication date: 5 February 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9527-3

zbMATH Keywords

algorithmic information theoryKolmogorov complexityquantum computingsearch problemssampling problemsfunction problemsextended Church-Turing thesisFBQPrelational problems

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 (2)

Constant-round blind classical verification of quantum sampling ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• PP is as Hard as the Polynomial-Time Hierarchy
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: The equivalence of sampling and searching