Robust Quantum Algorithms Computing OR with ε-Biased Oracles

Tomoya SUZUKI; Shigeru YAMASHITA; Masaki NAKANISHI; Katsumasa WATANABE

doi:10.1093/ietisy/e90-d.2.395

Robust Quantum Algorithms Computing OR with ε-Biased Oracles

Tomoya SUZUKI, Shigeru YAMASHITA, Masaki NAKANISHI, Katsumasa WATANABE

Full Text Views

0

Cite this

Summary :

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

Publication: IEICE TRANSACTIONS on Information Vol.E90-D No.2 pp.395-402

Publication Date: 2007/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e90-d.2.395

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category: Quantum Computing

Cite this

Copy

Tomoya SUZUKI, Shigeru YAMASHITA, Masaki NAKANISHI, Katsumasa WATANABE, "Robust Quantum Algorithms Computing OR with ε-Biased Oracles" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 2, pp. 395-402, February 2007, doi: 10.1093/ietisy/e90-d.2.395.
Abstract: This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with O(/ε) queries to ε-biased oracles. This improves the known upper bound of O(/ε²) and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of ε.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.2.395/_p

Copy

@ARTICLE{e90-d_2_395,
author={Tomoya SUZUKI, Shigeru YAMASHITA, Masaki NAKANISHI, Katsumasa WATANABE, },
journal={IEICE TRANSACTIONS on Information},
title={Robust Quantum Algorithms Computing OR with ε-Biased Oracles},
year={2007},
volume={E90-D},
number={2},
pages={395-402},
abstract={This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with O(/ε) queries to ε-biased oracles. This improves the known upper bound of O(/ε²) and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of ε.},
keywords={},
doi={10.1093/ietisy/e90-d.2.395},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Robust Quantum Algorithms Computing OR with ε-Biased Oracles
T2 - IEICE TRANSACTIONS on Information
SP - 395
EP - 402
AU - Tomoya SUZUKI
AU - Shigeru YAMASHITA
AU - Masaki NAKANISHI
AU - Katsumasa WATANABE
PY - 2007
DO - 10.1093/ietisy/e90-d.2.395
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2007
AB - This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with O(/ε) queries to ε-biased oracles. This improves the known upper bound of O(/ε²) and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of ε.
ER -