Access Restriction

Author Beals, Robert ♦ Buhrman, Harry ♦ Cleve, Richard ♦ Mosca, Michele ♦ de Wolf, Ronald
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Quantum computing ♦ Black-box model ♦ Lower bounds ♦ Polynomial method ♦ Query complexity
Abstract We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on ${0,1}^{N}$ in the $\textit{black-box}$ model. We show that the exponential quantum speed-up obtained for $\textit{partial}$ functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any $\textit{total}$ function: if a quantum algorithm computes some total Boolean function $\textit{f}$ with small error probability using $\textit{T}$ black-box queries, then there is a classical deterministic algorithm that computes $\textit{f}$ exactly with $O(Ts^{6})$ queries. We also give asymptotically tight characterizations of $\textit{T}$ for all symmetric $\textit{f}$ in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 4
Page Count 20
Starting Page 778
Ending Page 797

Open content in new tab

   Open content in new tab
Source: ACM Digital Library