RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC

Recovering unknown inputs in oracles with as few queries as possible is one of the most basic problems in theoretical computer science. In this paper, we survey the classical and quantum query complexity of this problem for various types of oracles with different types of queries.

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2013-11, Vol.24 (7), p.979-993
Main Authors: IWAMA, KAZUO, NISHIMURA, HARUMICHI
Format: Article
Language:English
Subjects:
Queries
Strings
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recovering unknown inputs in oracles with as few queries as possible is one of the most basic problems in theoretical computer science. In this paper, we survey the classical and quantum query complexity of this problem for various types of oracles with different types of queries.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054113400261