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.
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.
The problem Local Search, 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 both the randomized and the 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: $\text{{\it RLS\/}}(\{0,1\}^n)=\Theta(2^{n/2}n^{1/2})$, $\text{{\it QLS\/}}(\{0,1\}^n)=\Theta(2^{n/3}n^{1/6})$, $\text{{\it RLS\/}}([n]^d)=\Theta(n^{d/2})$ for d≥4, $\text{{\it QLS\/}}([n]^d)=\Theta(n^{d/3})$ for d≥6. Here $\text{{\it RLS\/}}(G)$ and $\text{{\it QLS\/}}(G)$ are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494–501]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(n(loglogn)1.5) queries is given. This improves the previously best known upper bound of O(n2/3) (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474]), and implies that Local Search on grids exhibits different properties in low dimensions.
The 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 many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube $\B^n$, the randomized query complexity of Local Search is Θ(2n/2n1/2) and the quantum query complexity is Θ(2n/3n1/6). We also show that for the constant dimensional grid [N1/d]d, the randomized query complexity is Θ(N1/2) for d≥4 and the quantum query complexity is Θ(N1/3) for d≥6. New lower bounds for lower dimensional grids are also given. These improve the previous results by Aaronson [STOC'04], and Santha and Szegedy [STOC'04]. Finally we show for [N1/2]2 a new upper bound of O(N1/4(loglogN)3/2) on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions.
We study the problem of \emph{local search} on a graph. Given a real-valued black-box function f on the graph's vertices, this is the problem of determining a local minimum of f---a vertex v for which f(v) is no more than f evaluated at any of v's neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires Ω(2n/2−o(n)) queries to determine a local minima on the n-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to Ω(2n/2/n2) and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph G of N vertices and diameter d, the randomized and quantum query complexities for local search on G are Ω(N/dlogN) and Ω(4N/dlogN), respectively.
The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}n, we show a lower bound of Ω(2n/4/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of Ω(2n/2/n2) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension d≥3.
The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (BMPV), answering a longstanding open question in quantum query complexity. For n×n matrices, our upper bound is O(n17/12), improving on the standard O(n3/2) bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an Ω(n5/4) lower bound, which improves over the previous best known lower bound of Ω(n19/18) by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors (OV), which asks whether an indexed list of n Boolean vectors of dimension n contains two vectors with disjoint supports. In particular, we prove equivalences between OV and BMPV and establish the above bounds for OV. We also prove a tight Θ(n3/2) bound for a variant of BMPV that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.