2021/09/08 by Taghavi, Leila
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2109.03902
In the oracle identification problem we have oracle access to bits of an unknown string x of length n, with the promise that it belongs to a known set C⊆\0,1\n. The goal is to identify x using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity O(√((nlog M )/(log(n/log M)+1))), where M is the size of C. This bound is already derived by Kothari in 2014, for which we provide a more elegant simpler proof.