2015
Exact quantum algorithms have advantage for almost all Boolean functions
AMBAINIS, Andris, Jozef GRUSKA a Shenggen ZHENGZákladní údaje
Originální název
Exact quantum algorithms have advantage for almost all Boolean functions
Autoři
AMBAINIS, Andris (428 Lotyšsko), Jozef GRUSKA (703 Slovensko, domácí) a Shenggen ZHENG (156 Čína, garant, domácí)
Vydání
Quantum Information & Computation, 2015, 1533-7146
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 1.328
Kód RIV
RIV/00216224:14330/15:00084458
Organizační jednotka
Fakulta informatiky
UT WoS
000358188600005
Klíčová slova anglicky
Quantum computing; Quantum query complexity; Boolean function; Symmetric Boolean function; Monotone Boolean function; Read-once Boolean functio n
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 28. 11. 2017 10:26, prof. RNDr. Jozef Gruska, DrSc.
Anotace
V originále
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.
Návaznosti
| EE2.3.30.0009, projekt VaV |
|