License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2021.1
URN: urn:nbn:de:0030-drops-139961
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13996/
Go to the corresponding LIPIcs Volume Portal

Hamoudi, Yassine ; Magniez, Frédéric

Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs

pdf-format:
LIPIcs-TQC-2021-1.pdf (0.8 MB)

Abstract

We study the problem of finding K collision pairs in a random function f : [N] → [N] by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using S qubits of memory must perform a number T of queries that satisfies the tradeoff T³ S ≥ Ω(K³N). Classically, the same question has only been settled recently by Dinur [Dinur, 2020], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener [Oorschot and Wiener, 1999] achieves the optimal time-space tradeoff of T² S = Θ(K² N). Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry’s recording query technique [Zhandry, 2019] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time-space tradeoff T² S ≥ Ω(N³) for sorting N numbers on a quantum computer, which was first obtained by Klauck, Špalek and de Wolf [Klauck et al., 2007].

BibTeX - Entry

@InProceedings{hamoudi_et_al:LIPIcs.TQC.2021.1,
  author =	{Hamoudi, Yassine and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13996},
  URN =		{urn:nbn:de:0030-drops-139961},
  doi =		{10.4230/LIPIcs.TQC.2021.1},
  annote =	{Keywords: Quantum computing, query complexity, lower bound, time-space tradeoff}
}

Keywords: Quantum computing, query complexity, lower bound, time-space tradeoff
Collection: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Issue Date: 2021
Date of publication: 22.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI