Search Results

Documents authored by Allcock, Jonathan

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.9
On the Quantum Time Complexity of Divide and Conquer

Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.
Cite as

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha. On the Quantum Time Complexity of Divide and Conquer. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{allcock_et_al:LIPIcs.ICALP.2025.9,
  author =	{Allcock, Jonathan and Bao, Jinge and Belovs, Aleksandrs and Lee, Troy and Santha, Miklos},
  title =	{{On the Quantum Time Complexity of Divide and Conquer}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.9},
  URN =		{urn:nbn:de:0030-drops-233863},
  doi =		{10.4230/LIPIcs.ICALP.2025.9},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Divide and Conquer}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.6
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Authors: Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Subset-Sum is an NP-complete problem where one must decide if a multiset of n integers contains a subset whose elements sum to a target value m. The best known classical and quantum algorithms run in time Õ(2^{n/2}) and Õ(2^{n/3}), respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value. Given any modulus p, our data structure can be constructed in time O(np), after which queries can be made in time O(n) to the lists of subsets summing to any value modulo p. We use this data structure in combination with variable-time amplitude amplification and a new quantum pair finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to give an O(2^{0.504n}) quantum algorithm for Shifted-Sums. This provides a notable improvement on the best known O(2^{0.773n}) classical running time established by Mucha et al. [Mucha et al., 2019]. We also study Pigeonhole Equal-Sums, a variant of Equal-Sums where the existence of a solution is guaranteed by the pigeonhole principle. For this problem we give faster classical and quantum algorithms with running time Õ(2^{n/2}) and Õ(2^{2n/5}), respectively.
Cite as

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{allcock_et_al:LIPIcs.ESA.2022.6,
  author =	{Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelh\"{o}fer, Felix and Santha, Miklos},
  title =	{{Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.6},
  URN =		{urn:nbn:de:0030-drops-169444},
  doi =		{10.4230/LIPIcs.ESA.2022.6},
  annote =	{Keywords: Quantum algorithm, classical algorithm, dynamic programming, representation technique, subset-sum, equal-sum, shifted-sum}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact