Composing Quantum Algorithms

Stacey Jeffery

Composing Quantum Algorithms

T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper argues that bounded-error quantum algorithms compose cleanly: a bounded-error algorithm making Q calls to a bounded-error subroutine B can be replaced by one with time O(Q·T(B)+L), with no logarithmic amplification factor.

desk verdict A transparent, well-written survey of quantum composition results; no new theorems, but the toy purifier is worked out correctly and the attributions are honest. read the letter →

arxiv 2502.09240 v1 pith:MLPZ3KSC submitted 2025-02-13 quant-ph

Stacey Jeffery This is my paper · ORCID

classification quant-ph MSC 68Q1281P68 PACS 03.67.-a03.67.Lx

keywords quantumalgorithmscompositionbounded-errorzero-errortransducerspurifierswalksquerycomplexity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper makes the case that quantum algorithms, long considered hard to compose, actually compose better than classical ones in the bounded-error setting. Its headline claim is that a bounded-error quantum algorithm that makes Q calls to a bounded-error subroutine can be replaced by a single bounded-error algorithm whose time is O(Q·T(B)+L), with no log factor. The paper explains why the naive obstacle—different branches of a superposition taking different times—is surmountable by viewing algorithms through the lens of transducers, and why zero-error composition genuinely fails. If true, this means subroutine-based quantum algorithm design is safe: efficient quantum building blocks compose into efficient quantum algorithms, just as they do classically, and even better than randomized algorithms.

What carries the argument

The central object is the transducer, a model of quantum computation that generalizes quantum random walks: it has an associated unitary action and a complexity, and it composes with a natural 'cost flow' formula (the quantum analogue of expected path length). The load-bearing identity is the purifier: an operation that maps any transducer for a function with perturbation δ to one with perturbation $2^{{-Θ(D)}}$ while multiplying complexity by O(1), independent of D. The paper illustrates this with a biased-coin transducer: a quantum walk on a line with edge weights w_ℓ = ((1-p0)/p0)^ℓ. The complexity of the walk is the square root of the product of the total weight in the rejecting case and the effective resistance in the accepting case, and both stay O(1) because only one of the two quantities blows up in each case. This 'purify then compose then recompile' pipeline is what removes the log factor.

What would settle it

Exhibit a bounded-error quantum algorithm for some function whose every purifier (as defined by the transducer framework) has complexity growing as Ω(log(1/δ)) for δ→0; or construct a family of composed functions g∘h for which every bounded-error quantum algorithm needs Ω(Q2(g)·Q2(h)·log m) queries, contradicting the claimed O(Q2(g)·Q2(h)) composition. A more targeted check: compute the exact overhead of the purifier on a concrete family like parity or majority and verify the constant is truly independent of the desired perturbation.

Watch

Extended reading notes

Core claim

The discovery the paper presents is that bounded-error quantum algorithms have a compositional structure that classical bounded-error algorithms lack. Formally, if A is a bounded-error quantum algorithm that makes Q calls to a subroutine whose desired behavior is implemented with bounded error by B, then there exists a bounded-error quantum algorithm Ã implementing A's behavior with complexity T(Ã) = O(Q·T(B)+L), where L is A's additional work. The log factor that classical composition pays—because each subroutine call must be repeated about log Q times and majority-voted to suppress error—can be avoided entirely by purifying transducers. The paper also contrasts this with zero-error quantum composition, which provably fails: there are functions g and h, each with constant zero-error quantum query complexity, whose composition has linear zero-error query complexity. The key to the positive result is that a transducer can be purified to arbitrarily small perturbation at O(1) multiplicative overhead independent of the perturbation, so that composing purified transducers keeps the total perturbation small without repeated subroutine calls.

Load-bearing premise

The argument rests on the existence of a general purifier that converts any bounded-error quantum algorithm into a transducer with arbitrarily small perturbation at constant relative overhead; the paper explicitly demonstrates this only for a two-dimensional biased-coin output, and the general construction is delegated to other works. If no such general purifier exists, the log-factor-free composition theorem collapses.

Editorial extensions

If this is right

Subroutine-based quantum algorithm design is safe: when a quantum algorithm is built from bounded-error subroutines, the total time is just the sum of the subroutine costs (weighted by number of calls) plus overhead, so libraries of quantum subroutines compose without error-amplification slowdowns.
The bounded-error quantum query complexity of composed functions satisfies Q2(g∘h) = O(Q2(g)·Q2(h)) constructively, matching the previously non-constructive bound; the same holds for time complexity in the quantum word-RAM model.
The separation between quantum and classical composition becomes concrete: randomized bounded-error composition needs a log factor that quantum composition provably does not, indicating a genuine structural difference in how the two models handle error.
Zero-error quantum composition remains impossible: the paper's explanation via cancellation failure shows the impossibility is robust and not an artifact of the model.
The purifier gives an unconditional O(1)-overhead way to reduce transducer perturbation, which may be useful beyond composition, such as in designing quantum algorithms with structured error guarantees.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The purifier's O(1)-overhead error reduction suggests that the conventional wisdom that quantum error reduction requires log-factor overhead (mirroring classical amplification) may need qualification: restricting to the transducer model, perturbation can be suppressed for free; the log cost only appears when recompiling back to circuits.
If the general purifier construction holds, a testable extension is a form of quantum derandomization of subroutine composition: replacing the randomness used in classical majority voting with coherent purification may yield concrete quantum algorithms for problems where classical composition pays the log factor, such as in sequential decision trees.
The paper's framing suggests that the right complexity measure for quantum algorithms may not be circuit depth but something like the effective-resistance-based transducer complexity; one could test this by re-deriving known quantum query lower bounds in transducer language and seeing whether they become simpler.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This is an invited SIGACT News column, not a research paper. Don't go looking for new theorems; you'll find none. What you do get is a clear, honest exposition of why bounded-error quantum algorithms compose without the log factor that classical randomized composition needs. The paper says up front that the general purifier construction is from [BJY24] and [BJ24], and it doesn't overclaim the toy example. That transparency is real and it's the right call.

The pedagogical core is the toy purifier: a biased quantum coin and a line graph with edge weights. That section is genuinely good. Equations (17) and (18) are correct, and the effective-resistance argument showing O(1) complexity independent of D is worked out cleanly. A reader with a background in quantum walks will come away with a real feel for why purification avoids the log factor. The earlier sections explaining why zero-error quantum algorithms don't compose, using the Deutsch-Jozsa algorithm and amplitude cancellation, are also well done. The visual language—probability as water, amplitude as signed flow—is appropriate for the intended audience.

Soft spots, in proportion: the main composition theorem is not proved here, and the paper doesn't pretend it is. If you want to rely on the log-factor-free result, you should read [BJY24] and [BJ24] directly. That is an external dependency, but not a flaw in a survey. One concrete issue: the reference [BJ24] lists arXiv:2412.00000, which looks like a placeholder ID, not a real identifier. That should be fixed before publication. Nothing else in the citation pattern bothered me; the attribution to [BdW03] for the zero-error non-composition and to [Rei09] for the no-log-factor bound in (4) is standard and correct.

Who should read this? Complexity theorists who want intuition for the transducer model, and quantum algorithm designers who might use modular composition as a design tool. It is not a research contribution, but it is a fair and accurate survey by someone who did the underlying work. It deserves a serious referee if considered as a journal submission, because the exposition could easily have contained subtle errors; here the included math checks out. My recommendation: accept it as a column, and send it to a referee who knows quantum query complexity to verify the attributions and the toy proof. I would cite this for its exposition, but for technical results I'd cite the original papers.

Referee Report

0 major / 5 minor

Summary. This paper is an expository survey, written for a general computer science audience, of recent results on composing quantum algorithms. It contrasts deterministic, zero-error, and bounded-error classical composition, explaining how the classical bounded-error bound incurs a log factor from majority-voting error reduction. It then explains why zero-error quantum algorithms fail to compose, using the Buhrman–de Wolf oracle separation. The main positive message is that, using a model of quantum transducers and a purification technique, bounded-error quantum algorithms can be composed without a log factor. The paper illustrates purification on a toy example involving a biased quantum coin and a line graph, with explicit effective-resistance bounds.

Significance. The survey is a clear and readable account of a surprising and technically deep result that is not widely known outside the quantum algorithms community. The toy example in Section 4 is genuinely instructive and self-contained, and the paper is honest about the fact that the general composition theorem is not proved here but is cited to published or preprinted work ([BJY24] and [BJ24]). The external dependency on those references is appropriate for an invited survey, and the article explicitly labels the toy construction as only a special case. For the intended readership, this is a valuable contribution to the complexity theory column.

minor comments (5)

[References and Section 4] The reference [BJ24] is given as "arXiv:2412.00000", which is not a valid arXiv identifier and appears to be a placeholder; please replace it with the correct identifier or published venue.
[Section 4 (title and body)] The section title "Transducers, Purifers, and no more log Factors" misspells "Purifiers", and the body uses "purifer" instead of "purifier" in several places.
[Section 3] There is a typo in "non-zero probabaility" in the paragraph describing Figure 4; it should be "probability".
[Section 4, Eqs. (17)-(18)] The upper-bound line in equations (17) and (18) is typeset incorrectly in the arXiv rendering ("≤ 1 1−ε 1−ε"); it should read "≤ 1/(1 − ε/(1−ε)) = O(1)".
[Section 2, Eq. (9)] The text says that the bound in Eq. (9) was shown "with polylog factor overhead" in [Jef24a], but the displayed equation does not include this overhead; please add a parenthetical remark to clarify that the polylog factor is omitted for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper is an invited survey whose central theorem is attributed to a published peer-reviewed source, and its self-contained example is explicitly a special case with no fitted-input-as-prediction reduction.

full rationale

The paper does not attempt to derive the log-factor-free composition theorem in this manuscript; it states the theorem and explicitly attributes it to [BJY24] ('we were able to show ... in complexity T(Ã) = O(Q·T(B)+L) [BJY24]'). [BJY24] is a published, peer-reviewed article in Quantum, and [Jef24a] is a separately attributed prior article; these are real external evidence rather than a circular self-citation chain. The only derivation worked out in the paper is the toy purifier for a two-dimensional biased coin. That derivation uses the electric-network quantum walk bound of [Bel13], an external, non-author reference, and the paper explicitly disclaims generality: 'The purifier presented below is much simpler than the one in [BJY24], but only applies to a special case.' The toy example is not a fitted parameter renamed as a prediction: the construction takes a subroutine producing the biased-coin state, builds a weighted-line quantum walk with weights derived from p0, and shows the two relevant complexity quantities are O(1); the perturbation is 2^{-Θ(D)} as stated. There is no equation that is equivalent by construction to an input, nor any quantity fitted to a subset of data and then reported as a prediction. The manuscript is a survey and intuition piece, and its load-bearing results genuinely live in the cited published works. Accordingly, no circular step is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The article's central claims rest on prior results, especially [BJY24] and [BJ24], which are self-cited. The toy example is self-contained but restricted to a special case. No free parameters are fitted to data; the constant ε is an assumed error bound in the promise, not a fitted value.

assumptions (4)

domain assumption Quantum algorithms can be compiled to transducers and back with O(T) overhead (Section 4, properties 1 and 2).
The transducer framework is the basis for the composition results; its properties are asserted with reference to [BJY24].
domain assumption A purifier reduces transducer perturbation to arbitrarily small δ with O(1) overhead independent of δ (Section 4).
This is the key lemma enabling log-factor-free composition; proved in [BJ24] for the general case, only illustrated here for a biased coin.
standard math Effective resistance equals expected commute time, H_{s,t}+H_{t,s}=2W R (Eq. 13).
Standard result from [CRR+96] used to interpret quantum walk complexity.
standard math The quantum walk decision complexity is sqrt(max W * max R) for the decision problem (Eq. 14, from [Bel13]).
Belovs' electric network framework is cited for the quantum walk hitting time bound.

invented entities (1)

quantum transducer independent evidence
purpose: Abstraction of a quantum algorithm that supports modular composition; perturbed transducers represent bounded-error algorithms and can be purified.
Defined in [BJY24] and used to prove log-factor-free composition; it yields concrete complexity bounds that can be checked against specific algorithms, giving a falsifiable handle.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Composing Quantum Algorithms." pith.science (2026). https://pith.science/paper/MLPZ3KSC

@misc{pith2026250209240,
  author       = {Pith},
  title        = {Pith review of: Composing Quantum Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MLPZ3KSC}},
  note         = {Machine review of arXiv:2502.09240}
}

read the original 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 \emph{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 \emph{better} than classical composition in the bounded-error setting.

Figures

Figures reproduced from arXiv: 2502.09240 by the authors.

**Figure 2.** On the left, we see a run of the algorithm on a constant input, and on the right, a run [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Here we see the probability flow for two runs of a randomized algorithm for [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: This image depicts the probability flow through the Deutsch-Jozsa algorithm from [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

**Figure 5.** Figure 5: The cases distinguished by a quantum walk algorithm (special case of a line). [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Quantum Multiscale Modeling: A Hierarchy of Algorithms for Complex Chemical Systems
quant-ph 2026-07 accept novelty 6.0 of 10

Multiscale quantum advantage in chemistry is governed by the structure of information transfer between algorithmic layers rather than by performance at individual scales alone.

Reference graph

Works this paper leans on

14 extracted references · 9 canonical work pages · cited by 1 Pith paper

[1]

Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach . Cambridge University Press, 2009

2009
[2]

Optimal separation and strong direct sum for randomized query complexity

Eric Blais and Joshua Brody. Optimal separation and strong direct sum for randomized query complexity. In 34th , pages 1--17, 2019

work page 2019
[3]

Quantum walks and electric networks

Aleksandrs Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013

arXiv 2013
[4]

Quantum error reduction without log factors, 2024

Aleksandrs Belovs and Stacey Jeffery. Quantum error reduction without log factors, 2024. arXiv:2412.00000

work page arXiv 2024
[5]

Taming Quantum Time Complexity

Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. Taming quantum time complexity. Quantum , 8(1444), 2024. arXiv:2311.15873

work page Pith review arXiv 2024
[6]

Quantum Zero-Error Algorithms Cannot be Composed

Harry Buhrman and Ronald Wolf d e Wolf. Quantum zero-error algorithms cannot be composed. Information Processing Letters , 87(2):79--84, 2003. arXiv:quant-ph/0211029

work page Pith review arXiv 2003
[7]

One-way ticket to Las Vegas and the quantum adversary

Aleksandrs Belovs and Duyal Yolcu. One-way ticket to Las Vegas and the quantum adversary. arXiv:2301.02003, 2023

arXiv 2023
[8]

Chandra, Prabhakar Raghavan, Walter L

Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity , 6(4):312--340, 1996

work page 1996

Show all 14 references

[9]

Rapid solutions of problems by quantum computation

David Deutsch and Richard Jozsa. Rapid solutions of problems by quantum computation. Proceedings of the Royal Society of London A , 1907:553--558, 1992

1907
[10]

Doyle and J

Peter G. Doyle and J. Laurie Snell. Random walks and electric networks . Mathematical Association of America, 1984. arXiv:math/0001057

1984 arXiv
[11]

How to recycle random bits

Russell Impagliazzo and David Zuckerman. How to recycle random bits. In 30th , pages 248--253, 1989

1989
[12]

Quantum subroutine composition

Stacey Jeffery. Quantum subroutine composition. Theory of Computing , 2024. To appear. arXiv:2209.14146

2024 arXiv
[13]

SIGACT N ews C omplexity T heory C olumn 123: Composing quantum algorithms

Stacey Jeffery. SIGACT N ews C omplexity T heory C olumn 123: Composing quantum algorithms. ACM SIGACT News , 55(4):49–69, December 2024

2024
[14]

Reichardt

Ben W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In 50th , pages 544--551, 2009

2009

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach . Cambridge University Press, 2009

2009

[2] [2]

Optimal separation and strong direct sum for randomized query complexity

Eric Blais and Joshua Brody. Optimal separation and strong direct sum for randomized query complexity. In 34th , pages 1--17, 2019

work page 2019

[3] [3]

Quantum walks and electric networks

Aleksandrs Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013

arXiv 2013

[4] [4]

Quantum error reduction without log factors, 2024

Aleksandrs Belovs and Stacey Jeffery. Quantum error reduction without log factors, 2024. arXiv:2412.00000

work page arXiv 2024

[5] [5]

Taming Quantum Time Complexity

Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. Taming quantum time complexity. Quantum , 8(1444), 2024. arXiv:2311.15873

work page Pith review arXiv 2024

[6] [6]

Quantum Zero-Error Algorithms Cannot be Composed

Harry Buhrman and Ronald Wolf d e Wolf. Quantum zero-error algorithms cannot be composed. Information Processing Letters , 87(2):79--84, 2003. arXiv:quant-ph/0211029

work page Pith review arXiv 2003

[7] [7]

One-way ticket to Las Vegas and the quantum adversary

Aleksandrs Belovs and Duyal Yolcu. One-way ticket to Las Vegas and the quantum adversary. arXiv:2301.02003, 2023

arXiv 2023

[8] [8]

Chandra, Prabhakar Raghavan, Walter L

Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity , 6(4):312--340, 1996

work page 1996