Quantum identification of boolean oracles

Andris Ambainis; Kazuo Iwama; Akinori Kawachi; Rudy Raymond; Shigeru Yamashita

doi:10.1007/11683858_1

Quantum identification of boolean oracles

Andris Ambainis^*
, Kazuo Iwama
, Akinori Kawachi
, Rudy Raymond
, Shigeru Yamashita

^*Corresponding author for this work

University of Waterloo
Kyoto University
Institute of Science Tokyo
Nara Institute of Science and Technology

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

Abstract

We introduce the Oracle Identification Problem (OIP), which includes many problems in oracle computation such as those of Grover search and Bernstein-Vazirani as its special cases. We give general upper and lower bounds on the number of oracle queries of OIP. Thus, our results provide general frameworks for analyzing the quantum query complexity of oracle computation. Our results are also related to exact learning in the computational learning theory.

Original language	English
Title of host publication	Quantum Computation and Information
Subtitle of host publication	From Theory to Experiment
Editors	Hiroshi Imai, Masahito Hayashi
Pages	3
Number of pages	1
DOIs	https://doi.org/10.1007/11683858_1
Publication status	Published - 10 Jun 2006
Externally published	Yes

Publication series

Name	Topics in Applied Physics
Volume	102
ISSN (Print)	0303-4216
ISSN (Electronic)	1437-0859

Access to Document

10.1007/11683858_1

Cite this

@inbook{33c33239362544d09b86dfe0596f8cc3,

title = "Quantum identification of boolean oracles",

abstract = "We introduce the Oracle Identification Problem (OIP), which includes many problems in oracle computation such as those of Grover search and Bernstein-Vazirani as its special cases. We give general upper and lower bounds on the number of oracle queries of OIP. Thus, our results provide general frameworks for analyzing the quantum query complexity of oracle computation. Our results are also related to exact learning in the computational learning theory.",

author = "Andris Ambainis and Kazuo Iwama and Akinori Kawachi and Rudy Raymond and Shigeru Yamashita",

year = "2006",

month = jun,

day = "10",

doi = "10.1007/11683858\_1",

language = "English",

isbn = "3540331328",

series = "Topics in Applied Physics",

pages = "3",

editor = "Hiroshi Imai and Masahito Hayashi",

booktitle = "Quantum Computation and Information",

}

TY - CHAP

T1 - Quantum identification of boolean oracles

AU - Ambainis, Andris

AU - Iwama, Kazuo

AU - Kawachi, Akinori

AU - Raymond, Rudy

AU - Yamashita, Shigeru

PY - 2006/6/10

Y1 - 2006/6/10

N2 - We introduce the Oracle Identification Problem (OIP), which includes many problems in oracle computation such as those of Grover search and Bernstein-Vazirani as its special cases. We give general upper and lower bounds on the number of oracle queries of OIP. Thus, our results provide general frameworks for analyzing the quantum query complexity of oracle computation. Our results are also related to exact learning in the computational learning theory.

AB - We introduce the Oracle Identification Problem (OIP), which includes many problems in oracle computation such as those of Grover search and Bernstein-Vazirani as its special cases. We give general upper and lower bounds on the number of oracle queries of OIP. Thus, our results provide general frameworks for analyzing the quantum query complexity of oracle computation. Our results are also related to exact learning in the computational learning theory.

UR - https://www.scopus.com/pages/publications/33748796358

U2 - 10.1007/11683858_1

DO - 10.1007/11683858_1

M3 - Chapter

AN - SCOPUS:33748796358

SN - 3540331328

SN - 9783540331322

T3 - Topics in Applied Physics

SP - 3

BT - Quantum Computation and Information

A2 - Imai, Hiroshi

A2 - Hayashi, Masahito

ER -

Quantum identification of boolean oracles

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this