PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum lower bounds for the collision and the element distinctness problems

Yaoyun Shi

arXiv:quant-ph/0112086v1quant-ph

TL;DR

The paper studies quantum lower bounds for Collision, a problem tied to cryptographic security and the limits of quantum computation. It proves stronger bounds for r-to-one Collision and transfers them to Element Distinctness, while noting an unresolved restricted-range case.

  • Problem

    Collision asks for two distinct oracle inputs with the same output, and its quantum hardness is relevant to cryptography resistant to quantum cryptanalysis.

    Source: §1 · p. 2

  • Method

    The paper proves Collision lower bounds using polynomial properties of quantum-query acceptance probabilities and reductions between collision variants.

    Source: §1 · p. 2, §2.1 · p. 4, §4.1 · p. 7

  • Results

    The resulting Collision lower bound is an improvement over Aaronson’s earlier bound and is stated to be tight.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The Collision result implies a quantum oracle-query lower bound for Element Distinctness, with the same number of comparisons required in the comparisons-only model.

    Source: §1 · p. 3

    The theorem’s general proof uses oracle range [3n/2], so whether the same lower bound holds when the range is restricted to [n] remains open.

    Source: §1 · p. 2

Abstract

from arXiv · show

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, quantum lower bounds for the collision problem would provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function Omega((n/r)^{1/3}) times, where n is the size of the domain and r|n. This improves the previous best lower bound of Omega((n/r)^{1/5}) evaluations due to Aaronson [quant-ph/0111102], and is tight up to a constant factor. Our result also implies a quantum lower bound of Omega(n^{2/3}) queries to the inputs for the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is Omega(sqrt{n}} queries in the black-box model; and Omega(sqrt{n}log{n}) comparisons in the comparisons-only model, due to H{\o}yer, Neerbek, and Shi [ICALP'01, quant-ph/0102078].

1 Introduction and summary of results

The paper establishes stronger quantum lower bounds for Collision and derives a corresponding lower bound for Element Distinctness. These results address limits of quantum computation relevant to cryptography and related quantum problems.

Motivation

  • The result is motivated by the need to understand quantum-computation limits and the possibility of cryptography resistant to quantum cryptanalysis.The paper also connects Collision to hidden subgroup problems and the structure of quantum speed-ups.Source: §1 · p. 2

Collision

  • The collision problem asks for distinct inputs with equal oracle outputs, under a promise that such inputs exist.The paper focuses on the r-to-one version, with r fixed in advance.Source: §1 · p. 2
  • The Collision lower bound is improved to a tight bound for finding collisions in r-to-one functions.The paper contrasts this result with Aaronson’s earlier lower bound and states that the new bound is tight.Source: §1 · p. 2

Scope and limitations

  • The paper leaves open whether its lower bound holds when the oracle range is restricted to [n], because Theorem 1.1 is proved using oracles with range [3n/2].For the small-range case, it reports an improved bound separately.Source: §1 · p. 2

Element Distinctness

  • A reduction from two-to-one Collision to Element Distinctness runs the latter on a random set of Θ(√n) inputs, where the Birthday Paradox yields a collision with high probability.This reduction transfers the Collision lower bound to Element Distinctness.Source: §1 · p. 3
  • The paper derives a quantum oracle-query lower bound for Element Distinctness, and the same number of comparisons is required in the comparisons-only model.Element Distinctness asks whether given real numbers are all distinct.Source: §1 · p. 3

2 Proof outline and previous works

The proof reduces collision lower bounds to structured partial-input problems and polynomial degree arguments, while improving Aaronson’s derived-polynomial approach and connecting the result to black-box quantum lower bounds.

2.1 Proof outline

  • The proof reduces the general collision problem to Half-two-to-one and then establishes a lower bound for that intermediate problem.The half-two-to-one construction fixes one portion of the function as two-to-one while varying whether the remaining portion is one-to-one or two-to-one.Source: §2.1 · pp. 3–4
  • The reduction from the small-range case to range 3n/2 uses symmetry and modifies undefined queried inputs by forcing the algorithm to abort.This partial-input idea extends the polynomial argument to partially defined inputs.Source: §2.1 · p. 4
  • The method symmetrizes the algorithm so its acceptance probability becomes a bounded polynomial in the input parameters, with degree at most 2T.A gap between acceptance probabilities for one-to-one and two-to-one cases then enables approximation-theoretic degree lower bounds.Source: §2.1 · p. 4

2.2 Relation with previous works

  • Aaronson’s derived polynomial method runs the algorithm over distributions parameterized by y and derives an O(T)-degree polynomial from average acceptance probabilities [1].The paper applies and improves this approach for the collision lower bound.Source: §2.2 · p. 4
  • The Half-two-to-one structure creates a central gap where Bernstein’s inequality gives stronger degree bounds than Markov’s inequality, while the new distributions yield exact polynomials.The authors also identify their partial-input technique as apparently new.Source: §2.2 · p. 5
  • The problem is formulated in the black-box model, whose simplicity and power make it a framework for studying many natural quantum computation problems.The paper situates its polynomial and symmetrization techniques among prior quantum lower-bound methods [5, 6, 17, 18, 19, 20].Source: §2.2 · p. 5

3 Preparations for the proofs

The paper formalizes quantum black-box algorithms and expresses their acceptance probabilities as low-degree polynomials of oracle predicates. Quantum query lower bounds then follow by proving that the relevant polynomial degree must be large.

3 Preparations for the proofs

  • A T-query black-box algorithm applies T+1 unitary operators, interleaved with oracle queries, and ends with a projection whose acceptance probability is P(f).The model includes a Hilbert space, an initial state, and an oracle-dependent unitary operation.Source: §3 · pp. 5–6
  • The algorithm computes a Boolean function when its acceptance probability approximates the target value on every promised input, with error bounded by ε.The paper uses error at most 1/3 to define quantum query complexity.Source: §3 · p. 6
  • The acceptance probability P(f) is a polynomial in the oracle predicates δ_i,j, with degree at most 2T [6].This converts quantum query complexity into a polynomial-degree problem.Source: §3 · p. 6
  • Partial functions are represented as subsets of [n]×[N], with domain and image tracked explicitly under permutations of inputs and output values.These definitions support the symmetrization and partial-input arguments used later.Source: §3 · p. 6
  • The proofs lower-bound deg(P) using Markov’s and Bernstein’s inequalities together with Paturi’s theorem for bounded polynomials with a discrete-to-continuous gap.The polynomial is bounded on integer points, while a gap between nearby values forces a degree lower bound.Source: §3 · pp. 6–7

4 Lower bound for the general collision problem

The section reduces the two-to-one collision problem to a half-two-to-one variant, proves a polynomial-degree lower bound for the latter, and extends the argument to arbitrary r-to-one functions.

4.1 The reduction

  • A reduction converts a two-to-one collision algorithm into one for distinguishing half-two-to-one and two-to-one functions, using random permutations and simulated oracle access.The construction separates one-to-one and two-to-one portions and preserves distinguishability through acceptance probabilities.Source: §4.1 · pp. 7–8

4.2 Lower bound for the half-two-to-one problem

  • The half-two-to-one lower bound analyzes the symmetrized acceptance probability of a quantum algorithm as a polynomial in parameters m and g.Valid parameter pairs satisfy 0 ≤ m ≤ n, 2|m, g|m, and, when g = 1, m ≤ n/2.Source: §4.2 · p. 8
  • The symmetrized acceptance polynomial has degree at most 2T for a T-query algorithm, so proving a matching degree lower bound yields a query lower bound.The proof bounds monomial support by the query count and then studies the polynomial on selected parameter values.Source: §4.2 · pp. 8–9

4.3 Generalizing to arbitrary r ≥2

  • The argument generalizes from two-to-one to arbitrary r-to-one functions by replacing half-two-to-one with half-r-to-one and requiring r|m.The r-to-one portion maps to a range of size n/r, while the remaining inputs are handled analogously to the two-to-one construction.Source: §4.3 · p. 9

5 Lower bound for Collision with small range

The small-range collision lower bound uses symmetrization and polynomial degree to constrain the acceptance probability of quantum algorithms.

5 Lower bound for Collision with small range

  • For a T-query algorithm, the symmetrized acceptance probability over partial functions f_m,g is a polynomial in m and g of degree at most 2T.This polynomial representation is the central bridge from quantum query complexity to degree lower bounds.Source: §5 · p. 10
  • The proof of Theorem 1.2 reduces the query lower bound to showing that the relevant polynomial has degree Ω((n/r)^1/4).The theorem's proof invokes Lemma 5.2 and states that the remaining argument parallels the earlier collision lower-bound proof.Source: §5 · p. 10

6 Open problems

The section presents set equality and index erasure as further open problems, emphasizing unresolved lower bounds despite known upper bounds and conjectured difficulty.

6 Open problems

  • The set equality problem distinguishes whether two oracle-defined sets are equal or disjoint and is presented as a special case of the two-to-one problem.It closely models Graph Isomorphism, but the authors report no ω(1) lower bound and conjecture hardness comparable to general Collision.Source: §6 · p. 11
  • The index erasure problem asks for a vector close to a uniform superposition over distinct input values and is equivalent to a quantum-parallel search problem.The supplied passage defines the target state and states the equivalence between the two formulations.Source: §6 · p. 11
  • Grover’s algorithm gives O(√n) queries for both additional problems, while the authors conjecture this bound is tight but cannot prove any ω(1) lower bound.The open status applies to the lower-bound side despite the stated upper bound.Source: §6 · p. 11
Loading quant-ph/0112086v1…