Quantum counterfeit coin problems

DOI10.1016/j.tcs.2012.05.039zbMath1253.68177MaRDI QIDQ714865

Rudy Raymond, Kazuo Iwama, Harumichi Nishimura, Junichi Teruyama

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.039

zbMATH Keywords

quantum computing; query complexity; counterfeit coin problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

Related Items

RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC, Quantum algorithms for learning symmetric juntas via the adversary bound

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of Ambainis lower bounds
• The general counterfeit coin problem
• Polynomial degree vs. quantum query complexity
• Searching for two counterfeit coins with two-arms balance
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Counterfeit Coin Problems
• Quantum Complexity Theory
• Coin-Weighing Problems
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Quantum Algorithms for the Triangle Problem
• Quantum Query Complexity of State Conversion
• Classical and Quantum Algorithms for Exponential Congruences
• Quantum lower bounds by quantum arguments