Exact quantum query complexity of weight decision problems via Chebyshev polynomials.

Xiaoyu He Xiaoming Sun Guang Yang Pei Yuan

Published in: Sci. China Inf. Sci. (2023)

Keyphrases

decision problems
query complexity
influence diagrams
data complexity
membership queries
computational complexity
utility function
np hard
optimal policy
resource consumption
exact learning
dnf formulas
concept class
pspace complete
uniform distribution
bandit problems
data mining
query evaluation
bayesian networks