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.
|