Quantum Algorithms Database
Quantum Counterfeit Coin Detection
A quantum algorithm for identifying counterfeit (different-weight) coins among genuine ones using a weighing-based query model, faster than the best classical strategies.
Year
2010
Inventor(s)
Iwama, Nishimura, Raymond & Teruyama
Speedup Type
Quadratic Speedup
Difficulty
★★★☆☆
The Problem
Given a set of coins where some unknown subset are counterfeit (heavier or lighter), identify the counterfeit coins using the fewest possible weighings.
How It Works
Uses a quantum query model analogous to Grover-style amplitude amplification, encoding weighing outcomes into a quantum state to narrow down counterfeit coins faster than classical weighing strategies.
Real-World Impact
Primarily of theoretical interest in quantum query complexity research, illustrating how classic combinatorial puzzles can sometimes be reformulated to benefit from quantum speedups.