How many functions can be distinguished with k quantum queries?

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)

• Quantum Lower Bounds by Polynomials

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