Composing Quantum Algorithms
Stacey Jeffery · 2025
Read Composing Quantum Algorithms by Stacey Jeffery (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09240.txt.
Introduction
Stacey Jeffery wrote this 2025 article on a quiet puzzle: why chaining quantum algorithms together is delicate. In classical computing, stacking efficient steps is assumed to stay efficient; that faith even shapes the definition of the word. Quantum steps share fragile states, so the assumption needs checking.
Jeffery walks a general computer science audience through the key results. Zero-error quantum algorithms, she explains, genuinely fail to compose. Bounded-error ones do compose, and with the right lens they compose even better than classical randomized ones. Classical composition pays a log factor to amplify success by majority vote; the quantum route avoids that tax. The article builds intuition for why the fragile case breaks and the noisy case thrives.
Catalog record
| CREATOR | Stacey Jeffery |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-09240
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Composing Quantum Algorithms Stacey Jeffery Abstract Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing “efficient” algorithms should result in an “efficient” algorithm – even using this intuition to justify our definition of “efficient.” Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms do not compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. In this article, aimed at a general computer science audience, we try to give some intuition for these results: why composing quantum algorithms is tricky, particularly in the zero-error setting, but why it nonetheless works better than classical composition in the bounded-error setting. 1 Introduction Algorithms designers and programmers make ubiquitous use of subroutines. Not only does this allow code to be easily reused, perhaps even in subroutine libraries used across platforms, it adds structure to a program, or algorithm, that makes the whole thing easier to analyze. For algorithms designers, the most important reason to use subroutines is probably that by black-boxing the algorithms designed by your ingenious colleagues, you can use them as building blocks within your own new algorithms. Composition is a fundamental idea in complexity theory as well. One of the motivations for using polynomials as the class of growth functions considered “efficient” is that we feel intuitively that whenever we compose “efficient” algorithms, the resulting algorithm should also be “efficient” [ AB09 ] . Perhaps one reason we take for granted that this should be true is the ease with which we can compose and analyze classical algorithms. If an algorithm {\cal A} makes Q queries to a subroutine {\cal B} with time complexity T({\cal B}) , and L additional operations, then its complexity is: T({\cal A})=Q\cdot T({\cal B})+L, as any first-year computer science student could tell you. This allows us to say things about the complexity of composed functions. Let f:\{0,1\}^{n}\rightarrow\{0,1\} be the composed function f=g\circ h , where g:\{0,1\}^{m}\rightarrow\{0,1\} for some m=m(n)\leq n , and h:\{0,1\}^{n/m}\rightarrow\{0,1\} , defined on x\in\{0,1\}^{n} by f(x)=f(x^{(1)},\dots,x^{(m)})=g(h(x^{(1)}),\dots,h(x^{(m)})), where each x^{(i)} is a n/m -bit string. Let \mathbf{D}(f) be the deterministic query complexity of f , also called the decision tree complexity , which is the minimum number of queries to the bits of the input needed to decide f (on the worst-case input). Then we can immediately see that \mathbf{D}(g\circ h)\leq\mathbf{D}(g)\cdot\mathbf{D}(h), by simply composing query-optimal deterministic algorithms for g and h (that is, every time the algorithm for g makes a query to the input, replace it with a subroutine call to h on the appropriate part of the input). A similarly easy composition applies to the expected running time of Las Vegas algorithms, which are randomized algorithms that always output the correct answer, but might run forever: In a Las Vegas algorithm {\cal A} , for any fixed input x (which we generally leave implicit), the running time T({\cal A}) of the algorithm is a random variable, and while its expected value (over the random choices made by the algorithm) is generally finite, the maximum value it may obtain could be unbounded. If {\cal A} is a Las Vegas algorithm that makes Q queries to a Las Vegas subroutine {\cal B} , and L additional operations, then 1 1 1 We make the reasonable assumption that the number of queries, Q , is independent of the time the queries take, which would be true, for example, if {\cal A} were designed with each subroutine query treated as a black box whose cost is always unit. \mathbb{E}[T({\cal A})]=\mathbb{E}[Q]\cdot\mathbb{E}[T({\cal B})]+\mathbb{E}[L]. Let \mathbf{R}_{0}(f) denote the zero-error randomized query complexity of f , which is the minimum expected number of input queries needed by any Las Vegas algorithm for f (on the worst-case input). Then we can easily see that \mathbf{R}_{0}(g\circ h)\leq\mathbf{R}_{0}(g)\cdot\mathbf{R}_{0}(h). (1) This naive composition doesn’t quite work if we use randomized algorithms that have some probability of error. Suppose \widetilde{\cal B} is a bounded-error (or Monte Carlo) algorithm, meaning that it is a randomized algorithm that outputs the correct answer with probability at least 2/3 on every input, and, in contrast to Las Vegas algorithms, for every input x , there is some finite number of steps after which it is guaranteed to have halted – we call this the running time, and it is not a random variable. Note that Monte Carlo algorithms are generally easier to come by than Las Vegas algorithms, since you can turn any Las Vegas algorithm with worst-case expected running time T into a Monte Carlo algorithm with (deterministic) running time O(T) by simply stopping the Las Vegas algorithm after 3T steps. By Markov’s inequality, the probability the Las Vegas algorithm has not yet found the correct answer is at most 1/3 . While 2/3 is generally considered an acceptable correctness probability, in the context of a subroutine that is called Q times by an algorithm {\cal A} that expects the right answer, this is insufficient. Assuming Q\gg 1 , with overwhelming probability, one of the calls to \widetilde{\cal B} will return the wrong answer, in which case, we no longer have any guarantees on the correctness of {\cal A} . To ensure that with probability at least 2/3 , all subroutine calls return the correct answer, we need the probability of error on each subroutine call to be \ll\frac{1}{Q} , so we can apply a union bound. The standard way to achieve this is as follows: every time {\cal A} wants to call the subroutine, we will make about \log Q parallel calls to \widetilde{\cal B} , and return the most commonly seen answer (the majority) 2 2 2 Note that majority voting only works if the desired behaviour of \widetilde{\cal B} is to output a deterministic bit or string, as opposed to a distribution, or an element from a set of many possible correct answers. . Then, by a binomial tail bound, each of the Q queries made by \cal A is correct except with probability \ll\frac{1}{Q} , as needed. If the resulting algorithm is called \widetilde{\cal A} , we have: T(\widetilde{\cal A})=O\left(Q\cdot T(\widetilde{\cal B})\log{Q}+L\right). (2) Letting \mathbf{R}_{2}(f) denote the bounded-error randomized query complexity of f , which is the minimum query complexity of a bounded-error randomized algorithm that decides f , we then have: \mathbf{R}_{2}(g\circ h)\leq O\left(\mathbf{R}_{2}(g)\cdot\mathbf{R}_{2}(h)\log m\right). (3) This inequality is tight: there exist composed functions for which this log factor is necessary [ BB19 ] . In complexity-theoretic terms, this gives us, for deterministic, zero-error, and bounded-error algorithms respectively: {\sf P}^{\sf P}={\sf P},\hskip 20.00003pt{\sf BPP}^{\sf BPP}={\sf BPP},\hskip 20.00003pt\mbox{and}\hskip 20.00003pt{\sf ZPP}^{\sf ZPP}={\sf ZPP}, (all of which relativize), meaning that each of these three classes is self-low . These complexity-theoretic statements are, of course, quite granular compared to the finer-grained complexities of composition described above, but they roughly state that each of the three types of algorithms – efficient deterministic, efficient Monte Carlo, and efficient Las Vegas – are “closed under composition”, as