A note on the quantum collision and set equality problems

Research output: Contribution to journalArticle

39 Scopus citations

Abstract

A collision for a function f is two distinct inputs x1 ≠ x2 such that f outputs the same value on both inputs: f(x1) = f(x2). The quantum query complexity of finding collisions has been shown [9, 2, 4, 11] in some settings to be (formula presented)(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to r-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of (formula presented)(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

Original languageEnglish (US)
Pages (from-to)557-567
Number of pages11
JournalQuantum Information and Computation
Volume15
Issue number7-8
StatePublished - Jan 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistical and Nonlinear Physics
  • Nuclear and High Energy Physics
  • Mathematical Physics
  • Physics and Astronomy(all)
  • Computational Theory and Mathematics

Keywords

  • Quantum collision problem
  • Random functions

Fingerprint Dive into the research topics of 'A note on the quantum collision and set equality problems'. Together they form a unique fingerprint.

  • Cite this