Note on quantum black-box complexity of almost all Boolean functions

Authors
Ambainis, A
Citation
A. Ambainis, Note on quantum black-box complexity of almost all Boolean functions, INF PROCESS, 71(1), 1999, pp. 5-7
Citations number
8
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
71
Issue
1
Year of publication
1999
Pages
5 - 7
Database
ISI
SICI code
0020-0190(19990716)71:1<5:NOQBCO>2.0.ZU;2-Z
Abstract
We show that, for almost all N-variable Boolean functions f, N/4 - O(root N log N) queries are required to compute f in quantum black-box model with b ounded error. (C) 1999 Published by Elsevier Science B.V. All rights reserv ed.