Quantum Counterfeit Coin Problems

Abstract

The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only ``balanced'' or ``tilted'' information and that we know the number k of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let Q(k,N) be the quantum query complexity of finding all k false coins from the N given coins. We show that for any k and N such that k < N/2, Q(k,N)=O(k^{1/4}), contrasting with the classical query complexity, Ω(k\log(N/k)), that depends on N. So our quantum algorithm achieves a quartic speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs Ω(k^{1/4}) queries.

18 pages

References in corpus (4)

• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (7)

• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems
• Quantum algorithm for learning secret strings and its experimental demonstration
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Quantum Algorithm for Monotonicity Testing on the Hypercube
• High-performance state-vector emulator of a gate-based quantum processor implemented in the Rust programming language
• Quantum algorithms for search with wildcards and combinatorial group testing