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

Leveraging Unknown Structure in Quantum Query Algorithms

Noel T. Anderson, Jay-U Chung, Shelby Kimmel

Published Dec 2, 2020• 1 citation
arXivHTMLPDF

Abstract

Quantum span program algorithms for function evaluation commonly have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time, and we extend this approach to the more general problem of state conversion. For example, there is a span program algorithm that decides whether two vertices are connected in an $n$-vertex graph with $O(n^{3/2})$ queries in general, but with $O(\sqrt{k}n)$ queries if promised that, if there is a path, there is one with at most $k$ edges. Our algorithm uses $\tilde{O}(\sqrt{k}n)$ queries to solve this problem if there is a path with at most $k$ edges, without knowing $k$ ahead of time.

DOI
10.48550/arxiv.2012.01276

Related papers

Improved Quantum Query Complexity on Easier Inputs

Noel T. Anderson, Jay-U Chung, Shelby Kimmel +2 more

Quantum span program algorithms for function evaluation sometimes have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these improvements persist even without a promise ahead of time, and we extend this approach to the more general problem of state conversion. As an application, we prove exponential and superpolynomial quantum advantages in average query complexity for several search problems, generalizing Montanaro's Search with Advice [Montanaro, TQC 2010].

arXiv:2303.00217•Quantum•Apr 8, 2024•4 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 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

Span-program-based quantum algorithm for tree detection

Guoming Wang

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.

arXiv:1309.7713•Sep 30, 2013•3 citations

Quantum Query Complexity and Span Programs from Pre-Geometry

Justin Roy Cox, Neil Epstein, Zhirui Hu +2 more

Span programs provide a general method for designing quantum query algorithms, and for Boolean coordinate queries their optimum cost agrees with the general adversary bound. We develop a matroidal organization of this optimization that separates dependence data determined by the query problem from the dependence structure chosen by a span program. The resulting source matroid records query dependence, target determination, and separation data, while a program matroid records dependencies among the target and response-labeled input elements of a candidate program. When a query problem admits a source matroid, we use its structure to organize adversary upper and lower bounds. For separating binary query sets in this setting, the global matroid-span-program optimum equals $\mathrm{Adv}^{\pm}_{\mathcal Q}(f)$. For a fixed regular program matroid, projective uniqueness reduces optimization over real representations to positive element weights. We express positive and negative costs as weighted basis ratios and derive exact $1$-, $2$-, and $3$-sum reductions, giving a compositional evaluation of the fixed-weight objective along a Seymour decomposition. For pointed $R_{10}$ closure, exact certificates give $3.9087553<\mathrm{Adv}^{\pm}_{\mathcal Q_R}(f_R)<3.9301$. The natural $R_{10}$ program has optimized cost $5$, while another regular program has cost at most $\sqrt{87/5}$. Recursive self-composition yields a family on $N$ input bits with randomized query complexity $Ω(N^{0.7324867\ldots})$, an explicit quantum algorithm using $O(N^{0.6500178\ldots})$ queries, and $Q(F)=Θ(N^α)$ for $0.6204277\ldots<α<0.6229063\ldots$.

quant-pharXiv:2610.03914•Oct 6, 2026•0 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 span program algorithms for function evaluation commonly have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time, and we extend this approach to the more general problem of state conversion. For example, there is a span program algorithm that decides whether two vertices are connected in an nnn-vertex graph with O(n3/2)O(n^{3/2})O(n3/2) queries in general, but with O(kn)O(\sqrt{k}n)O(k​n) queries if promised that, if there is a path, there is one with at most kkk edges. Our algorithm uses O~(kn)\tilde{O}(\sqrt{k}n)O~(k​n) queries to solve this problem if there is a path with at most kkk edges, without knowing kkk ahead of time.
Quantum span program algorithms for function evaluation sometimes have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these improvements persist even without a promise ahead of time, and we extend this approach to the more general problem of state conversion. As an application, we prove exponential and superpolynomial quantum advantages in average query complexity for several search problems, generalizing Montanaro's Search with Advice [Montanaro, TQC 2010].
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.
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.
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.
Span programs provide a general method for designing quantum query algorithms, and for Boolean coordinate queries their optimum cost agrees with the general adversary bound. We develop a matroidal organization of this optimization that separates dependence data determined by the query problem from the dependence structure chosen by a span program. The resulting source matroid records query dependence, target determination, and separation data, while a program matroid records dependencies among the target and response-labeled input elements of a candidate program. When a query problem admits a source matroid, we use its structure to organize adversary upper and lower bounds. For separating binary query sets in this setting, the global matroid-span-program optimum equals AdvQ±(f)\mathrm{Adv}^{\pm}_{\mathcal Q}(f)AdvQ±​(f). For a fixed regular program matroid, projective uniqueness reduces optimization over real representations to positive element weights. We express positive and negative costs as weighted basis ratios and derive exact 111-, 222-, and 333-sum reductions, giving a compositional evaluation of the fixed-weight objective along a Seymour decomposition. For pointed R10R_{10}R10​ closure, exact certificates give 3.9087553<AdvQR±(fR)<3.93013.9087553<\mathrm{Adv}^{\pm}_{\mathcal Q_R}(f_R)<3.93013.9087553<AdvQR​±​(fR​)<3.9301. The natural R10R_{10}R10​ program has optimized cost 555, while another regular program has cost at most 87/5\sqrt{87/5}87/5​. Recursive self-composition yields a family on NNN input bits with randomized query complexity Ω(N0.7324867…)Ω(N^{0.7324867\ldots})Ω(N0.7324867…), an explicit quantum algorithm using O(N0.6500178…)O(N^{0.6500178\ldots})O(N0.6500178…) queries, and Q(F)=Θ(Nα)Q(F)=Θ(N^α)Q(F)=Θ(Nα) for 0.6204277…<α<0.6229063…0.6204277\ldots<α<0.6229063\ldots0.6204277…<α<0.6229063….
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.