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:1309.7713

Span-program-based quantum algorithm for tree detection

Guoming Wang

Published Sep 30, 2013• 3 citations
arXivHTMLPDF

Abstract

Span program is a linear-algebraic model of computation originally proposed for studying the complexity theory. Recently, it has become a useful tool for designing quantum algorithms. In this paper, we present a time-efficient span-program-based quantum algorithm for the following problem. Let $T$ be an arbitrary tree. Given query access to the adjacency matrix of a graph $G$ with $n$ vertices, we need to determine whether $G$ contains $T$ as a subgraph, or $G$ does not contain $T$ as a minor, under the promise that one of these cases holds. We call this problem the subgraph/not-a-minor problem for $T$. We show that this problem can be solved by a bounded-error quantum algorithm with $O(n)$ query complexity and $\tilde{O}(n)$ time complexity. The query complexity is optimal, and the time complexity is tight up to polylog factors.

DOI
10.48550/arxiv.1309.7713

Related papers

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

Time- and Query-optimal Quantum Algorithms Based on Decision Trees

Salman Beigi, Leila Taghavi, Artin Tajdini

It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O( √ GT where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [ 3 , 14 ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (√ GT ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time O(n 3/2 log 2 n ) and with O(n 3/2 ) quantum queries. Moreover, finding a maximal matching can be solved with O(n 3/2 ) quantum queries in time O(n 3/2 log 2 n ), and maximum bipartite matching can be solved in time O(n 2 log 2 n ).

arXiv:2105.08309•ACM Transactions on Quantum Computing•Mar 28, 2022•8 citations

Span Programs and Quantum Time Complexity

Arjan Cornelissen, Stacey Jeffery, Māris Ozols +1 more

Span programs are an important model of quantum computation due to their tight correspondence with quantum query complexity. For any decision problem $f$, the minimum complexity of a span program for $f$ is equal, up to a constant factor, to the quantum query complexity of $f$. Moreover, this correspondence is constructive. A span program for $f$ with complexity $C$ can be compiled into a bounded error quantum algorithm for $f$ with query complexity $O(C)$, and vice versa. In this work, we prove an analogous connection for quantum time complexity. In particular, we show how to convert a quantum algorithm for $f$ with time complexity $T$ into a span program for $f$ such that it compiles back into a quantum algorithm for $f$ with time complexity $\widetilde{O}(T)$. While the query complexity of quantum algorithms obtained from span programs is well-understood, it is not generally clear how to implement certain query-independent operations in a time-efficient manner. We show that for span programs derived from algorithms with a time-efficient implementation, we can preserve the time efficiency when implementing the span program. This means in particular that span programs not only fully capture quantum query complexity, but also quantum time complexity. One practical advantage of being able to convert quantum algorithms to span programs in a way that preserves time complexity is that span programs compose very nicely. We demonstrate this by improving Ambainis's variable-time quantum search result using our construction through a span program composition for the OR function.

arXiv:2005.01323•Leibniz international proceedings in informatics•Jan 1, 2020•17 citations

Quantum algorithms for path and cycle containment problems

Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro

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 $\widetilde{O}(n^{3/2-α_k})$, where $α_k \in Θ(c^{-k})$ and $c = \sqrt{3+\sqrt{17}}/2 \approx 1.33$, beating the previous best upper bound $O(n^{3/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(\sqrt{n})$ query algorithm.

quant-pharXiv:2605.09017•Leibniz international proceedings in informatics•May 12, 2026•5 citations

Quantum Query Complexity of Some Graph Problems

Christoph Dürr, Mark Heiligman, Peter Høyer +1 more

Quantum algorithms for graph problems are considered, both in the adjacency matrix model and in an adjacency list-like array model. We give almost tight lower and upper bounds for the bounded error quantum query complexity of Connectivity, Strong Connectivity, Minimum Spanning Tree, and Single Source Shortest Paths. For example, we show that the query complexity of Minimum Spanning Tree is in $\Theta(n^{3/2})$ in the matrix model and in $\Theta(\sqrt{nm})$ in the array model, while the complexity of Connectivity is also in $\Theta(n^{3/2})$ in the matrix model but in $\Theta(n)$ in the array model. The upper bounds utilize search procedures for finding minima of functions under various conditions.

arXiv:quant-ph/0401091•SIAM Journal on Computing•Jan 1, 2006•190 citations

Approximate Span Programs

Tsuyoshi Ito, Stacey Jeffery

Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. It is known that for any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity, however finding such an algorithm is generally challenging. We consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a function f can also be used to decide “threshold” versions of the function f, or more generally, approximate a quantity called the span program witness size, which is some property of the input related to f. We achieve these results by relaxing the requirement that 1-inputs hit some target exactly in the span program, which could potentially make design of span programs significantly easier. In addition, we give an exposition of span program structure, which increases the general understanding of this important model. One implication of this is alternative algorithms for estimating the witness size when the phase gap of a certain unitary can be lower bounded. We show how to lower bound this phase gap in certain cases. As an application, we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, $$R_{s,t}(G)$$ . For this problem we obtain $$\widetilde{O}(\frac{1}{\varepsilon ^{3/2}}n\sqrt{R_{s,t}(G)})$$ , using $$O(\log n)$$ space. In addition, when $$\mu $$ is a lower bound on $$\lambda _2(G)$$ , by our phase gap lower bound, we can obtain an upper bound of $$\widetilde{O}\left( \frac{1}{\varepsilon }n\sqrt{R_{s,t}(G)/\mu }\right) $$ for estimating effective resistance, also using $$O(\log n)$$ space.

arXiv:1507.00432•Algorithmica•Nov 14, 2018•28 citations
Span program is a linear-algebraic model of computation originally proposed for studying the complexity theory. Recently, it has become a useful tool for designing quantum algorithms. In this paper, we present a time-efficient span-program-based quantum algorithm for the following problem. Let TTT be an arbitrary tree. Given query access to the adjacency matrix of a graph GGG with nnn vertices, we need to determine whether GGG contains TTT as a subgraph, or GGG does not contain TTT as a minor, under the promise that one of these cases holds. We call this problem the subgraph/not-a-minor problem for TTT. We show that this problem can be solved by a bounded-error quantum algorithm with O(n)O(n)O(n) query complexity and O~(n)\tilde{O}(n)O~(n) time complexity. The query complexity is optimal, and the time complexity is tight up to polylog factors.
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.
It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O( √ GT where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [ 3 , 14 ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (√ GT ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time O(n 3/2 log 2 n ) and with O(n 3/2 ) quantum queries. Moreover, finding a maximal matching can be solved with O(n 3/2 ) quantum queries in time O(n 3/2 log 2 n ), and maximum bipartite matching can be solved in time O(n 2 log 2 n ).
Span programs are an important model of quantum computation due to their tight correspondence with quantum query complexity. For any decision problem fff, the minimum complexity of a span program for fff is equal, up to a constant factor, to the quantum query complexity of fff. Moreover, this correspondence is constructive. A span program for fff with complexity CCC can be compiled into a bounded error quantum algorithm for fff with query complexity O(C)O(C)O(C), and vice versa. In this work, we prove an analogous connection for quantum time complexity. In particular, we show how to convert a quantum algorithm for fff with time complexity TTT into a span program for fff such that it compiles back into a quantum algorithm for fff with time complexity O~(T)\widetilde{O}(T)O(T). While the query complexity of quantum algorithms obtained from span programs is well-understood, it is not generally clear how to implement certain query-independent operations in a time-efficient manner. We show that for span programs derived from algorithms with a time-efficient implementation, we can preserve the time efficiency when implementing the span program. This means in particular that span programs not only fully capture quantum query complexity, but also quantum time complexity. One practical advantage of being able to convert quantum algorithms to span programs in a way that preserves time complexity is that span programs compose very nicely. We demonstrate this by improving Ambainis's variable-time quantum search result using our construction through a span program composition for the OR function.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph HHH is present in an input graph GGG, 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 kkk. 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 kkk, or at most kkk. 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)\widetilde{O}(n^{3/2-α_k})O(n3/2−αk​), where αk∈Θ(c−k)α_k \in Θ(c^{-k})αk​∈Θ(c−k) and c=3+17/2≈1.33c = \sqrt{3+\sqrt{17}}/2 \approx 1.33c=3+17​​/2≈1.33, beating the previous best upper bound O(n3/2)O(n^{3/2})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)O(\sqrt{n})O(n​) query algorithm.
Quantum algorithms for graph problems are considered, both in the adjacency matrix model and in an adjacency list-like array model. We give almost tight lower and upper bounds for the bounded error quantum query complexity of Connectivity, Strong Connectivity, Minimum Spanning Tree, and Single Source Shortest Paths. For example, we show that the query complexity of Minimum Spanning Tree is in Θ(n3/2)\Theta(n^{3/2})Θ(n3/2) in the matrix model and in Θ(nm)\Theta(\sqrt{nm})Θ(nm​) in the array model, while the complexity of Connectivity is also in Θ(n3/2)\Theta(n^{3/2})Θ(n3/2) in the matrix model but in Θ(n)\Theta(n)Θ(n) in the array model. The upper bounds utilize search procedures for finding minima of functions under various conditions.
Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. It is known that for any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity, however finding such an algorithm is generally challenging. We consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a function f can also be used to decide “threshold” versions of the function f, or more generally, approximate a quantity called the span program witness size, which is some property of the input related to f. We achieve these results by relaxing the requirement that 1-inputs hit some target exactly in the span program, which could potentially make design of span programs significantly easier. In addition, we give an exposition of span program structure, which increases the general understanding of this important model. One implication of this is alternative algorithms for estimating the witness size when the phase gap of a certain unitary can be lower bounded. We show how to lower bound this phase gap in certain cases. As an application, we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, Rs,t(G)R_{s,t}(G)Rs,t​(G) . For this problem we obtain O~(1ε3/2nRs,t(G))\widetilde{O}(\frac{1}{\varepsilon ^{3/2}}n\sqrt{R_{s,t}(G)})O(ε3/21​nRs,t​(G)​) , using O(log⁡n)O(\log n)O(logn) space. In addition, when μ\mu μ is a lower bound on λ2(G)\lambda _2(G)λ2​(G) , by our phase gap lower bound, we can obtain an upper bound of O~(1εnRs,t(G)/μ)\widetilde{O}\left( \frac{1}{\varepsilon }n\sqrt{R_{s,t}(G)/\mu }\right) O(ε1​nRs,t​(G)/μ​) for estimating effective resistance, also using O(log⁡n)O(\log n)O(logn) space.