Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/137663
Title: Adversary lower bounds for the collision and the set equality problems
Authors: Belovs, Aleksandrs
Rosmanis, Ansis
Keywords: Science::Physics
Issue Date: 2017
Source: Belovs, A., & Rosmanis, A. (2017). Adversary lower bounds for the collision and the set equality problems. Quantum Information and Computation, 18(3-4).
Journal: Quantum Information and Computation
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.
URI: https://hdl.handle.net/10356/137663
ISSN: 1533-7146
Rights: © 2017 Rinton Press. All rights reserved. This paper was published in Quantum Information and Computation and is made available with permission of Rinton Press.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Adversary lower bounds for the collision and the set equality problems.pdf317.57 kBAdobe PDFView/Open

Page view(s)

106
Updated on Feb 5, 2023

Download(s) 50

38
Updated on Feb 5, 2023

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.