Quantum algorithm for monotonicity testing on the hypercube

Aleksandrs Belovs; Eric Blais

doi:10.4086/toc.2015.v011a016

Quantum algorithm for monotonicity testing on the hypercube

Aleksandrs Belovs
, Eric Blais

Datorikas nodaļa

University of Waterloo

Pētījuma izpildes rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

10 Atsauces (Scopus)

Kopsavilkums

In this note, we develop a bounded-error quantum algorithm that makes Õ (n^1/4 ε^-1/2) queries to a function f: {0, 1}ⁿ→ {0, 1}, accepts when f is monotone, and rejects when f is ε-far from being monotone. This result gives a super-quadratic improvement compared to the best known randomized algorithm for all ε = o(1). The improvement is cubic when ε = 1/(Formula Presented).

Oriģinālvaloda	Angļu
Lapas (no-līdz)	403-412
Lapu skaits	10
Žurnāls	Theory of Computing
Sējums	11
DOIs	https://doi.org/10.4086/toc.2015.v011a016
Publikācijas statuss	Publicēts - 29 dec. 2015

Piekļuve Dokumentiem

10.4086/toc.2015.v011a016

Citi faili un saites

Saite uz publikāciju Scopus

Citēt šo

@article{aa03ed3bc4874e00b7281d90447d4f44,

title = "Quantum algorithm for monotonicity testing on the hypercube",

abstract = "In this note, we develop a bounded-error quantum algorithm that makes {\~O} (n1/4 ε-1/2) queries to a function f: \{0, 1\}n→ \{0, 1\}, accepts when f is monotone, and rejects when f is ε-far from being monotone. This result gives a super-quadratic improvement compared to the best known randomized algorithm for all ε = o(1). The improvement is cubic when ε = 1/(Formula Presented).",

keywords = "Boolean functions, Monotonicity, Property testing, Quantum query complexity",

author = "Aleksandrs Belovs and Eric Blais",

note = "Publisher Copyright: {\textcopyright} 2015 Aleksandrs Belovs and Eric Blais.",

year = "2015",

month = dec,

day = "29",

doi = "10.4086/toc.2015.v011a016",

language = "English",

volume = "11",

pages = "403--412",

journal = "Theory of Computing",

issn = "1557-2862",

publisher = "University of Chicago, Department of Computer Science",

}

TY - JOUR

T1 - Quantum algorithm for monotonicity testing on the hypercube

AU - Belovs, Aleksandrs

AU - Blais, Eric

PY - 2015/12/29

Y1 - 2015/12/29

N2 - In this note, we develop a bounded-error quantum algorithm that makes Õ (n1/4 ε-1/2) queries to a function f: {0, 1}n→ {0, 1}, accepts when f is monotone, and rejects when f is ε-far from being monotone. This result gives a super-quadratic improvement compared to the best known randomized algorithm for all ε = o(1). The improvement is cubic when ε = 1/(Formula Presented).

AB - In this note, we develop a bounded-error quantum algorithm that makes Õ (n1/4 ε-1/2) queries to a function f: {0, 1}n→ {0, 1}, accepts when f is monotone, and rejects when f is ε-far from being monotone. This result gives a super-quadratic improvement compared to the best known randomized algorithm for all ε = o(1). The improvement is cubic when ε = 1/(Formula Presented).

KW - Boolean functions

KW - Monotonicity

KW - Property testing

KW - Quantum query complexity

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

U2 - 10.4086/toc.2015.v011a016

DO - 10.4086/toc.2015.v011a016

M3 - Article

AN - SCOPUS:84979229892

SN - 1557-2862

VL - 11

SP - 403

EP - 412

JO - Theory of Computing

JF - Theory of Computing

ER -

Quantum algorithm for monotonicity testing on the hypercube

Kopsavilkums

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo