Další formáty:
BibTeX
LaTeX
RIS
@article{1315563,
author = {Ambainis, Andris and Gruska, Jozef and Zheng, Shenggen},
article_number = {5-6},
keywords = {Quantum computing; Quantum query complexity; Boolean function; Symmetric Boolean function; Monotone Boolean function; Read-once Boolean functio n},
language = {eng},
issn = {1533-7146},
journal = {Quantum Information & Computation},
title = {Exact quantum algorithms have advantage for almost all Boolean functions},
url = {http://www.rintonpress.com/journals/qiconline.html#v15n56},
volume = {15},
year = {2015}
}
TY - JOUR
ID - 1315563
AU - Ambainis, Andris - Gruska, Jozef - Zheng, Shenggen
PY - 2015
TI - Exact quantum algorithms have advantage for almost all Boolean functions
JF - Quantum Information & Computation
VL - 15
IS - 5-6
SP - 435-452
EP - 435-452
SN - 15337146
KW - Quantum computing
KW - Quantum query complexity
KW - Boolean function
KW - Symmetric Boolean function
KW - Monotone Boolean function
KW - Read-once Boolean functio n
UR - http://www.rintonpress.com/journals/qiconline.html#v15n56
L2 - http://www.rintonpress.com/journals/qiconline.html#v15n56
N2 - It has been proved that almost all n-bit Boolean functions have exact classical query complexity n. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all n-bit Boolean functions can be computed by an exact quantum algorithm with less than n queries. More exactly, we prove that ANDn is the only n-bit Boolean function, up to isomorphism, that requires n queries.
ER -
AMBAINIS, Andris, Jozef GRUSKA a Shenggen ZHENG. Exact quantum algorithms have advantage for almost all Boolean functions. \textit{Quantum Information \&{} Computation}. 2015, roč.~15, 5-6, s.~435-452. ISSN~1533-7146.
|
