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:2311.15873 · Quantum

Taming Quantum Time Complexity

Aleksandrs Belovs, Stacey Jeffery, Duyal Yolcu

Published Aug 23, 2024• 27 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2024-08-23-1444

Related papers

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

Distributional Quantum Query Complexity

Shalev Ben-David, M. H. Ebtehaj

Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.

quant-pharXiv:2610.06835•Oct 6, 2026•0 citations

Optimal transducers using symmetries

Benoît Dubus, Julien Ladeuze, Jérémie Roland

Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.

quant-pharXiv:2610.02133•Oct 2, 2026•0 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

Quantum query complexity in computational geometry revisited

Abhinav Bahadur, Christoph Dürr, Thibault Lafaye +1 more

We are interested in finding quantum algorithms for problems in the area of computation geometry. Many of the problems we study have already polynomial time algorithms. Bounded error quantum algorithms can actually have sublinear running time.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 5, 2006•2 citations

Space-Efficient Quantum Error Reduction without log Factors

Aleksandrs Belovs, Stacey Jeffery

Given an algorithm that outputs the correct answer with bounded error, say 1 / 3 , it is sometimes desirable to reduce this error to some arbitrarily small ε – e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of O ( log ⁡ 1 ε ) from calling the algorithm this many times.Transducers are a recently introduced model of quantum computation, and it is possible to reduce the “error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors.In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.Purifiers can be seen as a way of turning a “Monte Carlo'' quantum algorithm into a “Las Vegas'' quantum algorithm – a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.

arXiv:2502.09249•Quantum•Mar 23, 2026•7 citations
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.
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 enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g))Q(f\circ g)=Θ(Q(f)Q(g))Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions fff and ggg; a direct sum theorem asserting that computing kkk copies of a function (or search problem) costs Ω(k)Ω(k)Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k)Ω(k)Ω(k) times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μμμ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing kkk copies of fff when the input comes from the product distribution μkμ^kμk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2γ_2γ2​ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.
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.
Given an algorithm that outputs the correct answer with bounded error, say 1 / 3 , it is sometimes desirable to reduce this error to some arbitrarily small ε – e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of O ( log ⁡ 1 ε ) from calling the algorithm this many times.Transducers are a recently introduced model of quantum computation, and it is possible to reduce the “error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors.In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.Purifiers can be seen as a way of turning a “Monte Carlo'' quantum algorithm into a “Las Vegas'' quantum algorithm – a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.