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 (exactness). Second, through careful accounting (thriftiness), 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 time 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\circ g)=\OO(Q(f)\cdot Q(g))$, without log factors.

We achieve this by employing a novel approach to the design of quantum algorithms based on what we call transducers, 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.

§ INTRODUCTION

Since the introduction of span programs into quantum query complexity by Reichardt and Špalek
[34, 31]
[However, this particular connection is attributed to Troy Lee in the first of these two papers.],
the quantum query world became a nicer place to be.
A span program (alternatively, a feasible solution to the dual adversary bound) is an idealised computational model, in the sense that no real device corresponds to it.
Nonetheless, it has a strong connection to quantum query complexity.
We can turn any quantum query algorithm into a span program,
[Originally, this construction was non-constructive as it came from the dual of a lower bound.  Section 3 of [31] contains a constructive construction for algorithms with one-sided error.  This was later extended to two-sided error in [25].]
or we can construct one from scratch.
They can be composed as usual quantum subroutines.
At the end of the day, the span program can be transformed back into a quantum query algorithm.
We identify two main points of advantage of span programs compared to usual quantum subroutines.

* We call the first one exactness.
A span program evaluates a function exactly even if the quantum query algorithm it was converted from had a bounded error.
Therefore, span programs can be composed without any error reduction.
The conversion from the span program to a quantum query algorithm does introduce an error, and we do not get an exact quantum query algorithm at the end.
However, the error is introduced only once per the whole algorithm, and does not accumulate even in the case of many non-precise subroutines.

This idea was the major driving force behind this line of research starting with the algorithm for the iterated NAND function [22, 5] to general iterated Boolean functions [34, 33].

* We call the second one thriftiness.
Span programs have a natural predisposition towards accurate bookkeeping.
If an execution of a subroutine happens to be cheap on a particular input, this cheaper cost will contribute to the total complexity of the whole span program.
This is in contrast to the usual execution of quantum subroutines, where the maximal cost is to be paid no matter how easy the input is in a particular execution.
This is because we generally cannot measure a subroutine, which may be run only in some branch of a superposition, to see whether it has ended its work or not.
In specific cases, Ambainis' variable-time framework [2, 3, 6] allows for this particular approach.
We consider variable-time framework as a piece of motivation towards importance of thus defined thriftiness.  See, e.g., the results mentioned in the introduction of [6].
At the end, when converting to a quantum query algorithm, we still have to account for the maximal possible complexity, but this is done only once per the whole algorithm, thus amortising complexities of individual subroutines.

This point has been emphasised to a lesser extent than the exactness property, but we find it equally important.
In particular, this ability results in some rather interesting super-polynomial speed-ups [40].
We consider the thriftiness property in more detail in sec:conceptualPreliminaries.

In a recent paper by a subset of the authors [16], it was shown that one does not even have to change the model to obtain these benefits.
It suffices to keep the model of a quantum query algorithm, and only change the way query complexity is defined.
Namely, one can count total squared norm of all the states processed by the input oracle (coined quantum Las Vegas query complexity in [16] as it can be interpreted as the expected number of queries) instead of the number of executions of the input oracle (which is the usual definition, called Monte Carlo in [16]).
Note that quantum Las Vegas query complexity is an idealised complexity measure, but it has an operational meaning: at the end of the day, a quantum Las Vegas query algorithm can be turned into a Monte Carlo query algorithm with a constant increase in complexity and introducing a small error.

A major drawback of the above results is that while accounting of query complexity is very natural and important, analysis of the more meaningful time complexity
of the resulting algorithm can be quite difficult.
While the time complexity of some nicely structured span program algorithms has been successfully analyzed (e.g. [15, 34]), in other cases, time complexity analyses have proven much more challenging, perhaps most notably in [10], where a query algorithm was given, but a time complexity analysis remained elusive for more than a decade [27].

There has been a line of work attempting to extend some of the benefits of span programs to time complexity.
In [21],
it was shown how span programs could be made to capture time complexity of quantum algorithms, not only query complexity.
Essentially what [21] did was to extend the algorithm-to-span-program conversion of [31] so that the span program still encodes information about the gate structure of the original algorithm.
Thus, this structure can be recovered when the span program is converted back into an algorithm.
The resulting span programs could be manipulated in a limited number of ways.
For instance, this allowed for an alternative implementation of Ambainis' variable-time search algorithm [2].
This idea was further exploited in [24] by one of the authors (in the framework of multidimensional quantum walks [27]) to give a general composition result for time complexity of quantum algorithms, similar to the query results of [16], but lacking in generality.
While [24] achieved thriftiness, it failed to achieve exactness.  Instead, this work assumes that subroutines have had their success probability amplified through majority voting so that errors occur with inverse polynomial probability, which results in logarithmic factor overhead.

One of the main contributions of this a paper is a framework that achieves both exactness and thriftiness for quantum time complexity in a systematic manner.
In order to do so, we introduce transducers.
While quantum Las Vegas query complexity keeps the model of a quantum algorithm the same but changes the definition of the query complexity, transducers still keep the same model but change the definition of computation.
We consider two objects: a transducer that is a usual quantum algorithm in a larger Hilbert space, and its transduction action that is an idealised transformation obtained by “additively tracing out” a part of the Hilbert space of the transducer.
A simple procedure converts a transducer into an algorithm implementing its transduction action, introducing a small error in the process.
Monte Carlo query complexity of the resulting algorithm is Las Vegas query complexity of the transducer.
Its time complexity is a product of two things: time complexity of the transducer (considered as a usual quantum algorithm) and its transduction complexity, which measures the extent of the “traced-out” part of the system.
Compared to span programs, which most naturally model computations of decision problems,  transducers naturally model arbitrary state conversion computations, and as a transducer is itself a quantum computation, its time complexity analysis is more immediate.

For the composition results, we follow the same overall strategy as for span programs.
We can transform any quantum program into a transducer, and we can compose transducers in essentially the same way as we compose quantum programs.
The advantage is that both query complexity and time complexity (in the guise of transduction complexity) are composed in a thrifty manner.
At the end, we convert the composed transducer back into a quantum algorithm.
In parcitular, we obtain the following results:

Exact and thrifty composition of quantum algorithms: We show how to compose quantum algorithms in a way that is thrifty[For an idea of what we mean by thrifty composition, see eqn:randomComposition and eqn:randomComposition2, and the surrounding discussion of the “gold standard” for composition.] in time complexity, but also exact (thm:introCompositionQRAG). This improves on [24] in several ways.

* Exactness: We do not need to assume the composed algorithms have inverse polynomial errors, which saves log factors in the overall complexity.

* The results apply to composing quantum algorithms that solve general state conversion problems, whereas [24] only applies to algorithms that decide Boolean functions.

* In addition to achieving thrifty time complexity, the composed algorithm is also thrifty in its number of queries to the input oracle.

The one way in which our results, as stated, are not more general than [24] is that [24] considers quantum algorithms that work in the variable-time model, meaning their running times can be random variables, achieved by performing intermediate partial measurements that indicate if the algorithm is finished. While variable-time algorithms are also compatible with transducers, we omit their explicit treatment here, for the sake of simplicity, and leave it for future work.
We also give results that apply purely to the circuit model (without quantum random access gates (QRAGs)), but with worse complexity (thm:introCompositionCircuit).
We also explicitly consider multiple layers of composition (thm:introCompositionTree) in the QRAG model, and its special case of iterated functions in the circuit model (thm:introIterated).

Quantum analogue of majority voting, and time-efficient function composition: It
is known that the bounded-error quantum query complexity, $Q$, of a composed function $f \circ g$ is $Q(f\circ g)=\OO(Q(f)Q(g))$. This statement would be obvious with log factors, by using the standard technique of majority voting to reduce the error of each call to $g$ to inverse polynomial, but the fact that this holds without log factors is somewhat surprising. In sec:introPurifier, we shed some light on this surprising result, and show a similar result for time complexity. We extend a notion from [14], called a purifier, to show how to take a quantum algorithm with constant error, and convert it to a transducer with any error $\eps>0$ with only constant overhead on the query and time complexities. This, in turn, allows us to prove a log-factor-free composition result for time complexity in the QRAG model (thm:introCompositionFunctionQRAG). Specifically, if there is an algorithm for $f$ that makes $Q$ queries and takes $T_f$ additional time, and an algorithm for $g$ that takes $T_g$ time, then there is an algorithm for $f\circ g$ that takes time $\OO(T_f+QT_g)$. As with the aforementioned query result, this would be obvious with log factors on the second term, but the fact that it holds without log factor overhead is surprising. This implies log factor improvements in the time complexity of quantum algorithms obtained by composition, such as [27].

We stress that in addition to our concrete results, a major contribution is conceptual.
Along with
bringing the beautiful existing work on quantum query complexity to the real world of quantum time complexity, transducers achieve many existing results in a much simpler and cleaner way, and we feel that they are a novel and potentially instructive way of understanding quantum algorithms.

For example, discrete-time quantum walks are an important technical tool.
However, understanding their internal workings requires some background: the notion of the spectral gap, phase estimation subroutine, non-trivial spectral analysis.
In sec:introWalks we use transducers to devise a very simple implementation of a quantum walk that completely avoids all this background.

Let us end this section with a few remarks on the model of computation.
The previous results towards thriftiness in time complexity, [21] and [24], assumed the QRAG model in a fundamental way.
It is based around the quantum random access gate (QRAG), which allows index access to an array of quantum registers in superposition.
This should not be confused with quantum random access memory (QRAM), which assumes such access to an array of classical registers.
[This nomenclature is not completely standardised and has been a source of confusion, as different authors use the same name to refer to different models.]
QRAG is a stronger model than QRAM, but it is utilised in a large number of time-efficient quantum algorithms, Ambainis' element distinctness algorithm [1] being a noticeable example.

Our general attitude towards the QRAG model is one of ambivalence.
On the one hand, the QRAG model is a very natural quantization of the classical RAM machine, and, thus, makes a lot of sense to study theoretically.
On the other hand, the assumption that we can swap a large number of qubits in superposition in essentially constant time seems far-fetched given the current state of the art in development of quantum computers.
Because of that, we have chosen to pursue both directions.
We prove results involving the QRAG model, as they tend to have more natural formulations, and continue the aforementioned line of research in [21, 24], but we also design algorithms in the circuit model, which, while not being as efficient as in the QRAG model, are of significant interest.

We now give a technical overview of our results in sec:conceptualPreliminaries and sec:overview, before fleshing out full details in the remaining sections.

§ CONCEPTUAL PRELIMINARIES: QUANTUM LAS VEGAS COMPLEXITY

Quantum Las Vegas query complexity [16], also known as the total query weight [24], is a cornerstone in understanding this paper for a number of reasons.
First, the definition of the query complexity of a transducer is intrinsically the Las Vegas one.
Second, when converting a quantum program into a transducer, we take into account its Las Vegas query complexity.
Finally, we use composition results for the Las Vegas query complexity as a model that we strive to achieve for time complexity.

This section serves as a very brief overview of the composition properties for randomised and quantum Las Vegas complexity.
The randomised results are folklore, and the quantum ones are either from [16] or can be obtained similarly.
Both are for purely illustrative purpose and will serve as a reference point to the results obtained later in the paper.

§.§ Types of Composition

The composition property we have in mind is as follows.
Assume we have an algorithm $A$ with an oracle $O'$, and an algorithm $B$ that implements the oracle $O'$.
The functional composition of the two is an algorithm $A\circ B$, where the algorithm $B$ is used as a subroutine to process the queries made by $A$ to $O'$.
The subroutine $B$ has access to some oracle $O$, which is also the input to $A\circ B$.
For simplicity we will now assume that $A$ has no access to $O$, but we will drop this assumption shortly.
The main question is a bound on the complexity of $A\circ B$ in terms of complexities of $A$ and $B$.

One particular example studied extensively both classically and quantumly is given by composed functions, i.e., functions of the form

\begin{equation}
\label{eqn:randomComposedFunction}
g_1(z_{1,1}, \dots,z_{1,m}),
g_2(z_{2,1}, \dots,z_{2,m}),
\dots,
g_n(z_{n,1}, \dots,z_{n,m})].
\end{equation}

(For simplicity of notation, we assume all the functions $g_i$ are on $m$ variables, which is without loss of generality.)
Then, $O$ encodes the input string $z$, and $A$ evaluates the function $f$.
Concerning $B$, it is a parallel composition $B=\bigoplus_i B_i$ of algorithms evaluating $g_i$.
On query $i$, $B$ returns the output of $B_i$, which is $g_i(z_{i,1}, \dots,z_{i,m})$.

In general, the parallel composition $B=\bigoplus_i B_i$, which we also call the direct sum, has queries of the form $(i,j)$, on which it responds with the output of $B_i$ on query $j$.
We assume that all $B$ and $B_i$ have access to the same oracle $O$.
In the example above, all $j$ are absent.
Also, although each $B_i$ has access to $O$, it only uses the substring $z_i = (z_{i,1}, \dots,z_{i,m})$ thereof.

§.§ Randomised Complexity

Recall the distinction between Las Vegas and Monte Carlo randomised algorithms. A Monte Carlo algorithm is a randomised algorithm that takes at most some fixed number $T$ of time steps, and outputs the correct answer with bounded error.
The complexity of such an algorithm is simply $T$. This is analogous to the usual bounded-error quantum query model.
In contrast, a Las Vegas algorithm is a randomised algorithm whose number of steps is a random variable $T$, and that never outputs an incorrect answer (though it may run forever). The complexity of such an algorithm is $\E[T]$. More generally, one might consider the Las Vegas complexity, $\E[T]$, of an algorithm whose running time is a random variable $T$, even if the algorithm has some probability of erring (that is, it is not strictly a Las Vegas algorithm).

Randomised Las Vegas complexity behaves nicely with respect to composition.
Here we sketch the corresponding notions and results in order to facilitate the forthcoming introduction of the related quantum notions, and to have a reference point against which we can gauge our quantum composition results.

Let us start with functional composition.
Let $T\rand(A,O')$ be the complexity of the algorithm $A$ on the oracle $O'$.
Let $B(O)$ denote the action of the algorithm $B$ on the oracle $O$, and $T\rand(B, O, i)$ the complexity of $B(O)$ on query $i$.
Denote by $q^{(i)}\rand(A,O')$ the probability the algorithm $A$ will give $i$ as a query to the oracle $O'$ (we assume each query is given at most once).
Then, it is not hard to see that the total complexity of $A\circ B$ on oracle $O$ is given by

\begin{equation}
\label{eqn:randomComposition}
T\rand(A\circ B,O) = T\rand\sA[A, B(O)] + \sum_i q^{(i)}\rand\sA[A, B(O)]\cdot T\rand(B, O, i).
\end{equation}

Let us rewrite this formula to illuminate transition to the quantum case.
Define the total query vector of the algorithm $A$ as a formal linear combination

\[
q\rand(A, O') = \sum_i q^{(i)}\rand (A,O') e_i
\]

for $e_i$ the elements of the standard basis.
Let by definition the complexity of $B$ on such a vector be

\begin{equation}
\label{eqn:randomComplexityExtended}
T\rand\sB[B, O, \sum_i p_i e_i] = \sum_i p_i\, T\rand\sA[B, O, i].
\end{equation}

Then, we can rewrite eqn:randomComposition as

\begin{equation}
\label{eqn:randomComposition2}
T\rand(A\circ B, O) =  T\rand\sA[A,B(O)] + T\rand\sA[B, O, q\rand(A,B(O))],
\end{equation}

which says that the complexity of the composed program on the oracle $O$ equals the complexity of $A$ by itself plus the complexity of $B$ on its total query vector.
This equation will serve as our “gold standard” of thriftiness in functional composition.

Similarly, thriftiness holds for parallel composition.
Let $\xi = \sum_{i,j} \xi_{i,j} e_{i,j}$ be a query vector for $\bigoplus_i B_i$.
We can break it down as

\begin{equation}
\label{eqn:randomXiDecomposition}
\xi = \bigoplus_i \xi_i,
\end{equation}

where $\xi_i = \sum_j \xi_{i,j} e_{i,j}$ is the corresponding query vector for the constituent $B_i$.
Then, we have

\begin{equation}
\label{eqn:randomParallelComplexity}
T\rand\sB[\bigoplus_i B_i, O, \xi] = \sum_{i} T\rand\sA[B_i, O, \xi_i].
\end{equation}

(We assume here that relaying from $B$ to the corresponding $B_i$ is done instantly.)

These results can be combined in various ways.
For instance, assume the oracle $O'$ in the functional composition settings is a direct sum $O'=\bigoplus_{i=1}^n O^{(i)}$ of $r$ independent oracles $O^{(i)}$.
Let $B_i$ implement $O^{(i)}$, so that $B = \bigoplus_i B_i$ implements $O'$.
Similarly as in eqn:randomXiDecomposition, we can decompose the corresponding total query vector

\[
q\rand(A, O') = \bigoplus_i q\rand^{(i)}(A,O')
\]

into partial query states corresponding to the $i$-th oracle.
In this way, the multiple-oracle case differs from the single-oracle case only by this change of perspective.
Combining eqn:randomComposition2 and eqn:randomParallelComplexity, we obtain

\begin{equation}
\label{eqn:randomComposition3}
T\rand(A\circ B, O) = T\rand\sA[A,B(O)] + \sum_i T\rand\sA[B_i, O, q\rand^{(i)}(A,B(O))].
\end{equation}

§.§ Quantum Complexity

The usual definition of quantum query algorithms does not allow for different complexities on different inputs, hence, we cannot even properly define a meaningful analogue of eqn:randomComposition.
However, it is possible for Las Vegas complexity of quantum query algorithms defined in [16].
We will demonstrate here that it possesses properties essentially identical to those of the randomised case.
For a more formal definition of the model of query algorithms and the Las Vegas complexity, refer to sec:prelimQuery.

Let $A = A(O)$ be a quantum algorithm in space $\cH$ with an oracle $O$ in space $\cM$.
We denote by $A(O)$ the action of $A$ on a specific input oracle $O$.
We use $T(A)$ to denote time complexity of $A$, and $Q(A)$ to denote the number of queries made by $A$.

What is important, is that the queries to the input oracle $O$ are conditional.
This means that the query applies $O$ to a subspace $\cHq\subseteq\cH$ of the workspace $\cH$, and is the identity elsewhere.
The total query state $q(A,O,\xi)$ records the history of all the queries given by the algorithm $A$ to the input oracle $O$ on the initial state $\xi$.
In other words, it is the direct sum

\[
q(A,O,\xi) = \bigoplus_{t=1}^{Q(A)} \psi^\bullet_t = \sum_{t=1}^{Q(A)} \ket|t> \ket |\psi^\bullet_t>,
\]

where $\psi^\bullet_t\in \cHq$ is the state given to the input oracle on the $t$-th query.
We have $q(A,O,\xi) \in \cE\otimes \cM$ for some space $\cE$.
The Las Vegas query complexity is defined as $L(A,O,\xi) = \|q(A,O,\xi)\|^2$.
This definition has an operational meaning: the algorithm can be modified to use $\OO(L)$ queries, where $L$ is the worst-case Las Vegas query complexity, by introducing some small error.

One convention of this paper is that we usually only allow unidirectional access to $O$.  The algorithm can only execute $O$, but not its inverse $O^*$.
This is without loss of generality, as bidirectional access to $O$, when the algorithm can execute both $O$ and $O^*$, is equivalent to unidirectional access to $O\oplus O^*$.

As in the randomised case, $r$ input oracles can be combined into one as follows:

\begin{equation}
\label{eqn:introMultipleOracles}
O = O^{(1)}\oplus O^{(2)}\oplus \cdots \oplus O^{(r)}.
\end{equation}

The partial query state $q^{(i)}(A,O,\xi)$ of the $i$-th input oracle is defined as the direct sum of all the states given to that particular oracle $O^{(i)}$.
In particular,
q(A, O, \xi) = \bigoplus_i q^{(i)} (A, O,\xi).
Similarly as before, the Las Vegas query complexity of the $i$-th input oracle is
L^{(i)}(A, O, \xi) = \normA|q^{(i)}(A,O,\xi)|^2.

Parallel Composition
The parallel composition is straightforward.
For programs $B_1,\dots, B_n$, all on the input oracle $O$, its direct sum is $\bigoplus_i B_i$, which executes $B_i$ on orthogonal parts of the space.
It is not hard to show that

\begin{equation}
\label{eqn:quantumParallel}
q\sB[\bigoplus_i B_i, O, \bigoplus_i \xi_i] = \bigoplus_i q(B_i, O, \xi_i),
\end{equation}

where we implicitly assume the correct arrangement of the entries in the corresponding direct sums.
A direct consequence is the following counterpart of eqn:randomParallelComplexity:

\[
L\sB[\bigoplus_i B_i, O, \bigoplus_i \xi_i] = \sum_i L(B_i, O, \xi_i).
\]

Functional Composition
Let us now derive a quantum query analogue of eqn:randomComposition2.
First, though, we define a counterpart of eqn:randomComplexityExtended.
For $\xi'\in \cE\otimes \cH$, we can write $\xi' = \xi_1\oplus \xi_2 \oplus \cdots \oplus \xi_m$ with $\xi_t\in \cH$, and define

\begin{equation}
\label{eqn:queryStateExtended}
q(A,O,\xi') = \bigoplus_t q(A, O, \xi_t).
\end{equation}

This is precisely the total query state we will get if we tensor-multiply $A$ by the identity in the register $\cE$ and execute it on $\xi'$.
The corresponding Las Vegas query complexity is

\begin{equation}
\label{eqn:LasVegasExtended}
L(A, O, \xi') = \|q(A, O, \xi')\|^2.
\end{equation}

Now consider fig:composition, which depicts composition of two quantum programs, and which goes along the lines of our previously discussed randomised case.
This time, however, we consider a more general case when $A$ has access to the input oracle $O$ as well.

General case of functional composition of two programs.
The outer program $A$ has two oracles $O$ and $O'$, which we identify with the oracle $O\oplus O'$.
The oracle $O'$ is implemented by a program $B$ with access to $O$.
The diagram specifies the corresponding query states, where we use the upper indices ${}^{(0)}$ and ${}^{(1)}$ in relation to $O$ and $O'$, respectively.

\[
\begin{tikzpicture}[every path/.append style={thick,->}]
\draw[\xicolor] (-1, 1) node[left]{$\xi$} to (0,1);
\draw (0,0) rectangle (3,1.5) node[pos=0.5] {$A(O\oplus O')$};
\draw (4,0) rectangle (7,-1.5) node[pos=0.5] {$O' = B(O)$};
\draw (0, -3) rectangle (7,-4.5) node[pos=0.5] {\Large $O$};
\draw[purple] (1.5,0) to node[left] {\scriptsize $q^{(0)}(A, O\oplus O', \xi)$} (1.5,-3);
\draw[purple, out=0, in=90] (3, 1) to node[above]{\scriptsize $q^{(1)}(A, O\oplus O', \xi)$} (5.5,0);
\draw[purple] (5.5, -1.5) to node[right] {\scriptsize $q\sB[ B, O, q^{(1)}(A, O\oplus O', \xi)]$}(5.5,-3);
\end{tikzpicture}
\]

The composed algorithm $A\circ B$ is implemented by replacing each execution of $O'$ by an execution of $B$.
Its action on the input oracle $O$ is equal to $A\sA[O\oplus B(O)]$.
It is not hard to show that

\begin{equation}
\label{eqn:quantumComposition}
q(A\circ B, O, \xi) = q^{(0)}\sB[A, O\oplus B(O), \xi]\; \oplus\; q\sB[ B, O, q^{(1)}{\sA[A, O\oplus B(O), \xi]}].
\end{equation}

Similarly to eqn:randomComposition2, this slightly complicated expression represents a very intuitive observation that the total query state of $A\circ B$ on the input oracle $O$ consists of the part of the query state of $A$ given directly to $O$ (denoted $q^{(0)}$), together with the query state of $B$ on the initial state composed of the part of the query state of $A$ given to $O'$ (denoted $q^{(1)}$).

A version of fig:composition where the oracle $O'$ is decomposed into $r$ input oracles $O' = O^{(1)}\oplus\cdots\oplus O^{(r)}$ and the program $B$ is accordingly decomposed into $B = B_1\oplus\cdots\oplus B_r$ so that $B_i$ implements $O^{(i)}$.
The diagram specifies the corresponding query states, where we use the upper index ${}^{(0)}$ in relation to $O$.
We note that it is without loss of generality to assume that $A$ and all $B_i$ use the same input oracle $O$.
Indeed, if this is not the case, we can define $O$ as the direct sum of the oracles used by $A$ and $B_i$.

\[
\begin{tikzpicture}[every path/.append style={thick,->}]
\draw[\xicolor] (-1, 2) node[left]{$\xi$} to (0,2);
\draw (0,1) rectangle (3,2.5) node[pos=0.5] {$A(O\oplus O')$};
\draw (3,0) rectangle (6,-1.5) node[pos=0.5] {$O^{(1)} = B_1(O)$};
\node at (7.5, -0.75) {\Large$\cdots$};
\draw (8.5,0) rectangle (11.5,-1.5) node[pos=0.5] {$O^{(r)} = B_r(O)$};
\draw (0, -3) rectangle (11.5,-4.5) node[pos=0.5] {\Large $O$};
\draw[purple] (1.5,1) to node[left] {\scriptsize $q^{(0)}(A, O\oplus O', \xi)$} (1.5,-3);
\draw[purple, out=0, in=90] (3, 1.5) to node[right, pos=0.8]{\scriptsize $q^{(1)}(A, O\oplus O', \xi)$} (4.5,0);
\draw[purple, out=0, in=90] (3, 2.25) to node[right, pos=0.95]{\scriptsize $q^{(r)}(A, O\oplus O', \xi)$} (10.5,0);
\draw[purple] (4.5, -1.5) to node[right] {\scriptsize $q\sB[ B_1, O, q^{(1)}(A, O\oplus O', \xi)]$}(4.5,-3);
\draw[purple] (10, -1.5) to node[right] {\scriptsize $q\sB[ B_r, O, q^{(r)}(A, O\oplus O', \xi)]$}(10,-3);
\end{tikzpicture}
\]

It is quite often the case, that the oracle $O'$ above is composed of several input oracles, each implemented by its own subroutine $B_i$, see fig:compositionMultiple.
In this case, we can use eqn:quantumParallel to obtain an analogue of eqn:randomComposition3:

\begin{equation}
\label{eqn:quantumCompositionMultiple}
q(A\circ B, O, \xi) = q^{(0)}\sB[A, O\oplus B(O), \xi]\; \oplus\; \bigoplus_i q\sB[B_i, O, q^{(i)}{\sA[A, O\oplus B(O), \xi]}].
\end{equation}

It is often convenient to define $L_{\max}(B,O)$ as the worst-case complexity of $L(B,O,\xi)$ as $\xi$ ranges over all unit vectors (or over all unit vectors in some admissible subspace of initial vectors).
Then, using linearity, we can obtain from eqn:quantumComposition:

\begin{align}
L(A\circ B, O, \xi)
&= L^{(0)}\sB[A, O\oplus B(O), \xi]\; +\; L\sB[ B, O, q^{(1)}{\sA[A, O\oplus B(O), \xi]}] \label{eqn:quantumComposition1}\\
&\le L^{(0)}\sB[A, O\oplus B(O), \xi]\; +\; L_{\max}(B,O) L^{(1)}\sA[A, O\oplus B(O), \xi]
\label{eqn:quantumComposition2}.
\end{align}

and from eqn:quantumCompositionMultiple

\begin{align}
L(A\circ B, O, \xi)
&= L^{(0)}\sB[A, O\oplus B(O), \xi]\; +\; \sum_i L\sB[B_i, O, q^{(i)}{\sA[A, O\oplus B(O), \xi]}] \label{eqn:quantumCompositionMultiple1}\\
&\le L^{(0)}\sB[A, O\oplus B(O), \xi]\; +\; \sum_i L_{\max}(B_i,O) L^{(i)}\sA[A, O\oplus B(O), \xi]
\label{eqn:quantumCompositionMultiple2}.
\end{align}

In eqn:quantumComposition2 and eqn:quantumCompositionMultiple2, it is assumed that $B$ and $B_i$ are only executed on the admissible initial states.

To summarise, we see that quantum Las Vegas query complexity satisfies composition properties very similar to the “gold standard” of the randomised Las Vegas complexity.
One of the goals of this paper is to approach these results for quantum time complexity.
In [24], a result in this direction was obtained for evaluation of functions assuming the QRAG model of computation.
In this paper, we consider more general state conversion settings, and also obtain partial results for the circuit model.
We also think that the approach of this paper is less technical than the one taken in in [24].

§ OVERVIEW OF THE PAPER

This section serves as an informal version of the whole paper, where we introduce all the main concepts, ideas, and sketch the proofs of the main results.
In the remaining paper, we fill in all the technical gaps.

§.§ Transducers

In the current paper, we take a different approach to time complexity than in the two papers [21, 24] mentioned in sec:introPrior.
Instead of using span programs or quantum walks, we build on the key technical primitive from [16], which we call a transducer[Not to be confused with transducers from the theory of finite automata, however there are some connections between the two, as we discuss in sec:automaton.]
in this paper.

Transducers are based on the following mathematical observation
we prove in sec:transducerDefinition:

Let $S$ be a unitary acting in a direct sum of two vectors spaces $\cH\oplus \cL$.
For every $\xi\in \cH$, there exists a unique $\tau = \tau(S,\xi)\in \cH$ and in some sense unique $v = v(S,\xi)\in \cL$ such that

\begin{equation}
\label{eqn:1transduce}
S\colon \xi \oplus v \mapsto \tau \oplus v.
\end{equation}

We say in the setting of eqn:1transduce that $S$ transduces $\xi$ into $\tau$, denoted $\xi\transduce{S} \tau$ or $S\colon\xi\transduce{} \tau$.
This defines a mapping $\xi\mapsto \tau$ on $\cH$, which turns out to be unitary.
We call it the transduction action of $S$ on $\cH$, denoted by $S\DownTransduce_\cH$.
See fig:transducer for a schematic depiction.
The motivation behind this terminology is that while $S$ does not literally map $\xi$ into $\tau$, having $S$ is a legitimate and fruitful way of implementing $S\DownTransduce_\cH$ on a quantum computer, as we show shortly.
If a unitary $S$ is designed primarily with this application in mind, we call it a transducer, and say that it implements $S\DownTransduce_\cH$.

Schematic depiction of transducers.  To the left is the real action of $S$, which is interpreted as the action of $S\DownTransduce_\cH$ on $\cH$.

Note that parallel wires here denote direct sum of the corresponding subspaces, not tensor product.  The same applies to the other figures in this paper.

\[
\begin{tikzpicture}
\draw (0,0) rectangle (1, 2) node[pos=0.5] {$S$};
\draw[->,\witnesscolor, thick] (-1,0.5) node[above]{$v$} to (0,0.5);
\draw[->,\xicolor, thick] (-1,1.5) node[above]{$\xi$} to (0,1.5);
\draw[->,\witnesscolor, thick] (1,0.5) to (2,0.5) node[above]{$v$};
\draw[->,\taucolor, thick] (1,1.5) to (2,1.5) node[above]{$\tau$};
\draw (6,1) rectangle (7, 2) node[pos=0.5] {$S\DownTransduce_\cH$};
\draw[->,\xicolor, thick] (5,1.5) node[above]{$\xi$} to (6,1.5);
\draw[->,\taucolor, thick] (7,1.5) to (8,1.5) node[above]{$\tau$};
\end{tikzpicture}
\]

Let us note that this construction is not new.
It has appeared before as an additive trace in the category of isometries in finite-dimensional Hilbert spaces [8, 7].
Here we demonstrate that this construction has an operational meaning.
It would be interesting to understand the connection between our construction and the one taken in these two references.

We will stick to the following terminology.
We call $\cH$ the public and $\cL$ the private space of $S$.
We say that the transducer $S$ is on the space $\cH$, but works in the space $\cH\oplus \cL$.
Also, we will call $\xi$ the initial state of $S$, while $\xi\oplus v$ is
the initial coupling.

We call $v$ the catalyst of the transduction eqn:1transduce because it helps in the transformation of $\xi$ into $\tau$, but is not changed in the process.
The role of the catalyst is similar to the role of the witness in span programs.
In particular, the transduction complexity of the transducer $S$ on an initial vector $\xi\in \cH$ is given by its size:

\begin{equation}
\label{eqn:introWitnessSize}
W(S,\xi) = \|v(S,\xi)\|^2.
\end{equation}

Let $T(S)$ denote the usual time complexity of implementing $S$ as a unitary.
As a rule of thumb, among various transducers $S$ with the same transduction action, there is a trade-off between $W$ and $T$ so that the product

\begin{equation}
\label{eqn:tradeoff}
(1+W(S,\xi)) \;\cdot\; T(S)
\end{equation}

stays approximately the same.
The importance of this product can be readily seen from the following result.

Let spaces $\cH, \cL$, and parameters $W, \eps>0$ be fixed.
There exists a quantum algorithm that $\eps$-approximately transforms $\xi$ into $S\DownTransduce_\cH\, \xi$ for all transducers $S\colon \cH\oplus \cL \to \cH\oplus \cL$ and initial states $\xi\in\cH$ such that $W(S,\xi)\le W$.
The algorithm conditionally executes $S$ as a black box $K = \OO(1+W/\eps^2)$ times, and makes $\OO(K)$ other elementary operations.

Since $S$ generally takes at least one elementary operation, the complexity of the algorithm is dominated by the executions of $S$, which takes time eqn:tradeoff up to constant factors (assuming $\eps = \Theta(1)$).
The term 1 in the definition of $K$ is required as we can have non-trivial transducers with $W=0$, see, e.g., sec:introAlgorithm->Transducer.
Also, as follows from the discussion in [16], the dependence on $\eps$  is optimal.

[Proof sketch of thm:introImplementation]
We are given a copy of $\xi$, and our goal is to transform it into $\tau = S\DownTransduce_{\cH} \xi$ using $S$ as a black box.
Assume we are additionally given a copy of $v$ (in the sense of direct sum, cf. fig:transducer).
Then, we can perform the required transformation $\xi \oplus v \mapsto \tau\oplus v$ using $S$.

There are two problems here.
First, the algorithm is not given $v$, and, second, $v$ can have a huge norm.
The second problem is solved by breaking $\xi$ down into $K$ copies of $\xi/\sqrt K$, that is, performing the transformation $\xi \mapsto \sum_{t=0}^{K-1} \ket |t>\ket|\xi>/\sqrt K$.
The key idea is that we can use the same scaled down catalyst $v/\sqrt{K}$ to perform $K$ scaled down transductions $\xi/\sqrt{K} \transduce{} \tau/\sqrt{K}$ as $v/\sqrt{K}$ does not change in the process.
See fig:pumping, for an illustration.

The first problem is solved by “guessing” $v/\sqrt{K}$, i.e., using that $\xi$ is close to $\xi\oplus v/\sqrt{K}$ if $K$ is sufficiently large.
The larger the value of $K$, the smaller the error imposed by guessing, but the larger the number of executions of $S$.
For a formal proof, see sec:implementation.

A graphical illustration of the construction of thm:introImplementation.
The initial state $\xi$ is broken down into $K=4$ copies of $\xi/\sqrt{K}$, which are sequentially transformed into $\tau/\sqrt K$ using only one copy of the scaled-down catalyst $v/\sqrt{K}$.

witness/.style=above, node contents=$\frac{v}{\sqrt{K}}$

\[
\begin{tikzpicture}
\draw[thick, \xicolor] (-1.5,\xiheight) to node[above]{$\xi$} (-1,\xiheight);
\draw[thick, \taucolor] (12.5,\xiheight) to node[above]{$\tau$} (12,\xiheight);
\draw[->, thick, \witnesscolor] (-1.5,\witnessheight) to node[witness]{} (0.5,\witnessheight);
\OneIteration{0}
\OneIteration{1}
\OneIteration{2}
\OneIteration{3}
\end{tikzpicture}
\]

§.§ Connection to Quantum Walks

In this section, we take a short detour, and inspect the connection between transducers and quantum walks.
Like transducers, quantum walks [37] replace the desired transformation with some other transformation that is easier to implement: one iteration of the quantum walk.
See fig:trans2walk for an informal comparison between transducers and quantum walks, on which we will elaborate in this section.

An informal correspondence between transducers and quantum walks.

\[
\begin{tabular}{r>{$\longleftrightarrow$}cl}
Transducer&&Quantum Walk\\
Execution of $S$&&One Iteration $R_2R_1$\\
Transformation $S\DownTransduce_{\cH}$ && Accept/reject of the initial state\\
$W(S,\xi)$ && Spectral Gap\\
\rf{thm:introImplementation} && Phase Estimation
\end{tabular}
\]

In this paper, we consider broadly interpreted discrete-time quantum walks.
We identify the two characteristic properties of such algorithms, where the first one is essential, and the second one is usual, but not, strictly speaking, necessary.

The first, essential property is that one iteration of a quantum walk is a product of two reflections $R_1$ and $R_2$.
The quantum walk either rejects
the initial state $\xi$, when it is close to an eigenvalue-1 eigenvector of $R_2R_1$;
or accepts it, when $\xi$ is mostly supported on eigenvectors with eigenvalues far from 1.
The most standard implementation of quantum walks is a phase estimation of the product $R_2R_1$ on the initial state $\xi$.
The analysis of quantum walks involves spectral analysis, sometimes assisted by the effective spectral gap lemma [28].

The second, optional property is that each reflection, $R_1$ and $R_2$, is broken down as a product of local reflections that act on pairwise orthogonal subspaces.
This allows for their efficient implementation.
The walk is usually described using a bipartite graph (like in fig:walk), where each edge corresponds to a portion of the space.
Local reflections are given by vertices, and they act on the direct sum of spaces corresponding to their incident edges.
The reflection $R_1$ executes all the local reflections for one part of the bipartite graph, and $R_2$ for the second.
The two reflections, interleaving, transcend locality and form an involved global transformation.

Because of the second property, quantum walks find a large number of algorithmic applications.
This includes such basic primitives as Grover's algorithm [23] and amplitude amplification [18]; as well as the element distinctness algorithm [1], Szegedy quantum walks [39] and their various extensions, span programs [32], learning graphs [11], and others.

We will show that quantum walks are very often transducers of the following form.
Let $\cH$ and $\cL$ be the public and the private spaces, so that the initial state $\xi\in\cH$.
The transducer is the iteration of the walk: $S = R_2R_1$, where we additionally assume that the second reflection $R_2$ acts trivially on $\cH$.
If $\xi$ is negative, we have the following chain of transformations:

\begin{equation}
\label{eqn:QW_sequence_negative}
\xi \oplus v \maps{R_1} \xi \oplus v \maps{R_2} \xi \oplus v,
\end{equation}

certifying that $\xi\transduce{S}\xi$.
In the positive case, we have the following sequence of transformations:

\begin{equation}
\label{eqn:QW_sequence_positive}
\xi \oplus v \maps{R_1} -\xi \oplus -v \maps{R_2} -\xi \oplus v,
\end{equation}

certifying that $\xi\transduce{S}-\xi$.

Both sequences follow the standard practice of designing quantum walks.
In the negative case, $\xi\oplus v$ is a stationary vector of both $R_1$ and $R_2$, and, hence, $R_2R_1$.
In the positive case, $\xi\oplus v$ is the witness for the Effective Spectral Gap Lemma.
The transduction vantage point unites these asymmetric positive and negative analyses.
An interesting artefact of this construction is that the transduction action of the corresponding quantum walk is exact: It transduces $\xi$  to either $\xi$ or $-\xi$ exactly.

We will illustrate this construction in more detail in sec:walks by re-proving the main result of [12] on electric quantum walks.
However, the same applies to any quantum walk that adheres to the same design principles, including algorithms derived from span programs <cit.>, and more generally, algorithms of the type formally defined in <cit.>.

To epitomise, we keep the iteration of the quantum walk intact, but replace the wrapping phase estimation by the algorithm of thm:introImplementation.
In this way, we significantly simplify the construction by abandoning any spectral analysis both from the implementation and the analysis of the algorithm.
We believe this is worthy from the pedagogical point of view, as the corresponding algorithms now require very little background knowledge.

§.§ Input Oracle and the Canonical Form

Our previous discussion in sec:introTransducers did not consider the input oracle.
In this paper, we assume an approach similar to that of quantum query algorithms, where oracle executions and the remaining operations are separated.
Moreover, unlike the algorithms, it suffices to have one query for a transducer.

We define the canonical form of a transducer $S=S(O)$ with the input oracle $O$ in fig:canonical.
The private space $\cL = \cLw\oplus\cLq$ is decomposed into the work part $\cLw$ and the query part $\cLq$, with the imposed decomposition $v = \vw\oplus\vq$ of the catalyst $v$.
The query is the very first operation, and it acts only on $\vq$.
It is followed by a unitary $\Sw$ without queries.

A schematic depiction of a transducer in the canonical form.
It consists of one application of the oracle $O$ and an input-independent unitary $\Sw$.
The catalyst $v\in\cL$ is separated into two parts $v=\vw\oplus \vq$ with $\vw\in\cLw$ and $\vq\in\cLq$.
The first one is not processed by the oracle, and the second one is.
Note that the input oracle is not applied to the public space.

\[
\begin{tikzpicture}[every path/.append style={thick,->}]
\draw (2,0) rectangle (3, 3) node[pos=0.5] {$\Sw$};
\draw (-0.2,0) rectangle (1.2, 1) node[pos=0.5] {$I\otimes O$};
\draw[\nonquerycolor] (-1,0.5) node[above]{$\vq$} to (-0.2,0.5);
\draw[\witnesscolor] (-1,1.5) node[above]{$\vw$} to (2,1.5);
\draw[\xicolor] (-1,2.5) node[above]{$\xi$} to (2,2.5);
\draw[\nonquerycolor] (3,0.5)  to (4,0.5) node[above]{$\vq$};
\draw[\witnesscolor] (3,1.5) to (4,1.5) node[above]{$\vw$} ;
\draw[\taucolor] (3,2.5) to (4,2.5) node[above]{$\tau$} ;
\draw[\querycolor] (1.2,0.5) to (2,0.5);
\end{tikzpicture}
\]

Canonical transducers are easier to deal with, and every transducer can be converted into the canonical form (see prp:canoning).
We will generally assume our transducers are canonical.
We write $W(S, O, \xi)$ instead of $W\sA[S(O),\xi]$ for the transduction complexity $ W(S,O,\xi) = \|v\|^2 = \|\vw\|^2 + \|\vq\|^2$.
Also, the total query state is defined by $q(S, O, \xi) = \vq$, and the query complexity by $L(S, O, \xi) = \|\vq\|^2$.

This definition is compatible with the case when $O$ is combined of several input oracles like in eqn:introMultipleOracles.
In this case, we define the partial query state $q^{(i)}(S, O, \xi)$ as the state processed by the oracle $O^{(i)}$, and $L^{(i)}(S, O, \xi) = \norm|q^{(i)}(S, O, \xi)|^2$.

The following result, which justifies the name “query complexity”, is proven in sec:reducingOracle:

Let spaces $\cH, \cL=\cLw\oplus \cLq$ be fixed.
Moreover, assume the transducer uses $r=\OO(1)$ input oracles combined as in eqn:introMultipleOracles.
Let $\eps, W, L^{(1)},\dots,L^{(r)}>0$ be parameters.
Then, there exists an algorithm that conditionally executes $\Sw$ as a black box $K=\OO(1+W/\eps^2)$ times,
makes $\OO(L^{(i)}/\eps^2)$ queries to the $i$-th input oracle $O^{(i)}$, and uses $\OO(K)$ other elementary operations.
The algorithm $\eps$-approximately transforms $\xi$ into $\tau(S, O, \xi)$ for all $S$, $O^{(i)}$, and $\xi$ such that $W(S, O, \xi)\le W$ and $L^{(i)} (S, O, \xi) \le L^{(i)}$ for all $i$.

[Proof Sketch]
Let us first consider the special case of $r=1$ for simplicity.
The crucial new idea compared to thm:introImplementation is that we guess not one but some $D$ copies of the state $\vq$.
They are all processed by one oracle call, and then gradually given to $\Sw$, see fig:implementationBetter.
Thus, the transduction complexity becomes $\|\vw\|^2 + D \|\vq\|^2$, but we have to execute the input oracle only once in every $D$ iterations.
The correct choice of $D$ is around $\|\vw\|^2/ \|\vq\|^2$, so that the norms of the query and the non-query parts of the catalyst become equalised.
If there are $r=\OO(1)$ input oracles, we perform the same procedure for all of them.
The total transduction complexity grows by a factor of $r$, which is tolerable by our assumption of $r=\OO(1)$.

A graphical illustration of the construction of thm:introImplementationBetter with the same parameters as in fig:pumping, and $D=2$.
We write $O$ instead of $I \otimes O$ to save space.

Note that one oracle execution and $D$ subsequent executions of $\Sw$ form a transducer of its own.

witness/.style=above, node contents=$\frac{\vw}{\sqrt{K}}$

\[
\begin{tikzpicture}[every node/.style={font=\scriptsize}, every path/.append style={thick,->}]
\draw[-, \xicolor] (-1.5,\xiheight) to node[above]{\normalsize$\xi$} (-1,\xiheight);
\draw[-, \taucolor] (12.5,\xiheight) to node[above]{\normalsize$\tau$} (12,\xiheight);
\draw[\witnesscolor] (-1.5,\witnessheight) to node[witness]{} (0.5,\witnessheight);
\draw[\nonquerycolor] (-1.5,\queryheight) to node[above]{\scriptsize $\frac{\vq}{\sqrt{K}}$} (-0.9,\queryheight);
\draw[thick, \nonquerycolor] (-1.5,1.5) to node[above]{\scriptsize $\frac{\vq}{\sqrt{K}}$} (-0.9,1.5);
\draw[\nonquerycolor] (11, 3) to (12.5,3);
\draw[\nonquerycolor] (11, 1.5) to (12.5,1.5);
\OneIteration{0}
\OneIteration{1}
\OneIteration{2}
\OneIteration{3}
\Oracle{0}
\Oracle{2}
\end{tikzpicture}
\]

This theorem does not hold for superconstant values of $r$, in which case a more technical thm:optimalImplementation should be used.
Note how canonicity of the transducer $S$ is used here.
Indeed, the input oracle is executed only once in each execution of the transducer, reducing the total number of oracle calls.

The definition of the canonical form is inspired by the implementation of the adversary bound for state conversion from [16].
Moreover, as we show in sec:stateConversion, the adversary bound is essentially equivalent to the above construction with $\cLw$ being empty.
Also, we show in sec:function how to implement the usual adversary bound for function evaluation:

For every function $f\colon D\to [p]$ with $D\subseteq[q]^n$, there exists a canonical transducer $S_f$ with input oracle $O_x$ encoding the input string $x$, such that, for every $x\in D$, $S_f$ transduces $\ket |0>\transduce{} \ket |f(x)>$ on the input oracle $O_x$, and

\[
W\sA[S_f, O_x, \ket|0>] =
L\sA[S_f, O_x, \ket|0>] \le \Adv(f),
\]

where $\Adv(f)$ is the adversary bound of $f$, defined in sec:function.

We can draw the following parallels with span programs.
It is known that the dual adversary bound for Boolean functions is equivalent to a very special case of span programs [31].
General span programs provide more flexibility, and thus are more suitable for time-efficient implementations [15, 34, 26, 21].
While it is possible to implement the dual adversary bound time-efficiently [4], the constructions are more complicated.

Span programs sometimes model more general function evaluation [9]; but the dual adversary has been extended much further to include arbitrary state conversion [28] with general unitary input oracles [14].

Transducers treat state conversion with unitary input oracles very naturally.
Adding the non-query space $\cLw$ provides more flexibility compared to the dual adversary, which again is beneficial for time-efficient implementations.
It is also of great help that transducers are quantum algorithms themselves, which makes time analysis especially straightforward.

Summarising, there are three basic complexity measures associated with a transducer:

* Time complexity $T(S)$, which is independent of the input oracle $O$ and the initial state.  Similarly to usual quantum algorithms, the precise value of $T(S)$ depends on the chosen model of quantum computation.

* Transduction complexity $W(S,O,\xi)$.  It is defined mathematically, and does not depend on the model.
On the other hand, it depends on both the input oracle and the initial state.

* Query complexity $L(S,O,\xi)$.
It is also defined mathematically, and does not depend on the model.
The query state $q(S,O,\xi)$ provides more information.

Let us finish this section with a few technicalities.
Similarly to eqn:queryStateExtended and eqn:LasVegasExtended, we extend the above definitions to $\xi' = \xi_1\oplus\cdots\oplus \xi_m\in\cE\otimes \cH$ via

\begin{equation}
\label{eqn:transductionExtended}
q(S,O,\xi') = \bigoplus_t q(S, O,\xi_t),\quad
L(S,O,\xi') = \sum_t L(S, O,\xi_t),
\quad \text{and}\quad
W(S, O, \xi') = \sum_t W(S, O,\xi_t).
\end{equation}

Again, these can be interpreted as the complexities of the transducer $I_\cE\otimes S$, see cor:byIdentity.

If for $\xi\in\cH$ we use a catalyst $v$, for $c\xi$ with $c\in\bC$, we can use the catalyst $cv$.
This yields

\begin{equation}
\label{eqn:introLinearity}
W(S, O, c\xi) = |c|^2 W(S, O, \xi),
\quad
q^{(i)} (S, O, c\xi) = c\, q^{(i)} (S, O, \xi),
\quad
L^{(i)} (S, O, c\xi) = |c|^2 L^{(i)} (S, O, \xi).
\end{equation}

It often makes sense to define the subspace $\Hgood\subseteq \cH$ of admissible initial vectors to the transducer $S(O)$,
and define $\Wmax(S, O)$ as the supremum of $W(S, O, \xi)$ as $\xi$ ranges over unit vectors in $\Hgood$.
We define $\Lmax$ and $\Lmax^{(i)}$ similarly.
We say that the initial state $\xi'\in \cE\otimes \cH$ is admissible if it lies in $\cE\otimes \Hgood$.
For any such state, by eqn:transductionExtended and eqn:introLinearity, we have

\begin{equation}
\label{eqn:admissibleQuery}
W(S, O, \xi') \le \Wmax(S, O) \|\xi'\|^2
\qqand
L(S, O, \xi') \le \Lmax(S, O) \|\xi'\|^2.
\end{equation}

§.§ Transducers from Quantum Algorithms

In this section, we briefly explain how we achieve one of the points on our agenda: conversion of arbitrary quantum algorithms into transducers.
We consider both the QRAG model mentioned at the end of sec:introPrior, and the usual circuit model.
While the stronger QRAG model allows for better and more intuitive exposition, we are still able to get some useful results in the circuit model.

\begin{equation}
\label{eqn:introAlgorithm}
A(O) = G_TG_{T-1}\cdots G_2 G_1
\end{equation}

be a quantum algorithm, where $G_i$ are individual elementary operations (gates), which also include queries to the input oracle.
We call the mapping $i\mapsto G_i$ the description of $A$.
The number of elementary operations $T = T(A)$ is the time complexity of the algorithm.

Trivial Transducer
On the one extreme of the trade-off eqn:tradeoff is the trivial transducer $S=A$.
In this case, the catalyst $v=0$, hence, $W(S,O,\xi) = 0$, and we get that eqn:tradeoff equals $T(A)$, as expected.
Of course, this does not require any change of the model.

QRAG Transducer
The other extreme of the trade-off eqn:tradeoff is covered by the following construction, which assumes the QRAG model.
Write the sequence of states the algorithm eqn:introAlgorithm goes through on the initial state $\xi$:

\begin{equation}
\label{eqn:introSequenceOfStates}
\xi = \psi_0 \maps{G_1} \psi_1 \maps{G_2} \psi_2 \maps{G_3}\cdots \maps {G_T} \psi_{T} = \tau.
\end{equation}

We utilize the following history state:

\begin{equation}
\label{eqn:introHistoryState}
v = \sum_{t=1}^{T-1} \ket |t> \ket |\psi_t>.
\end{equation}

And define the transducer $S_A$ as follows:

\begin{equation}
\label{eqn:introProgram->Transducer}
\xi \oplus v = \sum_{t=0}^{T-1} \ket |t> \ket |\psi_t> \maps{S_A} \sum_{t=1}^{T} \ket |t> \ket |\psi_t> = \tau \oplus v,
\end{equation}

where, in $S_A$, we first apply $G_t$ conditioned on the first register having value $t$, and then increment $t$ by one.
The first operation is possible assuming the QRAG model and QRAM access to the description of $A$, see sec:QRAG.
The transduction action of $S_A(O)$ is exactly $A(O)$, and $W(S_A,O,\xi) = (T-1)\|\xi\|^2$, which we will simplify to $T\|\xi\|^2$ for brevity.

Comments on Time Complexity
But what is the time complexity $T(S_A)$?
In $S_A$, we perform two operations: increment a word-sided register and execute one instruction from the program specified by the address $t$.
If this were a modern randomised computer, both operations would be elementary and took $\OO(1)$ time.
From the theoretical side, this is captured by the notion of RAM machine.
If we consider the scale of individual qubits instead of word-sided registers, the increment operation takes time $\OO(\log T)$, and the second operation at least as much.
In order to simplify the following discussion, let us assume that both operations take some time we denote $\timeR$.  That is

\begin{equation}
\label{eqn:timeR}
\text{$\timeR$: time required to perform basic word operations, including random access.}
\end{equation}

For simplicity, we do not discriminate between different word operations.
We may think of $\timeR$ as being 1, or $\OO(\log T)$, but either way, it is some fixed factor which denotes transition from the circuit model, where $A$ operates,
[It is the usual assumption that $A$ is a bona fide quantum circuit, but we may also assume that $A$ uses QRAG gates.]
to the QRAG model, where $S_A$ is implemented.

Canonical Form
Neither the first, nor the second transducer above are in the canonical form.
The latter is given by the following result, which we prove in sec:programs->transducers.

For a quantum program $A$ on the input oracle $O$, there exists a canonical transducer $S_A = S_A(O)$, whose transduction action is identical to $A$, and whose complexity is given by fig:complexityTable.
In the QRAG model, we assume QRAM access to the description of the program $A$.

Complexity of canonical transducers derived from a quantum algorithm in terms of complexities of the algorithm.  Both the circuit and the QRAG model versions are considered.

\[
\begin{tabular}{rl|cc|}
&&Circuit Model&QRAG model\\\hline
Time& $T(S_A)$& $\OO(T(A))$ & $\OO(\timeR)$ \\
Transduction &$W(S_A,O,\xi)$ & $L(A,O,\xi)$ & $T(A)\|\xi\|^2$\\
Query state & $q(S_A,O,\xi)$ & $q(A, O,\xi)$ & $q(A, O,\xi)$\\
\hline
\end{tabular}
\]

The constructions in both circuit and the QRAG models are already sketched above.
We describe here how they can both be transformed into the canonical form so that the query state $\vq$ from fig:canonical becomes equal to the total query state $q(A, O, \xi)$ of the algorithm.

For the trivial transducer, the catalyst is the total query state, which is all processed by one query to the oracle.
Whenever the algorithm was making a query, the transducer switches the query state with the corresponding part of the catalyst, thus simulating a query.

For the QRAG transducer, the catalyst eqn:introHistoryState already contains of all the intermediate states of the program.
The transducer can then apply the oracle to all of them in one go, and then proceed as before without making a single additional query.

Query Compression
One consequence of the above results is that we can compress the number of queries of a quantum algorithm $A$ to match its worst-case Las Vegas query complexity.
The following result is an immediate corollary of Theorems <ref> and <ref>.

Assume $A=A(O)$ is a quantum algorithm with $r=\OO(1)$ input oracles as in eqn:introMultipleOracles.
Let $\eps, L^{(1)},\dots, L^{(r)}>0$ be parameters.
There exists a quantum algorithm $A'=A'(O)$ with the following properties:

* It makes $\OO(L^{(i)}/\eps^2)$ queries to the $i$-th input oracle $O^{(i)}$.

* For every normalised initial state $\xi$ and every input oracle $O=O^{(1)}\oplus O^{(2)}\oplus \cdots \oplus O^{(r)}$ as in eqn:introMultipleOracles, we have
$\norm|A(O)\xi - A'(O)\xi| \le \eps$ as long as $L^{(i)}(A, O,\xi)\le L^{(i)}$ for all $i$.

* In the QRAG model and assuming QRAM access to the description of $A$, its time complexity is $\OO(\timeR\cdot T(A)/\eps^2)$.

* In the circuit model, its time complexity is $\OO(L\cdot T(A)/\eps^2)$, where
$L = 1 + L^{(1)}+\cdots+ L^{(r)}$.

This improves over the analogous result from [16] in two respects.
First, it essentially preserves the time complexity of the algorithm in the QRAG model, while [16] did not consider time complexity at all.
Second, it allows multiple input oracles, as long as its number is bounded by a constant, while [16] only allowed for a single input oracle.

[Proof of thm:introQueryCompression]
First, obtain the transducer $S_A$ as in thm:introProg->Transducer.
Then, apply thm:introImplementationBetter to $S_A$.

One key observation is that $q(S_A, O,\xi) = q(A, O,\xi)$ for all $O$ and $\xi$.
Hence, $S_A$ and $A$ have the same partial Las Vegas query complexities on all $O$ and $\xi$.
This yields the statement on the number of queries bounded by $L^{(i)}/\eps^2$.

In the QRAG model, $W(S_A, O, \xi) = T(A)$ and $T(S_A) = \OO(\timeR)$.
This gives the required runtime, as we can use that $T(A)\ge 1$ to remove the additive 1 factor.

In the circuit model, we use that $T(S_A) = \OO\sA[T(A)]$ and

\[
W(S_A, O, \xi) = L(A, O, \xi) = \sum_i L^{(i)} (A, O, \xi) \le \sum_i L^{(i)}.
\]

We take care of the additive 1 factor by adding it explicitly to $L$.
This covers the extreme case of $L$ being too small, in particular, 0.

§.§ Composition of Transducers

Transducers can be composed just like usual quantum algorithms: we consider parallel, sequential, and functional composition of transducers.
Thus, from the design point of view, there is little difference between dealing with quantum algorithms and transducers.
The advantage is that in all these composition modes, the resources are more tightly accounted for than is the case for traditional quantum algorithms.

We will first sketch the composition results for transducers.
We will completely omit the case of sequential composition from this section.
It suffices to say, that it is very similar to the transformation of programs in sec:introAlgorithm->Transducer.
After that, we will give few applications both in the circuit and the QRAG models.
Unlike other subsections of this section, we will be able to give complete proofs for most of the results.

Composition of Transducers
The parallel composition of transducers is straightforward.  They are just implemented in parallel as usual quantum algorithms.
We have the following relations, akin to eqn:randomParallelComplexity and eqn:quantumParallel:

\begin{equation}
\label{eqn:introParallel}
W\sB[\bigoplus_i S_i, O, \bigoplus_i \xi_i] = \sum_i W(S_i, O, \xi_i)
\qqand
q\sB[\bigoplus_i S_i, O, \bigoplus_i \xi_i] = \bigoplus_i q(S_i, O, \xi_i).
\end{equation}

For the time complexity of implementing $\bigoplus_i \Sw_i$, we can say precisely as much as for usual quantum algorithms.
In some cases it is easy: when all $\Sw_i$ are equal, for example.
Also, it can be efficiently implemented assuming the QRAG model, see cor:selectProgram.
In general, however, direct sum in the circuit model can take as much time as the total complexity of all $\Sw_i$ together.

The functional composition of transducers parallels fig:composition, where we replace the programs $A$ and $B$ with transducers $S_A$ and $S_B$, respectively.
The functional composition of the two is a transducer $S_A\circ S_B$ whose transduction action on the oracle $O$ is equal to the transduction action of $S_A$ on the oracle $O\oplus O'$, where $O'$ is the transduction action of $S_B(O)$.
The following result, proven in sec:functional, parallels eqn:quantumComposition.

[Functional Composition of Transducers]

The functional composition $S_A\circ S_B$ can be implemented in the following complexity, where we use the extended notion of complexity from eqn:transductionExtended.

* Its transduction complexity satisfies

\begin{equation}
\label{eqn:introFunctionalTransduction}
W(S_A\circ S_B, O, \xi) = W(S_A, O\oplus O', \xi) + W\sB[ S_B, O, q^{(1)}(S_A, O\oplus O', \xi)].
\end{equation}

* Its total query state is

\begin{equation}
\label{eqn:introFunctionalQuery}
q(S_A\circ S_B, O, \xi) = q^{(0)}(S_A, O\oplus O', \xi) \oplus q\sB[ S_B, O, q^{(1)}(S_A, O\oplus O', \xi)].
\end{equation}

* Its time complexity is the sum of the (conditional) time complexities of $S_A$ and $S_B$.

Here $q^{(0)}$ and $q^{(1)}$ denote the partial query states of $S_A$ to the oracles $O$ and $O'$, respectively.

One can see that eqn:introFunctionalTransduction and eqn:introFunctionalQuery meet the form of the “gold standard” of eqn:randomComposition2.
The second one strongly resembles eqn:quantumComposition.
One unfortunate deviation from this is the time complexity, which afterwards gets multiplied by the transduction complexity in eqn:tradeoff.
But since the dependence is additive, we can generally tolerate it, see, e.g., thm:introIterated below.

Let us state, for the ease of future referencing, a number of simple consequences of prp:introFunctional similar to eqn:quantumCompositionMultiple–eqn:quantumCompositionMultiple2.
First, if all the queries to $S_B$ are admissible, we have by eqn:introFunctionalTransduction and eqn:admissibleQuery:

\begin{equation}
\label{eqn:compositionTransductionUpper}
W(S_A\circ S_B, O, \xi) \le W(S_A, O\oplus O', \xi) + \Wmax(S_B, O) L^{(1)}\sA[S_A, O\oplus O', \xi].
\end{equation}

Also, from eqn:introFunctionalQuery:

\begin{align}
\label{eqn:compositionLasVegas}
L(S_A\circ S_B, O, \xi)
&= L^{(0)}(S_A, O\oplus O', \xi) + L\sB[ S_B, O, q^{(1)}(S_A, O\oplus O', \xi)]\\
\label{eqn:compositionLasVegasUpper}
&\le L^{(0)}(S_A, O\oplus O', \xi) + \Lmax(S_B, O) L^{(1)}\sA[S_A, O\oplus O', \xi].
\end{align}

In the case of multiple input oracles, similar to fig:compositionMultiple, with $O' = \bigoplus_i O^{(i)}$ and $S_B = \bigoplus S_{B_ i}$, so that $S_{B_i}$ implements $O^{(i)}$, we have by eqn:introParallel:

\begin{align}
\label{eqn:compositionTransductionMultiple}
W(S_A\circ S_B, O, \xi)
&= W(S_A, O\oplus O', \xi) + \sum_i W\sB[ S_{B_i}, O, q^{(i)}(S_A, O\oplus O', \xi)]\\
\label{eqn:compositionTransductionMultipleUpper}
&\le W(S_A, O\oplus O', \xi) + \sum_i \Wmax( S_{B_i}, O) L^{(i)}\sA[S_A, O\oplus O', \xi],\\
\label{eqn:compositionQueryMultiple}
q(S_A\circ S_B, O, \xi)
&= q^{(0)}(S_A, O\oplus O', \xi) \oplus \bigoplus_i q\sB[ S_{B_i}, O, q^{(i)}(S_A, O\oplus O', \xi)]
\end{align}

\begin{align}
\label{eqn:compositionLasVegasMultiple}
L(S_A\circ S_B, O, \xi)
&= L^{(0)}(S_A, O\oplus O', \xi) + \sum_i L\sB[ S_{B_i}, O, q^{(i)}(S_A, O\oplus O', \xi)]\\
\label{eqn:compositionLasVegasMultipleUpper}
&\le L^{(0)}(S_A, O\oplus O', \xi) + \sum_i \Lmax( S_{B_i}, O) L^{(i)}\sA[S_A, O\oplus O', \xi].
\end{align}

In eqn:compositionTransductionMultipleUpper and eqn:compositionLasVegasMultipleUpper, we used eqn:admissibleQuery in assumption that all the queries to $S_B$ and $S_{B_i}$ are admissible.

Composition of Programs
Let us give a few examples of composition of quantum programs using transducers.
We focus on the general state conversion here, evaluation of function postponed till sec:introPurifier.
We consider both the circuit and the QRAG models.

Assume the settings of fig:compositionMultiple, where $r=\OO(1)$ and all $A$ and $B_i$ are in the circuit model.
Define $B = \bigoplus_i B_i$, and let $\eps, L^{(1)},\dots, L^{(r)}>0$ be parameters.

Then, there exists a quantum algorithm $A' = A'(O)$ such that $\normA|A'(O)\xi - A\sA[O\oplus B(O)]\xi|\le \eps$ for every normalised $\xi$ as long as $L^{(i)}(A, O\oplus B(O), \xi)\le L^{(i)}$ for all $i\ge 1$.
The program $A'$ can be implemented in the circuit model in time

\begin{equation}
\label{eqn:introCompositionCircuit}
\OO\s[\frac{L\cdot T(A) + \sum_i T\s[B_i] L^{(i)}}{\eps^2}],
\end{equation}

where $L = 1+L^{(1)}+\cdots+L^{(r)}$.

Use the circuit version of thm:introQueryCompression for the program $A$, where we treat calls to $O$ as ordinary operations (in other words, we assume $A$ has $r$ input oracles $O^{(1)},\dots, O^{(r)}$).
After that, replace each call to $O^{(i)}$ by the execution of $B_i$.

It turns out that it is not efficient to use prp:introFunctional here as this would increase time complexity of the resulting transducer.

In thm:introCompositionCircuit, the emphasis is on the time complexity.
If we want to simultaneously bound query complexity, we treat $O$ as the input oracle in $A$ as well.
This gives time complexity eqn:introCompositionCircuit with $L = 1+ L^{(0)}+L^{(1)}+\cdots+L^{(r)}$ and the total number of queries

\[
\OO\s[\frac{L^{(0)} + \sum_i Q\s[B_i] L^{(i)}}{\eps^2}],
\]

where $Q(B_i)$ is the number of queries made by $B_i$.
We additionally require that $L^{(0)}\sA[A, O\oplus B(O), \xi]\le L^{(0)}$.

Assume the settings of fig:compositionMultiple.
Let $\eps, T>0$ be parameters.
Assuming the QRAG model and QRAM access to an array with description of $A$ and all $B_i$, there exists a quantum algorithm $A' = A'(O)$ with time complexity $\OO(\timeR\cdot T/\eps^2)$ such that, for every normalised $\xi$, we have $\|A'(O)\xi - A\sA[O\oplus B(O)]\xi\| \le \eps$ as long as

\begin{equation}
\label{eqn:introCompositionQRAG}
T(A) + \sum_{i=1}^r T(B_i) L^{(i)}(A, O\oplus B(O), \xi) \le T.
\end{equation}

The algorithm makes $\OO(L/\eps^2)$ queries to the input oracle $O$, where $L$ is an upper bound on $L(A\circ B, O, \xi)$, given by eqn:quantumCompositionMultiple1.

Convert $A$ and all the $B_i$ into transducers $S_A$ and $S_{B_i}$ as in thm:introProg->Transducer.
We obtain the transducer $S_B = \bigoplus_i S_{B_i}$ for $B$.
Then compose $S_A\circ S_B$ using prp:introFunctional.
By definition, its transduction action is identical to $A(B)$.

Since the transduction complexity of $S_A$ on a normalised initial state is bounded by $T(A)$ and that of $S_{B_i}$ by $T(B_i)$, we get from eqn:compositionTransductionMultipleUpper that for a normalised $\xi$:

\[
W(S_A\circ S_B, O, \xi) \le T(A) + \sum_i T(B_i) L^{(i)}\sA[A, O\oplus B(O), \xi].
\]

The main reason this construction is efficient in the QRAG model is that the time complexity of the transducers stays bounded by $\OO(\timeR)$ the whole time.
Indeed, such is the time complexity of the individual transducers obtained from $A$ and $B^{(i)}$.
Parallel composition can be performed efficiently in the QRAG model (prp:program->transducerParallel), and the time complexity of the functional composition is the sum of its constituents.

The transducers $S_A$ and $S_{B_i}$ have the same query states as $A$ and $B_i$, respectively.
By eqn:compositionQueryMultiple, we get that the total query state of $S_A\circ S_B$ is identical to that of $A\circ B$, which is given by eqn:quantumCompositionMultiple.
The statement of the theorem follows from thm:introImplementationBetter.

Observe that thm:introCompositionQRAG, while assuming a stronger model, gives a stronger result than thm:introCompositionCircuit.
The differences are as follows.
First, we do not have to assume that $r=\OO(1)$.
Second, the $L^{(i)}(A, O\oplus B(O), \xi)$ in eqn:introCompositionQRAG are the actual values of the Las Vegas query complexity, while $L^{(i)}$ in eqn:introCompositionCircuit are only upper bounds on them.
This can be important if $L^{(i)}(A, O\oplus B(O), \xi)$ heavily fluctuates over different input oracles $O$.
Finally, the $T(A)$ term is oddly multiplied by $L$ in eqn:introCompositionCircuit.

Altogether, the expression in eqn:introCompositionQRAG is more natural.
It is also similar to the one in Section 1.2 of [24].
Our result is more general though, as it covers arbitrary state conversion, and not only function evaluation (we can assume $\eps=\Omega(1)$ in thm:introCompositionQRAG as it gives bounded-error evaluation of a function).

On the other hand, if the estimates $L^{(i)}$ are sufficiently precise, and $T(A)$ is smaller than average $T(B^{(i)})$, the expression in eqn:introCompositionCircuit is quite close to eqn:introCompositionQRAG.

Multiple Layers of Composition
Here we assume the QRAG model of computation.
Theorems <ref> and <ref> considered one layer of composition.
In the case of multiple layers, similarly as for the span programs, it is advantageous to perform all the compositions in the realm of transducers, and to transform the resulting transducer back into an actual algorithm only at the very end.

One node $B_{t; i_1, i_2, \dots, i_t}$ in the composition tree.
Its initial state (in the general sense of eqn:transductionExtended) is given by $\xi_{t; i_1, i_2, \dots, i_t}$.
It has several subroutines of the form $B_{t+1; i_1; i_2,\dots,i_t, i_{t+1}}$ with the corresponding query state $\xi_{t+1; i_1; i_2,\dots,i_t, i_{t+1}}$.

\[
\begin{tikzpicture}[every path/.append style={thick,->}]
\draw[\xicolor] (-2, -0.5) node[left]{$\xi_{t; i_1, i_2,\dots, i_t}$} to (-1,-0.5);
\draw (-1,0) rectangle (1,-1) node[pos=0.5] {$B_{t; i_1; i_2,\dots,i_t}$};
\draw (0,-2) rectangle (2.5,-3) node[pos=0.5] {$B_{t+1; i_1; i_2,\dots,i_t, 1}$};
\draw (3,-2) rectangle (5.5,-3) node[pos=0.5] {$B_{t+1; i_1; i_2,\dots,i_t, 2}$};
\node at (6.3, -2.5) {$\cdots$};
\node at (10.5, -2.5) {$\cdots$};
\draw (7,-2) rectangle (10,-3) node[pos=0.5] {$B_{t+1; i_1; i_2,\dots,i_t, i_{t+1}}$};
\draw[purple, out=0, in=90] (1,-0.8) to node[left, pos=0.7] {$\xi_{t+1; i_1, i_2,\dots, i_t,1}$} (1.5,-2);
\draw[purple, out=0, in=90] (1,-0.6) to node[left, pos=0.85] {$\xi_{t+1; i_1, i_2,\dots, i_t,2}$} (4.5,-2);
\draw[purple, thick, -] (1,-0.4) to (1.2,-0.4);
\draw[purple, thick, -] (1,-0.2) to (1.2,-0.2);
\draw[purple, out=0, in=90] (1,-0.3) to node[left, pos=0.95] {$\xi_{t+1; i_1, i_2,\dots, i_t,i_{t+1}}$} (9,-2);
\end{tikzpicture}
\]

Consider a composition tree of quantum subroutines.
The top layer is the algorithm $B_{0}$ that has several subroutines of the form $B_{1,i}$, like $B_i$ used to be for $A$ in fig:compositionMultiple.
We define the tree downwards so that, in general, a subroutine $B_{t; i_1,i_2,\dots,i_t}$ has several subroutines of the form $B_{t+1; i_1, i_2, \dots, i_t, i_{t+1}}$, see fig:multipleLayers.
Let $d$ be the maximal value of $t$ in $B_{t; i_1,i_2,\dots,i_t}$.
It is the depth of the composition tree.
We assume all the subroutines have access to some common oracle $O$.
Define the composition $B=B(O)$ of the whole tree in the obvious inductive way, so that the initial state $\xi$ of the composed algorithm is the initial state $\xi$ of $B_0$.

It is not hard to get the Las Vegas query complexity of $B$ using eqn:quantumCompositionMultiple inductively or from the general principles.
Let $q_{t; i_1,i_2,\dots,i_t}(O,\xi)$ be the query state given by $B_{t; i_1,i_2,\dots,i_t}$ to the input oracle $O$ when $B$ is executed on the initial state $\xi$.

\begin{equation}
\label{eqn:compositionTreeQueryComplexity}
q(B, O, \xi) = \bigoplus_{t; i_1,\dots, i_t} q_{t; i_1,i_2,\dots,i_t}(O,\xi).
\end{equation}

We obtain a similar result for the time complexity.
Let $\xi_{t; i_1,i_2,\dots,i_t}(O,\xi)$ be the total query state given to the subroutine $B_{t; i_1,i_2,\dots,i_t}$.
In particular, $\xi_0(O,\xi) = \xi$.

Assuming the QRAG model and QRAM access to the description of all $B_{t; i_1,\dots,i_t}$ as above, there exists a quantum algorithm $B' = B'(O)$ with time complexity $\OO(\timeR\cdot (d+1)\cdot T/\eps^2)$ such that, for every $\xi$, we have $\|B'(O)\xi - B(O)\xi\| \le \eps$ as long as

\begin{equation}
\label{eqn:introCompositionTree}
\sum_{t; i_1,\dots, i_t}  T(B_{t; i_1,i_2,\dots,i_t}) \|\xi_{t; i_1,i_2,\dots,i_t}(O,\xi)\|^2 \le T,
\end{equation}

where the summation is over all the vertices of the composition tree.
The algorithm makes $\OO(L/\eps^2)$ queries to $O$, where $L$ is an upper bound on the Las Vegas query complexity of $B$ as obtained from eqn:compositionTreeQueryComplexity.

We use the induction on $d$ to show that, under the assumptions of the theorem, there exists a transducer $S_B$ whose transduction action is identical to $B$, whose transduction complexity is given by the left-hand side of eqn:introCompositionTree, and whose time complexity is $\OO\sA[(d+1)\cdot\timeR]$.

The base case is given by $d=0$, where we only have $B_0$, which we transform into a transducer using thm:introProg->Transducer.
The transduction complexity of $S_{B_0}$ on a normalised initial state is $T(B_0)$.
Hence on the initial state $\xi_0$, the transduction complexity is $T(B_0)\|\xi_0\|^2$ by eqn:introLinearity.

Assume the theorem is true for depth $d$.
For the depth $d+1$, we treat the nodes $B_{t; i_1,i_2,\dots,i_t}$ with $t\le d$ as forming a composition tree $A$ with depth $d$, and the nodes $B_{d+1; i_1,i_2,\dots,i_d, i_{d+1}}$ as input oracles to $A$.
In other words, $A$ has an input oracle $O\oplus O'$ with

\[
O' = \bigoplus_{i_1,\dots,i_d, i_{d+1}} B_{d+1; i_1,\dots,i_d, i_{d+1}}(O).
\]

We use the induction assumption to obtain a transducer $S_A$ for the composition tree $A$, whose transduction complexity on $O \oplus O'$ and $\xi$ is given by the sum in eqn:introCompositionTree, where we restrict the sum to $t\le d$.
We convert each $B_{d+1; i_1,\dots,i_d, i_{d+1}}$ into a transducer and join them via direct sum to obtain a transducer $S_{B_{d+1}}$ whose transduction action on the oracle $O$ is identical to $O'$.
Then, we apply prp:introFunctional to get the transducer $S_B = S_A\circ S_{B_{d+1}}$.
Its transduction complexity on $O$ and $\xi$ is given by the left-hand side of eqn:introCompositionTree with all the terms involved, where the term

\[
T(B_{d+1; i_1,i_2,\dots,i_d, i_{d+1}}) \|\xi_{d+1; i_1,i_2,\dots,i_d, i_{d+1}}(O,\xi)\|^2
\]

is the contribution of $B_{d+1; i_1,i_2,\dots,i_d, i_{d+1}}$.

All the transducers in $S_{B_{d+1}}$ can be implemented in parallel due to the QRAG assumption (see prp:program->transducerParallel), hence, its time complexity is $\OO(\timeR)$.
Thus, $T(S_B) = T(S_A) + T(S_{B_{d+1}}) = \OO\sA[(d+1)\timeR]$.
Finally, using eqn:quantumCompositionMultiple and eqn:compositionQueryMultiple, we get that $S_B$ and $B$ have the same query state.
The statement of the theorem again follows from thm:introImplementationBetter.

Iterated Functions
Due to the discussion after thm:introCompositionCircuit, one might think that several layers of composition are difficult for the circuit model.
However, this is not the case if the composition tree is sufficiently homogenous.
As an example, we consider evaluation of iterated functions in the circuit model.

Let $f\colon [q]^{n} \to [q]$ and $g\colon [q]^m\to [q]$ be total functions.
The composed function $f\circ g\colon [q]^{nm} \to [q]$ is defined by

\begin{equation}
\label{eqn:introComposedFunction}
\begin{aligned}
\sS[f\circ g]&(z_{1,1}, \dots,z_{1,m},\;\; z_{2,1},\dots,z_{2,m},\;\;\dots\dots,\;\;z_{n,1},\dots,z_{n,m})\\
&= f\sA[
g(z_{1,1}, \dots,z_{1,m}),
g(z_{2,1}, \dots,z_{2,m}),
\dots,
g(z_{n,1}, \dots,z_{n,m})],
\end{aligned}
\end{equation}

which is equivalent to eqn:randomComposedFunction with all the inner functions being equal.
The function composed with itself several times is called iterated function.
We use the following notation
$f^{(1)} = f$ and $f^{(d+1)} = f^{(d)}\circ f = f\circ f^{(d)}$.

Iterated functions have been studied before both classically [38, 35, 36, 30, 29] and quantumly [22, 5, 33, 34].
For the case of Boolean functions, an essentially optimal algorithm
was given by Reichardt and Špalek in [33, 34] using span programs.
Papers [33, 34] are mostly known for their query results, but they also contain statements on the time complexity of the resulting algorithms.
It is these time complexity statements that we extend in thm:introIterated.
It is based on the use of span programs.
Similar results for the general case of non-Boolean functions can be easily obtained using composition of transducers.
While it is true that the time complexity grows with each layer of iteration, it only does so additively, which is overshadowed by optimal multiplicative handling of the query complexity.
We formally prove the following result in sec:iterated.

Let $f\colon [q]^n\to[q]$ be a total function.
There exists a bounded-error quantum algorithm that evaluates the iterated function $f^{(d)}$ in query complexity $\OO(\Adv(f)^d)$ and time complexity[We use $\OO_f(\cdot)$ to indicate that the suppressed constant may depend on the particular function $f$.] $\OO_f\sA[d\cdot\Adv(f)^d]$, where $\Adv(f)$ is the adversary bound of $f$.
The algorithm works in the circuit model.

We use induction to construct the transducer $S_{f^{(d)}}$ evaluating the function $f^{(d)}$ and having worst-case query complexity $\Adv(f)^d$, and transduction complexity $\OO\sA[\Adv(f)^d]$.

The base case is the transducer $S_f$ from thm:introAdv.
For the inductive step, we use prp:introFunctional with $S_A = S_{f^{(d)}}$ and $S_B = S_f$ to get $S_{f^{(d+1)}} = S_A\circ S_B$.
In notations of that theorem, $O$ encodes the input to $f^{(d+1)}$ and $O'$ the input to $f^{(d)}$ obtained by evaluating the lowest level of the composition tree.
First, $S_A$ does not make direct queries to $O$.
Second, $S_B = S_f$ has worst-case Las Vegas query complexity $\Adv(f)$ on a unit admissible vector.
Hence, by eqn:compositionLasVegasUpper and the induction assumption:

\[
L\sA[S_A\circ S_B, O, \ket |0>]
\le \Adv(f) L\sA[S_A, O', \ket|0>] \le \Adv(f)^{d+1}.
\]

Similarly, the worst-case transduction complexity of $S_B$ on a unit admissible vector is $\Adv(f)$, hence by eqn:compositionTransductionUpper:

\begin{align*}
W\sA[S_A\circ S_B, O, \ket |0>]
&\le W\sA[S_A, O, \ket |0>] + \Adv(f) L(S_A, O', \ket |0>)\\
&\le \OO\sA[\Adv(f)^d] + \Adv(f)^{d+1} = \OO\sA[\Adv(f)^{d+1}]
\end{align*}

for a sufficiently large constant behind the big-Oh.

For the time complexity, we have by induction that $S_{f^{(d)}}$ has time complexity $d\cdot T(S_f)$.
The theorem follows from thm:introImplementationBetter.

Note that the transducer $S_{f^{(d)}}$ in the proof of thm:introIterated is different from the transducer $S'_{f^{(d)}}$ we would get by applying thm:introAdv to the adversary bound of $f^{(d)}$ obtained using the composition results for the adversary bound.
Indeed, for $S'_{f^{(d)}}$, its transduction and query complexities are equal, which is not the case for $S_{f^{(d)}}$.
Also, for $S'_{f^{(d)}}$, we have no guarantees on its running time.
In thm:introIterated, we use the non-query part $\vw$ of the catalyst as a “scaffolding” to build a time-efficient iterative algorithm.

§.§ Purifiers and Composition of Functions

Although we have studied thriftiness from sec:introPrior, we have so far not touched much on exactness.
True, in most cases, like in sec:introWalks on quantum walks, or thm:introAdv on the adversary bound, the transduction action of the corresponding transducer is exact.
In this section, we will show how to get very close to general exactness starting from an arbitrary algorithm evaluating a function with bounded error.

We consider both Boolean and non-Boolean functions.
In the Boolean case, we abstract the action of the function-evaluating algorithm as an input oracle performing the following state generation:

\begin{equation}
\label{eqn:introPurifierInput}
O_\psi\colon \ket M |0> \mapsto \ket M|\psi> = \ket B|0>\ket N|\psi_0> + \ket B|1> \ket N|\psi_1>
\end{equation}

in some space $\cM = \cB\otimes \cN$ with $\cB = \bC^2$.
The action of the purifier only depends on the state $\psi$ in eqn:introPurifierInput, hence the notation $O_\psi$.
We allow the gap to be at any position $c$ between 0 and 1.
In other words, we assume there exist constants $0\le c-d < c + d \le 1$ such that

\begin{equation}
\label{eqn:introPurifierCases}
\text{either \qquad
$\|\psi_1\|^2 \le c-d$
\qquad  or \qquad
$\|\psi_1\|^2 \ge c+d$.
\end{equation}

The first case is negative, the second one positive, or, $f(\psi)=0$ and $f(\psi)=1$, respectively.

In the non-Boolean case, the range is some $[p]$.
For simplicity, we assume $p=\OO(1)$ here. An input oracle has the form

\begin{equation}
\label{eqn:introrPurifierInput2}
O_\psi\colon \ket M |0> \mapsto \ket M|\psi>
\sum_{j=0}^{p-1} \ket B|j>\ket N|\psi_j>,
\end{equation}

with $\cB = \bC^p$, and we assume there exists a (unique) $f(\psi)\in[p]$ such that

\begin{equation}
\label{eqn:introPurifierCases2}
\|\psi_{f(\psi)}\|^2 \ge \frac12+d
\end{equation}

for some constant $d>0$.

The traditional way of performing error reduction is via majority voting.
The following result is folklore.

For any $\eps>0$, there exists an algorithm with bidirectional access to an oracle like in eqn:introrPurifierInput2 that has the following properties.
Assuming the oracle satisfies eqn:introPurifierCases or eqn:introPurifierCases2, the algorithm evaluates $f(\psi)$ with error at most $\eps$.
The query complexity of the algorithm is $\OO\sA[\log \frac1\eps]$ and its time complexity in the circuit model is polynomial in $\log\frac1\eps$.

The majority-voting construction is a direct quantisation of a purely classical technique.
The logarithmic query complexity in the above theorem results in extra logarithmic factors that can be found in the analyses of a large variety of quantum algorithms.
In this paper, we develop an alternative, genuinely quantum approach to error reduction, that we call a purifier.
The main feature is that, unlike majority voting, the query complexity of a purifier stays bounded by a constant no matter how small the error $\eps$ is.
This is effectively equivalent to having an errorless algorithm (although, we cannot obtain an exact algorithm with a finite overhead in general).
We prove the following theorem in sec:purifiers.

For any $\eps>0$, there exists a canonical transducer $\purifier$ with bidirectional access to an oracle like in eqn:introrPurifierInput2 that has the following properties.
Assuming the oracle satisfies eqn:introPurifierCases or eqn:introPurifierCases2, the purifier transduces $\ket |0>$ into $\ket|f(\psi)>$ with error at most $\eps$ (in the sense to be made exact in sec:perturbedTransducers).
Both its transduction and query complexities are bounded by a constant.
Its time complexity is $\OO\sA[s\log \frac1\eps]$ in the circuit model, and $\OO(\timeR)$ in the QRAG model, where $s$ is the number of qubits used by $\cM$.

The purifier is inspired by the corresponding construction in [14], which used the dual adversary bound.
It had the same characteristic property of query complexity being bounded by a constant, but there are some differences.

* The purifiers in [14] worked solely in the query complexity settings.
The resulting dual adversary bound was for exact function evaluation.
Also, by the nature of the adversary bound, it was implicitly assumed that there is only a finite collection of possible input oracles, and, technically, for different collections, we obtain different purifiers.

* The purifiers in the current paper are constructed keeping both query and time complexity in mind.
Also, the same purifier works for all (infinitely many) possible input oracles.

* Due to these improvements, the purifier ceases to be exact, but introduces a small error.

[Proof sketch of thm:introPurifier]
We consider the Boolean case, as the general case can be easily obtained using the Bernstein-Vazirani algorithm [17] as in, e.g., <cit.>.
Our construction is a quantum walk in the sense of sec:introWalks.
In particular, it transduces $\ket |0>$ into $(-1)^{f(\psi)}\ket |0>$.

The overall structure is given by the following toy transducer $\Stoy$ in fig:introPurifier1.
It is a quantum walk on the one-sided infinite line.
That is, $\Stoy = R_2R_1$, where the reflection $R_1$ is the product of the local reflections about the odd vertices $1,3,5,\cdots$, and $R_2$ about the positive even vertices $2,4,6,\cdots$.
The local reflection at the vertex $i>0$ is given by the $X$ operation, which maps

\begin{equation}
\label{eqn:toyOperations}
\ket |i-1> + \ket |i> \mapsto \ket |i-1> + \ket |i>
\qqand
\ket |i-1> - \ket |i> \mapsto -\ket |i-1> + \ket |i>.
\end{equation}

A toy transducer illustrating the overall construction of a purifier.
It is a quantum walk on the one-sided infinite line.
Each edge correspond to an element of the standard basis written below it.
The public space is given by $\ket |0>$.
We have two different catalysts (a) and (b) for the same initial state, the numbers above the edge giving the corresponding coefficients.

\[
\begin{tikzpicture}[auto]
\node at (-2,0) {(a)};
\node (0) at (0,0) [circle, draw] {$0$};
\foreach \x [remember=\x as \prevx (initially 0)] in {1,...,5}
\node (\x) at (\x*2,0) [circle, draw] {$\x$};
\draw (\prevx) to node [above, blue] {$1$}
node [below, gray] {$\ket|\prevx>$} (\x);
\draw (5) to (11,0) node[right] {$\cdots$};
\begin{scope}[shift={(0,-2)}]
\node at (-2,0) {(b)};
\node (0) at (0,0) [circle, draw] {$0$};
\foreach \x [remember=\x as \prevx (initially 0)] in {1,...,5}
\node (\x) at (\x*2,0) [circle, draw] {$\x$};
\pgfmathparse{mod(\x,2) ? 1 : int(-1)}
\draw (\prevx) to node [above, blue] {$\pgfmathresult$}
node [below, gray] {$\ket|\prevx>$} (\x);
\draw (5) to (11,0) node[right] {$\cdots$};
\end{scope}
\end{tikzpicture}
\]

Now, it is not hard to see that in the negative and the positive case, we have the following mappings, which follow the general case of eqn:QW_sequence_negative and eqn:QW_sequence_positive:

\begin{equation}
\label{eqn:toyTransduce}
\ket |0> + \sum_{i=1}^{+\infty} \ket |i> \maps{\Stoy} \ket |0> + \sum_{i=1}^{+\infty} \ket |i>
\qqand
\ket |0> + \sum_{i=1}^{+\infty} (-1)^i\ket |i> \maps{\Stoy} - \ket |0> + \sum_{i=1}^{+\infty} (-1)^i\ket |i>.
\end{equation}

This formally gives us both $\ket |0> \transduce{\Stoy} \ket |0>$ and $\ket |0> \transduce{\Stoy} -\ket |0>$.
Of course, this does not contradict thm:introTransduce, because the corresponding space has infinite dimension and both catalysts in eqn:toyTransduce have infinite norm.

Nonetheless, we will be able to utilise this general construction.
The first order of business is to reduce the norm of the catalysts.
Our next step towards a purifier will be a multidimensional quantum walk on the line, in the sense that each edge corresponds to a multidimensional subspace.
See fig:introPurifier2.

An improved transducer.
It is a multidimensional quantum walk.
Each edge corresponds to the element of the standard basis beneath it tensor multiplied by $\cM^{\otimes \infty}$.
The public space is given by $\ket |0>$.
For the negative and positive case, we have the catalysts like in (a) and (b), respectively, where the vector above the edge is placed in the corresponding subspace.

\[
\begin{tikzpicture}[auto]
\node at (-2,0) {(a)};
\node (0) at (0,0) [circle, draw] {$0$};
\foreach \x [remember=\x as \prevx (initially 0)] in {1,...,5}
\node (\x) at (\x*2,0) [circle, draw] {$\x$};
\draw (\prevx) to node [below, gray] {$\ket|\prevx>$} (\x);
\draw (0) to node[above, blue] {$1$} (1);
\draw (1) to node[above, blue] {$\wpsi$} (2);
\draw (2) to node[above, blue] {$\wpsi^{\otimes 2}$} (3);
\draw (3) to node[above, blue] {$\wpsi^{\otimes 3}$} (4);
\draw (4) to node[above, blue] {$\wpsi^{\otimes 4}$} (5);
\draw (5) to (11,0) node[right] {$\cdots$};
\begin{scope}[shift={(0,-2)}]
\node at (-2,0) {(b)};
\node (0) at (0,0) [circle, draw] {$0$};
\foreach \x [remember=\x as \prevx (initially 0)] in {1,...,5}
\node (\x) at (\x*2,0) [circle, draw] {$\x$};
\pgfmathparse{mod(\x,2) ? 1 : int(-1)}
\draw (\prevx) to node [below, gray] {$\ket|\prevx>$} (\x);
\draw (0) to node[above, blue] {$1$} (1);
\draw (1) to node[above, blue] {$-\wpsi$} (2);
\draw (2) to node[above, blue] {$\wpsi^{\otimes 2}$} (3);
\draw (3) to node[above, blue] {$-\wpsi^{\otimes 3}$} (4);
\draw (4) to node[above, blue] {$\wpsi^{\otimes 4}$} (5);
\draw (5) to (11,0) node[right] {$\cdots$};
\end{scope}
\end{tikzpicture}
\]

We will define a vector $\wpsi$ that depends on $\psi$ and satisfies $\|\wpsi\| = 1-\Omega(1)$.
The initial coupling is given by

\[
\sum_{i=0}^\infty (-1)^{i\cdot f(\psi)} \ket |i> \ketO |\wpsi>^{\otimes i},
\]

and the transduction complexity is bounded by

\[
\sum_{i=1}^\infty \|\wpsi\|^{2i} = \OO(1).
\]

Let us now explain how to implement the local reflections eqn:toyOperations for this modified transducer.
Up to a sign, the content of the space incident to a vertex $i>0$ is given by

\begin{equation}
\label{eqn:introPurifier1}
\ket |i-1> \ketO |\wpsi>^{\otimes i-1} + (-1)^{f(\psi)} \ket |i> \ketO |\wpsi>^{\otimes i}.
\end{equation}

We use the input oracle to obtain the state

\begin{equation}
\label{eqn:introPurifier2}
\ket |i-1> \ketO |\wpsi>^{\otimes i-1}\ket |\psi> + (-1)^{f(\psi)} \ket |i> \ketO |\wpsi>^{\otimes i}.
\end{equation}

Later we can get back from eqn:introPurifier2 to eqn:introPurifier1 by uncomputing the $\psi$.
Therefore, bringing the term $\ket |i> \ketO |\wpsi>^{\otimes i-1}$ outside the brackets, it suffices to implement the mapping

\begin{equation}
\label{eqn:notToyOperations}
\begin{cases}
\ket |0> \ket |\psi> + \ket |1>\ketO|\wpsi> \mapsto \ket |0> \ket |\psi> + \ket |1>\ketO|\wpsi>,&\text{if $f(\psi)=0$;\; and}\\
\ket |0> \ket |\psi> - \ket |1>\ketO|\wpsi> \mapsto -\ket |0> \ket |\psi> + \ket |1>\ketO|\wpsi>,&\text{if $f(\psi)=1$.}
\end{cases}
\end{equation}

This is where the condition eqn:introPurifierCases comes into play.
We use the same rescaling idea as in [14], and define the state

\[
\wpsi =
\begin{cases}
\frac 1a \ket |0> \ket |\psi_0> + b \ket|1>\ket|\psi_1>,& \text{if $f(\psi)=0$};\\
a \ket |0> \ket |\psi_0> + \frac 1b \ket|1>\ket|\psi_1>,& \text{if $f(\psi)=1$}.\\
\end{cases}
\]

\[
a = \sqrt[4]{\frac{1-c+d}{1-c-d}}
\qqand
b = \sqrt[4]{\frac{c+d}{c-d}}.
\]

It is not hard to check that $\|\wpsi\|^2 = 1-\Omega(1)$.
Now the operation in eqn:notToyOperations reads as

\[
\begin{cases}
\sA[\ket |0> + \frac1a \ket |1>] \ket |0> \ket |\psi_0> +
\sA[\ket |0> + b \ket |1>]\ket |1> \ket |\psi_1>
\mapsto
\sA[\ket |0> + \frac1a \ket |1>] \ket |0> \ket |\psi_0> +
\sA[\ket |0> + b \ket |1>]\ket |1> \ket |\psi_1>,
\\
\sA[\ket |0> - a \ket |1>] \ket |0> \ket |\psi_0> +
\sA[\ket |0> - \frac1b \ket |1>]\ket |1> \ket |\psi_1>
\mapsto
\sA[-\ket |0> + a \ket |1>] \ket |0> \ket |\psi_0> +
\sA[-\ket |0> + \frac1b \ket |1>]\ket |1> \ket |\psi_1>,
\end{cases}
\]

which can be implemented as the 2-qubit reflection about the span of the states

\[
\sA[a\ket |0> + \ket |1> ]\ket |0>
\qqand
\sA[\ket |0> + b \ket |1> ]\ket |1>.
\]

Following the same logic as in the toy example, we obtain that $\ket |0> \transduce{} (-1)^{f(\psi)} \ket |0>$.
However, this time, both the transduction and the query complexities are bounded by a constant.
The problem is that this construction still requires infinite space.
We solve this by truncating the line after some vertex $D$.
This introduces an error, but since the norms of the vectors decrease exponentially with $i$, it suffices to take $D = \OO\sA[\log \frac 1\eps]$.
Finally, the transducer can be converted into a canonical form by the standard technique of prp:canoning.

The main purpose of purifiers is to reduce error.
Let us give few examples.
First, recall the definition of the composed function $f\circ g$  from eqn:introComposedFunction:

\[
\begin{aligned}
\sS[f\circ g]&(z_{1,1}, \dots,z_{1,m},\;\; z_{2,1},\dots,z_{2,m},\;\;\dots\dots,\;\;z_{n,1},\dots,z_{n,m})\\
&= f\sA[
g(z_{1,1}, \dots,z_{1,m}),
g(z_{2,1}, \dots,z_{2,m}),
\dots,
g(z_{n,1}, \dots,z_{n,m})].
\end{aligned}
\]

We use notation

\begin{equation*}
\yy_i = (z_{i,1}, \dots,z_{i,m})
\qqand
x = \sA[g(\yy_1), g(\yy_2),\dots g(\yy_n)]
\end{equation*}

so that $f(x) = \sS[f\circ g](z)$.
In the circuit model, we have the following result on the evaluation of this function.

Let $A$ and $B$ be quantum algorithms in the circuit model that evaluate the functions $f$ and $g$, respectively, with bounded error.
Then, there exists a quantum algorithm in the circuit model that evaluates the function $f\circ g$ with bounded error in time complexity

\begin{equation}
\label{eqn:introCompositionFunctionCircuit}
\OO(L)\sA[T(A) + T(B) + s\log L]
\end{equation}

where $L$ is the worst-case Las Vegas query complexity of $A$, and $s$ is the space complexity of $B$.

We obtain the transducer $S_A$ in the circuit model using thm:introProg->Transducer.
The transduction and query complexities of $S_A$ are bounded by $L$.
Let $\purifier$ be the purifier for the input oracle $B$.
Consider the transducer $S = S_A\circ\bigoplus_i \purifier$, see fig:introCompositionFunctionCircuit.
The transducer $\purifier$ on the input oracle $B(O_{\yy_i})$ evaluates $g(y_i)$ with diminished error.
It suffices to make error somewhat smaller than $1/L$.
Then, $S$ on the input oracle $\bigoplus_i B(O_{\yy_i})$ evaluates $f\circ g$ with bounded error.

A composition scheme for thm:introCompositionFunctionCircuit.
The input oracle $O_z$ is broken down as $\bigoplus_i O_{\yy_i}$.
The composed transducer contains the elements inside the blue box.
The program $B$ is executed as is, serving as an input oracle to the composed transducer.

(0,0) rectangle (2,-1) node[pos=0.5] $\purifier$;
(0,-1.5) rectangle (2,-2.5) node[pos=0.5] $B$;
(0,-3) rectangle (2,-4) node[pos=0.5] $O_{\yy_#3}$;
[purple] (1,-1) to (1,-1.5);
[purple] (1,-2.5) to (1,-3);

\[
\begin{tikzpicture}[every path/.append style={thick,->}]
\draw (7,0) rectangle (9,-1) node[pos=0.5] {$S_A$};
\funkcijaB(3,-2)1
\funkcijaB(6,-2)2
\node at (9,-2.5) {\Large$\cdots$};
\funkcijaB(10,-2)n
\draw[purple, out=270, in=90] (7.2, -1) to (4,-2) ;
\draw[purple, out=270, in=90] (7.5, -1) to (7,-2) ;
\draw[purple, out=270, in=90] (8.8, -1) to (11,-2) ;
\draw[rounded corners=10pt, blue] (2,0.5) rectangle (13,-3.25);
\end{tikzpicture}
\]

The transduction complexity of $\purifier$ on a unit admissible vector is $\OO(1)$.
Hence, by eqn:compositionTransductionUpper

\[
W(S, O_z, \ket|0>) \le W(S_A, O_x, \ket|0>) + \OO(1)\cdot L(S_A, O_x, \ket |0>) = \OO(L).
\]

All the purifiers can be implemented in parallel, hence by prp:introFunctional,

\[
T(S) = T(S_A) + T(\purifier) = \OO\sA[T(A)] + \OO(s\log L).
\]

The theorem follows from thm:introImplementation applied to $S$, where we replace execution of the input oracle by the execution of $B$.
Again, all the $B$ can be executed in parallel.

In the QRAG model, we can easily deal with different functions $g_i$, like in the following function, which we already considered in eqn:randomComposedFunction:

\begin{equation}
\label{eqn:randomComposedFunctionCopy}
g_1(z_{1,1}, \dots,z_{1,m}),
g_2(z_{2,1}, \dots,z_{2,m}),
\dots,
g_n(z_{n,1}, \dots,z_{n,m})].
\end{equation}

We again use notation

\[
\yy_i = (z_{i,1}, \dots,z_{i,m})
\qqand
x = \sA[g_1(\yy_1), g_2(\yy_2),\dots g_n(\yy_n)].
\]

Consider the function as in eqn:randomComposedFunctionCopy.
Let $A$ and $B_1,\dots, B_n$ be quantum algorithms that evaluate the functions $f$ and $g_1,\dots, g_n$, respectively, with bounded error.
Assuming the QRAG model and QRAM access to the description of $A$ and $B_1,\dots, B_n$, there exists a quantum algorithm that evaluates the function eqn:randomComposedFunctionCopy with bounded error in time complexity

\begin{equation}
\label{eqn:introCompositionFunctionQRAG}
\OO(\timeR)\max_x\sB[T(A) + \sum_{i=1}^n T(B_i) L^{(i)}_x(A)].
\end{equation}

Here $L^{(i)}_x(A)$ is the $i$-th partial Las Vegas complexity $L^{(i)}\sA[A, O_x, \ket|0>]$ of the algorithm $A$ on the input oracle encoding $x$.

We obtain the transducer $S_A$ in the QRAG model using thm:introProg->Transducer.
Its transduction complexity is $T(A)$.
We assume all $B_i$ have the same range and the same error.
Let $\purifier$ be the corresponding purifier.
Finally, let $S_{B_i}$ be the transducer in the QRAG model corresponding to $B_i$.
Consider the composed transducer $S$ as in fig:introCompositionFunctionQRAG.
Similarly to thm:introCompositionFunctionCircuit,
the transducer $S$ on the input oracle $O_z = \bigoplus_i O_{\yy_i}$ evaluates the function $f\circ g$ with bounded error provided that the error of the purifier is sufficiently smaller than $1/L$.

A composition scheme for thm:introCompositionFunctionQRAG.
The input oracle $O_z$ is again broken down as $\bigoplus_i O_{\yy_i}$.
The composed transducer $S$ contains the elements inside the blue box.
This time every $B_i$ is turned into a transducer and partakes in the composition.

(0,0) rectangle (2,-1) node[pos=0.5] $\purifier$;
(0,-1.5) rectangle (2,-2.5) node[pos=0.5] $S_{B_#3}$;
(0,-3) rectangle (2,-4) node[pos=0.5] $O_{\yy_#3}$;
[purple] (1,-1) to (1,-1.5);
[purple] (1,-2.5) to (1,-3);

\[
\begin{tikzpicture}[every path/.append style={thick,->}]
\draw (7,0) rectangle (9,-1) node[pos=0.5] {$S_A$};
\funkcijaB(3,-2)1
\funkcijaB(6,-2)2
\node at (9,-2.5) {\Large$\cdots$};
\funkcijaB(10,-2)n
\draw[purple, out=270, in=90] (7.2, -1) to (4,-2) ;
\draw[purple, out=270, in=90] (7.5, -1) to (7,-2) ;
\draw[purple, out=270, in=90] (8.8, -1) to (11,-2) ;
\draw[rounded corners=10pt, blue] (2,0.5) rectangle (13,-4.75);
\end{tikzpicture}
\]

Using that the transduction and the query complexity of $\purifier$ are $\OO(1)$, we obtain that
\Wmax(\purifier \circ S_{B_i}, O_{\yy_i}) = \OO\sA[T(B_i)].
Therefore, by eqn:compositionTransductionMultipleUpper and using that $A$ and $S_A$ have the same query state:

\[
W\sA[S, O_z, \ket|0>] \le W(S_A, O_x, \ket |0>) + \sum_i \OO\sA[T(B_i)] L^{(i)}\sA[A, O_x, \ket|0>].
\]

For the time complexity, $S$ is a composition of three transducers, where the last two are direct sums.  All three of them have time complexity $\OO(\timeR)$, hence, this is also the time complexity of $S$.
The theorem follows from thm:introImplementation.

Comparison between Theorems <ref> and <ref> is similar to the comparison between Theorems <ref> and <ref> in sec:introComposition.
The second theorem considers a more general case eqn:randomComposedFunctionCopy, and its formulation is close to eqn:randomComposition2.
On the other hand, in eqn:introCompositionFunctionCircuit, $T(B)$ will most likely dominate $s\log L$, so the latter can be removed.
Also, if $T(A)$ is smaller than $T(B)$, the whole expression is dominated by $L\cdot T(B)$, which is what we would like to have.

Finally, in the QRAG model, any bounded-error quantum algorithm $A$ can be turned into an essentially exact transducer $S_A$ such that, up to constant factors, its transduction complexity is $T(A)$ and its query complexity is the query complexity of $A$.
The latter transducers can be composed in multiple layers as in thm:introCompositionTree.

§ PRELIMINARIES

If not said otherwise, a vector space is a finite-dimensional complex inner product space.  They are denoted by calligraphic letters.  We assume that each vector space has a fixed orthonormal basis, and we often identify an operator with the corresponding matrix.
$I_{\cX}$ stands for the identity operator in $\cX$.
The inner product is denoted by $\ip<\cdot,\cdot>$.
$A^*$ stands for the adjoint linear operator.
All projectors are orthogonal projectors.
We use ket-notation to emphasise that a vector is a state of a quantum register, or to denote the elements of the computational basis.

We use $\OO$ for the big-Oh notation in order to distinguish from $O$, which we use for input oracles.
$\OO_A$ means that the constant may depend on $A$.
If $P$ is a predicate, we use $1_P$ to denote the corresponding indicator variable; which is equal to 1 if $P$ is true, and to 0 otherwise.

§.§ Query Algorithms

In this section, we briefly describe the model of quantum query algorithms, and define quantum Las Vegas query complexity.
The query model itself is essentially standard [19, 20], with the main difference that we do not restrict ourselves to the evaluation of functions, and also allow for multiple input oracles, which can be arbitrary unitaries.
The notion of quantum Las Vegas query complexity is relatively new [16].

A quantum query algorithm $A$ works in space $\cH$, which we call the workspace of the algorithm.
The algorithm is given an oracle $O$, which is a unitary
While [16] define more general input oracles, we, for simplicity, consider only unitary input oracles in this paper.
in some space $\cM$.
The interaction between the algorithm and the oracle is in the form of queries, which we are about to define.
The workspace is decomposed as $\cH = \cHw\oplus \cHq$, where the oracle is only applied to the second half.
Also, $\cHq = \cHt \otimes \cM$ for some $\cHt$, and the query is

\begin{equation}
\label{eqn:query}
\tO = \Iw \oplus I\otimes O,
\end{equation}

where $\Iw$ and $I$ are the identities in $\cHw$ and $\cHt$, respectively.

In terms of registers, we assume the decomposition $\cH = \cHw\oplus \cHq$ is marked by a register $\cR$ so that $\ket R|0>$ corresponds to $\cHw$ and $\ket R|1>$ to $\cHq$.
Then, the query $\tO$ is an application of $O$, controlled by $\cR$, where $O$ acts on some subset of the registers (which constitute $\cM$).

The quantum query algorithm $A=A(O)$ is a sequence of linear transformations in $\cH$:

\begin{equation}
\label{eqn:preAlgorithm}
A(O) = U_Q\, \tO\, U_{Q-1}\,\tO\,\cdots U_{1}\, \tO\, U_0,
\end{equation}

where $U_t$ are some input-independent unitaries in $\cH$.
See fig:queryAlgorithm.
Thus, the algorithm implements a transformation $O\mapsto A(O)$: from the input oracle $O$ in $\cM$ to the linear operator eqn:preAlgorithm in $\cH$.

A graphical illustration of a quantum query algorithm with $Q=3$ queries.
The algorithm interleaves input-independent unitaries $U_t$ with queries $\tO = \Iw \oplus I\otimes O$.
The intermediate state $\psi_t$ after $U_{t-1}$ and before the $t$-th query is decomposed as $\psi_t^\circ\oplus \psi_t^\bullet$, where only the second half is processed by the oracle.

\[
\begin{tikzpicture}[every node/.style={font=\scriptsize}, every path/.append style={thick,->}]
\draw[\xicolor] (-1.9,1.9) to node[above]{$\xi$} (-0.9,1.9);
\draw (-0.9,0.15) rectangle (0, 3.35) node[pos=0.5] {\Large $U_{0}$};
\OneIteration{1}
\OneIteration{2}
\OneIteration{3}
\draw[\taucolor] (12,1.9) to node[above]{$\tau$} (13,1.9);
\end{tikzpicture}
\]

We will generally work with the state conversion formalism.  We say that $A$ transforms $\xi$ into $\tau$ on oracle $O$, if $A(O)\xi = \tau$.
We say that $A$ does so $\eps$-approximately if $\normA|\tau - A(O)\xi|\le\eps$.
In this context, we will often call $\eps$ the error of the algorithm.

Let us make two important remarks on the structure of thus defined query algorithms.

Note that all the queries in eqn:preAlgorithm are identical, i.e., the oracle $O$ is always applied to the same registers and is always controlled by $\cR$.
To acknowledge this, we say that all the queries in $A$ are aligned.
Usually, this is not important, but the alignment property will play a significant role in this paper, in particular in Sections <ref> and <ref>.
The main reason is that for the aligned program we can perform all the queries in parallel (assuming we have the intermediate states $\psi_t$ from fig:queryAlgorithm somehow).

The input oracle is unidirectional: the algorithm only has access to $O$.
This suffices for most of our results.
Quite often, however, bidirectional access to the input oracle is allowed, where the algorithm can query both $O$ and $O^*$.
The latter is a special case of the former, as bidirectional access to $O$ is equivalent to unidirectional access to $O\oplus O^*$.
As this situation will be common in some sections of the paper, we utilise the following piece of notation:

\begin{equation}
\label{eqn:bi}
\bi{O} = O \oplus O^*.
\end{equation}

The standard complexity measure of a quantum query algorithm is $Q=Q(A)$: the total number of times the query $\tO$ is executed.
It was called Monte Carlo complexity in [16] in order to distinguish it from Las Vegas complexity defined next.

Let $\Pi^\bullet$ be the projector onto $\cHq$.
The state processed by the oracle on the $t$-th query is $ \psi_t^\bullet = \Pi^\bullet U_{t-1}\, \tO\, U_{t-2} \cdots \tO\, U_0 $, and the total query state is

\begin{equation}
\label{eqn:totalQueryState}
q(A, O, \xi) = \bigoplus_{t=1}^Q \psi_t^\bullet.
\end{equation}

This is the most complete way of specifying the work performed by the input oracle $O$ in the algorithm $A$ on the initial state $\xi$.
It is a member of $\cE\otimes \cM$ for some space $\cE$ (the latter actually being equal to $\bC^Q\otimes \cHt$).
The simplest way to gauge the total query state is by defining the corresponding quantum Las Vegas query complexity:

\begin{equation}
\label{eqn:LasVegasComplexity}
L(A, O, \xi) = \|q(A, O, \xi)\|^2.
\end{equation}

As mentioned in sec:conceptualQuantum, we extend the definitions eqn:totalQueryState and eqn:LasVegasComplexity for the case $\xi'\in \cE\otimes \cH$ for some $\cE$ using identities eqn:queryStateExtended and eqn:LasVegasExtended.

§.§ Multiple Input Oracles

It is also possible for an algorithm to have access to several input oracles $O^{(1)},\dots,O^{(r)}$.
Las Vegas query complexity can naturally accommodate such a scenario.
Indeed, access to several input oracles is equivalent to access to the one combined oracle

\begin{equation}
\label{eqn:severalOracles}
O = O^{(1)}\oplus O^{(2)}\oplus \cdots \oplus O^{(r)}.
\end{equation}

Consequently, the space of the oracle has a similar decomposition $\cM = \cM^{(1)}\oplus\cdots\oplus \cM^{(r)}$, where $O^{(i)}$ acts in $\cM^{(i)}$.
The total query state can also be decomposed into partial query states

\[
q(A,O,\xi) = q^{(1)}(A,O,\xi)\oplus q^{(2)}(A,O,\xi) \oplus \cdots \oplus q^{(r)}(A,O,\xi),
\]

where $q^{(i)}(A,O,\xi)$ is processed by $O^{(i)}$.
This gives partial Las Vegas query complexities

\[
L^{(i)}(A, O, \xi) = \normA|q^{(i)}(A,O,\xi)|^2.
\]

In terms of registers, it can be assumed that the input oracle is controlled by some register $\reg R$, where the value $\ket R|0>$ indicates no application of the input oracle, and $\ket R|i>$ with $i>0$ indicates the $i$-th input oracle $O^{(i)}$.
We note that we use $i$ in $\ket R|i>$ only as a label.
In particular, we do not perform any arithmetical operations on them.
Therefore, $\ket R|i>$ can have a complicated internal encoding that can facilitate the application of the oracle.

The assumption on the register $\cR$ in this section is not necessarily in contradiction with the assumptions of sec:prelimQuery, as $\reg R$ can have a separate qubit that indicates whether $i$ in $\ket R|i>$ is non-zero.
This qubit can serve as $\reg R$ in the sense of sec:prelimQuery.

The case of usual Monte Carlo query complexity requires additional changes, as per now it turns out that all the oracles are queried the same number of times, $Q$.
One way to allow for different number of queries is as follows.
Similarly to eqn:query, define the query to the $i$-th input oracle as

\[
\tO^{(i)} = \Ic \oplus I \otimes
\s[I^{(1)} \oplus \cdots\oplus I^{(i-1)} \oplus O^{(i)} \oplus I^{(i+1)}\oplus\cdots\oplus I^{(r)} ],
\]

where the decomposition in the brackets is the same as in eqn:severalOracles.
In other words, $\tO^{(i)}$ is just the application of $O^{(i)}$ controlled by $\ket R|i>$.
The query algorithm is then defined as

\begin{equation}
\label{eqn:algorithmMultipleOracles}
A(O) = U_Q\, \tO^{(s_Q)}\, U_{Q-1}\,\tO^{(s_{Q-1})}\,\cdots\, U_{2}\, \tO^{(s_2)}\, U_{1}\, \tO^{(s_1)}\, U_0,
\end{equation}

where $s_1,s_2,\dots,s_Q \in [r]$.
The number of invocations of the $i$-th oracle, $Q^{(i)}$, is defined as the number of $s_j$ equal to $i$ in eqn:algorithmMultipleOracles.

§.§ Evaluation of Functions

The standard settings for quantum algorithms evaluating a (partial) function $f\colon D\to [p]$ with $D\subseteq [q]^n$ are as follows.
For an input $x\in [q]^n$, the corresponding input oracle acts in $\bC^n \otimes \bC^q$ as

\begin{equation}
\label{eqn:standardOracle}
O_x \colon \ket|i>\ket |b> \mapsto \ket |i> \ket |b \oplus x_i>
\end{equation}

for all $i\in[n]$ and $b\in [q]$.
Here $\oplus$ stands for the bitwise XOR, and we assume that $q$ is a power of 2 (we can ignore the inputs outside of the domain).

The algorithm $A$ itself has a special output register isomorphic to $\bC^p$.
After finishing the algorithm, measuring the output register should yield the value $f(x)$.
This either happens with probability 1 (for exact algorithms), or with probability at least $1/2+d$ for some constant $d>0$ (bounded error).

This definition is nice because there is one well-defined input oracle $O_x$ for each input.
Also $O_x^2 = I$, which makes uncomputing very easy.
Unfortunately, the standard definition has a drawback that the input oracle of the algorithm has a more restricted form than the one required for the algorithm itself.
This is problematic if the algorithm is expected to be used as an input oracle for another algorithm.
This issue is solved by noting that $\ket |b> \mapsto \ket |b\oplus f(x)>$ can be implemented by evaluating $f(x)$, performing the XOR operation, and uncomputing $f(x)$.
This increases the complexity by a factor of 2, which is fine if we ignore constant factors.
We call it robust evaluation of function, as the action of the algorithm is specified for all input states, not just $\ket|0>$.

However, constant factors can be important, for instance, in iterated functions, where such factors appear as a base of the exponent, or in the settings of Las Vegas complexity in [16], where precise complexity is sought for.
In this case, a more homogenous definition would be appreciated.

We follow one such approach from [14], which we call state-generating.
We say that the input oracle $O_x$ encodes the input string $x\in[q]^n$ if it performs the transformation

\begin{equation}
\label{eqn:stateGeneratingOracle}
O_x \colon \ket |i>\ket|0> \mapsto\ket |i>\ket|x_i>
\end{equation}

for all $i\in [n]$.
The action of this oracle on $\ket |i>\ket|0>$ is identical to that of eqn:standardOracle, but we do not require anything for other states.
In other words, the admissible subspace of $O_x$ consists of vectors having $\ket|0>$ in the second register.
The admissible subspace of the algorithm itself is spanned by $\ket|0>$.
On that, it has to perform the transformation $\ket |0> \mapsto \ket |f(x)>$.
The algorithm has bidirectional access to $O_x$, which we treat as unidirectional access to $\bi{O_x}$ defined in eqn:bi.
It is possible to assume the input oracle $O_x$ is a direct sum of $n$ unitaries acting in $\bC^q$ in order to apply the multiple input oracle settings from sec:multipleInputOracles.

As the initial state is always $\ket |0>$, and $O_x$ is essentially determined by $x$, we will write

\begin{equation}
\label{eqn:function_QueryComplexity}
L_x (A) = L\sA[A, \bi{O_x}, \ket |0>]
\qqand
L(A) =  \max_{x\in D} L_x(A).
\end{equation}

More precisely, we define $L_x(A)$ as the supremum over all input oracles
$O_x$ that encode the input $x$.
We use similar notation for $L^{(i)}_x$ and $L^{(i)}$.

This approach has a number of advantages.
First, it casts function evaluation as a special case of state conversion with state-generating input oracles [14].
Second, the algorithm can be directly used as a part of the input oracle for another algorithm without any uncomputation.
Finally, this definition does not involve the somewhat arbitrary XOR operation and may be, thus, regarded as being more pure.
In particular, it makes sense to ask for the precise value of its quantum Las Vegas query complexity (and not just only up to constant factors).

This approach has a number of disadvantages.
First, we have to explicitly allow bidirectional access to $O_x$ in order to allow uncomputing, as it is no longer the case that $O_x$ is its own inverse.
More importantly, though, neither the action nor the Las Vegas complexity of the algorithm is specified for the initial states orthogonal to $\ket |0>$.
For our own algorithms, we can design them so that $O_x$ is only executed with $\ket|0>$ in the second register (maybe after some perturbation, see sec:perturbed).
But, if we are dealing with an arbitrary algorithm, we have no such guarantees.

§.§ Circuit Model

We assume that the space of the algorithm is embedded into a product of qubits, $(\bC^2)^{\otimes s}$, for some $s$ called the space complexity of the algorithm.
A quantum program is a product of elementary operations called gates:

\begin{equation}
\label{eqn:program}
A = G_TG_{T-1}\cdots G_1.
\end{equation}

In the circuit model, each gate $G_i$ is usually a 1- or a 2-qubit operation that can be applied to any qubit or a pair of qubits.
The number of elementary operations, $T$, is called the time complexity of $A$, and is denoted by $T(A)$.
We assume a universal gate set, so that every unitary can be written as a quantum program.
We do not focus too much on a particular model, as they are all essentially equivalent.

In a query algorithm like in sec:prelimQuery, each execution of the input oracle $\tO$ also traditionally counts as one elementary operation.
In other words, each unitary in eqn:preAlgorithm can be decomposed into elementary gates as in eqn:program to give a corresponding program in the circuit model.
We use $T$ to denote its time complexity, and $Q$ to denote its Monte Carlo query complexity.

We will often require an algorithm like in eqn:program to be executed conditionally, that is, controlled by the value of some external qubit.
In other words, we would like to perform an operation $A^{\mathrm{c}}$ of the form

\[
\ket |0>\ket |\xi> \maps{A^{\mathrm{c}}} \ket |0>\ket |\xi>
\ket |1>\ket |\xi> \maps{A^{\mathrm{c}}} \ket |1>\ket |A\xi>,
\]

where the first qubit is the control qubit.
We will denote time complexity of this procedure by $\TC(A)$.

Since it is possible to substitute each $G_i$ in eqn:program by its controlled version, we have that $\TC(A) = \OO(T(A))$.
But it is often possible to do better.
For instance, assume that $A$ is of the form $A_2A_1^{\mathrm{c}}$, i.e., a large chunk of $A$ is already conditioned.
We have that $T(A) = T(A_2) + \TC(A_1)$.
On the other hand, $\TC(A) = \TC(A_2) + \TC(A_1) + \OO(1)$, because we can calculate the AND of the two control qubits of $A_1$ into a fresh qubit, execute $A_1$ controlled by this fresh qubit, and uncompute the new qubit afterwards.
In other words, the constant factor of $\TC(A) = \OO(T(A))$ is not getting accumulated with each new conditioning, but is, in a way, paid only once.

§.§ QRAG model

The QRAG model extends the circuit model by allowing the following Quantum Random Access Gate:

\[
\mathrm{QRAG}\colon
\ket |i> \ket |b> \ket |x_1,\dots,x_{i-1}, x_i, x_{i+1},\dots, x_m>
\mapsto
\ket |i> \ket |x_i> \ket |x_1,\dots,x_{i-1}, b, x_{i+1},\dots, x_m>,
\]

where the first register is an $m$-qudit, and the remaining ones are quantum words (i.e., quantum registers large enough to index all the qubits in the program).
We assume the QRAG takes time $\timeR$ as specified in eqn:timeR.
Note that this gate would require time $\Omega(m)$ to implement in the usual circuit model, as it depends on all $m+2$ registers.

This should not be confused with the QRAM model, which allows oracle access to an array of classical registers $x_1,x_2,\dots,x_m$:

\[
\mathrm{QRAM}\colon
\ket |i> \ket |b> \mapsto \ket |i> \ket |b\oplus x_i>,
\]

where $\oplus$ stands for the bit-wise XOR.  The difference is that $x_i$s are being fixed during the execution of the quantum procedure (but they may be changed classically between different executions).
The QRAG model is more powerful than the QRAM model.

The main reason we need the QRAG is the following result (see, e.g., [27] for a formal statement, although the same construction has been used elsewhere including [2, 21, 24]):

Assume the QRAG model and that we have QRAM access to a description of a quantum program as in eqn:program in some space $\cH$, where each gate $G_i$ either comes from a fixed set of 1- or 2-qubit operations (which can be applied to different qubits each time), or is a QRAG.
Let $\cI$ be a $T$-qudit.  Then, the following Select operation

\begin{equation}
\label{eqn:select}
\sum_i \ket I|i>\ket H|\psi_i> \mapsto \sum_i \ket I|i> \ket H |G_i\psi_i>
\end{equation}

can be implemented in time $\OO(\timeR)$.

[Proof sketch]
We add a number of scratch registers to perform the following operations.
Conditioned on $i$, we use the QRAM to read the description of $G_i$.
We switch the arguments of $G_i$ into the scratch space using the QRAG.
We apply the operation $G_i$ on the scratch space.
We switch the arguments back into memory, and erase the description of $G_i$ from the scratch memory.
All the operations besides applying $G_i$ take time $\OO(\timeR)$.
Application of a usual gate $G_i$ takes time $\OO(1)$ as the gate set is fixed, or $\OO(T_R)$ if $G_i$ is a QRAG.

It is also possible to not store the whole program in memory, but compute it on the fly, in which case the complexity of this computation should be added to the complexity stated in thm:select.

Assume that in the settings of thm:select we have QRAM access to an array storing descriptions of $m$ quantum programs $A^{(1)},\dots, A^{(m)}$.
Let $\cI$ be a $m$-qudit.  Then, the following operation

\[
\sum_i \ket I|i>\ket H|\psi_i> \mapsto \sum_i \ket I|i> \ketA H |A^{(i)}\psi_i>,
\]

can be implemented in time $\OO\sA[\timeR\cdot \max_i T(A^{(i)})]$.

[Proof sketch]
Use thm:select to implement the first gate in all of $A^{(i)}$ in parallel, then the second one, and so on until the time mark $\max_i T(A^{(i)})$.

Another important primitive is the random access (RA) input oracle.
If $O\colon \cM\to\cM$ is an input oracle, then its RA version acts on $\cJ\otimes \cM^{\otimes K}$, where $\cJ$ is a $K$-qudit.
If the register $\cJ$ contains value $i$, the input oracle is applied to the $i$-th copy of $\cM$ in $\cM^{\otimes K}$.

The idea behind this is that if $O$ is implemented as a subroutine, then the RA input oracle is a special case of cor:selectProgram, where all $A^{(i)}$ are the same, but act on different sets of registers (which is easy to define using $\ket J|i>$ as an offset).
Therefore, it makes sense to define the RA input oracle as an elementary operation in the QRAG model.

§.§ Perturbed Algorithms

The following lemma is extremely useful in quantum algorithms, but for some reason has seldom experienced the honour of being explicitly stated.

Assume we have a collection of unitaries $U_1,\dots, U_m$ all acting in the same vector space $\cH$.
Let $\psi_0',\dots,\psi_m'$ be a collection of vectors in $\cH$ such that

\[
\psi_t' = U_t \psi_{t-1}'
\]

for all $t$.
Let $\psi_0,\dots, \psi_m$ be another collection of vectors in $\cH$ such that $\psi_0 = \psi'_0$ and

\begin{equation}
\label{eqn:surgeryPerturbation}
\normA | \psi_t - U_i \psi_{t-1} | \le \eps_i
\end{equation}

for all $i$.

\begin{equation}
\label{eqn:surgeryResult}
\normA | \psi_m - \psi'_m | \le \sum_{t=1}^m \eps_t.
\end{equation}

Denote by $V_t$ the product $U_m U_{m-1} \cdots U_{t+1}$.
In particular, $V_m = I$.

\[
\psi_m - \psi'_m = V_m \psi_{m} - V_0 \psi_0
=\sum_{t=1}^m \sA[ V_t \psi_{t} - V_{t-1} \psi_{t-1}]
= \sum_{t=1}^m V_t \sA[ \psi_{t} - U_t \psi_{t-1}].
\]

We obtain eqn:surgeryResult from the triangle inequality using eqn:surgeryPerturbation and the unitarity of $V_t$.

In the application of this lemma, $U_t$ stands for sequential sections of a quantum algorithm.
The vectors $\psi'_t$ form the sequence of states the algorithm goes through during its execution.
The vectors $\psi_t$ is an idealised sequence, which is used instead of $\psi_t'$ in the analysis.

We call the difference between $\psi_t$ and $U_t \psi_{t-1}$ a (conceptual) perturbation.
The expression in eqn:surgeryPerturbation is the size of the perturbation.
Therefore, the Eq. eqn:surgeryResult can be stated as the total perturbation of the algorithm does not exceed the sum of the perturbations of individual steps.
If this sum is small, the final state $\psi_m$ of the analysis is not too far away from the actual final state $\psi'_m$ of the algorithm.

This lemma is implicitly used every time an approximate version of a quantum subroutine is used, which happens in pretty much every non-trivial quantum algorithm.

§.§ Efficient Implementation of Direct-Sum Finite Automata

We will repeatedly use the following construction in this paper, for which we describe a time-efficient implementation.
We call it direct-sum quantum finite automata due to its superficial similarity to quantum finite automata.

The space of the algorithm is $\cK\otimes \cP\otimes \cH$, where $\cK$ is a $K$-qudit, $\cP$ is a qubit, and $\cH$ is an arbitrary space.
Additionally, we have black-box access to $K$ unitaries $S_0,\dots,S_{K-1}$ in $\cP\otimes \cH$.
The algorithm is promised to start in the state of the form

\begin{equation}
\label{eqn:automatonInitialState}
\ket K|0> \ket P|0> \ket H|\phi> + \sum_{t=0}^{K-1} \ket K|t>\ket P|1> \ket H|\psi_t>,
\end{equation}

and it has to perform the following transformation

\begin{equation}
\label{eqn:automaton}
\begin{minipage}{.9\linewidth}
\begin{itemize}
\item For $t=0,1,\dots,K-1$:\negmedskip
\begin{itemize}\itemsep=0pt
\item[(a)] Execute $S_t$ on $\cP\otimes \cH$ conditioned on $\ket K|t>$.
\item[(b)] Conditioned on $\ket P|0>$, replace $\ket K|t>$ by $\ket K|t+1>$.
\end{itemize}
\end{itemize}
\end{minipage}
\end{equation}

Let us elaborate on the “replace” in point (b).
It is not hard to show by induction that the $\ket P|0>$-part of the state contains a vector of the form $\ket K|t>\ket H|\phi_{t+1}>$.
This vector has to be replaced by $\ket K|t+1>\ket H|\phi_{t+1}>$.
We also assume that $\ket K|K>$ is identical with $\ket K|0>$.
For a graphical illustration refer to fig:automaton.

A graphical illustration of the action of a direct-sum finite automaton.
States $\phi_t$ represent the internal state of the automaton, as it processes a “string” of quantum vectors $\psi_0,\dots,\psi_{K-1}$ into $\psi'_0,\dots,\psi'_{K-1}$.
Unlike the usual quantum automata, the internal state of the automaton and the current “letter” of the “string” are joined via the direct sum.
Similarity with fig:pumping is apparent.
It is an interesting question, whether such finite automata can find other applications.

\[
\begin{tikzpicture}[every node/.style={font=\scriptsize}, every path/.append style={thick,->}]
\OneIteration{0}
\OneIteration{1}
\OneIteration{2}
\OneIteration{3}
\draw[\taucolor] (9,4) to node[above]{$\phi_{4}$} (10.5,4);
\end{tikzpicture}
\]

It is trivial to implement the transformation in eqn:automaton in $\OO(K\log K)$ elementary operations besides the executions of $S_t$.
It is a technical observation that we can remove the logarithmic factor.

The transformation in eqn:automaton can be implemented in time $\OO(K) + \sum_t \TC(S_t)$, where $\TC$ is defined in sec:prelimCircuit.

The register $\reg K$ uses $\ell = \log K$ qubits.
We introduce an additional register $\cC$ that also consists of $\ell$ qubits.
For $i, t\in [K]$, we denote

\[
\ket C|i\curlyvee t> = \ket |1>^{\otimes c} \ket |0>^{\otimes \ell-c}
\]

if the binary representations of $i$ and $t$, considered as elements of $\bool^\ell$, agree on the first $c$ most significant bits, and disagree on the $(c+1)$-st one (or $c=\ell$).

We modify the algorithm so that before the $t$-th iteration of the loop, the algorithm is in a state of the form

\begin{equation}
\label{eqn:automatonModifiedState}
\ket K|t> \ket P|0> \ket C|t\curlyvee t> \ket H|\phi_t>
\sum_{i=0}^{t-1}\ket K|i> \ket P|1> \ket C|i\curlyvee t> \ket H|\psi'_t>
\sum_{i=t}^{K-1}\ket K|i>\ket P|1>\ket C|i\curlyvee t> \ket H|\psi_t>
\end{equation}

In particular, in the $\ket P|0>$-part, the register $\reg C$ contains $\ell$ ones.

The state eqn:automatonModifiedState with $t=0$ can be obtained from eqn:automatonInitialState in $\OO(\ell)$ elementary operations by computing $\cC$ starting from the highest qubit.
Execution of $S_t$ on Step (a) can be conditioned on the lowest qubit of $\reg C$, which is equal to 1 if and only if $\cK$ contains $t$.

It remains to consider Step (b) and the update of the register $\cC$ during the increment from $t$ to $t+1$.
Assume that $t+1$ is divisible by $2^d$, but not by $2^{d+1}$.
Then, Step (b) takes $d+1$ controlled 1-qubit operations.
Similarly, the change from $t$ to $t+1$ in $\ket C|i\curlyvee t>$ in eqn:automatonModifiedState takes time $\OO(d)$ by first uncomputing the $d+1$ lowest qubits for $t$, and then computing them for $t+1$.
Finally, after the loop, the register $\reg C$ can be uncomputed in $\OO(\ell)$ operations.
Therefore, the total number of elementary operations is $\OO(K)$.

§ TRANSDUCERS

In this section, we define transducers and give their basic properties.
This is an initial treatment and will be extended in sec:canonical to include query complexity.

§.§ Definition

Mathematically, our approach is based on the following construction.

Let $\cH\oplus \cL$ be a direct sum of two vector spaces, and $S$ be a unitary on $\cH\oplus \cL$.
Then, for every $\xi\in\cH$, there exist $\tau\in\cH$ and $v\in\cL$ such that

\begin{equation}