| Identifikační kód | RIV/00216224:14330/15:00084458 |
|---|
| Název v anglickém jazyce | Exact quantum algorithms have advantage for almost all Boolean functions |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 2 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Andris Ambainis (státní příslušnost: LV - Lotyšská republika)
Jozef Gruska (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9594744)
Shenggen Zheng (státní příslušnost: CN - Čínská lidová republika, domácí tvůrce: A) |
|---|
| Popis výsledku v anglickém jazyce | 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 Booleanfunctions 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. |
|---|
| Klíčová slova oddělená středníkem | Quantum computing; Quantum query complexity; Boolean function; Symmetric Boolean function; Monotone Boolean function; Read-once Boolean functio n |
|---|
| Stránka www, na které se nachází výsledek | http://www.rintonpress.com/journals/qiconline.html#v15n56 |
|---|