Abboud, Amir
FineGrained Reductions and Quantum Speedups for Dynamic Programming
Abstract
This paper points at a connection between certain (classical) finegrained reductions and the question: Do quantum algorithms offer an advantage for problems whose (classical) best solution is via dynamic programming?
A remarkable recent result of Ambainis et al. [SODA 2019] indicates that the answer is positive for some fundamental problems such as SetCover and Travelling Salesman. They design a quantum O^*(1.728^n) time algorithm whereas the dynamic programming O^*(2^n) time algorithms are conjectured to be classically optimal. In this paper, finegrained reductions are extracted from their algorithms giving the first lower bounds for problems in P that are based on the intriguing SetCover Conjecture (SeCoCo) of Cygan et al. [CCC 2010].
In particular, the SeCoCo implies:
 a superlinear Omega(n^{1.08}) lower bound for 3SUM on n integers,
 an Omega(n^{k/(c_k)epsilon}) lower bound for kSUM on n integers and kClique on nnode graphs, for any integer k >= 3, where c_k <= log_2{k}+1.4427.
While far from being tight, these lower bounds are significantly stronger than what is known to follow from the Strong Exponential Time Hypothesis (SETH); the wellknown n^{Omega(k)} ETHbased lower bounds for kClique and kSUM are vacuous when k is constant.
Going in the opposite direction, this paper observes that some "sequential" problems with previously known finegrained reductions to a "parallelizable" core also enjoy quantum speedups over their classical dynamic programming solutions. Examples include RNA Folding and LeastWeight Subsequence.
BibTeX  Entry
@InProceedings{abboud:LIPIcs:2019:10584,
author = {Amir Abboud},
title = {{FineGrained Reductions and Quantum Speedups for Dynamic Programming}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {8:18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10584},
URN = {urn:nbn:de:0030drops105846},
doi = {10.4230/LIPIcs.ICALP.2019.8},
annote = {Keywords: FineGrained Complexity, SetCover, 3SUM, kClique, kSUM, Dynamic Programming, Quantum Algorithms}
}
04.07.2019
Keywords: 

FineGrained Complexity, SetCover, 3SUM, kClique, kSUM, Dynamic Programming, Quantum Algorithms 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 