Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Transactions on Information and Systems

Robust Quantum Algorithms Computing OR with ε-Biased Oracles(Quantum Computing, Foundations of Computer Science)

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi, Katsumasa Watanabe

Published Feb 1, 2007• 0 citations
OpenAlex

Related papers

Robust Quantum Algorithms with ε-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

Lecture notes in computer science•Jan 1, 2006•2 citations

Robust Quantum Algorithms with epsilon -Biased Oracles.

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

Computing and Combinatorics Conference•Jan 1, 2006•0 citations

General Bounds for Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

An oracle with bias ε is an oracle that answers queries correctly with a probability of at least 1/2+ε. In this paper, we study the upper and lower bounds of quantum query complexity of oracles with bias ε. For general upper bounds, we show that for any quantum algorithm solving some problem with high probability using T queries of perfect quantum oracles, i.e., oracles with ε =1/2, there exists a quantum algorithm solving the same problem, also with high probability, using O(T/ε) queries of the corresponding biased quantum oracles. As corollaries we can show robust quantum algorithms and gaps between biased quantum and classical oracles, e.g., by showing a problem where the quantum query complexity is O(N/ε) but the classical query complexity is lower bounded by Ω(N logN/ε2). For general lower bounds, we generalize Ambainis' quantum adversary argument to biased quantum oracles and obtain the first lower bounds with explicit bias factor. As one of its applications we can provide another proof of the optimality of quantum algorithms for the so-called quantum Goldreich-Levin problem which was proved before by Adcock, et al. using different and more complicated methods.

IPSJ Digital Courier•Jan 1, 2005•6 citations

A Survey of Quantum Algorithms for Computer Science

Ajay H. Kumar, Amar Jeet Singh, Sanjay Kumar

Communications in computer and information science•Jan 1, 2025•1 citation

Quantum computing and quantum search algorithms

Zijian Diao, Goong Chen

•Jan 1, 2001•0 citations

Robust Quantum Algorithms Computing OR with -Biased Oracles

T. SUZUKI, Shigeru Yamashita, Masaki Nakanishi +1 more

This paper considers the quantum query complexity of e-biased oracles that return the correct value with probability only 1/2 + e. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√N/e) queries to e-biased oracles. This improves the known upper bound of O(√N/e2) and matches the known lower bound; we answer the conjecture raised by the paper yamashita affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of e. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of e.

IEICE Transactions on Information and Systems•Feb 1, 2007•0 citations
An oracle with bias ε is an oracle that answers queries correctly with a probability of at least 1/2+ε. In this paper, we study the upper and lower bounds of quantum query complexity of oracles with bias ε. For general upper bounds, we show that for any quantum algorithm solving some problem with high probability using T queries of perfect quantum oracles, i.e., oracles with ε =1/2, there exists a quantum algorithm solving the same problem, also with high probability, using O(T/ε) queries of the corresponding biased quantum oracles. As corollaries we can show robust quantum algorithms and gaps between biased quantum and classical oracles, e.g., by showing a problem where the quantum query complexity is O(N/ε) but the classical query complexity is lower bounded by Ω(N logN/ε2). For general lower bounds, we generalize Ambainis' quantum adversary argument to biased quantum oracles and obtain the first lower bounds with explicit bias factor. As one of its applications we can provide another proof of the optimality of quantum algorithms for the so-called quantum Goldreich-Levin problem which was proved before by Adcock, et al. using different and more complicated methods.
This paper considers the quantum query complexity of e-biased oracles that return the correct value with probability only 1/2 + e. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√N/e) queries to e-biased oracles. This improves the known upper bound of O(√N/e2) and matches the known lower bound; we answer the conjecture raised by the paper yamashita affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of e. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of e.