Exact quantum algorithms have advantage for almost all Boolean functions

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

AMBAINIS Andris GRUSKA Jozef ZHENG Shenggen

Rok publikování 2015
Druh Článek v odborném periodiku
Časopis / Zdroj Quantum Information & Computation
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.rintonpress.com/journals/qiconline.html#v15n56
Obor Informatika
Klíčová slova Quantum computing; Quantum query complexity; Boolean function; Symmetric Boolean function; Monotone Boolean function; Read-once Boolean functio n
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info