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:1507.00432 · Algorithmica

Approximate Span Programs

Tsuyoshi Ito, Stacey Jeffery

Published Nov 14, 2018• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s00453-018-0527-1

Related papers

Span Programs and Quantum Space Complexity

Stacey Jeffery

While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of space-bounded quantum computation. We relate the quantum space complexity of computing a function f with one-sided error to the logarithm of its span program size, a classical quantity that is well-studied in attempts to prove formula size lower bounds. In the more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (two-sided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program size. While no non-trivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first non-trivial lower bound on the approximate span program size of an explicit function.

arXiv:1908.04232•Leibniz international proceedings in informatics•Aug 12, 2019•1 citation

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•4 citations

Leveraging Unknown Structure in Quantum Query Algorithms

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

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.

arXiv:2012.01276•Dec 2, 2020•0 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•7 citations

Taming Quantum Time Complexity

Aleksandrs Belovs, Stacey Jeffery, Duyal Yolcu

Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction e x a c t n e s s . Second, through careful accounting t h r i f t i n e s s , the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity . Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum t i m e complexity.In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, Q ( f ∘ g ) = O ( Q ( f ) ⋅ Q ( g ) ) , without log factors.We achieve this by employing a novel approach to the design of quantum algorithms based on what we call t r a n s d u c e r s , and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.

arXiv:2311.15873•Quantum•Aug 23, 2024•5 citations
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.
While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of space-bounded quantum computation. We relate the quantum space complexity of computing a function f with one-sided error to the logarithm of its span program size, a classical quantity that is well-studied in attempts to prove formula size lower bounds. In the more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (two-sided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program size. While no non-trivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first non-trivial lower bound on the approximate span program size of an explicit function.
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.
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.
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.
Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction e x a c t n e s s . Second, through careful accounting t h r i f t i n e s s , the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity . Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum t i m e complexity.In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, Q ( f ∘ g ) = O ( Q ( f ) ⋅ Q ( g ) ) , without log factors.We achieve this by employing a novel approach to the design of quantum algorithms based on what we call t r a n s d u c e r s , and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.