Advice Coins for Classical and Quantum Computation

DOI10.1007/978-3-642-22006-7_6zbMath1332.68052arXiv1101.5355MaRDI QIDQ3012792

Andrew Drucker, Scott Aaronson

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

zbMATH Keywords

quantum computation; finite automata; root-finding; PSPACE; finite-precision arithmetic; BQP

Mathematics Subject Classification ID

81P68: Quantum computation

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68Q12: Quantum algorithms and complexity in the theory of computing

Cites Work

• Unnamed Item
• Unnamed Item
• On approximate majority and probabilistic time
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Specified precision polynomial root isolation is in NC
• Space-bounded quantum complexity
• An efficient algorithm for the complex roots problem
• BQP and the polynomial hierarchy
• Pseudorandom Generators for Regular Branching Programs
• Closed timelike curves make quantum and classical computing equivalent
• Bounds on the Size of Small Depth Circuits for Approximating Majority
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• On Relating Time and Space to Size and Depth
• Approximation by DNF: Examples and Counterexamples
• Hypothesis Testing with Finite Statistics
• Learning with Finite Memory
• Algorithms in real algebraic geometry