Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1704.00765 · Quantum

Quantum algorithms for graph connectivity and formula evaluation

Stacey Jeffery, Shelby Kimmel

Published Aug 17, 2017• 32 citations
arXivHTMLPDF

Abstract

We give a new upper bound on the quantum query complexity of deciding s t -connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for s t -connectivity to Boolean formula evaluation problems, we match the O ( N ) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this s t -connectivity-based approach may be the "right" way of looking at quantum algorithms for formula evaluation.

DOI
10.22331/q-2017-08-17-26

Related papers

Quantum Algorithms for Connectivity and Related Problems

Michael Jarret, Stacey Jeffery, Shelby Kimmel +1 more

An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.

arXiv:1804.10591•Leibniz international proceedings in informatics•Jan 1, 2018•22 citations

Quantum Adversary (Upper) Bound

Shelby Kimmel

We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound.This nonconstructive method can give an upper bound on query complexity without producing an algorithm.For example, we describe an oracle problem which we prove (nonconstructively) can be solved in O(1) queries, where the previous best quantum algorithm uses a polylogarithmic number of queries.We then give an explicit O(1)-query algorithm for this problem based on span programs.

arXiv:1101.0797•Chicago Journal of Theoretical Computer Science•Jan 1, 2013•28 citations

Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure

Bohua Zhan, Shelby Kimmel, Avinatan Hassidim

We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed inputs, our algorithm can evaluate a depth n tree using O(n2+logω) queries, where ω is independent of n and depends only on the type of subformulas within the tree. We also prove a classical lower bound of nΩ(log log n) queries, thus showing a (small) super-polynomial speed-up.

arXiv:1101.0796•Conference on Innovations in Theoretical Computer Science•Jan 8, 2012•24 citations

Efficient algorithms in quantum query complexity

Robin Kothari

In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

•Aug 13, 2014•26 citations

Span programs and quantum query algorithms.

Ben W. Reichardt

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semidefinite program that lower-bounds quantum query complexity. By giving a matching quantum algorithm, we show that the general adversary lower bound is tight for every boolean function. The proof is based on span programs, a linear-algebraic computational model without inherent dynamics. Span programs correspond to solutions to the dual semi-definite program, and to bipartite graphs. The analysis shows that properties of eigenvalue-zero eigenvectors of the graphs in fact imply an “effective” spectral gap around zero We thus develop a quantum algorithm for evaluating span programs. It follows that span programs, measured by witness size, and quantum algorithms, measured by query complexity, are equivalent computational models, up to a constant factor. The result efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It also implies that the quantum query complexity of the composition f ◦ (g, . . . , g) of two boolean functions matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. The algorithm alternates a fixed reflection with input queries. Originally introduced for solving the unstructured search problem, this structure is therefore a universal feature of quantum query algorithms. We give a second algorithm for evaluating span programs that has the further potential to be time-efficient. Subsequent applications have derived nearly time-optimal quantum algorithms for evaluating many read-once formulas. Span programs may have promise for developing more quantum algorithms.

Electronic colloquium on computational complexity•Jan 1, 2010•9 citations

Classical-Quantum Separations in Minimal Query Complexity of Boolean Functions.

Chandra Sekhar Mukherjee, Subhamoy Maitra

Query complexity is a model of computation in which functions are evaluated by making queries to the variables. In a very recent paper [Physical Review A 101, 022325 (2020)], Chen, Ye and Li provided a characterization of exact one-query quantum algorithms. We first note that this result is an immediate corollary of what was proved five years back by Montanaro, Jozsa and Mitchison [Algorithmica 71, pp. 775-796 (2015)]. Further, in this model, we concentrate on understanding the differences between classical and quantum computation in terms of number of influencing variables of a function given lowest query complexity in the classical domain. We explore the parity decision tree model to portray possible separations between classical and quantum computations in specific cases. Our results classify different classes of Boolean functions on $n$-variables ($n$ being a function of $k$), that can be evaluated (i) with exactly $k$ queries in both classical and exact quantum model or (ii) with $k$ queries in classical model and $(k-1)$ queries in exact quantum model.

•Apr 27, 2020•0 citations
We give a new upper bound on the quantum query complexity of deciding s t -connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for s t -connectivity to Boolean formula evaluation problems, we match the O ( N ) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this s t -connectivity-based approach may be the "right" way of looking at quantum algorithms for formula evaluation.
An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound.This nonconstructive method can give an upper bound on query complexity without producing an algorithm.For example, we describe an oracle problem which we prove (nonconstructively) can be solved in O(1) queries, where the previous best quantum algorithm uses a polylogarithmic number of queries.We then give an explicit O(1)-query algorithm for this problem based on span programs.
In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.
Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semidefinite program that lower-bounds quantum query complexity. By giving a matching quantum algorithm, we show that the general adversary lower bound is tight for every boolean function. The proof is based on span programs, a linear-algebraic computational model without inherent dynamics. Span programs correspond to solutions to the dual semi-definite program, and to bipartite graphs. The analysis shows that properties of eigenvalue-zero eigenvectors of the graphs in fact imply an “effective” spectral gap around zero We thus develop a quantum algorithm for evaluating span programs. It follows that span programs, measured by witness size, and quantum algorithms, measured by query complexity, are equivalent computational models, up to a constant factor. The result efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It also implies that the quantum query complexity of the composition f ◦ (g, . . . , g) of two boolean functions matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. The algorithm alternates a fixed reflection with input queries. Originally introduced for solving the unstructured search problem, this structure is therefore a universal feature of quantum query algorithms. We give a second algorithm for evaluating span programs that has the further potential to be time-efficient. Subsequent applications have derived nearly time-optimal quantum algorithms for evaluating many read-once formulas. Span programs may have promise for developing more quantum algorithms.
Query complexity is a model of computation in which functions are evaluated by making queries to the variables. In a very recent paper [Physical Review A 101, 022325 (2020)], Chen, Ye and Li provided a characterization of exact one-query quantum algorithms. We first note that this result is an immediate corollary of what was proved five years back by Montanaro, Jozsa and Mitchison [Algorithmica 71, pp. 775-796 (2015)]. Further, in this model, we concentrate on understanding the differences between classical and quantum computation in terms of number of influencing variables of a function given lowest query complexity in the classical domain. We explore the parity decision tree model to portray possible separations between classical and quantum computations in specific cases. Our results classify different classes of Boolean functions on nnn-variables (nnn being a function of kkk), that can be evaluated (i) with exactly kkk queries in both classical and exact quantum model or (ii) with kkk queries in classical model and (k−1)(k-1)(k−1) queries in exact quantum model.