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

Department of Computer Science

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

5 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	198-222
Number of pages	25
Journal	Quantum Information and Computation
Volume	18
Issue number	3-4
DOIs	https://doi.org/10.26421/qic18.3-4-2
Publication status	Published - Mar 2018

Keywords

Quantum query complexity
Representation theory
Symmetric group

Access to Document

10.26421/qic18.3-4-2

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this