Matching Triangles and Triangle Collection: Hardness based on a Weak
Quantum Conjecture
- URL: http://arxiv.org/abs/2207.11068v1
- Date: Fri, 22 Jul 2022 13:16:50 GMT
- Title: Matching Triangles and Triangle Collection: Hardness based on a Weak
Quantum Conjecture
- Authors: Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian
Speelman
- Abstract summary: We show that an $n1.5-epsilon$ time quantum algorithm for either of these two graph problems would imply faster quantum algorithms for k-SAT, 3SUM, and APSP.
We also present quantum algorithms that require careful use of data structures and Ambainis' variable time search.
- Score: 0.8924669503280332
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Classically, for many computational problems one can conclude time lower
bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM
and APSP. More recently, similar results have been derived in the quantum
setting conditioned on the hardness of k-SAT and 3SUM. This is done using
fine-grained reductions, where the approach is to (1) select a key problem $X$
that, for some function $T$, is conjectured to not be solvable by any
$O(T(n)^{1-\epsilon})$ time algorithm for any constant $\epsilon > 0$ (in a
fixed model of computation), and (2) reduce $X$ in a fine-grained way to these
computational problems, thus giving (mostly) tight conditional time lower
bounds for them.
Interestingly, for Delta-Matching Triangles and Triangle Collection,
classical hardness results have been derived conditioned on hardness of all
three mentioned key problems. More precisely, it is proven that an
$n^{3-\epsilon}$ time classical algorithm for either of these two graph
problems would imply faster classical algorithms for k-SAT, 3SUM and APSP,
which makes Delta-Matching Triangles and Triangle Collection worthwhile to
study.
In this paper, we show that an $n^{1.5-\epsilon}$ time quantum algorithm for
either of these two graph problems would imply faster quantum algorithms for
k-SAT, 3SUM, and APSP. We first formulate a quantum hardness conjecture for
APSP and then present quantum reductions from k-SAT, 3SUM, and APSP to
Delta-Matching Triangles and Triangle Collection. Additionally, based on the
quantum APSP conjecture, we are also able to prove quantum lower bounds for a
matrix problem and many graph problems. The matching upper bounds follow
trivially for most of them, except for Delta-Matching Triangles and Triangle
Collection for which we present quantum algorithms that require careful use of
data structures and Ambainis' variable time search.
Related papers
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT [0.0]
This paper introduces a family of structured quantum search algorithms, termed $k$-local quantum search.
We prove that the max-$k$-SSAT is on average if $m=Omega(n2+epsilon)$ based on the average-case complexity theory.
arXiv Detail & Related papers (2024-03-05T15:03:47Z) - Using 1-Factorization from Graph Theory for Quantum Speedups on Clique
Problems [0.0]
We provide new Quantum oracle designs based on the 1-factorization of complete graphs.
We also discuss the usage of one of these oracles in bringing the Triangle Finding time complexity down to $O(n2.25 poly(log n))$.
arXiv Detail & Related papers (2023-08-31T15:59:35Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems.
The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
arXiv Detail & Related papers (2023-06-07T12:19:22Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor $w$, where $w$ is the computer word size.
We show that a simple bit-parallel algorithm on such restricted family of graphs can indeed be converted into a realistic quantum algorithm.
arXiv Detail & Related papers (2023-02-06T15:14:34Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks [0.0]
We prove optimal lower-bounds on the time complexity of quantum algorithms for several computational problems.
Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup.
arXiv Detail & Related papers (2021-06-03T17:22:08Z) - Quantum algorithm of a set of quantum 2-sat problem [0.0]
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem.
For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain.
arXiv Detail & Related papers (2020-09-05T21:01:27Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.