Exact quantum algorithms have advantage for almost all boolean functions

Andris Ambainis; Jozef Gruska; Shenggen Zheng

Exact quantum algorithms have advantage for almost all boolean functions

Andris Ambainis
, Jozef Gruska
, Shenggen Zheng^*

^*Corresponding author for this work

Department of Computer Science

Institute for Advanced Studies
Masaryk University

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	435-452
Number of pages	18
Journal	Quantum Information and Computation
Volume	15
Issue number	5-6
Publication status	Published - 1 Apr 2015

Keywords

Boolean function
Monotone Boolean function
Quantum computing
Quantum query complexity
Read-once Boolean function
Sym-metric Boolean function

Cite this

@article{c2da8d18693e479d8b043f5f7a30a8f7,

title = "Exact quantum algorithms have advantage for almost all boolean functions",

abstract = "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.",

keywords = "Boolean function, Monotone Boolean function, Quantum computing, Quantum query complexity, Read-once Boolean function, Sym-metric Boolean function",

author = "Andris Ambainis and Jozef Gruska and Shenggen Zheng",

note = "Publisher Copyright: {\textcopyright} Rinton Press.",

year = "2015",

month = apr,

day = "1",

language = "English",

volume = "15",

pages = "435--452",

journal = "Quantum Information and Computation",

issn = "1533-7146",

publisher = "Sciendo",

number = "5-6",

}

TY - JOUR

T1 - Exact quantum algorithms have advantage for almost all boolean functions

AU - Ambainis, Andris

AU - Gruska, Jozef

AU - Zheng, Shenggen

N1 - Publisher Copyright: © Rinton Press.

PY - 2015/4/1

Y1 - 2015/4/1

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.

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

KW - Boolean function

KW - Monotone Boolean function

KW - Quantum computing

KW - Quantum query complexity

KW - Read-once Boolean function

KW - Sym-metric Boolean function

UR - https://www.scopus.com/pages/publications/84920407782

M3 - Article

AN - SCOPUS:84920407782

SN - 1533-7146

VL - 15

SP - 435

EP - 452

JO - Quantum Information and Computation

JF - Quantum Information and Computation

IS - 5-6

ER -

Exact quantum algorithms have advantage for almost all boolean functions

Abstract

Keywords

Other files and links

Fingerprint

Cite this