How many functions can be distinguished with k quantum queries?
arXiv:quant-ph/9901012 · doi:10.1103/PhysRevA.60.4331
Abstract
Suppose an oracle is known to hold one of a given set of D two-valued functions. To successfully identify which function the oracle holds with k classical queries, it must be the case that D is at most 2^k. In this paper we derive a bound for how many functions can be distinguished with k quantum queries.
5 pages. Lower bound on sorting n items improved to (1-epsilon)n quantum queries. Minor changes to text and corrections to references
References in corpus (1)
Cited by in corpus (11)
- Unambiguous discrimination among oracle operators
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- Identification of a reversible quantum gate: assessing the resources
- Quantum algorithms for multivariate Monte Carlo estimation
- Bounds on quantum ordered searching
- A Quantum Algorithm for the Classification of Patterns of Boolean Functions
- Classical Encryption and Authentication under Quantum Attacks
- Probabilistic Links Between Quantum Classification of Patterns of Boolean Functions and Hamming Distance
- Quantum algorithms for search with wildcards and combinatorial group testing
- The quantum query complexity of learning multilinear polynomials
- Speed from Repetition