Exact quantum algorithms have advantage for almost all Boolean functions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00084458" target="_blank" >RIV/00216224:14330/15:00084458 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.rintonpress.com/journals/qiconline.html#v15n56" target="_blank" >http://www.rintonpress.com/journals/qiconline.html#v15n56</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Exact quantum algorithms have advantage for almost all Boolean functions

Popis výsledku v původní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.

Název v anglickém jazyce

Exact quantum algorithms have advantage for almost all Boolean functions

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Quantum Information & Computation

ISSN

1533-7146

e-ISSN

—

Svazek periodika

15

Číslo periodika v rámci svazku

5-6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

435-452

Kód UT WoS článku

000358188600005

EID výsledku v databázi Scopus

—