We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model.In GRAPH-COLLISION we are given free access to a graph (V, E) and access to a function f : V → {0, 1} as a black box.We are asked to determine if there exist (u, v) ∈ E, such that f (u) = f (v) = 1.In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle.For both of these problems the known lower bounds are trivial (Ω( √ n) and Ω(n), respectively) and there is no known matching upper bound.
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model.In GRAPH-COLLISION we are given free access to a graph (V, E) and access to a function f : V → {0, 1} as a black box.We are asked to determine if there exist (u, v) ∈ E, such that f (u) = f (v) = 1.In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle.For both of these problems the known lower bounds are trivial (Ω( √ n) and Ω(n), respectively) and there is no known matching upper bound.
Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For N-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from O(N3/2) to O(N5/4). However, the best known lower bound has remained the elementary Ω(N) bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that Ω(N13/12) queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.
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. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.
Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: RLS((0, 1)n) = Θ(2n/2n1/2), QLS((0, 1)n) = Θ(2n/3n1/6); RLS([n]d) = Θ(nd/2), ∀ d ≥ 4, QLS([n]d) = Θ(nd/3), ∀ d ≥ 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [2], Ambainis (unpublished) and Santha and Szegedy [20].Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(☂n(log log n)1.5) queries is given. This improves the previous best known upper bound of O(n2/3) (Aaronson, [2]), and implies that Local Search on grids exhibits different properties in low dimensions.
In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for k-vertex cover and k-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small. Our main results are as follows. Parameterized quantum query complexity of vertex cover. In the k-vertex cover problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a vertex cover of size at most k. We show that the quantum query complexity of the k-vertex cover problem is O(√kn + k^{3/2}√n) in the adjacency matrix model. For the design of the quantum query algorithm, we use the method of kernelization, a well-known tool for the design of parameterized classical algorithms, combined with Grover’s search. Parameterized quantum query complexity of matching. In the k-matching problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a matching of size at least k. We show that the quantum query complexity of the k-matching problem is O(√kn + k²) in the adjacency matrix model. We obtain this upper bound by using Grover’s search carefully and analyzing the number of Grover’s searches by making use of potential functions. We also show that the quantum query complexity of the maximum matching problem is O(√pn + p²) where p is the size of the maximum matching. For small p, it improves known bounds Õ(n^{3/2}) for bipartite graphs [Blikstad-v.d.Brand-Efron-Mukhopadhyay-Nanongkai, FOCS 2022] and O(n^{7/4}) for general graphs [Kimmel-Witter, WADS 2021]. Lower bounds on parameterized quantum query complexity. We also present lower bounds on the quantum query complexities of the k-vertex cover and k-matching problems. The lower bounds prove the optimality of the above parameterized quantum query algorithms up to a constant factor when k is small. Indeed, the quantum query complexities of the k-vertex cover and k-matching problems are both Θ(√k n) when k = O(√n) and k = O(n^{2/3}), respectively.
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly.
As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight Ω(N1/4) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was Ω(N1/12) due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of Ω(ΔV) for graphs with m edges, Θ(m) triangles, and constant ΔE, where ΔV and ΔE denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that 1≤ΔV≤m2/3. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.