STACS 2004

DOI10.1007/B96012MaRDI QIDQ5309692zbMATH OpenOpenAlexFDO

Authors Akinori Kawachi, Hiroyuki Masuda, S. Yamasita, Andris Ambainis, Kazuo Iwama, Raymond H. Putra

Publication date 1 October 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0403056

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68)

Abstract: The oracle identification problem (OIP) is, given a set $S$ of $M$ Boolean oracles out of $2^N$ ones, to determine which oracle in $S$ is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to $S$. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper and lower bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is $O(sqrtNlogMlogNloglogM)$ for {it any} $S$ such that $M=|S|>N$, which is better than the obvious bound $N$ if $M<2^{N/lo{g}^{3}N}$. (ii) It is $O(sqrtN)$ for {it any} $S$ if $|S|=N$, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles ($|S|=N$) such as random oracles and balanced oracles, the query complexity is $Theta(sqrtN/K)$, where $K$ is a simple parameter determined by $S$.

Recommendations

• Quantum identification of Boolean oracles
• Improved Algorithms for Quantum Identification of Boolean Oracles
• Improved algorithms for quantum identification of Boolean oracles
• An optimal quantum algorithm for the oracle identification problem
• Boolean functions identification via quantum computing methods

Cited in

(15)

• Quantum algorithms for learning symmetric juntas via the adversary bound
• Improved bounds on quantum learning algorithms
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• Boolean functions identification via quantum computing methods
• An optimal quantum algorithm for the oracle identification problem
• Quantum identification of Boolean oracles
• Query complexity of quantum biased oracles
• Quantum query complexity of almost all functions with fixed on-set size
• Oracles with costs
• Single-query learning from abelian and non-abelian Hamming distance oracles
• Improved Algorithms for Quantum Identification of Boolean Oracles
• A framework of quantum strong exponential-time hypotheses
• Improved algorithms for quantum identification of Boolean oracles
• On the distinguishability of random quantum states
• The geometry of quantum learning

This page was built for publication: STACS 2004

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5309692)