Adversary lower bounds for the collision and the set equality problems

Aleksandrs Belovs; Ansis Rosmanis

doi:10.26421/qic18.3-4-2

Adversary lower bounds for the collision and the set equality problems

Aleksandrs Belovs
, Ansis Rosmanis

Datorikas nodaļa

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

5 Atsauces (Scopus)

Kopsavilkums

We prove tight Ω(n^1/3) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.

Oriģinālvaloda	Angļu
Lapas (no-līdz)	198-222
Lapu skaits	25
Žurnāls	Quantum Information and Computation
Sējums	18
Izdevuma numurs	3-4
DOIs	https://doi.org/10.26421/qic18.3-4-2
Publikācijas statuss	Publicēts - marts 2018

Piekļuve Dokumentiem

10.26421/qic18.3-4-2

Citi faili un saites

Saite uz publikāciju Scopus

Citēt šo

@article{587b6adee4e546c9b76d11777f1e9051,

title = "Adversary lower bounds for the collision and the set equality problems",

abstract = "We prove tight Ω(n1/3) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.",

keywords = "Quantum query complexity, Representation theory, Symmetric group",

author = "Aleksandrs Belovs and Ansis Rosmanis",

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

year = "2018",

month = mar,

doi = "10.26421/qic18.3-4-2",

language = "English",

volume = "18",

pages = "198--222",

journal = "Quantum Information and Computation",

issn = "1533-7146",

publisher = "Sciendo",

number = "3-4",

}

TY - JOUR

T1 - Adversary lower bounds for the collision and the set equality problems

AU - Belovs, Aleksandrs

AU - Rosmanis, Ansis

N1 - Publisher Copyright: © Rinton Press.

PY - 2018/3

Y1 - 2018/3

N2 - We prove tight Ω(n1/3) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.

AB - We prove tight Ω(n1/3) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.

KW - Quantum query complexity

KW - Representation theory

KW - Symmetric group

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

U2 - 10.26421/qic18.3-4-2

DO - 10.26421/qic18.3-4-2

M3 - Article

AN - SCOPUS:85045068112

SN - 1533-7146

VL - 18

SP - 198

EP - 222

JO - Quantum Information and Computation

JF - Quantum Information and Computation

IS - 3-4

ER -

Adversary lower bounds for the collision and the set equality problems

Kopsavilkums

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo