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

Department of Computer Science

University of Waterloo

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

10 Citations (Scopus)

Abstract

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

Original language	English
Pages (from-to)	403-412
Number of pages	10
Journal	Theory of Computing
Volume	11
DOIs	https://doi.org/10.4086/toc.2015.v011a016
Publication status	Published - 29 Dec 2015

Keywords

Boolean functions
Monotonicity
Property testing
Quantum query complexity

Access to Document

10.4086/toc.2015.v011a016

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this