††thanks: These authors made equal contributions<EMAIL_ADDRESS><EMAIL_ADDRESS>These authors made equal contributions.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Modular quantum signal processing in many variables

Zane M. Rossi  Department of Physics, Massachusetts Institute of Technology,
Cambridge, Massachusetts 02139, USA  Jack L. Ceroni  Department of
Mathematics, University of Toronto, Toronto, Ontario M5S1A1, Canada  Isaac L.
Chuang  Department of Physics, Massachusetts Institute of Technology,
Cambridge, Massachusetts 02139, USA

###### Abstract

Despite significant advances in quantum algorithms, quantum programs in
practice are often expressed at the circuit level, forgoing helpful structural
abstractions common to their classical counterparts. Consequently, as many
quantum algorithms have been unified with the advent of quantum signal
processing (QSP) and quantum singular value transformation (QSVT), an
opportunity has appeared to cast these algorithms as modules that can be
combined to constitute complex programs. Complicating this, however, is that
while QSP/QSVT are often described by the polynomial transforms they apply to
the singular values of large linear operators, and the algebraic manipulation
of polynomials is simple, the QSP/QSVT protocols realizing analogous
manipulations of their embedded polynomials are non-obvious. Here we provide a
theory of modular multi-input-output QSP-based superoperators, the basic unit
of which we call a _gadget_ , and show they can be snapped together with LEGO-
like ease at the level of the functions they apply. To demonstrate this ease,
we also provide a Python package for assembling gadgets and compiling them to
circuits. Viewed alternately, gadgets both enable the efficient block encoding
of large families of useful multivariable functions, and substantiate a
functional-programming approach to quantum algorithm design in recasting QSP
and QSVT as monadic types.

##  I Introduction

Quantum algorithms, persistently strange, remain difficult to design and
interpret [1]; correspondingly, great effort has been spent to not only
generate algorithms, but formalize the motifs of quantum advantage [2, 3, 4].
Both of these desires have been partially addressed by the advent of quantum
signal processing (QSP) [5, 6, 7, 8] and its lifted version quantum singular
value transformation (QSVT) [9]. These algorithms allow one to modify the
singular values of large linear operators by precisely tunable polynomial
functions, unifying and simplifying most known quantum algorithms [10], with
good numerical properties [11, 12, 13, 14], and deep, fruitful connections to
well-studied matrix factorization techniques [15].

In reducing diverse algorithmic problems to statements on the existence of
classes of polynomial functions, QSP and QSVT encourage but do not
substantiate interpreting quantum computations _functionally_. That is, it
becomes tempting to treat these algorithms purely in terms of the functions
they apply, directly working within the natural ring over polynomials
(generated by addition and multiplication), or the monoid associated with
polynomial composition. Such _function-first_ operations have clear semantic
interpretation, offer connection to a wealth of preëxisting mathematical
literature, and connect neatly to existing classical formalisms for the
design, verification, and optimization of programs [16, 17, 18].

Limited techniques for treating QSP and QSVT function-first have appeared,
answering the following narrow question: given repeatable oracle access to a
QSP protocol, and a description of another QSP protocol, can one instantiate
the protocol achieving _the composition of the functions achieved by each
protocol_ in black-box way? Independent lines of work [19, 20] have answered
this positively, with the former enumerating necessary and sufficient
conditions under which such composition is possible, and the latter examining
recursive composition converging to a useful class of functions. In both
works, however, only a single oracular unitary process is considered, and the
resulting computations are described only by compositions of polynomials in a
single variable, limiting the variety of achievable behavior and concomitant
algorithmic use. We also note that such limited methods for self-embedding
simple quantum subroutines has a long history [21, 5, 22, 23, 24], with roots
in composite pulse theory [25, 26] and classical signal processing [27, 28],
albeit without clear functional interpretation. Ultimately, a mature,
function-first theory, closed over operations natural to multivariable
polynomials (e.g., ring operations, the composition monoid) has not been
realized.

In moving to the multiple oracle setting, we are seeking a more ambitious
construction than previous work; that is, we want to be able to blithely snap
together basic modules, with structure similar to that of QSP, at the level of
the functions they apply. We will show this is surprisingly possible, with a
bit of additional work, through a careful synthesis of two previous
techniques: multivariable QSP (M-QSP) [29] and an intricate series of powerful
results on fractional queries from Sheridan, Maslov, and Mosca [30] extended
beautifully to QSVT by Gilyén, Su, Low, and Weibe [9]. In turn, these M-QSP-
based examples will then be generalized to a more encompassing theory of
_gadgets_. Ultimately, we will be able to succinctly describe and subsume
previous work on modular QSP-based algorithms [19, 20], the most obvious
bridge between our work and previous work on the level of the aforementioned
multivariable quantum signal processing (M-QSP) [29]. M-QSP (Def. II.1),
despite having a well-defined series of conditions under which a transform is
achievable, has proven unwieldy in practice, as multivariable analogues of the
algebraic geometric results characterizing achievable polynomial transforms
(chiefly the Fejér-Riesz Theorem [31, 32]) are unavoidably weaker in the
multivariable setting. We will show that such barriers, however, do not rule
out the existence of independently interesting subroutines strictly subsuming
M-QSP, and which allow one to freely manipulate and combine polynomial
functions. That is, to yield the same functional class as the one originally
desired but disallowed in standard M-QSP, we show it is sufficient to generate
algebraic structures over polynomials with rich closures; constructively
achieving such closures by expanding the class of circuits considered is a
central result of this paper.

The fundamental units of computation we construct are termed _gadgets_ , which
take as input (possibly multiple) unknown unitary processes, and produce as
output (possibly multiple) unitary processes, where outputs depend entirely on
multivariable polynomials applied to parameters of the inputs. We highlight an
important subclass of gadgets, _atomic gadgets_ , which are built directly
using M-QSP, and subsequently combined with rich fractional query techniques
[30, 9] to realize _snappable gadgets_ , which, having been suitably
_corrected_ , can be freely combined. We provide a characterization of the
_syntax_ for combining gadgets into composite gadgets (described by a two-
level grammar, which under basic restrictions becomes context-free), as well
as a description of valid _semantic_ manipulations for functions achieved by
these gadgets (in the form of a monadic type over M-QSP protocols). In
providing both a _syntactic_ and _semantic_ theory of gadgets, we provide a
formal response to the temptation to view QSP- and QSVT-based modules purely
functionally, and embed our constructions within established terminology from
functional programming and category theory.

Unlike in the single-oracle setting, the conditions under which functional
manipulations are possible within gadgets (for which the work of [19, 20]
consider a special case) do not depend solely on simple circuit symmetries;
consequently, the bulk of appendices of this work are spent specifying
detailed functional analytic arguments on the existence and performance of
special _correction protocols_ by which the output of a given gadget can be
_corrected_ such that it can be connected to the input of another gadget while
preserving the desired functional manipulation. We show that such gadget
connections are generally ill-conditioned without correction, and we prove
that correction generically cannot be done exactly, only to arbitrary
precision. In fact, it is this softened condition of approximate
achieveability that enables the huge variety of functional transforms. We
emphasize that unlike with other methods for generating composite
superoperators, like linear combination of unitaries (LCU), we maintain both
stringent space requirements and rapid convergence (polylogarithmic in inverse
error) to intended functional transforms. These constraints together
constitute the core difficulty of this work, though once settled, they can be
supressed, with the resulting gadgets (and simple methods for computing their
costs) relied on for algorithm design instead.

The results of this work can be taken at multiple levels of abstraction. At
the lowest, we achieve highly space- and query-efficient block encodings of
multivariable polynomials in commuting linear operators, asserting that QSVT
can retain key advantages over alternative methods like linear combination of
unitaries (LCU) [33, 34] in the multivariable setting (this fact is detailed
in Appx. B). Slightly higher, this work solidifies and greatly expands the
approach of [19] in treating QSP and QSVT protocols in the language of
functional programming through the composite objects of _gadgets_. We can
rephrase our results as instantiating a _monad_ over QSP and QSVT _types_ ,
and situate this monad in quantum programming language theory, with possible
compositions described by simple formal grammars. To support both of these
interpretations, we provide and highlight a series of concrete, linked
examples of achievable multivariable functions, as well as a (beta) Python
package for assembling gadgets and compiling their circuits, linked here:
[pyqsp].

Our presentation is generally divided in two components (the main body
Secs.I-V, and appendices A-I); in this main body, we provide the construction
for _gadgets_ (Sec. II) (of which there are sub-types, Appx. D.3), define and
discuss the connection of these gadgets into composite gadgets (Sec. III), and
provide a series of linked concrete examples of useful functions achieved by
assembling gadgets (Sec. IV), with detailed cost analysis (Appx. C). Within
the second major division, we provide a series of appendices which detail the
main proofs of theorems made in the main body (Appx. A), detailed analysis of
the aforementioned correction protocols (Appxs. E and F), detailed analysis of
the non-obvious method for computing gadget cost (Appx. C), discussion of how
gadgets instantiate monadic functions and relate to functional programming
(gadget _semantics_ , Appxs. I.1 and I.2), and finally discussion of a formal
language for gadgets constituted by an attribute grammar (gadget _syntax_ ,
Appx. I.3).

##  II Motivating and constructing gadgets

We have claimed that gadgets, properly constructed, can enable the efficient
achievement of multivariable polynomial transformations and a modular approach
to assembling quantum algorithms. This is shown explicitly in this section, by
building from M-QSP and its combination with fractional queries to create
_atomic gadgets_ , a remarkably useful subclass of gadgets. We use and extend
fractional query techniques [30, 9] to allow certain imperfections in atomic
gadgets to be corrected, leading the fundamental unit of our construction, the
_snappable gadget_ , which we suitably generalize beyond explicit reference to
QSP. For the moment, however, we recall that QSP circuits prescribe how to
take simply parameterized unknown unitary inputs and produce as output
unitaries with properties non-linearly dependent on, and carefully tuneable
with respect to, the input unitaries [9]. Crucially, within QSP, input
unitaries are highly constrained (in fact rotations about a fixed, known
axis), while the output unitiaries are not; even worse, if one were to
consider a QSP-like ansatz depending on multiple unknown unitaries as input,
not only can the form of the output unitary depend _on the function applied_ ,
but also on the _relation between each of the many unknown inputs_. At a high
level it is this _mismatch of basis_ between input and output unitaries in QSP
(and inherited in singular vector subspaces in QSVT) which prevents simple
composition of protocols at the level of the functions they achieve.

The core result of this work (Thm. III.2) lies in a terse equivalence between
general compositions of multivariable polynomials and general compositions of
gadgets (themselves based on QSP-like components) achieving these polynomials.
Toward gathering the components to state this equivalence, we first build off
of a QSP-related circuit to generate a powerful subclass of gadgets, followed
by identifying key issues in their compositions, and special protocols to
resolve these issues.

To start off, we recall the general definition of an _M-QSP protocol_ [29], of
which a standard QSP protocol is a special case. For the moment we will not
need to know any properties of this algorithm (covered in Appx. D for the
curious) besides its simple circuit form, other than to note that the problems
M-QSP protocols exhibit when we attempt to combine them as modules will
showcase shortcomings eventually resolved by the definition of _gadgets_ and
_correction protocols_ given later in this section. These problems also
distinguish the general setting from the single variable setting, where the
former is substantively more difficult to address.

######  Definition II.1 (M-QSP protocol).

Let $\Phi\equiv\\{\phi_{0},\dots,\phi_{n}\\}\in\mathbb{R}^{n+1}$ and
$s\in[t]^{\times n},\,t\in\mathbb{N}$, where $[t]=\\{0,\dots,t-1\\}$. Then the
$t$-variable M-QSP protocol specified by $(\Phi,s)$ generates the unitary
circuit

$\Phi[U_{0},\cdots,U_{t-1}]\equiv
e^{i\phi_{0}\sigma_{z}}\prod_{k=1}^{n}U_{s_{k}}e^{i\phi_{k}\sigma_{z}},$ (1)

where $U_{0},\cdots,U_{t-1}$ are unitaries of the form $U_{k}\equiv
e^{i\theta_{k}\sigma_{x}},k\in[t]$ for unrelated $\theta_{k}$ (see Def. II.2).
Here $\sigma_{z},\sigma_{x}$ are the standard Pauli matrices. We say an M-QSP
protocol is _antisymmetric_ if both $(N\circ R)(\Phi)=\Phi$ and $R(s)=s$,
where $R,N$ reverse and negate lists of scalars respectively, with equality
taken elementwise (when $\Phi$ contains zeros and the oracles can commute past
each other, this definition can be replaced one stating
$\Phi[U_{0},\cdots,U_{t-1}]=\Phi[U_{0},\cdots,U_{t-1}]^{\dagger}$.). Often $s$
will be suppressed when denoting $(\Phi,s)$ as a superoperator (see Appx. D).
An M-QSP protocol _achieves_ a function $f$, where $f\equiv\langle
0|\Phi[U_{0},\cdots,U_{t-1}]|0\rangle$ is a function over scalars (namely
those $x_{k}\equiv\cos(\theta_{k})$) parameterizing the oracles.

To understand the problem eventually solved by gadgets, we recall one of the
insights of previous work on embedding QSP-based circuits within themselves
[19]. In this work, it was shown how to iteratively compose antisymmetric
single-variable QSP protocols to compose their achieved functions. Such
compositions can be realized by successively using the QSP unitary produced by
some protocol $\Phi_{k}$ as the signal operator of another QSP protocol
$\Phi_{k+1}$, continuing perhaps for some collection protocols
$\\{\Phi_{0},\dots,\Phi_{n-1}\\}$. The admissibility of this recursion follows
from the fact that for any antisymmetric protocol $\Phi$ and oracle unitary
$e^{i\theta\sigma_{x}}$, the polynomial $P$ achieved by a single-variable QSP
protocol $\Phi$ is invariant under twisting. More specifically, for any
unitary $U$ and any $\sigma_{z}$-rotation $e^{i\varphi\sigma_{z}}$,
$\Phi[e^{i\varphi\sigma_{z}}Ue^{-i\varphi\sigma_{z}}]=e^{i\varphi\sigma_{z}}\Phi[U]e^{-i\varphi\sigma_{z}}$.
Thus for a sequence of antisymmetric QSP protocols
$\\{\Phi_{0},\dots,\Phi_{n-1}\\}$ the $(k+1)$-th protocol automatically treats
the function achieved by the $k$-th protocol as a variable for the function
achieved by $\Phi_{k+1}$. The output of each protocol remains in some sense
_embeddable_ , and the composability of functions follows. Below, we clarify
this notion of embeddability (introducing a few named types).

######  Definition II.2 (Variations on embeddable unitaries).

An $\text{SU}(2)$ unitary $U$ is embeddable if it has the form
$e^{i\theta\sigma_{x}}$ for some $\theta\in[0,\pi]$. A unitary is
$\varepsilon$-embeddable if it is at most $\varepsilon$-far (in operator norm)
from an embeddable unitary. An $\text{SU}(2)$ unitary $U$ is twisted
embeddable (half-twisted embeddable) if it has the form
$e^{i\varphi\sigma_{z}/2}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}$ for
some $\theta\in[0,\pi]$ and $\varphi\in[-\pi,\pi]$
($\varphi\in[-\pi/2,\pi/2]$). A unitary $U$ is $\varepsilon$-twisted
embeddable ($\varepsilon$-half-twisted embeddable) if it is at most
$\varepsilon$-far from a twisted embeddable (half-twisted embeddable) unitary
over a specified domain. Given a twisted or half-twisted embeddable unitary of
the form
$e^{i\varphi\sigma_{z}/2}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}$, we
refer to $e^{i\theta\sigma_{x}}$ as its embeddable component.

In what follows we show that maintaining such embeddability is vital for a
variety of desired computational tasks and discuss some subtleties of the
definitions contained in Def. II.2. To begin, we highlight a pedagogical
example: consider two antisymmetric, single-variable QSP protocols $\Phi_{0}$
and $\Phi_{1}$ and signal operators $e^{i\theta_{0}\sigma_{x}}$,
$e^{i\theta_{1}\sigma_{x}}$. By Thm. D.7,
$\Phi_{0}[e^{i\theta_{0}\sigma_{x}}]$ and
$\Phi_{1}[e^{i\theta_{1}\sigma_{x}}]$ are twisted embeddable, with

$\Phi_{0}[e^{i\theta_{0}\sigma_{x}}]=e^{i\varphi_{0}\sigma_{z}/2}e^{i\theta_{0}^{\prime}\sigma_{x}}e^{-i\varphi_{0}\sigma_{z}/2}\quad\text{and}\quad\Phi_{1}[e^{i\theta_{1}\sigma_{x}}]=e^{i\varphi_{1}\sigma_{z}/2}e^{i\theta_{1}^{\prime}\sigma_{x}}e^{-i\varphi_{1}\sigma_{z}/2}.$
(2)

Suppose $\Phi_{0}$ and $\Phi_{1}$ achieve functions $f_{0}$ and $f_{1}$, with
$\theta_{0}^{\prime}=f_{0}(\cos(\theta_{0}))$ and
$\theta_{1}^{\prime}=f_{1}(\cos(\theta_{1}))$. Given a two-variable
antisymmetric M-QSP protocol $\Phi$ achieving the function $g(x_{0},x_{1})$,
in the general case,

$\langle
0|\Phi\left[\Phi_{0}[e^{i\theta_{0}\sigma_{x}}],\Phi_{1}[e^{i\theta_{1}\sigma_{x}}]\right]|0\rangle\neq
g\left(f_{0}(\cos(\theta_{0})),f_{1}(\cos(\theta_{1}))\right).$ (3)

This is entirely due to the conjugation of the embeddable components of
$\Phi_{0}[e^{i\theta_{0}\sigma_{x}}]$ and
$\Phi_{1}[e^{i\theta_{1}\sigma_{x}}]$ by different $\sigma_{z}$-rotations.
Because $\varphi_{0}\neq\varphi_{1}$, it is no longer possible to factor the
$\sigma_{z}$-rotations out of the overall M-QSP protocol, in the same way as
the single variable case. In single variable protocols, accumulating
$\sigma_{z}$-conjugations by successively composing antisymmetric QSP
protocols had no effect on the function achieved by the QSP polynomial. Here,
one finds

$\Phi[e^{i\varphi\sigma_{z}}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}}]=e^{i\varphi\sigma_{z}}\Phi[e^{i\theta\sigma_{z}}]e^{-i\varphi\sigma_{z}}\Longrightarrow\langle
0|\Phi[e^{i\varphi\sigma_{z}}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}}]|0\rangle=\langle
0|\Phi[e^{i\theta\sigma_{x}}]|0\rangle.$ (4)

Therefore, in the multivariable case, we require a technique for suppressing
the disagreeing $\sigma_{z}$-conjugations of Eq. (2), leaving the relevant
embeddable components such that there is no interference with the outer M-QSP
protocol. Such a correction would turn Eq. (3) into an approximate equality.
Consequently we identify a concrete question: is it possible to map a twisted
embeddable unitary $U$ with unknown $\varphi$ and $\theta$ to its embeddable
component? In other words, can we _align_ the axes of rotation for two (or
more) unitary oracles in an efficient, black box way? We provide an
affirmative answer to this question, up to slightly weakened conditions, and
call this process of alignment _correction_.

######  Lemma II.1 (Efficient correction of $\varepsilon$-twisted embeddable
unitaries).

Let $U$ be a $\nu$-twisted embeddable unitary, so $U$ is $\nu$-close to
$U^{\prime}=e^{i\varphi\sigma_{z}/2}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}$.
Suppose $\cos(\theta)\in[-1+\delta,1-\delta]$. Let $\varepsilon>0$. Then,
given controlled access to $U$, there exists a quantum circuit using
$\zeta=\mathcal{O}(\delta^{-1}\log(\varepsilon^{-2}\delta^{-1/2}))$ black-box
calls to $U$ and a single ancilla qubit which yields a
$(\zeta\nu+\varepsilon)$-embeddable unitary $V$, which is at most
$(\zeta\nu+\varepsilon)$-far from $e^{i\theta\sigma_{x}}$ (the embeddable
component of $U^{\prime}$) with success probability at least
$(1-(\zeta\nu+\varepsilon))^{2}$. Alternatively, given access to two ancilla
qubits and uncontrolled oracle access to $U$, it is possible to implement a
circuit which achieves the same $(\zeta\nu+\varepsilon)$-approximation with
the same asymptotic query complexity and success probability, on the domain
$\cos(\theta_{k})\in[\delta,1-\delta]$. Finally, if $U$ is $\nu$-half-twisted
embeddable, and satisfies the same conditions, with the additional constraint
that $\cos(\varphi)\in[\gamma,\sqrt{1-\gamma^{2}}]$ (or
$\varphi\in[-\pi/2+2\gamma,-2\gamma]\cup[2\gamma,\pi/2-2\gamma]$), there
exists a quantum circuit using
$\zeta^{\prime}=\mathcal{O}(\delta^{-1}\gamma^{-2}\log^{2}(\gamma^{-4}\varepsilon^{-2}\delta^{-1/2}))$
black-box calls to $U$ and zero ancilla qubits which yields an
$(\zeta^{\prime}\nu+\varepsilon)$-embeddable unitary, at most
$(\zeta^{\prime}\nu+\varepsilon)$-far from the embeddable component
$e^{i\theta\sigma_{x}}$, with unit success probability. In all cases, the
quantum circuits effectuating the corrections can be specified constructively,
efficiently.

Lem. II.1 shows that given an approximately embeddable unitary, (1) the error
accumulated during its correction is proportional to the error of the input,
and (2) the constant of proportionality is linear in the length of the
correction procedure. This scaling as not as poor as it first appears, mainly
due to the ease with which $\nu$ can be made small and the limited number of
correction procedures that will be used by any physically reasonable
protocols. We call such protocols _acceptable_ if their length scales at worst
inverse polynomially in the desired output error, and argue for the
reasonableness of this class of protocols in the context of the efficiency of
Lem. II.1 in the expanded Rem. A.1. The resource costs for the correction
procedures under different access model assumptions is elaborated upon further
in Appxs. B and H (for a summary, see Table 1).

The correction procedure described enables us to take M-QSP protocols, apply
corrective protocols to their output, and pass these outputs into other M-QSP
protocols, such that the function achieved is the multivariate composition of
the functions achieved by the individual protocols. The closure over unitary
superoperators achieved by arbitrarily composing sequences of M-QSP unitaries
and corrections is what will be formalized by the generic notion of a
_gadget_. Below, we give two definitions for gadgets; the first, the _atomic
gadget_ (Def. II.3), is built directly from M-QSP protocols, while the second,
the _gadget_ (Def. II.4) captures the most general relevant definition for our
purposes. Under special conditions (discussed in detail in Sec. D.3), atomic
gadgets form a strict subset of gadgets, and we will work with such atomic
gadgets exclusively. In the following section, we show that such gadgets can
be successively composed to yield composite gadgets describing complex,
expressive quantum computations and achieving general and interpretable
functional transforms. Moreover, gadget objects have a highly-interpretable
form; we describe their permitted combinations described by attribute grammars
(a _syntax_ for gadgets), and describe their functional action by monadic
functions over QSP/QSVT types (a _semantics_ for gadgets).

######  Definition II.3 (Atomic $(a,b)$ gadget).

Let $(\Xi,S)$ be a tuple with $\Xi\equiv\\{\Phi_{0},\dots,\Phi_{b-1}\\}$ where
$\Phi_{k}\in\mathbb{R}^{r_{k}+1},r_{k}\in\mathbb{N}$ and
$S\equiv\\{s_{0},\dots,s_{b-1}\\}$ where $s_{k}\in[a]^{r_{k}}$ and
$[a]=\\{0,\dots,a-1\\}$. Then the atomic $(a,b)$ gadget labelled by $(\Xi,S)$
refers to the parameterization of $b$ M-QSP protocols using $a$ single-qubit
oracles $U_{k}$, where each of the $b$ output unitaries
$\Phi_{k}[U_{0},\dots,U_{a-1}]\,,k\in[b]$ has parameterization
$(\Phi_{k},s_{k})$ following Def. II.1. A gadget is _antisymmetric_ if its
constituting $(\Xi,S)$ generate only antisymmetric M-QSP protocols [19]. Note
that not all _atomic gadgets_ are _gadgets_ (Def. II.4), as discussed in Sec.
D.3, though atomic gadgets considered in this work (e.g., antisymmetric
gadgets) _will_ be.

######  Definition II.4 ($(a,b)$ gadget).

An $(a,b)$ gadget $\mathfrak{G}$ is a superoperator which takes as input $a$
single-qubit embeddable oracles $U_{k}$ for $k\in[a]$, and outputs $b$
twisted-embeddable unitaries $U_{k}^{\prime}$ for $k\in[b]$, denoted by
$U_{k}^{\prime}=\mathfrak{G}[U_{0},\dots,U_{a-1}]_{k}$. Note that
_antisymmetric_ atomic $(a,b)$ gadgets (Def. II.3) are a strict subset of
$(a,b)$ gadgets (Thm. D.7). However, there also exist other circuit-based
methods for constructing gadgets from M-QSP (Def. D.2). A gadget
$\mathfrak{G}$ is said to achieve $F\equiv\\{f_{0},\dots,f_{b-1}\\}$ where
$f_{k}\equiv\langle 0|U^{\prime}_{k}|0\rangle$ is the top-left matrix element
of the $k$-th output unitary given by applying $\mathfrak{G}$ to a set of
oracles. In the case that the input oracles are parameterized by variables
$x_{0},\dots,x_{a-1}$, each output unitary $U_{k}^{\prime}$ and each $f_{k}$
can be treated as functions $U_{k}^{\prime}(x_{0},\dots,x_{a-1})$ and
$f_{k}(x_{0},\dots,x_{a-1})$.

######  Remark II.1 (Gadget terminology).

Going forward, if an $(a,b)$ gadget $\mathfrak{G}$ is said to achieve output
unitaries $U_{k}^{\prime}(x_{0},\dots,x_{a-1}),k\in[b]$ and functions
$f_{k}(x_{0},\dots,x_{b-1}),k\in[b]$, it is meant that the gadget achieves
these functions for input unitaries $U_{k}=e^{i\theta_{k}\sigma_{x}},k\in[a]$,
where each $x_{k}=\cos(\theta_{k}),k\in[a]$ is possibly restricted to a fixed
domain specified along with the gadget.

In many cases, a gadget will achieve its output unitaries $U_{k}^{\prime}$ via
some sequence of products and interspersed quantum (and possibly even
classical) operations. The only criteria on the input oracles is that the
gadget sees them as black-boxes, which can only be utilized through quantum
circuit queries. When we refer to the cost associated with a gadget
$\mathfrak{G}$, we are referencing the number of black-box queries that must
be made to the input oracles to achieve some particular output unitary,
possibly at a specified precision over a specified parameter domain. Detailed
discussion of cost and its associated objects for gadgets are restricted to
Appx. C.

We now present the key theorem which describes how the correction protocol of
Lem. II.1 enables _snappable gadgets_ to be constructed from general gadgets.
Snappable gadgets are engineered such that their outputs are embeddable – not
merely twisted-embeddable – and may be passed as input to another gadget in a
black-box way and while respecting achieved functions. Note that going forward
we let $\widetilde{\mathcal{O}}$ indicate asymptotic complexity up to leading
order/logarithmic factors in each independent variable.

######  Theorem II.1 (Efficient correction of unitaries produced by $(a,b)$
gadgets).

Let $\varepsilon,\delta>0$ and $\mathfrak{G}$ an $(a,b)$ gadget whose output
unitaries are guaranteed to be $\nu$-twisted-embeddable: they are $\nu$-close
to unitaries
$e^{i\varphi\sigma_{z}/2}e^{i\theta_{k}\sigma_{x}}e^{-i\varphi\sigma_{z}/2}$
whose embeddable components encode $\cos{\theta}_{k},k\in[b]$ within
$[-1+\delta,1-\delta]$. Assuming an access model in which one can query the
_controlled_ single-qubit unitaries achieved by the output legs of
$\mathfrak{G}$, then given $k\in[b]$, there exists a computable
$\nu^{\prime}=\widetilde{\mathcal{O}}(\delta\varepsilon)$ and a quantum
circuit using
$\zeta=\widetilde{\mathcal{O}}(\delta^{-1}\text{log}{(\varepsilon^{-1}}))$
black-box calls to the controlled unitaries produced by executing
$\mathfrak{G}$ on the input oracles, as well as one ancilla qubit, such that
if $\nu\leq\nu^{\prime}$ then the circuit achieves an
$\varepsilon$-approximation of $U_{k}^{\prime}=e^{i\theta_{k}\sigma_{x}}$ (the
embeddable component of the $k$-th output unitary of $\mathfrak{G}$), with
success probability at least $(1-\varepsilon)^{2}$, for all $k$.
Alternatively, given access to two ancilla qubits and access only to
uncontrolled $U$ queries, the same outcome can be achieved with the same
asymptotic complexity and success probability over the domain
$\cos(\theta_{k})\in[\delta,1-\delta]$. Finally, in the case that the output
legs are all $\nu$-half twisted embeddable with
$\cos(\varphi)\in[\gamma,\sqrt{1-\gamma^{2}}]$, the same can be done with no
extra space and unit success probability using
$\zeta=\widetilde{\mathcal{O}}(\delta^{-1}\gamma^{-2}\log^{2}(\varepsilon^{-1}))$
black-box calls to $\mathfrak{G}$ and the guarantee that
$\nu\leq\nu^{\prime\prime}$, for a computable
$\nu^{\prime\prime}=\widetilde{\mathcal{O}}(\delta\gamma^{2}\varepsilon)$.
Each protocol described above can be constructed efficiently and obliviously
to the output unitaries of the gadget.

Essentially this theorem (proven in Appx. A) applies Lem. II.1 to each output
leg of a gadget, obtaining our desired endpoint for this section: _snappable
gadgets_. While the following definition is somewhat innocuous, in the
following we show that such gadgets, when assembled, induce natural and
simple-to-track algebraic manipulations of their achieved transforms.

######  Definition II.5 (Snappable gadget).

A gadget is said to be $\varepsilon$-$\delta$-_snappable_ if each of its
output legs, over all unitary inputs with the form of $\sigma_{x}$-rotations
by an angle $\theta$ such that $\delta<|\cos{(\theta)}|<1-\delta$, produces a
unitary which is $\varepsilon$-close to a $\sigma_{x}$-rotation in norm.

##  III Composing QSP gadgets

The gadgets of Defs. II.3 and II.4 and the correction procedure of Thm. II.1
bring us to _snappable gadgets_. Such gadgets can finally be freely assembled
into composite gadgets to build complex, useful functional transforms; in this
section we formally define this assembly, and enumerate its properties. The
desired endpoint of this section, the statement of Thm. III.2, shows a neat
equivalence between a series of (partially) composed polynomials achieved by
individual gadgets, and a structured network of those gadgets. This section
begins by focusing on the linkages of these networks, captured in Thm. III.1,
such that Thm. III.2 can be used to snap together a series of example gadgets
with LEGO-like ease in Sec. IV.

As mentioned, we show in this section that gadgets permit a simple
diagrammatic representation of their semantics, depicted in Fig. 1; in this
way, complex functions can be built hierarchically out of simpler ones and
visually reasoned about in an intuitive way. More specifically, we can think
of so-called $(a,b)$ gadgets as boxes with $a$ _input legs_ , representing
oracular unitary inputs, and $b$ _output legs_ , representing output unitaries
(These boxes are shown in (c) of Fig. 1 for $a=b=2$). To flesh out this
diagrammatic language, we present a theorem (Thm. III.1) enumerating the valid
ways to link gadgets together, and translate the effect of such compositions
into statements on algebraic manipulations over each gadget’s achieved
polynomial functions. Diagrammatically, linking gadgets is depicted by joining
input and output legs. In this way, as exemplified in the _Rosetta Stone_
diagram of Fig. 1, one can freely reason about assemblages of gadgets in terms
of any among (a) the circuits realizing them, (b) the functional manipulations
they achieve, or (c) as linkages between boxes with semantically simple input
and output legs. While not discussed in this section explicitly, the syntax of
gadget assemblages follows a formal grammar (Appx. I.3), while the semantics
of achievable functional manipulations is described by the instantiation of a
monadic type (Appx. I.2). We finally note briefly that depicting quantum
superoperators as such acyclic graphs is not entirely new, as previous works
considering quantum combs (circuits with open slots) have expressed them in
terms of simple _causal networks_ [35, 36, 37]; the difference between those
works’ general prescription and ours is that our networks depict semantic
properties of interactions between achieved functional transforms, and we
require careful constraints on allowed unitary inputs. For this reason, as
well ease of description for higher-order operations over gadgets defined
later, relying on causal networks rather than quantum combs to depict our
superoperators leads to an expedient, clarified visual language.

Figure 1: A gadget _Rosetta Stone_ giving three depictions of the same self-
composition of a $(2,2)$ gadget (Def. II.3). Arrows indicate direct
substitution, of (a) quantum circuits (time going left to right), (b)
polynomials, and (c) gagdet legs, where $A,B$ are slots (places where an
oracle unitary can be substituted) and $\Phi$ are programmable, generally
distinct $\sigma_{z}$ rotations. The (Laurent) polynomial transforms achieved
by the two protocols, $P_{0},P_{1}$, are real-valued with real arguments, and
the correction protocol of Thm. II.1 is implicitly interspersed between
substitutions (represented explicitly by dots in Fig. 2). Note that the
circuit (a) and functional (b) depictions are different from the _gadget_ (c)
depiction given, e.g., in Figs. 2 and 4 and elsewhere; this difference is
detailed in Rem. I.2.

We begin our description of gadget compositions with a definition.

######  Definition III.1 (Interlink for gadgets).

Let $\mathfrak{G}$ and $\mathfrak{G}^{\prime}$ be $(a,b)$ and $(c,d)$ gadgets
respectively. An _interlink_ between these gadgets specifies a way to validly
connect them. Take $[b],[c]$ to be the length-$b$ and length-$c$ (zero-
indexed) ordered lists of labels of the outputs of $\mathfrak{G}$ and the
inputs of $\mathfrak{G}^{\prime}$ respectively. An _interlink_ is a three
element list $\mathfrak{I}\equiv(B,C,W)$ with the following prescription: $B$
is a sublist of $[b]$ of size $e\in\\{0,1,\cdots,\min{(b,c)}\\}$, $C$ is a
sublist of $[c]$ also of size $e$, and $W$ is a member of $S_{e}$ the
permutation group over $e$ elements.

We can use this definition to precisely state the following theorem on the
general combinations of gadgets. This theorem shows that gadgets can be
composed in a nearly unconstrained way, snapped together like LEGOs, with
well-understood associated cost and functional action.

######  Theorem III.1 (Composing a gadget with an atomic gadget).

Let $\varepsilon,\delta>0$, $\mathfrak{G}$ be an $(a,b)$ gadget and $(\Xi,S)$
an antisymmetric atomic $(c,d)$ gadget, where
$\Xi\equiv\\{\Phi_{0},\dots,\Phi_{b-1}\\}$ and
$S\equiv\\{s_{0},\dots,s_{b-1})$ for $(\Xi,S)$. Suppose the gadget
$\mathfrak{G}$ achieves

$F(x)\equiv\\{f_{0}(x_{0},\cdots,x_{a-1}),f_{1}(x_{0},\cdots,x_{a-1}),\dots,f_{b-1}(x_{0},\cdots,x_{a-1})\\}\in(\mathbb{R}^{a}\rightarrow\mathbb{R}^{b})$
(5)

over $x\in[-1,1]^{\times a}$, and the atomic gadget $(\Xi,S)$ achieves

$G(y)\equiv\\{g_{0}(y_{0},\cdots,y_{c-1}),g_{1}(y_{0},\cdots,y_{c-1}),\dots,g_{d-1}(y_{0},\cdots,y_{c-1})\\}\in(\mathbb{R}^{c}\rightarrow\mathbb{R}^{d})$
(6)

over $y\in[-1,1]^{\times c}$. Let $\mathfrak{I}=(B,C,W)$ be an interlink
between these gadgets. Then, there exists a gadget $\mathfrak{G}^{\prime}$
which $\varepsilon$-approximately achieves

$H(x,y^{\prime})\equiv\bigcup_{k\in[d]}g_{k}\left(\bigcup_{j\in
B}f_{W(j)}(x_{0},\dots,x_{a})\cup\bigcup_{k\not\in
C}y_{k}\right)\cup\bigcup_{k\not\in B}f_{k}(x_{0},\dots,x_{a})$ (7)

over $(F(x),y^{\prime})\in\mathcal{D}$, where $y^{\prime}$ is the subset of
$y_{k}$ such that $k\notin C$ and $\mathcal{D}$ is a domain determined by the
correction procedure utilized. The set union symbol is abused to mean
concatenation of lists with respect to the pre-established order of the labels
of the relevant input and output _lists_ (not sets), and where $W(j)$ is the
result of the application of the specified permutation applied to the _index_
of the subset member $j$ in the ordered sublist $C$ of $[c]$. Moreover,
$\mathfrak{G}^{\prime}$ can be constructed efficiently, and uses only a
description of $(\Xi,S)$ and a total of
$\widetilde{\mathcal{O}}(d\lvert\Xi\rvert_{\infty}\,\zeta)$ black-box calls to
the _unitaries produced by running_ $\mathfrak{G}$ to realize the function
$H$.

Note $\zeta$, the cost of correcting the gadget $\mathfrak{G}$, is precisely
the cost to make $\mathfrak{G}$ _snappable_ , and this snappability enables
the simple compositional form of Eq. 7. $\zeta$ is one among two choices
presented in Thm II.1, with the variables $\varepsilon$ and $\delta$ carrying
over. Generally,
$\zeta=\widetilde{O}(\text{polylog}(\varepsilon^{-1})\text{poly}(\delta^{-1}))$,
with possible polynomial scaling in a parameter $\gamma$, given in Thm. II.1,
as well. This choice also dictates whether $\mathcal{O}(1)$ or zero ancilla
qubits are required to perform this composition, and whether the success
probability of achieving each individual function is at least
$(1-\varepsilon)^{2}$, or $1$. $\lvert\Xi\rvert_{\infty}$ is the maximum
length of lists within $\Xi$. For a proof of this result, see Appx. A.

######  Remark III.1 (Arbitrary gadget interlinks).

While it is possible to consider interlinks between _arbitrary_ gadgets,
rather than assuming _a priori_ that the second gadget is atomic, it isn’t
possible to make a general claim about the required complexity to implement
such a composition. For a generic gadget, treated as a black box accepting and
outputting unitaries, one cannot know the required query complexity of the
input legs in order to achieve a given output, with some precision, without
knowledge of exactly how the input legs are queried within the gadget:
behaviour which can, in principle, vary dramatically between different
gadgets. We do know this internal structure for the special case of atomic
gadgets (they are collections of M-QSP circuits). Nevertheless,
characterization of interlinks between gadgets and atomic gadgets allows for
full characterizations of arbitrary “gadget networks” of many interlinks along
with associated corrections (as an atomic gadget which has been corrected may
not longer strictly be an atomic gadget, due to the possible introduction of
ancilla qubits). As a result, Thm. III.1 is sufficiently powerful for all
practical purposes within the scope of this paper.

Via Thm. III.1, an interlink $\mathfrak{I}$ can be thought of as an operator
over gadgets, mapping a pair of gadgets to a single gadget with a possibly new
type

$(a,b),(c,d)\rightarrow(a+c-e,b+d-e),$ (8)

for any $e\in\\{0,1,\cdots,\min{(b,c)}\\}$.

######  Remark III.2.

Given an interlink, $\mathfrak{I}$, a gadget $\mathfrak{G}$, and an
antisymmetric atomic gadget $(\Xi,S)$, we refer to the gadget
$\mathfrak{G}^{\prime}$ resulting from the above operation as
$\mathfrak{I}[\mathfrak{G},(\Xi,S)]$. Moreover, we can think of an interlink
as inducing an operation of pairs of functions themselves. Going forward,
given an interlink $\mathfrak{I}$, as well as functions $F$ and $G$ of the
form of Eq. (5) and Eq. (6), we let $G\circ_{\mathfrak{I}}F$ denote the
function $H$ of Eq. (7).

Graphically an interlink is simple to describe, as is shown in Fig. 2, which
also depicts the general action described in Thm. III.1.

Figure 2: A depiction of gadgets coupled by interlinks (Def. III.1) both in
example (a-b), and generally (c). Given two gadgets, an interlink $(B,C,W)$
specifies a subset of output legs $B$, input legs $C$, and a permutation $W$,
joining gadgets according to Thm. III.1. Two possible interlinks are shown
explicitly in (a-b) for $(2,2)$-gadgets. In (c), possibly many legs are
suppressed in dashed legs, and the sets $B,C$ in Thm. III.1 are precisely
those composing the composite leg $z$; in this way (c) captures the most
general coupling of two gadgets, per Thm. III.1. In all cases black dots
indicate a correction protocol (II.1) necessary to properly couple legs.

Beyond composition, one can define a variety of operators over gadgets; we
note that, as these gadgets are themselves superoperators, we are free to
duplicate and elide outputs at the possible cost of additional queries. As
discussed in Appx. A, one can _augment_ an $(a,b)$ gadget to an $(a,b+c)$
gadget, as well as _elide_ an $(a,b)$ gadget to an $(a,b-c)$ gadget by
ignoring outputs. Moreover, the input of an $(a,b)$ gadget can be _pinned_ to
yield an $(a-c,b)$ gadget, or the output legs of an $(a,b)$ gadget can be
_permuted_ to yield an $(a,b)$ gadget. Finally, note that the correction
protocol itself can be thought of as an operator over gadgets, leaving the
function achieved by the gadget approximately unchanged, but transforming its
unitary output by a $\sigma_{z}$ conjugation. The form and cost of these basic
operations is covered in Appx. A and, once generally computed, these rules
allow the algorithmist to reason about complex, multi-input/output functional
operations agnostic to their realizing circuits, in a _functional style_.

Before continuing, we note that defining the closure over arbitrarily
interlinking finite-size gadgets is not a simple task. For instance,
decomposing a given polynomial in a single-variable into an optimal tower of
composed, lower degree polynomials (a strictly simpler problem) was once
assumed to be a computationally hard problem [38, 39, 40], and the conditions
under which such decomposition is efficient in the multivariable case have
only recently been generally understood [41] and analyzed in the approximate
setting [42, 43, 44], with the generic problem known to be NP-hard [45].
Nevertheless such decompositions, if they do exist, are basically unique (a
consequence of Ritt’s theorem [46]), and packages exist within most computer
algebra systems for computing them. Consequently, while we show that we can
achieve the full algebraic and monoidal operations natural to multivariable
polynomials, our constructions only furnish competitive upper bounds on the
required space, gate, and query complexity to achieve a given transform, with
lower bounds depending on deep results in algorithmic complexity theory [47,
48, 49] and polynomial decomposition theorems not exposited here. Despite this
fact, we are still able to provide a compact _equivalence theorem_ for
composite gadgets achieving polynomials which can be decomposed into a tower
of lower-degree polynomials for which atomic gadgets are known.

######  Theorem III.2 (Efficient equivalence of polynomial compositions and
gadget assemblages).

Let $\mathcal{L}(x_{1},\dots,x_{n})$ denote the set of all polynomials
achievable by atomic gadgets in the variables $x_{1},\dots,x_{n}$. Suppose
$P(x_{1},\dots,x_{n})$ is a polynomial of degree $D$ and can be split into a
tower of $m=\mathcal{O}(\log(D))$ _interlinked polynomials_ (Rem. III.2),

$P=P^{(m-1)}\circ_{\mathfrak{I}_{m-2}}\left(P^{(m-2)}\circ_{\mathfrak{I}_{m-3}}\circ\left(\cdots\left(P^{(1)}\circ_{\mathfrak{I}_{0}}P^{(0)}\right)\cdots\right)\right)$
(9)

such that $P_{i}^{(j)}\in\mathcal{L}(x_{1},\dots,x_{n})$ for all $i$ and $j$.
Assume that the composition satisfies the domain condition (Rem. C.1) with
$P_{k}$ supported on $\mathcal{D}_{k}$ such that each $\mathcal{D}_{k}$ is
separated from singular points $\pm 1$ (and possibly $0$) by some length
$\delta\in\mathcal{O}(1)$ for all $k$. Then, there exists an assemblage of $m$
atomic, snappable gadgets which $\varepsilon$-approximates the polynomial $P$
on the domain yielded from the $\mathcal{D}_{k}$, with cost
$\widetilde{O}(\text{poly}(D)\,\text{polylog}(\varepsilon))$.

For a proof of this theorem, see Appx. A. We remark that the discussion of
query and gate complexity in Thm. III.1 and thus Thm. III.2, while simple,
does not immediately extend to composite gadgets with complex internal
structure. For this purpose we introduce a variety of independently
interesting mathematical objects which allow for expedient calculation of the
cost of implementing a gadget which achieves a desired function up to a
desired precision over a desired range of inputs. The basic object for such
costs is a _cost matrix_ (Def. C.1 in Appx. C), which permits one to determine
the query complexity of a gadget with respect to a given input leg for a given
output leg, up to a specified precision over a specified range of inputs. With
a few simple abstractions, computing composite gadget costs is thus reduced to
a lightly augmented form of matrix multiplication over sub-gadget cost
matrices. Details of this calculation are presented in Appx. C.

##  IV Examples

The results of Sec. III together project a new path for building quantum
subroutines: namely, the equivalence of Thm. III.2 ensures that we can think
purely in terms of the polynomials achieved by a series of gadgets when
snapping them together visually as modular pieces, while this LEGO-like
construction is governed behind the scenes in the circuit picture by the
simple rules of Thm. III.1. To highlight these principles together in action,
we thus consider a series of linked examples making use of minimally complex
pieces. We provide an overview of these examples in Fig. 3, grouping them in
terms of the natural algebraic structures they constitute; in turn, these
examples are exposited in Sec. IV.1, which covers common basic arithmetic, and
Sec. IV.2, which combines these pieces to achieve a variety of familiar and
utilitarian functional classes.

Figure 3: A summary of functional transforms achieved in this work, grouped
(above the line) by their constitution of common mathematical structures over
polynomials. Addition, polynomial multiplication, and scalar multiplication
form a polynomial ring, where (${\ddagger}$) indicates we consider (possibly
clipped) polynomials over $x\in[-1,1]$ of definite parity, maximum norm one,
and taking real-values; these properties are preserved under the specified
operations. We also achieve a monoid generated by single-variable polynomial
composition, as well as its generalized form capturing tuples of multivariable
polynomials, described by the grammar and language of gadgets (Appx. I). We
stress that in the general case we cannot achieve these operations exactly,
only to arbitrary precision and with an associated cost. These operations,
together with the ability to generate arbitrary single-variable bounded,
definite parity, real polynomials using QSP, and a special subset ($\dagger$)
of such polynomials with M-QSP [29], permit all highlighted examples of Sec.
IV (enumerated below the line).

###  IV.1 Basic arithmetic with gadgets

One of the most immediately useful applications of the protocols derived in
the previous section is the ability to perform basic arithmetic and
interpolation, coherently, between two polynomial functions, each achieved by
an independently specified QSP protocol.

######  Example IV.1 (Inversion and negation).

We start with two simple $(1,1)$ gadgets with utility in the creation of
composite functions. Each take as input some $x_{0}\in[-1,1]$ as usual. The
first, termed _inversion_ pre-applies an $iX$ (special unitary) to the oracle,
producing $\sqrt{1-x_{0}^{2}}$ which ‘logically inverts’ the input on
$\\{0,1\\}$. The second, termed _negation_ conjugates the oracle by the
(special unitary) $iY$, and achieves $-x_{0}$. Note that these are not _atomic
gadgets_ per Def. II.3, as their form is outside that of M-QSP protocols, but
that they produce embeddable output (Def. II.2).

######  Example IV.2 (Angle sum and difference).

To illustrate a useful but non-obviously antisymmetric gadget, we can consider
the $(2,1)$ gadget resulting from multiplying two oracles in different
variables with QSP phases all zero, e.g., $U_{0}U_{1}$, which achieves
$x_{0}x_{1}-\sqrt{1-x_{0}^{2}}\sqrt{1-x_{1}^{2}}$. This corresponds to adding
the angles associated with oracle unitaries. This can be changed to an angle
difference by conjugating one oracle, e.g., $U_{1}\mapsto
e^{i\pi/4\sigma_{z}}U_{1}e^{-i\pi/4\sigma_{z}}$.

######  Example IV.3 (Multiplication).

Let $\mathfrak{G}_{\text{mult}}\equiv(\Xi,S)$ be the $(2,1)$ atomic gadget
with

$\Xi\equiv\\{\Phi\\}=\\{\\{-\pi/4,\pi/4,-\pi/4,\pi/4\\}\\}\ \text{ and }\
S=\\{\\{0,1,0\\}\\}.$ (10)

This gadget achieves $f(x_{0},x_{1})=T_{2}(x_{0})x_{1}$, which can be linked
to gadget outputs to multiply functions (up to pre-application of
$T_{2}(x)=2x^{2}-1$, the second Chebyshev polynomial of the first kind, to the
first argument).

######  Example IV.4 (Sub-normalization).

Let $(\Xi,S)$ be the $(2,1)$ atomic gadget of Ex. IV.3. Let
$\mathfrak{G}_{\text{subnorm}}(a)$ be the $(1,1)$ gadget obtained from pinning
(Def. A.1) the index-$0$ input leg to the unitary
$U_{0}=e^{i\arccos(x_{0})\sigma_{x}}$ where $x_{0}=\sqrt{(1+a)/2}$, for
$a\in[-1,1]$. Then $\mathfrak{G}_{\text{subnorm}}(a)$ obtains the function
$f(x)=T_{2}(\sqrt{(1+a)/2})x=ax$, for all $x\in[-1,1]$.

######  Example IV.5 (Scaling).

Take the $(1,1)$ atypical gadget constructed in Ex. D.2, which achieves an
arbitrary bounded real polynomial $P$ of definite parity. Consider the
polynomial approximation of $P$ from Lemma 30 of [9], which
$\varepsilon$-approximates the linear function $ax$ for $a>1$ on the interval
$x\in[(-1+\delta)/a,(1-\delta)/a]$. Then the QSP phases $\Phi$ of the protocol
achieving $P$ can be inserted into the prescription of Ex. D.2 to yield a
$(1,1)$ gadget which multiplies its input by a scalar greater than $1$ with a
clipped output: $\mathfrak{G}_{\text{scale}}(a)$. Moreover, the cost of this
gadget is $\mathcal{O}([a/\delta]\log{[a/\varepsilon]})$ queries to $x_{0}$,
by [9], and requires no additional space.

######  Example IV.6 (Addition).

Let $\mathfrak{G}_{\text{add}}\equiv(\Xi,S)$ be the $(2,1)$ atomic gadget with

$\Xi\equiv\\{\Phi\\}=\\{0,\pi/4,0,-\pi/4,0\\}\ \text{ and }\ S=\\{0,1,1,0\\}$
(11)

This protocol will achieve the function
$f(x_{0},x_{1})=T_{2}(x_{0})T_{2}(x_{1})$ for $x_{0},x_{1}\in[-1,1]$. Let
$U_{0}$ and $U_{1}$ be embeddable, with $U_{0}=e^{i\arccos(x_{0})\sigma_{x}}$
and $U_{1}=e^{i\arccos(x_{1})\sigma_{x}}$. The products

$\displaystyle V_{0}$
$\displaystyle=U_{0}U_{1}=e^{i(\arccos(x_{0})+\arccos(x_{1}))\sigma_{x}},$
(12) $\displaystyle V_{1}$
$\displaystyle=U_{0}e^{i\pi\sigma_{z}/2}U_{1}e^{-i\sigma_{x}\pi/2}=U_{0}U_{1}^{\dagger}=e^{i(\arccos(x_{0})-\arccos(x_{1}))\sigma_{x}},$
(13)

define simple $(2,1)$ gadgets. We can achieve a $(2,1)$ gadget by first
duplicating the input legs corresponding to $U_{0}$ and $U_{1}$, passing a
pair $(U_{0},U_{1})$ into each of the $V_{0}$ and $V_{1}$ gadgets, then
passing these two output legs into $(\Xi,S)$. However, note that $V_{0}$ and
$V_{1}$, while being $\sigma_{x}$-rotations, can generally have their rotation
angle in $[-\pi,\pi]$, rather than $[0,\pi]$. Thus, either $V_{0}$ is
embeddable _or_ $\sigma_{z}V_{0}\sigma_{z}$ is embeddable, with the same
holding true for $V_{1}$. However, as can be easily checked, this
$\sigma_{z}$-ambiguity will not matter: these extra $\sigma_{z}$-rotations
(when absorbed into the phase sequence $\Phi$ as extra $\pi/2$-rotations) will
have no effect on the output polynomial: this gadget will always achieve

$\displaystyle f(x_{0},x_{1})$
$\displaystyle=T_{2}\left(\cos(\arccos(x_{0})+\arccos(x_{1}))\right)T_{2}\left(\cos(\arccos(x_{0})-\arccos(x_{1}))\right)$
(14)
$\displaystyle=\cos\left(2(\arccos(x_{0})+\arccos(x_{1}))\right)\cos\left(2(\arccos(x_{0})-\arccos(x_{1}))\right)$
(15)
$\displaystyle=\frac{\cos(4\arccos(x_{0}))+\cos(4\arccos(x_{1}))}{2}=\frac{T_{4}(x_{0})+T_{4}(x_{1})}{2}.$
(16)

See Fig. 4 for a graphical depiction of the interlinks constituting this
gadget.

######  Example IV.7 (Constant shift).

It is possible to pin the addition gadget to perform a “constant shift” (up to
the fourth Chebyshev polynomial): $x\mapsto\frac{1}{2}T_{4}(x)+b$ for
$b\in[-1/2,1/2]$. This gadget, denoted $\mathfrak{G}_{\text{shift}}(b)$, is
achieved by taking the gadget of Ex. IV.6 and pinning its second input (Def.
A.1) to $e^{i\arccos(x_{1})\sigma_{x}}$, with $T_{4}(x_{1})=2b$. Note it is
possible to combine the sub-normalization and constant shift protocols into an
_affine shift_ of the form $x\mapsto\frac{1}{2}T_{4}(ax)+b$.

The above examples, implementing basic arithmetic, have the constraint that
they apply a Chebyshev polynomial to at least one of the inputs. As a final
point, note that all of the provided examples can be rid of the inclusion of
Chebyshev polynomials (approximately), via composition with the inverse
Chebyshev protocol of Thm. IV.1, stated and proved below.

######  Theorem IV.1 (Inverses of Chebyshev polynomials).

Given $0<\delta\leq 1$ and $0<\varepsilon\leq 1/2$, there exists $(1,1)$
gadgets of depth and cost
$\mathcal{O}(\delta^{-1}\log(\varepsilon^{-2}\delta^{-1/4}))$ which
$\varepsilon$-approximately achieve functions $T_{2^{n}}^{-1}(x)$ (right-
inverses) for $x\in[-1+\delta,1-\delta]$, using a single qubit (no ancillae).

For a proof of this result, see Appx. H. Using this protocol (in particular,
by interlinking the inverse Chebyshev gadget with the arithmetic gadgets), it
is possible to realize the following transformations of the functions achieved
above, approximately, on restricted domains:

$\displaystyle f(x_{0},x_{1})=T_{2}(x_{0})x_{1}$ $\displaystyle\Longrightarrow
f^{\prime}(x_{0},x_{1})=x_{0}x_{1},$ (17) $\displaystyle
f(x_{0},x_{1})=\frac{T_{4}(x_{0})+T_{4}(x_{1})}{2}$
$\displaystyle\Longrightarrow f^{\prime}(x_{0},x_{1})=\frac{x_{0}+x_{1}}{2}.$
(18)

This, of course, will come at the expense of added circuit depth. To this end,
we have the following theorems.

######  Theorem IV.2 (Arbitrary approximate multiplication).

Given $0<\delta\leq 1$ an $0<\varepsilon\leq 1/2$, there exists a $(2,1)$
gadget of depth/cost
$\mathcal{O}(\delta^{-1}\log(\varepsilon^{-2}\delta^{-1/4}))$ which
$\varepsilon$-approximately achieves the function $f(x_{0},x_{1})=x_{0}x_{1}$
for all $x_{0}\in[-1+\delta,1-\delta]$ and $x_{1}\in[-1,1]$ using no ancilla
qubits.

######  Theorem IV.3 (Arbitrary approximate addition).

Given $0<\delta\leq 1$ and $0<\varepsilon\leq 1/2$, there exists a $(2,1)$
gadget of depth/cost
$\mathcal{O}(\delta^{-1}\log(\varepsilon^{-2}\delta^{-1/4}))$ which
$\varepsilon$-approximately achieves the function
$f(x_{0},x_{1})=(x_{0}+x_{1})/2$ for all $x_{0},x_{1}\in[-1+\delta,1-\delta]$
using no ancilla qubits.

We refer to Appx. H for proofs of these results, and more details about the
cost of performing these transformations. With these basic operations
instantiated, it is now easy to see how Thm. III.2 immediately implies that
all multivariable polynomials up to bound and parity constraints are
approximately achieveable by _some_ composite gadget mirroring the structure
of the algebraic manipulations achieved. While the question of the _most
efficient_ gadget realization is more difficult, we can freely use the gadgets
above sparingly in the next section to instantiate a series of familiar and
useful functions.

Figure 4: Component breakdown of the sum gadget (Ex. IV.6). The sum gadget (a)
is achieved by the composition of multiple $(1,1)$ and $(2,1)$ gadgets as
shown, specifically $A$ (the square root gadget from Thm. IV.1 with $T_{2}$),
$B$ (angle sum gadget, Ex. IV.2), $C$ (angle subtraction gadget, Ex. IV.2),
and $D$ (product gadget, Ex. IV.3). The achieved composite operation $(b)$ can
be treated as a $(2,1)$ gadget labelled by $E$, whose partial composition with
itself $(c)$ has the expected semantic behavior.

###  IV.2 Familiar multivariable functions from gadgets

Having highlighted basic examples of arithmetic operations with respect to two
variables, we leverage these operations to construct more complicated
functional transformations. We begin with a short remark.

######  Remark IV.1 (Algebra of gadget operations).

Given the operations of addition and multiplication presented in Eq. (17), Eq.
(18), as well as the scaling operations of Ex. IV.4 and Ex. IV.5, and the
general ability to compose gadgets arbitrarily, it is possible to achieve
approximations of arbitrary multivariate polynomials on mildly restricted
domains. This is a somewhat surprising result in and of itself: sufficiently
high-depth M-QSP protocols (up to the possible use of ancilla qubits during
correction) can approximately achieve all multivariate polynomials, modulo
certain constraints imposed in the examples of Sec. IV.1. In general, these
naïve, “ground-up” constructions of polynomials will have poor scaling, due to
the need to perform the highly non-linear inverse Chebyshev and corrective
protocols. Nevertheless, there are also other examples of short protocols
which achieve useful transformations without the added depth of performing
square roots or many nested correction protocols. This fact is one of the
fundamental takeaways of the following results we wish to emphasize: while it
is possible to build all transformations from the repeated composition of only
a few low-degree gadgets, in order to achieve experimentally reasonable
protocols, it is much more advantageous to use such basic gadgets sparingly,
relying on functions efficiently achieved by standard M-QSP protocols where
possible.

To begin our discussion of more advanced examples, we present a brief
discussion of techniques for constructively achieving step and bandpass
functions through gadget composition.

######  Example IV.8 (Basic step function of [20]).

The protocol introduced in [20], refered to as _r-QSP_ is an example of an
$n$-fold composition of $(1,1)$ atomic gadgets. In particular, the authors
(implicitly) construct a family of $(1,1)$ atomic gadgets
$\mathfrak{G}^{(\ell)}_{\text{step}}\equiv(\Xi^{(\ell)},S^{(\ell)})=(\Phi_{\text{step}}^{(\ell)},\\{0,\dots,0\\})$
with $|\Phi_{\text{step}}^{(\ell)}|=2\ell+1$ such that the $n_{\ell}$-fold
full composition (Thm. III.1)
$\mathfrak{G}^{(\ell)}_{\text{step}}\circ\cdots\circ\mathfrak{G}^{(\ell)}_{\text{step}}$
achieves an $\varepsilon$-approximation of the function $f(x)=\text{sign}(x)$
on the interval $[-1,-\delta]\cup[\delta,1]$ when the length of the resulting
gadget, $\zeta=(2\ell+1)^{n_{\ell}}$, satisfies

$\zeta=\mathcal{O}\left(\delta^{-2(\nu_{\ell}+1)}\log^{1+\nu_{\ell}}\left(\varepsilon^{-1}\right)\right),\
\ \ \nu_{\ell}=\frac{\log(2\ell+1)}{\log(\ell+1)}-1.$ (19)

Making use of the basic step function construction of [20], as well as the
arithmetic operations of the previous section, it is possible to construct a
simple, infinite family of bandpass filters.

######  Example IV.9 (Simple bandpass family).

Given $a\in[\delta,1/\sqrt{2}]$, there exists a family of $(1,1)$ gadgets
$\mathfrak{G}_{\text{bandpass}}^{(\ell)}(a)$, such that
$\mathfrak{G}^{(\ell)}_{\text{bandpass}}(a)$ $\varepsilon$-approximately
achieves a function $f$ satisfying $|f|\leq 1$ as well as

$f(x)\in\begin{cases}[1-\varepsilon,1]&\text{if}\ x\in[-a+\delta,a-\delta]\\\
[-1,-1+\varepsilon]&\text{if}\
x\in\left[-\frac{1}{\sqrt{2}},-a-\delta\right]\cup\left[a+\delta,\frac{1}{\sqrt{2}}\right],\end{cases}$
(20)

where the total depth of the gadget, $\zeta^{\prime}$, satisfies

$\zeta^{\prime}=\mathcal{O}\left((2a\delta)^{-4(\nu_{\ell}+1)}\log^{1+\nu_{\ell}}\left(\varepsilon^{-1}\right)\right).$
(21)

Moreover, given the phases of $\Phi^{(\ell)}_{\text{step}}$, a sequence of Ex.
IV.8, the gadget $\mathfrak{G}^{(\ell)}_{\text{bandpass}}(a)$ can be described
analytically, in terms of these phases.

For a proof of this result, see Appx. H. This example provide good
illustration of the fundamental tension between the generality of the classes
of functions that can be achieved via composition of gadgets, and the
asymptotic scaling of resource requirements. Here, we have shown that it is
possible to achieve a _restricted_ class of bandpass filters via the gadget
formalism. It is, generally speaking, possible to drop the restrictions of
this example (in particular, the constraint that the function approximately
achieves only the values $\pm 1$), at the expense of more queries/corrective
protocol applications (see Ex. IV.11).

There are many other examples of low-depth protocols which can be achieved via
gadget composition, and the simple arithmetic operations discussed previously.
We highlight some of these examples below.

######  Example IV.10 ($2^{n}$ mean).

Let $\mathfrak{G}$ be the $(2,1)$ gadget achieving $(x_{0}+x_{1})/2$. Then one
can build a composite $(2^{n},1)$ gadget $\mathfrak{G}^{\prime}$, as well as
the correction protocol, achieving $2^{-n}(x_{0}+x_{1}+\dots+x_{2^{n}-1})$
using $(2^{n}-1)$ instances of $\mathfrak{G}$ and successively pooling pairs
of variables. E.g., $(x_{0}+x_{1})/2$ and $(x_{2}+x_{3})/2$ are taken to their
average $(x_{0}+x_{1}+x_{2}+x_{3})/4$.

The cost of implementing gadgets will depend on the range of input parameters
for which it must output an $\varepsilon$-approximation of the desired
function. Moreover, the cost will depend on whether the ancilla of ancilla-
free gadget correction protocol is used, which will vary on a case-by-case
basis. As an illustrative example, we provide a detailed discussion of the
complexity of implementing the $2^{n}$-gadget, and discuss how its cost
differs from the cost LCU, in Appx. H. In addition to this example, we make
note of some other gadgets, which are, in principle, possible to achieve. The
complexity analysis of each, and how it compares to other techniques such as
LCU, carries forward in the same manner of casework as is presented in the
example of Appx. H.

######  Example IV.11 (Arbitrary one-dimensional bandpass functions).

Consider $\mathfrak{G},\mathfrak{G}^{\prime}$ two $(1,1)$ gadgets
approximately achieving sign functions
$\Theta(x_{0}-a_{0}),\Theta(x_{0}-a_{1})$ (Ex. IV.8), where $\Theta(x_{0})$
takes the value $-1$ for $x<0$ and $1$ for $x>0$ on the interval $[-1,1]$.
Without loss of generality assume $a_{0}<a_{1}$; then the averaging gadget
applied to $\mathfrak{G}$ and $\mathfrak{G}^{\prime\prime}$ (the modified
gadget achieving $-\Theta(a_{1})$, enabled by Ex. IV.1) achieves an
approximation to the following ideal bandpass function:
$\Theta^{\prime}(x_{0})\equiv[\Theta(x_{0}-a_{0})-\Theta(x_{0}-a_{1})]/2$.which
for $x_{0}<a_{0}$ achieves $0$, for $a_{0}<x<a_{1}$ achieves $1$, and for
$x>a_{1}$ again achieves zero.

######  Example IV.12 (Majority vote).

Majority vote among $2^{n}$ elements follows directly from the previous
examples; let $\mathfrak{G}$ the $(2^{n},1)$ gadget of Ex. IV.10 and
$\mathfrak{G}^{\prime}$ the $(1,1)$ gadget thresholding at $x_{0}=1/2$ (Ex.
IV.11). Then the simple composition $\mathfrak{G}^{\prime}\circ\mathfrak{G}$
is a $(2^{n},1)$ gadget satisfying the desired properties.

######  Example IV.13 (Subnormalized functional interpolation).

There exists a $(3,1)$ gadget that approximately achieves the function
$f(x_{0},x_{1},x_{2})=[x_{0}x_{2}+x_{1}\sqrt{1-x_{2}^{2}}]/2$. In other words,
depending on $x_{2}$, the gadget smoothly interpolates between the sub-
normalized variables $x_{0}$ and $x_{1}$. If $x_{0},x_{1}$ result from
previous gadgets, this realizes a (sub-normalized) interpolation between two
functions. Construction follows from previous gadgets. Namely the products
$x_{0}x_{2}$ and $x_{1}\sqrt{1-x_{2}^{2}}$ are realized by Ex. IV.3, with
$\sqrt{1-x^{2}}$ achieved from $x_{2}$ by Ex. IV.1. Finally, both results are
summed by Ex. IV.6.

The cost analysis of these gadgets carries forward similarly to the example
highlighted in Appx. H, depending on which corrective protocol is chosen.

##  V Discussion and conclusion

At the most basic level this work gives a modular construction, rooted in QSP
and QSVT, for achieving highly expressive multivariable block encodings for
commuting operators. This construction relies on special _corrective_
subroutines which restore the _embeddability_ (Def. II.2) of QSP- and QSVT-
like protocols in a black-box way. Recovering embeddability allows assemblages
of such protocols, which can take many unitary oracles as input and produce
many unitary outputs, to be simply wired together _at the level of the
functions they apply_ to matrix-invariant quantities; that this is a true
modular process is demonstrated in the statements of the work’s main theorems:
Thms. III.1 and III.2, which indicate how to intersperse independently defined
correction protocols (Thm. II.1) between modules. Such modules are named
_gadgets_ (Def. II.4), and their valid combinations are shown to follow a
simple grammar, and generate both the natural commutative ring and composition
monoid over multivariable polynomials. In the terminology of programming
language theory, the modularity of gadgets is formalized in identifying them
as _monadic types_ , with the correction protocol furnishing a previously
missing component of the monaic function _bind_ (Appx. I).

We can thus phrase our results in three styles, in level of increasing burden
of proof and abstractness. (a) We provide improved, constructive upper bounds
on the resource requirements (space, gate, and query complexity) of
multivariable polynomial block encodings, and make comparisons to previously
known methods (see Appx. B), with inspiration from older results in modular
classical filter design [27, 28] and composite pulse sequences [26, 23, 22].
(b) We provide methods for interpretable constructions of coherent (quantum)
control flow, with no obvious incoherent counterpart. Specifically, we work in
a coherent-access model, analogous to that of recent work on the benefit of
measurement-free oracular access [50, 51], and show that the enaction of
complex QSVT-protocols can be coherently conditioned on, or in general coupled
to, within each singular-vector subspace, another set of singular values. (c)
We apply methods in functional programming, type theory, and category theory
to re-situate QSP and QSVT as quantum _types_ , in relation to which our
results instantiate a _monadic type_ over real-valued, real-argument
multivariable polynomials (see Appx. I). Our methods thus offer aid in quantum
algorithm design, pragmatically generalizing the work of [19] and providing a
simpler path for applying M-QSP [29] to achieve useful multivariable
functional transforms.

Our construction of gadgets couples to the design of quantum algorithms on two
levels, inspired by a natural division in formal and natural languages:
semantics and syntax [52, 16, 17]. On the first, gadgets specify which
polynomial transforms can be treated functionally, serving as basic units of
computation; formally this is summarized in the instantiation of a monad, and
characterizes the basic _semantics_ of the resulting system. At the second
level, we define a formal grammar enumerating valid ways to connect gadgets,
which characterizes _syntax_ of our system. While the ultimate relation
between our construction’s syntax and semantics is more complicated than this
simple division implies, depending on various hybrid structures such as
attribute grammars [52], these two levels help to situate this work in
classical programming language theory, where division into semantics and
syntax is considered a first step along the path of parsing, optimizing over,
and deriving expression meaning from structural information and basic semantic
assignments.

To restate a crucial point, this work considers gadgets comprising QSP/QSVT
protocols that can be linked, following intermediary processing, to other
gadgets _such that_ their embedded functional transforms are combined in a
_semantically clear way_. This intermediary processing is generally necessary,
non-trivial, and strictly subsumes the single-variable case [19], which itself
subsumed more limited but intriguing families of techniques in the recursive
use of quantum algorithms [22, 23, 26]. The key benefit of our method is that
each gadget inherits the approximative efficiency and ancilla-efficient
character of QSP, meaning that the complexity of achieving a desired
polynomial transform is no longer coupled directly to term number, polynomial
degree, or polynomial norm, as in LCU or standard QSVT [53], but instead
sophisticated results in the theory of multivariable polynomial decomposition
[38, 39, 45, 41], and multivariable quantum signal processing. In turn, this
opens intriguing questions in the algorithmic complexity (or
Solomonoff–Kolmogorov–Chaitin complexity) [47, 48, 49] of certain approximate
functional transforms under the composition of gadgets, for which our results
provide an upper bound. The benefit of this approach to quantum algorithm
design is multiform: numerical (given a new utility for low-order gadgets),
experimental (given the reduced number of distinct QSP phases to compute),
conceptual (given the fungibility/reusability of precomputed gadgets), and
finally pedagogical (given the expanded role offered to QSP in quantum
information processing).

We stress, however, that there remain significant open questions on the
optimality of method offered here, especially in light of the dependence of a
gadget’s complexity on sophisticated results in the theory of polynomial
decompositions [38, 39, 45, 41]. It is thus the authors’ belief that existing
methods for multivariable block encoding, such as LCU, continue to offer
diverse, context-specific utility, and deserve continued attention in future
related work on generating novel block encodings.

Whether viewed in terms of highly-efficient block encodings, or as the
instantiation of a monadic type [54, 55, 56] over higher-order quantum
processes composable in accordance to a simple grammar, this work instantiates
new and expressive QSP/QSVT-based quantum algorithms, with function-first
interpretability and a declarative style. To support this claim, we provide
multiple examples, constructing block encodings of algorithmically useful
multivariable polynomials with improved query and space complexity over
alternative methods. Finally, we remark that the ability to semantically
combine QSP/QSVT as modules in a black-box way relies strongly on their
restricted circuit form, and we believe the balance between this structure and
the known algorithmic expressivity of QSP/QSVT points toward a larger family
of parameterized quantum circuits to which functional programming abstractions
can be fruitfully applied.

##  VI Acknowledgements

Z.R. was supported in part by the NSF EPiQC program. J.C. thanks Prof. Nathan
Wiebe for valuable conversations, and for catalyzing and funding an internship
during the summer of 2023 at MIT, where the majority of the work on this
project was conducted. J.C. also thanks the MIT Research Laboratory of
Electronics (RLE) for their hospitality during his time at MIT. I.C. was
supported in part by the U.S. DoE, Office of Science, National Quantum
Information Science Research Centers, and Co-design Center for Quantum
Advantage (C2QA) under contract number DE-SC0012704.

## References

  * [1] Scott Aaronson.  Read the fine print.  Nat. Phys., 11(4):291–293, 2015.
  * [2] Andrew M Childs and Wim Van Dam.  Quantum algorithms for algebraic problems.  RMP, 82(1):1, 2010.
  * [3] Ashley Montanaro.  Quantum algorithms: an overview.  Npj Quantum Inf., 2(1):1–8, 2016.
  * [4] Scott Aaronson.  How much structure is needed for huge quantum speedups?  arXiv preprint, arXiv:2209.06930, 2022.
  * [5] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang.  Fixed-point quantum search with an optimal number of queries.  Phys. Rev. Lett., 113(21):210501, 2014.
  * [6] G. H. Low, T. J. Yoder, and I. L. Chuang.  Methodology of resonant equiangular composite quantum gates.  Phys. Rev. X, 6:041067, 2016.
  * [7] G. H. Low and I. L. Chuang.  Optimal Hamiltonian simulation by quantum signal processing.  Phys. Rev. Lett., 118:010501, 2017.
  * [8] G. H. Low and I. L. Chuang.  Hamiltonian simulation by qubitization.  Quantum, 3:163, Jul 2019.
  * [9] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics.  Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019.
  * [10] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang.  Grand unification of quantum algorithms.  PRX Quantum, 2(4), dec 2021.
  * [11] Jeongwan Haah.  Product decomposition of periodic functions in quantum signal processing.  Quantum, 3:190, Oct 2019.
  * [12] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy.  Finding angles for quantum signal processing with machine precision.  arXiv preprint, arXiv:2003.02831, 2020.
  * [13] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin.  Efficient phase-factor evaluation in quantum signal processing.  Phys. Rev. A, 103(4), Apr 2021.
  * [14] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang.  Infinite quantum signal processing.  arXiv preprint, arXiv:2209.10162, 2022.
  * [15] Ewin Tang and Kevin Tian.  A CS guide to the quantum singular value transformation.  arXiv preprint, arXiv:2302.14324, 2023.
  * [16] Peter Selinger.  Towards a quantum programming language.  Math. Struct., 14(4):527–586, 2004.
  * [17] Peter Selinger.  Towards a semantics for higher-order quantum computation.  In Proceedings of the 2nd International Workshop on Quantum Programming Languages, TUCS General Publication, volume 33, pages 127–143. Citeseer, 2004.
  * [18] Simon J. Gay.  Quantum programming languages: Survey and bibliography.  Math. Struct., 16(4):581–600, 2006.
  * [19] Zane M. Rossi and Isaac L. Chuang.  Semantic embedding for quantum algorithms.  arXiv preprint, arXiv:2304.14392, 2023.
  * [20] Kaoru Mizuta and Keisuke Fujii.  Recursive quantum eigenvalue/singular-value transformation: Analytic construction of matrix sign function by Newton iteration.  arXiv preprint, arXiv:2304.13330, 2023.
  * [21] Lov K Grover.  Fixed-point quantum search.  Phys. Rev. Lett., 95(15):150501, 2005.
  * [22] Guang Hao Low, Theodore J Yoder, and Isaac L Chuang.  Optimal arbitrarily accurate composite pulse sequences.  Phys. Rev. A, 89(2):022341, 2014.
  * [23] Jonathan A Jones.  Nested composite NOT gates for quantum computation.  Phys. Lett. A, 377(40):2860–2862, 2013.
  * [24] Sami Husain, Minaru Kawamura, and Jonathan A Jones.  Further analysis of some symmetric and antisymmetric composite pulses for tackling pulse strength errors.  J. Magn. Reson., 230:145–154, 2013.
  * [25] F. M. Toyama, S. Kasai, W. van Dijk, and Y. Nogami.  Matched-multiphase Grover algorithm for a small number of marked states.  Phys. Rev. A, 79:014301, Jan 2009.
  * [26] Elica Kyoseva and Nikolay V Vitanov.  Arbitrarily accurate passband composite pulses for dynamical suppression of amplitude noise.  Phys. Rev. A, 88(6):063410, 2013.
  * [27] J Kaiser and R Hamming.  Sharpening the response of a symmetric nonrecursive filter by multiple use of the same filter.  IEEE Transactions on Acoustics, Speech, and Signal Processing, 25(5):415–422, 1977.
  * [28] Tapio Saramaki.  Design of FIR filters as a tapped cascaded interconnection of identical subfilters.  IEEE Transactions on Circuits and Systems, 34(9):1011–1029, 1987.
  * [29] Zane M. Rossi and Isaac L. Chuang.  Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle.  Quantum, 6:811, Sep 2022.
  * [30] L Sheridan, D Maslov, and M Mosca.  Approximating fractional time quantum evolution.  J. Phys. A Math. Theor., 42(18):185302, 2009.
  * [31] George Polya and Gabor Szegö.  Problems and Theorems in Analysis II.  Springer, Berlin, 1998.
  * [32] J. Geronimo and Hugo Woerdeman.  Positive extensions, Fejér-Riesz factorization and autoregressive filters in two variables.  Ann. Math., 160:839–906, Nov 2004.
  * [33] Dominic W Berry, Andrew M Childs, and Robin Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In 2015 IEEE 56th annual symposium on foundations of computer science, pages 792–809. IEEE, 2015.
  * [34] Yonah Borns-Weil, Tahsin Saffat, and Zachary Stier.  A quantum algorithm for functions of multiple commuting Hermitian matrices.  arXiv preprint, arXiv:2302.11139, 2023.
  * [35] Dennis Kretschmann and Reinhard F Werner.  Quantum channels with memory.  PRA, 72(6):062323, 2005.
  * [36] Giulio Chiribella, G Mauro D’Ariano, and Paolo Perinotti.  Quantum circuit architecture.  Phys. Rev. Lett., 101(6):060401, 2008.
  * [37] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti.  Theoretical framework for quantum networks.  Physical Review A, 80(2):022339, 2009.
  * [38] David R Barton and Richard Zippel.  Polynomial decomposition algorithms.  J. Symb. Comput., 1(2):159–168, 1985.
  * [39] Dexter Kozen and Susan Landau.  Polynomial decomposition algorithms.  J. Symb. Comput., 7(5):445–456, 1989.
  * [40] Matthew T Dickerson.  The functional decomposition of polynomials.  PhD thesis, Cornell University, 1989.
  * [41] Jean-Charles Faugère and Ludovic Perret.  An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography.  J. Symb. Comput., 44(12):1676–1689, 2009.
  * [42] Robert M Corless, Mark W Giesbrecht, David J Jeffrey, and Stephen M Watt.  Approximate polynomial decomposition.  In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, pages 213–219, 1999.
  * [43] Mark Giesbrecht and John May.  New algorithms for exact and approximate polynomial decomposition.  In Symbolic-Numeric Computation, pages 99–112. Springer, 2007.
  * [44] Sefa Demirtas, Guolong Su, and Alan V. Oppenheim.  Exact and approximate polynomial decomposition methods for signal processing applications.  In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5373–5377. IEEE, 2013.
  * [45] Matthew T Dickerson.  General polynomial decomposition and the s-1-decomposition are NP-hard.  Int. J. Found. Comput. Sci., 4(02):147–156, 1993.
  * [46] Joseph Fels Ritt.  Prime and composite polynomials.  Trans. Amer. Math. Soc., 23(1):51–66, 1922.
  * [47] R.J. Solomonoff, United States. Air Force. Office of Scientific Research, and Zator Company.  A Preliminary Report on a General Theory of Inductive Inference.  AFOSR TN-60-1459. United States Air Force, Office of Scientific Research, 1960.
  * [48] A. N. Kolmogorov.  Three approaches to the definition of “the quantity of information”.  Problemy peredachi informatsii, 1(1):3–11, 1965.
  * [49] Gregory J Chaitin.  On the simplicity and speed of programs for computing infinite sets of natural numbers.  Journal of the ACM (JACM), 16(3):407–422, 1969.
  * [50] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi.  Quantum algorithmic measurement.  Nat. Commun, 13(1), 2022.
  * [51] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al.  Quantum advantage in learning from experiments.  Science, 376(6598):1182–1186, 2022.
  * [52] Donald E Knuth.  Semantics of context-free languages.  Mathematical systems theory, 2(2):127–145, 1968.
  * [53] Danial Motlagh and Nathan Wiebe.  Generalized quantum signal processing.  arXiv preprint, arXiv:2308.01501, 2023.
  * [54] Philip Wadler.  Comprehending monads.  In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, pages 61–78, 1990.
  * [55] Philip Wadler.  The essence of functional programming.  In Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 1–14, 1992.
  * [56] Philip Wadler.  Monads for functional programming.  In Advanced Functional Programming: First International Spring School on Advanced Functional Programming Techniques Båstad, Sweden, May 24–30, 1995 Tutorial Text 1, pages 24–52. Springer, 1995.
  * [57] Andrew K Tan, Yuan Liu, Minh C Tran, and Isaac L Chuang.  Error correction of quantum algorithms: Arbitrarily accurate recovery of noisy quantum signal processing.  arXiv preprint, arXiv:2301.08542, 2023.
  * [58] Jiasu Wang, Yulong Dong, and Lin Lin.  On the energy landscape of symmetric quantum signal processing.  arXiv preprint, arXiv:2110.04993, 2021.
  * [59] Xin Wang, Youle Wang, Zhan Yu, and Lei Zhang.  Quantum phase processing: Transform and extract eigen-information of quantum systems.  arXiv preprint, arXiv:2209.14278, 2022.
  * [60] Zhan Yu, Hongshun Yao, Mujin Li, and Xin Wang.  Power and limitations of single-qubit native quantum neural networks.  Advances in Neural Information Processing Systems, 35:27810–27823, 2022.
  * [61] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, USA, 10th edition, 2011.
  * [62] Camille Jordan.  Essai sur la géométrie à $n$ dimensions.  Bulletin de la Société mathématique de France, 3:103–174, 1875.
  * [63] Oded Regev.  Fast amplification of QMA (lecture notes), 2006.  https://cims.nyu.edu/~regev/teaching/quantum_fall_2005/ln/qma.pdf.
  * [64] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 387–400, New York, NY, USA, 2020. Association for Computing Machinery.
  * [65] Michele Pagani, Peter Selinger, and Benoît Valiron.  Applying quantitative semantics to higher-order quantum computing.  In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 647–658, 2014.
  * [66] Thorsten Altenkirch and Jonathan Grattage.  A functional quantum programming language.  In 20th Annual IEEE Symposium on Logic in Computer Science (LICS’05), pages 249–258. IEEE, 2005.
  * [67] Saunders Mac Lane.  Categories for the Working Mathematician.  Springer New York, NY, 2nd edition, 1978.
  * [68] Eugenio Moggi.  Computational lambda-calculus and monads.  University of Edinburgh, 1988.
  * [69] Eugenio Moggi.  An abstract view of programming languages.  University of Edinburgh, 1989.
  * [70] Joachim Lambek and Philip J Scott.  Introduction to higher-order categorical logic, volume 7.  Cambridge University Press, 1988.
  * [71] Tatsuki Odake, Hlér Kristjánsson, Akihito Soeda, and Mio Murao.  Higher-order quantum transformations of hamiltonian dynamics.  arXiv preprint, arXiv:2303.09788, 2023.
  * [72] Noam Chomsky.  Three models for the description of language.  IRE Transactions on information theory, 2(3):113–124, 1956.
  * [73] Adriaan van Wijngaarden.  Orthogonal design and description of a formal language.  Stichting Mathematisch Centrum. Rekenafdeling, 1965.
  * [74] Adriaan Van Wijngaarden, Barry J Mailloux, John EL Peck, Cornelis HA Koster, Charles Hodgson Lindsey, Michel Sintzoff, Lambert GLT Meertens, and Richard G Fisker.  Revised report on the algorithmic language ALGOL 68.  Springer Science & Business Media, 2012.
  * [75] Monica Lam, Ravi Sethi, Jeffrey D Ullman, and Alfred Aho.  Compilers: principles, techniques, and tools.  Pearson Education, 2006.

Supplemental Materials

In what follows we provide a series of appendices. In turn, these detail
proofs of theorems in the main body (Appx. A), provide an overview of related
prior techniques with performance comparisons (Appx. B), provide detailed
analysis of the non-obvious method for computing gadget cost (Appx. C),
provide a review of the major results of QSP, M-QSP, and QSVT (Appx. D),
provide analysis of _correction protocols_ (Appxs. E and F), cover some
caveats in the theory of functional approximation by polynomials (Appx. G),
compare certain concrete example gadgets for specific problems to their best
known counterpart using other quantum algorithms (Appx. H), discuss how
gadgets instantiate monadic functions and relate to functional programming
(gadget _semantics_ , Appxs. I.1 and I.2), and finally provide a formal
language for gadgets constituted by an attribute grammar (gadget _syntax_ ,
Appx. I.3).

##  Appendix A Proofs of main results

We begin by providing proofs of the main results of Sec. II. Note that
$\widetilde{\mathcal{O}}$ denotes scaling to leading order. In addition, when
using $\mathcal{O}$, we will often suppress scaling beyond leading and second-
order (i.e. given leading-order polynomial scaling in parameter $p$, we keep
$\log(p)$ terms and suppress terms of order $\log\log(p)$ and greater).

See II.1

###### Proof.

We will prove each of the complexities corresponding to the three different
methods for performing the correction of an $\varepsilon$-twisted embeddable
unitary. We will begin with the simplest case: the scenario where we are
provided access to ancilla qubits as well as controlled oracle access to $U$.

From Thm. E.1, we know that there exists a single-qubit protocol (effectuated
by the superoperator $\mathcal{E}$) making
$\zeta_{1}=\mathcal{O}(\delta^{-1}\log(\varepsilon_{1}^{-2}\delta^{-1/2}))$
black-box calls to the unitary $U^{\prime}$ which yields an
$\varepsilon_{1}$-approximation of $e^{i\varphi\sigma_{z}}$, assuming
$\cos(\theta)\in[-1+\delta,1-\delta]$. We then have

$||\mathcal{E}[U]-e^{i\varphi\sigma_{z}}||\leq||\mathcal{E}[U]-\mathcal{E}[U^{\prime}]||+||\mathcal{E}[U^{\prime}]-e^{i\varphi\sigma_{z}}||\leq||\Phi[U]-\Phi[U^{\prime}]||+\varepsilon_{1},$
(22)

where $\Phi$ is a QSP protocol. Due to Lem. D.4, we know that
$||\Phi[U]-\Phi[U^{\prime}]||\leq\zeta_{1}\nu$, implying that the overall
error is $\zeta_{1}\nu+\varepsilon_{1}$. Due to Cor. F.2.1, there exists a
protocol $\mathcal{R}$ making a single black-box call to
controlled-$\mathcal{E}[U]$ (which we have assumed we can access, as we have
controlled-$U$ access) and using an extra qubit, such that
$(\mathcal{R}\circ\mathcal{E})[U]$ will be an
$(\zeta_{1}\nu+\varepsilon_{1})$-approximation of
$e^{i\varphi/2}e^{i\varphi\sigma_{z}/2}$, with probability at least
$1-(2\zeta_{1}\nu+2\varepsilon_{1})$. It follows, in the case of success, that

$\displaystyle||(\mathcal{R}\circ\mathcal{E})[U]^{\dagger}U(\mathcal{R}\circ\mathcal{E})[U]-e^{i\theta\sigma_{x}}||$
$\displaystyle\leq||(\mathcal{R}\circ\mathcal{E})[U]^{\dagger}e^{i\varphi\sigma_{z}/2}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}(\mathcal{R}\circ\mathcal{E})[U]-e^{i\theta\sigma_{x}}||+\nu$
(23) $\displaystyle\leq
2||e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}(\mathcal{R}\circ\mathcal{E})[U]-e^{i\theta\sigma_{x}}||+\nu$
(24) $\displaystyle\leq
2||(\mathcal{R}\circ\mathcal{E})[U]-e^{i\varphi\sigma_{z}/2}||+\nu$ (25)
$\displaystyle\leq(2\zeta_{1}+1)\nu+2\varepsilon_{1},$ (26)

where we can drop the overall phases $e^{i\varphi/2}$ within the operator
norm, via cancellation (see Rem. F.4). Since the ancilla qubits can be re-used
with each non-nested action of $\mathcal{R}$ (see Rem. F.3), the overall
protocol will use two ancilla qubits, and makes $\zeta=2\zeta_{1}+1$ black-box
calls to $U$. Thus, setting $\varepsilon_{1}=\varepsilon/2$, so the
approximation error is $\zeta\nu+\varepsilon$, the success probability is
greater than $(1-(\zeta\nu+\varepsilon))^{2}$ (as $\mathcal{R}$ is called
twice), and
$\zeta=\mathcal{O}(\delta^{-1}\log(\varepsilon^{-2}\delta^{-1/2}))$ yields the
desired result.

In the case where we are provided ancillae, but do not have access _a priori_
to the signal oracles, we make use of the protocol of Thm. F.1 to get, from
$U$, an approximation of its controlled-variant. We then make use of the
previous protocol $\mathcal{R}$ to achieve an approximation of the desired
$\sigma_{z}$-square root. We call this composite protocol
$\mathcal{R}^{\prime}$. Because the first part of the protocol has the exact
same asymptotic complexity as the protocol $\mathcal{R}$, and is effectively
the implementation of two parallel QSP sequences interspersed by CSWAP gates,
the error analysis will proceed in exactly the same way as above.

Finally, from Thm. F.3, not that there exists a single-qubit protocol
$\mathcal{R}^{\prime\prime}$ making
$\zeta_{2}=\mathcal{O}(\gamma^{-2}\log(\varepsilon_{2}^{-2}\gamma^{-1/2}))$
black-box calls to $e^{i\varphi\sigma_{z}}$ such that
$\mathcal{R}^{\prime\prime}[e^{i\varphi\sigma_{z}}]$ is an
$\varepsilon_{2}$-approximation to $e^{i\varphi\sigma_{z}/2}$, assuming
$\cos(\varphi)\in[\gamma,\sqrt{1-\gamma^{2}}]$. Of course, since
$\mathcal{R}^{\prime\prime}$ is effectively a QSP protocol, we can once again
make use of Lem. D.4 to bound the accumulation of errors once again. We have

$\displaystyle||(\mathcal{R}^{\prime\prime}\circ\mathcal{E})[U]^{\dagger}U(\mathcal{R}^{\prime\prime}\circ\mathcal{E})[U]-e^{i\theta\sigma_{x}}||$
$\displaystyle\leq||(\mathcal{R}^{\prime\prime}\circ\mathcal{E})[U]^{\dagger}e^{i\varphi\sigma_{z}/2}e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}(\mathcal{R}^{\prime\prime}\circ\mathcal{E})[U]-e^{i\theta\sigma_{x}}||+\nu$
(27) $\displaystyle\leq
2||e^{i\theta\sigma_{x}}e^{-i\varphi\sigma_{z}/2}(\mathcal{R}^{\prime\prime}\circ\mathcal{E})[U]-e^{i\theta\sigma_{x}}||+\nu$
(28) $\displaystyle\leq
2||(\mathcal{R}^{\prime\prime}\circ\mathcal{E})[U]-e^{i\varphi\sigma_{z}/2}||+\nu$
(29) $\displaystyle\leq
2||\mathcal{R}^{\prime\prime}[e^{i\varphi\sigma_{z}}]-e^{i\varphi\sigma_{z}/2}||+2||\mathcal{R}^{\prime\prime}[e^{\varphi
i\sigma_{z}}]-\mathcal{R}^{\prime\prime}[\mathcal{E}[U]]||+\nu$ (30)
$\displaystyle\leq
2\varepsilon_{2}+2\zeta_{2}\varepsilon_{1}+(2\zeta_{2}\zeta_{1}+1)\nu$ (31)

Clearly, a total of $\zeta^{\prime}=2\zeta_{2}\zeta_{1}+1$ black-box calls are
made to $U$ throughout the entire protocol. We set
$\varepsilon_{2}=\varepsilon/4$ and
$\varepsilon_{1}=\varepsilon/4\zeta_{2}=\widetilde{\mathcal{O}}(\varepsilon\gamma^{2})$,
where we drop the log factor of $\log(\varepsilon^{-2}\gamma^{-1/2})^{-1}$ (as
this will only contribute a $\log\log$ factor when plugged into the protocol
depth upper-bound). Therefore,
$\zeta_{1}=\mathcal{O}(\delta^{-1}\log(\varepsilon^{-2}\gamma^{-4}\delta^{-1/2}))$,
and

$\zeta^{\prime}=2\zeta_{2}\zeta_{1}+1=\mathcal{O}\left(\frac{1}{\gamma^{2}\delta}\log^{2}\left(\frac{1}{\gamma^{4}\varepsilon^{2}\delta^{1/2}}\right)\right).$
(32)

The approximation error is then $\zeta^{\prime}\nu+\varepsilon$, and the proof
is complete. ∎

Method/Access model | Complexity | Ancillae |  $\cos(\theta)$-domain |  $\cos(\varphi)$-domain | Success
---|---|---|---|---|---
Ancillae / controlled oracles | $\widetilde{\mathcal{O}}(\delta^{-1}\log(\varepsilon^{-1}))$ | 1 | $[-1+\delta,1-\delta]$ | $[-1,1]$ | $1-\varepsilon$
No ancillae / un-controlled |  |  |  |  |
oracles | $\widetilde{\mathcal{O}}(\delta^{-1}\gamma^{-2}\log^{2}(\varepsilon^{-1}))$ | None | $[-1+\delta,1-\delta]$ | $[\gamma,\sqrt{1-\gamma^{2}}]$ | $1$
Ancillae / un-controlled |  |  |  |  |
oracles | $\widetilde{\mathcal{O}}(\delta^{-1}\log(\varepsilon^{-1}))$ | 2 | $[\delta,1-\delta]$ | $[-1,1]$ | $1-\varepsilon$
Table 1: Comparison of the resource costs of three correction procedures which
apply under different assumptions about the oracle access model.

With this result, the main theorem characterizing gadget correction follows
fairly immediately.

See II.1

###### Proof.

This follows immediately from invoking Lem. II.1 for each of the output
gadgets, enforcing the condition that
$\zeta\nu=\varepsilon\Rightarrow\nu=\varepsilon/\zeta=\widetilde{\mathcal{O}}(\varepsilon\delta)$
in the first and second cases, and
$\zeta\nu=\varepsilon\Rightarrow\nu=\widetilde{\mathcal{O}}(\delta\gamma^{2}\varepsilon)$
in the final case, so that the total approximation error in both cases is
$2\varepsilon=\mathcal{O}(\varepsilon)$. ∎

######  Remark A.1 (On the acceptable efficiency of correction protocols).

Lemma II.1 shows that, given an approximately embeddable unitary, the error
accumulated during its correction is (1) proportional to the error of the
input unitary and (2) the constant of proportionality is linear in the length
of the correction procedure. We clarify in what follows that this scaling is
not as poor as it appears, and connect this to natural but implicit
assumptions for protocols given in this work:

  1. (a)

Firstly, the error in the input approximately embeddable unitary ($\nu$ in
Lemma II.1) arises _only from previous correction protocols_ , and thus can be
suppressed by a factor of $\zeta$, for instance, by increasing the length of
the previous correction procedure by a factor only _logarithmic_ in $\zeta$
(noting the $\varepsilon$-dependence in Lemma II.1, and that the argument is
more subtle when corrections are changed). In other words, $\nu$ can be made
small quite easily, inheriting the rapid convergence of QSP polynomials to
desired smooth functions.

  2. (b)

Secondly, analogously to previous work on the self-composition of QSP and
general classical signal processing [27, 28, 26, 23, 22], this work considers
circuits comprising logarithmically-many protocol-nesting operations, and thus
only logarithmically-many uses of correction protocols in the length of a
given ‘base protocol.’ While such scaling is more difficult to define where
protocols of varying length are used, rather than where one protocol is
recursively self-composed, this statement will be true even if scaling is
taken with respect to the length of the longest ‘base protocol.’ Ultimately,
this restriction is equivalent to requiring that our composite protocols have
length _polynomial in the length of their smallest sub-protocols_.

  3. (c)

Taken together the (a) rapid convergence of polynomial approximation in QSP
and the (b) natural restriction to logarithmic-depth composite _gadgets_ (Def.
II.3; for now to be thought of as parallel circuits with the basic form of
QSP/M-QSP), means the ultimate length of protocols scales, at worst, inverse
polynomially in the desired output error.

While the precise cost of a specific composite gadget can be involved to
compute (Appx. C), and can change depending on properties of the achieved
functions it comprises (Rems. H.1 and H.2), we can assert that QSP-based
computations are _acceptable_ (in a colloquial sense) if their required length
scales only inverse-polynomially in the desired error. While this is worse
than the best case scenario of using QSP or M-QSP to approximate smooth
functions, it is no worse than the scaling appearing when approximating common
discontinuous functions. Note also this error is distinct from the error of
functional approximation within a standard QSP or M-QSP protocol, but is of
the same order, and can be independently manipulated in minimizing gadget
depth.

We are now able to discuss the cost associated with composing gadgets. First,
a minor result, showing the simple relationship between unitary approximations
and function approximations achieved with gadgets.

######  Lemma A.1.

Let $\mathfrak{G}$ be an $(a,b)$ gadget which achieves unitaries
$U_{k}^{\prime}$ which $\varepsilon$-approximate unitaries $V_{k}$ for
$k\in[b]$ over all $(x_{0},\dots,x_{a-1})\in\mathcal{D}$. Then $\mathfrak{G}$
achieves functions $f_{k}$ which $\varepsilon$-approximate functions
$g_{k}=\langle 0|V_{k}|0\rangle$ for $k\in[b]$ over all $(x_{0},\dots
x_{a-1})\in\mathcal{D}$.

###### Proof.

Note that $|f_{k}-g_{k}|=|\langle 0|U_{k}^{\prime}|0\rangle-\langle
0|V_{k}|0\rangle|=|\langle
0|U_{k}^{\prime}-V_{k}|0\rangle|\leq||U_{k}^{\prime}-V_{k}||\leq\varepsilon$.
∎

Figure 5: High-level breakdown of the correction protocol of Thm. II.1. We
depict multiple pipelines for preparing, given a gadget’s output leg which
embeds the polynomial transform $P$, a leg which embeds $P$ in the same way
but whose rotation axis is approximately fixed and known (denoted
$P^{\prime}$). Dotted boxes indicate substitution of the enclosed circuit as a
module into another circuit, and $\cong$ indicates circuits with approximately
identical action. Here (1) gives substitution into a QSP protocol, which
generates $V$ (an approximate $z$-rotation). Using a pair of Fredkin gates and
two additional qubits in fixed, known states, through (2) we can approximately
apply the square root of this $z$-rotation to a qubit of our choice by
creating approximate controlled-$V$ access using the pair of QSP protocols
parameterized by $\Phi_{0},\Phi_{1}$ as in Thm. F.1; here $C$ is a fixed,
known correction unitary. If a different access assumption is made (see Tab.
3), (2) can be skipped, as in (2a) one assumes either direct access to
controlled-$V$ per Cor. 72 of [9], or a domain restriction on the possible $V$
allows ancilla-free square roots to be taken. In (3) one conjugates the
original protocol $P$ (1a), which is precisely, through (4), what was desired
of $P^{\prime}$. Note both $W$ and $W^{\dagger}$ are preparable as gadget
outputs are obliviously invertible for all arguments: $ZPZ\equiv P^{\dagger}$.
Here boxes $\Phi,\Psi_{0},\Psi_{1}$ are in general different, controllable
$z$-rotations, and brackets indicate finite repetition of a block with
possibly different phases.

See III.1

###### Proof.

We must correct each of the gadget $\mathfrak{G}$’s $e$ outputs involved in
the interlink, via the protocol of Thm. II.1, before composition. The overall
complexity will simply amount to the cost of the corrective protocol,
multiplied by the total query complexity required to implement all of the
output legs of the atomic $(c,d)$ gadget involved in the interlink, given its
black-box use of input gadgets (a quantity upper-bounded by
$d\lvert\Xi\rvert_{\infty}$). Of course, this query complexity will often be
much lower, since the sequence of $\Xi$ will often only utilize a small number
of queries to input legs involved in the interlink, which are the only legs
which require correction.

Moreover, given that corrective protocols used in Thm. II.1 only have
logarithmic dependence on $\varepsilon$, and accumulate errors linearly in
circuit depth, making the transformation of
$\varepsilon\mapsto\varepsilon/\lvert\Xi\rvert_{\infty}$ introduce only
logarithmic factors in $\lvert\Xi\rvert_{\infty}$. This implies that we
require the given $\widetilde{\mathcal{O}}(d|\Xi|_{\infty}\zeta)$ query-
complexity (for $\zeta$ of Thm. II.1) to $\varepsilon$-achieve all of the
unitaries of the M-QSP protocols/atomic gadget achieving functions
$g_{0},\dots,g_{d-1}$, composed with the signal operators
$e^{i\arccos(f_{1}(x))\sigma_{x}},\dots,e^{i\arccos(f_{b-1}(x))\sigma_{x}}$,
for $x$ over a prescribed domain (depending on the correction protocol), with
respect to the interlink. Lem. A.1 implies that the composite gadget will
$\varepsilon$-approximate the desired function composition, $H$. ∎

######  Remark A.2 (Counting gadget interlinks).

Note that given $\mathfrak{G}$ and $(\Xi,S)$ as $(a,b)$ and $(c,d)$ gadgets
respectively, then there are

$L_{(a,b),(c,d)}\equiv\sum_{e=0}^{\min{(b,c)}}\binom{b}{e}\binom{c}{e}(e!)$
(33)

valid interlinks between these gadgets, and $\binom{b}{e}\binom{c}{e}(e!)$
interlinks which induce the same type transformation, but which may not in
general be equivalent.

######  Definition A.1 (Augmenting, eliding, pinning, and permuting gadgets).

There exist a number of simple operations over gadgets that take only one
argument, and we discuss them here, terming them _augmentation_ , _elision_ ,
_pinning_ , and _permutation_. Graphically, these correspond to adding or
removing out-going legs, fixing in-going legs, or permuting out-going legs in
the picture discussed in Fig. 9. These have the following types

$\displaystyle(a,b)$
$\displaystyle\rightarrow(a,b+c),\quad\text{augmentation},$ (34)
$\displaystyle(a,b)$ $\displaystyle\rightarrow(a,b-c),\quad\text{elision},$
(35) $\displaystyle(a,b)$
$\displaystyle\rightarrow(a-c,b),\quad\text{pinning},$ (36)
$\displaystyle(a,b)$
$\displaystyle\rightarrow\mathmakebox[0pt][l]{(a,b),}\phantom{(a,b-c)\;\,}\quad\text{permutation}.$
(37)

Given an $(a,b)$ gadget that achieves
$\\{f_{0}(x_{0},\cdots,x_{a-1}),f_{1}(x_{0},\cdots,x_{a-1}),\dots,f_{b-1}(x_{0},\cdots,x_{a-1})\\}$,
the result of the above actions are gadgets which achieve the following:

$\displaystyle\bigcup_{k\in
B^{\prime}\hphantom{{}^{\prime}}}f_{k}(x_{0},\cdots,x_{a-1}),$ (38)
$\displaystyle\bigcup_{k\in B^{\prime\prime}}f_{k}(x_{0},\cdots,x_{a-1}),$
(39) $\displaystyle\bigcup_{k\in
B\hphantom{{}^{\prime}\prime}}f^{\prime}_{k}(x_{j_{0}},\cdots,x_{j_{a-c-1}}),$
(40) $\displaystyle\bigcup_{k\in
B\hphantom{{}^{\prime}\prime}}f_{W(k)}(x_{0},\cdots,x_{a-1}),$ (41)

where $W(k)$ is the action of a permutation over $[b]$ on the index of an out-
going leg of the gadget, $f_{k}^{\prime}$ is the function $f_{k}$ with some
size-$c$ subset of its input arguments fixed, $B^{\prime}$ is a list
containing $[b]$ in order, possibly interspersed with repeated elements from
$[b]$, and $B^{\prime\prime}$ is an ordered sublist of $B$. We can again
simply depict these operators graphically:

where $M$ is chosen here to be a $(2,2)$ gadget, whose legs can be permuted,
elided, pinned, or augmented, resulting in $(2,2)$, $(2,1)$, $(1,2)$, and
$(2,3)$ gadgets respectively. Here $N$ is some superoperator which returns a
fixed unitary (often chosen by the computing party).

The cost of an operator over a gadget is most clearly expressed in the number
of queries to the subsidiary gadget(s) (as their outputs are used in a black-
box way), as well as any additional space required. Given an interlink (Def.
III.1) defined by $\mathfrak{I}\equiv(B,C,W)$, it is evident that the
permutation requires at most $\mathcal{O}(|B|)$ two-qubit gates. Moreover, for
each of the $|B|$ out-going legs, the assumptions of Thm. II.1 do not
distinguish between their corrections, meaning that the same superoperator is
applied to each, with the same asymptotic query complexity. This induces a
cost dependent only on the out-going leg number and the maximum length among
sub-components of the outer gadget. For augmentations (Def. A.1) of size $c$,
a total of $c$ calls to the first gadget are necessary and sufficient (with
additional space linear in $c$), while elisions and pinnings of size $c$
require only a single call, and no additional space.

To conclude the proofs of the main results, we revisit the equivalence
theorem, Thm. III.2.

See III.2

###### Proof.

To construct the desired polynomial, we will perform an $m$-fold composition
of atomic gadgets, each of which have had the correction procedure applied to
their output legs. We are able to bound the accumulated error within the
gadget via Thm. C.2, and we are able to guarantee that the desired polynomial
is achieved to $\varepsilon$-accuracy via Thm. III.1. Since each gadget being
considered is atomic and achieves polynomial is the variables
$x_{1},\dots,x_{n}$ (it could, of course, be constant in some of these
variables), each gadget can have at most $n$ input legs. Thus, we think of
each interlink $\mathfrak{I}_{k}$ as being between two sets of _precisely_ $n$
legs, where the action of a gadget on some of these legs may merely be the
identity. This viewpoint, while leading to sub-optimal scaling in particular
cases when interlinks are sparse, will simplify the proof of this theorem.

Let $\mathfrak{G}^{(k)}$ be the gadget $\nu$-achieving polynomial $P^{(k)}$,
with the correction procedure appended to the output legs. For the sake of
simplicity, we are using the correction procedure which requires ancilla
qubits, so there is no concern about half-twisted embedability. It follows
that to implement a single output leg of this gadget on $\mathcal{D}_{k}$
requires circuit depth
$\widetilde{O}(d_{k}\delta^{-1}\text{polylog}(\nu^{-1}))$, where
$d_{k}=\max_{j}\deg(P^{(k)}_{j})$ is the depth of the uncorrected gadget
achieving $P^{(k)}$ (Thm. II.1). Because each of the gadgets
$\mathfrak{G}^{(k)}$ has $\nu$-embeddable output, they can be interlinked in a
way such that the polynomials will (approximately) compose as expected. In
particular, we know that $\mathfrak{G}^{(k)}$ will $\nu$-approximate the
unitary function $\mathfrak{F}^{(k)}$ with

$\mathfrak{F}^{(k)}\left[e^{i\arccos(x_{0})\sigma_{x}},\dots,e^{i\arccos(x_{n})\sigma_{x}}\right]=\left(e^{i\arccos(P^{(k)}_{1}(x_{1},\dots,x_{n}))\sigma_{x}},\dots,e^{i\arccos(P^{(k)}_{n}(x_{1},\dots,x_{n}))\sigma_{x}}\right)$
(42)

for $x\in\mathcal{D}_{k}$. Thus, by Thm. C.2, it follows that the error
between $\mathfrak{F}$: the composition of all the $\mathfrak{F}^{(k)}$ and
the function achieved by $\mathfrak{G}$: the gadget which is a full interlink
of the sequence of $\mathfrak{G}^{(k)}$ is given by

$\left|\left|\mathfrak{G}\left[e^{i\arccos(x_{0})\sigma_{x}},\dots,e^{i\arccos(x_{n})\sigma_{x}}\right]-\mathfrak{F}\left[e^{i\arccos(x_{0})\sigma_{x}},\dots,e^{i\arccos(x_{n})\sigma_{x}}\right]\right|\right|\leq\displaystyle\sum_{k=-1}^{m-1}v_{\nu}^{T}\displaystyle\prod_{k<\ell\leq
m-1}C^{(\ell)}$ (43)

where $C^{(\ell)}$ is the cost matrix of the $\ell$-th gadget in the
composition. Note that each of the columns of $C^{(\ell)}$ sum to some
$d_{\ell}^{\prime}=\widetilde{O}(d_{\ell}\text{polylog}(\nu^{-1}))$, and each
entry of $v_{\nu}$ is equal to $\nu$. Therefore,

$\displaystyle\sum_{k=-1}^{m-1}v_{\nu}^{T}\displaystyle\prod_{k<\ell\leq
m-1}C^{(\ell)}=\widetilde{\mathcal{O}}\left(\nu d_{1}\cdots
d_{m}\left(K\delta^{-1}\text{polylog}(\nu^{-1})\right)^{m}\right)$ (44)

for some constant $K$. Note that $D=d_{1}\cdots d_{m}$. In addition, since
$m=\mathcal{O}(\log(D))$,

$\widetilde{O}\left((K^{\prime}\delta^{-1}\text{polylog}(\nu^{-1}))^{m}\right)=\mathcal{O}\left(\exp\left(K^{\prime\prime}\log(D)\log\log(\nu^{-1})\right)\right),$
(45)

and thus an error of $\nu$ on an input generates an error of the asymptotic
form $\widetilde{\mathcal{O}}(\nu D^{K^{\prime\prime}\log{\log{\nu^{-1}}}})$
on an output. If we want to achieve error at maximum some desired
$\varepsilon$, one then finds that the required initial $\nu$ must satisfy the
implicit equation

$-\log{\nu^{-1}}+K^{\prime\prime}\log{\log{\nu^{-1}}}\log{D}=-\log{\varepsilon^{-1}},$
(46)

which can be rearranged into the suggestive form

$-e^{\log{\log{\nu^{-1}}}}+K^{\prime\prime}\log{D}\log{\log{\nu^{-1}}}=-\log{\varepsilon^{-1}}$
(47)

This permits us to express $\log{\log{\nu^{-1}}}$ in terms of the Lambert W
function (taking the $W_{-1}$ branch, which is valid for our intended range of
small $\varepsilon$), namely

$\log{\log{\nu^{-1}}}=-\frac{\log{\varepsilon^{-1}}}{K^{\prime\prime}\log{D}}-W_{-1}\left(-\frac{e^{-\log{\varepsilon^{-1}}/K^{\prime\prime}\log{D}}}{K^{\prime\prime}\log{D}}\right).$
(48)

For small $\varepsilon$ the the Lambert W function has simple behavior,
approaching $\log{-x}$ for small argument $x$, meaning that the whole
expression simplifies to $\log{\log{\nu^{-1}}}=\log{K^{\prime\prime}D}$ at
leading order. As such we see that for very small $\varepsilon$,
$\log\nu^{-1}$ grows only as $K^{\prime\prime}D$; as this is the only
multiplicative factor from the precision $\nu$ entering into the complexity of
each sub-gadget as constructed, we see that their length is not made to grow
superpolynomially in the logarithm of $\varepsilon^{-1}$. This yields the
desired
$\widetilde{\mathcal{O}}(\text{poly}(D)\,\text{polylog}(\varepsilon^{-1}))$
scaling. ∎

##  Appendix B Related prior techniques and performance comparisons

The resource requirements for enacting a multivariable polynomial
transformation on the mutual singular values of a series of commuting block
encodings requires some scaffolding to analyze, which we present here. We will
call $d$ the (generalized) functional degree of the achieved multivariable
polynomial, $r$ the number of variables within this transform, and $s$ is the
number of additional qubits used for the original block encoding(s). In
compressing these values to single scalars, we usually mean the maximum over
an implicit tuple, e.g., of the degree of the desired polynomial in each
variable, or the required auxiliary space of each block-encoded input. Note
that the generalized degree of the implemented function $d$ generally scales
as the polylogarithm of the inverse uniform approximation error $\varepsilon$
to some idealized continuous function. We will suppress this factor in the
discussion below, though one is free to substitute
$\text{poly}{(d)}\text{polylog}{(\varepsilon^{-1})}$ for $\text{poly}{(d)}$
where it appears, if one is trying to achieve only a polynomial approximation
to a desired, ideal functional transform. We also note that $\delta$ is
sometimes introduced to bound uniform approximation away from regions in which
the function has an $\mathcal{O}(1)$ jump discontinuity, or a hard boundary
condition; for this,
$\text{poly}{(d)}\text{polylog}{(\varepsilon^{-1})}\text{poly}(\delta^{-1})$
can be substituted in the same way.

We give the defining complexities of multivariable quantum eigenvalue
transformation (M-QET), which relies on techniques from linear combination of
unitaries (LCU) based methods, from [34]. Their work does not consider
successive composition of protocols; moreover works which do consider such
compositions, e.g., [20], do so only only in the single-variable setting, and
only in the case of recursive function application. In this way our work is
not directly comparable to either of these methods, as our correction
procedure (Thm. II.1) confers an additional ability to not just compose
functions or block encode multivariable polynomial transforms, but to link and
partially-compose gadgets achieving such transforms.

Consequently, when we compare our methods to previous works below, we are
doing so on the level of individual multivariable quantum eigenvalue
transforms (a restriction of QSVT to normal operators). On this front both our
work and [34] demonstrate near arbitrary block encodings of multivariable
polynomials in commuting operators, allowing for general comparison.

Namely, we consider the resource costs of the basic units of our work: gadgets
(Def. II.3), each of whose out-going legs yield an embeddable unitary which,
if the gadget was built from the composition of atomic gadgets, can be seen to
achieve a given (approximation to) a multivariable polynomial transform of the
input leg variables. Viewed in this way our work approaches the problem of
multivariable polynomial block encodings from a starkly different direction
than [34]. Rather than considering the efficiency of an algorithmic method
that achieves arbitrary functional block encodings, we investigate the closure
of a highly-resource-efficient _class of subroutines_ under _block encoding-
preserving_ superoperators, and show that we can achieve unexpectedly
expressive multivariable block encodings with improved resource scaling, i.e.,
without the space use and post-selection requirements of LCU. In this way, our
methods achieve a synthesis of the aims of [34] and [20], albeit using tools
from M-QSP [29] language from work on semantic embedding [19], and
abstractions from the classical theory of functional programming languages.
The ultimate result is significant savings in space complexity and success
probability at the cost of immediate generality of embeddable functions. It is
also important to observe that, just as in initial comparisons between LCU and
QSVT methods for Hamiltonian simulation [33, 7, 9], the _query-complexity’s_
dependence on polynomial degree and approximation error are both within
polynomial of optimal already. Our benefit is however not just tied to the
query complexity, but in the modular re-use of pre-computed gadgets,
substantial auxiliary space savings, and ability to leverage the powerful
functional-analytic results underlying the quite mature theory of QSP-based
algorithms.

Comparisons of our methods along major resource axes in terms of $d,r,s$ are
made in Table 2. We also emphasize that our methods are not algorithmically
incompatible with those of [34], just resource incomparable. I.e., our gadgets
are agnostic to the circuit having constructed a given block encoding used as
input, and thus similar constructions to those of [34] can furnish immediately
applicable upper bounds for certain multivariable eigenvalue transforms
(following amplifying into the proper block), and in turn be fed into our
gadgets if desired. In this way, we hope multiple methods for efficient block
encoding can mutually inform one another, and settle sophisticated questions
of the minimum-required space and query complexity to achieve certain
(approximations to) desired functional transforms.

Method | Query complexity | Space complexity | Subnormalization
---|---|---|---
[34] | $\mathcal{O}(\text{poly}{(r)}d^{\text{poly}(r)})$ | $\mathcal{O}(\text{poly}{(r)}[\text{poly}{(d)}+\text{poly}{(s)}])$ | $\mathcal{O}(\text{poly}{(d)}^{\text{poly}{(r)}})$
This work | $\mathcal{O}(d)$ | $\mathcal{O}(s+c)$ | $\mathcal{O}(1)$
Table 2: Asymptotic query and space complexity, as well as block encoding sub-
normalization factor for this work’s multivariable block encodings and those
of other methods based on LCU methods. Note that the $\varepsilon,\delta$
dependencies are here suppressed, but are in general identical between methods
[9], and that the polynomial scaling described for LCU methods are often low-
degree or linear in practice. Here subnormalization relates roughly linearly
to the number of runs required to measure the proper subblock of the block
encoding. Note also that this comparison does not consider the new ability,
proposed in this paper, to curry gadgets comprising M-QSP protocols in a
semantically clear way. Note that the variable $c$ is a constant that can be
zero for half-twisted-embeddable protocols (Def. II.2).

Beyond query and space complexity, we take some time to discuss additional
benefits to our method in relation to observations made by previous works. One
of these relates to the fact that, if a gadget uses a discrete set of phases,
and a composite computation is built from repeated interlinks of that gadget
with itself (or some other finite set of gadgets), then the phases used in the
resulting circuit necessarily come from the union of phases used by the
constituting gadgets. As discussed by [20], there exist settings [57] in which
the number of distinct QSP phases used in a protocol defines the complexity of
certain error-correction procedures on that protocol. It is an intriguing open
question whether the limited distinct phase character possible with our
methods (already an experimental advantage) can be exploited in the same way
as those of the single variable setting [57]. Moreover, even if a variety of
gadgets are used, those most often repeated, or prone to error, can be
selectively optimized, given their ubiquity, and applied wherever given our
method’s preservation of gadget contiguity as subroutines.

As a concluding note, we repeat that the comparison made here cannot be
entirely fair, due to the different goals of the previous works considered and
our own. We assume, within Table 2, that a given multivariable polynomial
transformation _can_ be reached by both methods, and then show that the query
complexities, space complexities, and subnormalization factors differ.
Nevertheless, the transforms possible with our method are sufficiently
expressive to warrant comparison within this implied overlap, and moreover, a
wealth of results exist in classical signal processing showing the success of
considering composite protocols comprising multiple uses of inter-related and
simpler sub-filters [27, 28].

######  Remark B.1 (On the general inequivalence composite gadgets).

As discussed previously, as well as in the caption of Tab. 2, there exist non-
obvious conditions on polynomial transforms in M-QSP which effect the space
and query complexity of the correction procedures used to compose gadgets.
This is in tandem with the (approximate) polynomial decomposition theorems
[44, 42, 43, 39] specifying how to break a composite polynomial into smaller
sub-protocols combined through composition. Both of these subtleties to
understanding the resource requirements of achieving a given transform are
further confounded by the non-trivial inequivalence of gadgets which
apparently achieve the same transform. For instance, consider the simple
$(1,1)$ product gadget (Ex. IV.3, with a pre-applied square root) which
outputs $x_{0}^{2}$, as well as the $(1,1)$ gadget which squares an oracle,
achieving $2x_{0}^{2}-1$, and averages it with the $(1,1)$ trivial gadget
achieving $1$ (using the $(2,1)$ gadget of Ex. IV.6) to achieve the same
$x_{0}^{2}$. The averaging gadget, by merit of using the product gadget as a
subroutine, has strictly higher query complexity, complicating the question of
determining the minimal composition of gadgets achieving a given function.
Evidently, the resources required for a given functional transform (or its
approximate version) are sensitive to small changes in objective or
constitutive subroutines.

The relative incomparability of our work and those of others extends further,
considering that our work explicitly characterizes the cost of gadget
composition (Sec. C), in direct generalization of techniques discussed in [20,
29], which considered the simpler single-variable setting. Modular filter
design, from which our work draws some inspiration, is classically well-
developed, as mentioned, and undergirded by a correspondingly rich theory of
polynomial decomposition theorems, whose approximate forms and associated
algorithms [44, 43, 39], can be used to approach the generality offered [34].
By focusing on smaller, modular, and well-characterized subsets of possible
transforms, algorithmic clarity is improved, automatic optimization and
program verification becomes possible, and experimental realizations become
simpler.

##  Appendix C On computing the cost of gadgets

General gadgets are composite objects with multiple inputs and outputs, and
consequently defining their implementation cost requires some bookkeeping.
Here, we define basic objects associated with this cost, such that the cost of
compositions of (possibly composite) gadgets is simple to compute.

######  Definition C.1 (Gadget cost matrix).

Let $\mathfrak{G}$ be an $(m,n)$ gadget. Then there is a $m\times n$ _cost
matrix_ $C$ associated with $\mathfrak{G}$

(49)

where element $c_{jk}$ indicates the required number of queries to the input
leg encoding $x_{j}$ to achieve an output leg encoding $x_{k}^{\prime}$ up to
some precision $\varepsilon_{k}\geq 0$ for $x_{j},j\in[n]$ in a particular
domain $\mathcal{D}_{j}$.

It is not so difficult to determine these cost matrices in common cases. For
instance, let $(\Xi,S)$ define an atomic gadget $\mathfrak{G}$; then the cost
matrix $C$ of $\mathfrak{G}$ has elements $c_{jk}=S_{jk}$, where $S_{jk}$ is
the number of occurrences of $j$ in the $k$-th element of $S$. Furthermore, if
one considers the correction procedure defined previously, then the cost
matrix of a corrected gadget has each $c_{jk}$ for the non-corrected gadget
multiplied by a factor $\zeta$ determined by Thm. II.1, for a desired
precision $\varepsilon$ to an embeddable output, over a desired range. For our
purposes, we care primarily about the asymptotic behavior of elements of the
cost matrix, and will thus treat them up to logarithmic factors. Cost matrices
provide a clean formalism in which we can compute the cost of implementing
composite gadgets.

######  Lemma C.1 (Cost matrix for a composite gadget).

We compute the cost matrix of a composite gadget. Let $\mathfrak{G}$ be an
$(a,b)$ gadget and $\mathfrak{G}^{\prime}$ a $(c,d)$ gadget. Given an
interlink $\mathfrak{I}\equiv(\tilde{B},\tilde{C},W)$ (Def. III.1, where
tildes have been added to prevent variable overloading), we know that the
resulting gadget has type $(a+c-e,b+d-e)$ where
$e\equiv|\tilde{B}|=|\tilde{C}|$ is the number of contracted legs. We can
define block versions of the cost matrices $C,C^{\prime}$

$C=\left[\begin{array}[]{c|c}A&A^{\prime}\end{array}\right],\quad
C^{\prime}=\left[\begin{array}[]{c}B\\\ \hline\cr
B^{\prime}\end{array}\right],$ (50)

where $A$ is $a\times e$, $A^{\prime}$ is $a\times(b-e)$, $B$ is $e\times d$,
and $B^{\prime}$ is $(c-e)\times d$; this will result in $C^{\prime\prime}$ as
defined below as $(a+c-e)\times(d+b-e)$, as expected. Note that input and
output variables have been permuted such that $A,B$ encompass the marked
subsets $\tilde{B},\tilde{C}$ of the interlink. The block version of the cost
matrix $C^{\prime\prime}$ for the composition according to the interlink
$\mathfrak{I}$ can then be simply defined in terms of $C,C^{\prime}$:

$C^{\prime\prime}=\left[\begin{array}[]{c | c}W(A)B&A^{\prime}\\\ \hline\cr B^{\prime}&0\end{array}\right].$ (51)

Here $W$, from the interlink, possibly permutes the columns of $A$, and
$W(A)B$ is the standard matrix product between $W(A)$ and $B$. The bottom
right block is all zeros. Note that in the case that $\mathfrak{G}^{\prime}$
is an atomic gadget, the cost matrix $C^{\prime}$ can be explicitly computed
as discussed previous to this lemma.

It is apparent that the general cost matrix of a series of interlinked gadgets
can be quite complex, with elements that can grow quickly in the number of
compositions. It follows that in the generic case, using cost matrices to
determine the required input-leg precision to achieve a desired output-leg
precision is a task very particular to individual gadget networks. However,
certain generalizations can be made, provided a gadget is of a particular
form. To conclude this section, we present a large class of gadgets for which
the cost matrix formalism allows computation of accumulating errors upon
iterated, complete gadget composition to go forward easily.

######  Definition C.2 (Circuit gadget).

Let an $(a,b)$ gadget $\mathfrak{G}$ be a _circuit gadget_ if it achieves
unitaries $U_{k}^{\prime}$ via mapping input unitaries $U_{k}$ to an $m$-qubit
quantum circuit, where the unitary $U_{k}^{\prime}$ is achieved via
$(c_{0k},\dots,c_{(a-1)k})$ (the $k$-th column of a cost matrix) queries to
$(U_{0},\dots,U_{a-1})$ on any of the $m$ qubits, interspersed with fixed
$m$-qubit unitaries.

Clearly, antisymmetric atomic gadgets are a particular type of circuit gadget.
There is a simple upper-bound on the error accumulated within circuit gadgets.

######  Theorem C.1 (Linear error accumulation in circuit gadgets).

Suppose $\mathfrak{G}$ is an $(a,b)$ circuit gadget. In addition, suppose
$V_{k}$ and $V^{\prime}_{k}$ are sets of unitaries such that
$||V_{k}-V^{\prime}_{k}||\leq\varepsilon_{k}$, for each $k\in[a]$. Then the
output error of the $k$-th output unitary achieved by the gadget can be upper-
bounded as

$||\mathfrak{G}[V_{0},\dots,V_{a-1}]_{k}-\mathfrak{G}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]_{k}||\leq\displaystyle\sum_{j=0}^{a-1}c_{jk}\varepsilon_{j}=v_{\varepsilon}^{T}Ce_{k}$
(52)

where $v_{\varepsilon}=(\varepsilon_{0},\dots,\varepsilon_{a-1})$ and $e_{k}$
is the $k$-th standard basis vector.

###### Proof.

By definition of the circuit gadget, we can write

$\mathfrak{G}[V_{0},\dots,V_{a-1}]_{k}=W_{0}\displaystyle\prod_{j=1}^{M}V_{s_{j}}W_{j}$
(53)

for some length-$M$ sequence $s\in[b]^{\times M}$, where $M=\sum_{j}C_{jk}$
(the total number of queries to input oracles characterizing the $k$-th output
leg), and each $W_{j}$ is a fixed $M$-qubit unitary. It follows that we can
bound the difference of gadget actions via a telescoping series,

$\displaystyle\left|\left|\mathfrak{G}[V_{0},\dots,V_{a-1}]_{k}-\mathfrak{G}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]_{k}\right|\right|$
$\displaystyle=\left|\left|W_{0}\displaystyle\prod_{j=1}^{M}V_{s_{j}}W_{j}-W_{0}\displaystyle\prod_{j=1}^{M}V^{\prime}_{s_{j}}W_{j}\right|\right|$
$\displaystyle=\left|\left|\displaystyle\sum_{i=1}^{M}\left[\displaystyle\prod_{j<i}V_{s_{j}}W_{j}\right](V_{s_{i}}W_{i}-V^{\prime}_{s_{i}}W_{i})\left[\displaystyle\prod_{j>i}V^{\prime}_{s_{j}}W_{j}\right]\right|\right|$
$\displaystyle\leq\displaystyle\sum_{i=1}^{M}\left|\left|V_{s_{i}}W_{i}-V^{\prime}_{s_{i}}W_{i}\right|\right|$
$\displaystyle=\displaystyle\sum_{i=1}^{M}||V_{s_{i}}-V^{\prime}_{s_{i}}||\leq\displaystyle\sum_{j=1}^{a-1}C_{jk}\varepsilon_{j}=v_{\varepsilon}^{T}Ce_{k},$
(54)

and the proof is complete. ∎

In general, in a sequence of gadget compositions, there are two sources of
error: error in the unitaries inputted to a particular gadget, and error due
to the imperfections in the gadget protocol itself. Both types of error can be
understood in the the following results. First, consider what is essentially a
corollary of the previous theorem.

######  Corollary C.1.1 (Output error in circuit gadgets).

Let $\mathfrak{G}$ be an $(a,b)$ circuit gadget with cost matrix $C$ which
achieves, in its $j$-th leg, an $\varepsilon^{\prime}_{j}$-approximation of
the function $\mathfrak{F}_{j}$, mapping $a$ individual unitaries to a single
unitary, over the domain $\mathcal{D}$, so for
$W_{0},\dots,W_{a-1}\in\mathcal{D}$,

$\left|\left|\mathfrak{G}[W_{0},\dots,W_{a-1}]_{j}-\mathfrak{F}_{j}[W_{0},\dots,W_{a-1}]\right|\right|\leq\varepsilon^{\prime}_{j}.$
(55)

for each $j$. Then, given sets of unitaries $V_{0},\dots,V_{a-1}$ and
$V^{\prime}_{0},\dots,V_{a-1}^{\prime}$ for which
$||V_{k}-V^{\prime}_{k}||\leq\varepsilon_{k}$ for $k\in[a]$ with
$V^{\prime}_{k}\in\mathcal{D}$, $\mathfrak{G}[V_{0},\dots,V_{a-1}]_{j}$, for
all $j\in[b]$,
$(v_{\varepsilon}^{T}Ce_{j}+\varepsilon^{\prime}_{j})$-approximately achieves
$\mathfrak{F}_{j}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]$, where
$v_{\varepsilon}=(\varepsilon_{0},\dots,\varepsilon_{a-1})$.

###### Proof.

Via Thm. C.1,
$||\mathfrak{G}[V_{0},\dots,V_{a-1}]_{j}-\mathfrak{G}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]_{j}||\leq
v_{\varepsilon}Ce_{j}$. Then, from a triangle inequality,

$||\mathfrak{G}[V_{0},\dots,V_{a-1}]_{j}-\mathfrak{F}_{j}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]||\leq||\mathfrak{G}[V_{0},\dots,V_{a-1}]_{j}-\mathfrak{G}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]_{j}||\\\
+||\mathfrak{G}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]_{j}-\mathfrak{F}_{j}[V^{\prime}_{0},\dots,V^{\prime}_{a-1}]||\leq
v_{\varepsilon}Ce_{j}+\varepsilon^{\prime}_{j},$ (56)

which completes the proof. ∎

Immediately, we are able to prove more sophisticated results about the error
accumulation in $n$-fold gadget compositions.

######  Theorem C.2 (Error in $n$-fold composition of circuit gadgets).

Let $\mathfrak{G}^{(k)}$ be $(a_{k},a_{k+1})$ circuit gadgets for $k$ ranging
from $0$ to $n-1$ with cost matrices $C^{(k)}$. Let $\mathfrak{G}$ be the
circuit gadget obtained from performing full composition of gadget legs,
$\mathfrak{G}=\mathfrak{G}^{(n-1)}\circ\cdots\circ\mathfrak{G}^{(0)}$. Suppose
the gadget $\mathfrak{G}^{(k)}$ achieves, in its $j$-th leg, an
$\varepsilon^{(k)}_{j}$-approximation of the unitary-valued function
$\mathfrak{F}_{j}^{(k)}$ over the domain $\mathcal{D}^{(k)}$. This is to say
that for all $W_{0},\dots,W_{a_{k}-1}\in\mathcal{D}^{(k)}$,