Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time
Computability of Quantum Functions111A preliminary report [29] has appeared
under a different title in the Proceedings of the 28th International
Conference on Logic, Language, Information, and Computation (WoLLIC 2022),
Iaşi, Romania, September 20–23, 2022, Lecture Notes in Computer Science, vol.
13468, pp. 88–104, Springer, 2022.

Tomoyuki Yamakami222Present Affiliation: Faculty of Engineering, University of
Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan

###### Abstract

Quantum computing has been studied over the past four decades based on two
computational models of quantum circuits and quantum Turing machines. To
capture quantum polynomial-time computability, a new recursion-theoretic
approach was taken lately by Yamakami [J. Symb. Logic 80, pp. 1546–1587, 2020]
by way of recursion schematic definitions, which constitute six initial
quantum functions and three construction schemes of composition, branching,
and multi-qubit quantum recursion. By taking a similar approach, we look into
quantum logarithmic-time computability and further explore the expressing
power of elementary schemes designed for such quantum computation. In
particular, we introduce an elementary form of the quantum recursion, called
the fast quantum recursion and formulate EQS (elementary quantum schemes) of
“elementary” quantum functions. This class EQS captures exactly quantum
logarithmic-time computability, represented by BQPOLYLOGTIME. We also
demonstrate the separation of BQPOLYLOGTIME from NLOGTIME and PPOLYLOGTIME. As
a natural extension of EQS, we further consider an algorithmic procedural
scheme that implements the well-known divide-and-conquer strategy. This
divide-and-conquer scheme helps compute the parity function but the scheme
cannot be realized within our system EQS.

Keywords: recursion schematic definition, quantum Turing machine, fast quantum
recursion, quantum logarithmic-time computability, divide-and-conquer strategy

##  1 Background, Motivations, and Challenges

We provide a quick overview of this work from its background to challenging
questions to tackle.

###  1.1 Recursion Schematic Definitions That Capture Quantum Computability

Over the four decades, the study of quantum computing has made a significant
progress in both theory and practice. Quantum computing is one of the most
anticipated nature-inspired computing paradigms today because it relies on the
principle of quantum mechanics, which is assumed to govern nature. The core of
quantum computing is an exquisite handling of _superpositions_ , which realize
massive quantum “parallelism”, and _entanglement_ , which binds multiple
quantum bits (or qubits, for short) with no direct contact, of quantum states.
Early models of quantum computation were proposed by Benioff [5], Deutsch [9,
10], and Yao [31] as quantum analogues of Turing machines and Boolean
circuits. Those models have been used in a theoretical study of quantum
computing in the area of computational complexity theory since their
introduction. The quantum Turing machine (QTM) model, which is a natural
quantum extension of the classical Turing machine (TM) model, has successfully
served for decades as a basis to theoretical aspects of computer science. The
basic formulation of the QTM model333Bernstein and Vazirani discussed only
single-tape QTMs. The multiple-tape model of QTMs was distinctly discussed in
[24, 26]. The foundation of QTMs was also studied in [18, 19]. used today
attributes to Bernstein and Vazirani [6]. QTMs provide a blueprint of
algorithmic procedures by describing how to transform each superposition of
configurations of the machines. There have been other computational models
proposed to capture different aspects of quantum computing, including a
(black-box) query model.

A _recursion schematic approach_ has been a recent incentive for the full
characterization of the notion of quantum polynomial-time computability [27],
which can be seen as a quantum extension of deterministic polynomial-time
computability. The primary purpose of taking such an exceptional approach
toward quantum computability stems from a successful development of recursion
theory (or recursive function theory) for classical computability. Earlier,
Peano, Herbrand, Gödel, and Kleene [14, 15] all made significant contributions
to paving a straight road to a coherent study of computability and
decidability from a purely logical aspect (see, e.g., [21] for further
references therein). In this theory, recursive functions are formulated in the
following simple “schematic” way. (i) We begin with a few initial functions.
(ii) We sequentially build more complicated functions by applying a small set
of construction schemes to the already-built functions. The description of how
to construct a recursive function actually serves as a blueprint of the
function, which resembles like a “computer program” of the modern times in
such a way that each construction scheme is a command line of a computer
program. Hence, a schematic definition itself may be viewed as a high-level
programming language by which we can render a computer program that describes
the movement of any recursive function. As the benefit of the use of such a
schematic definition, when we express a target function as a series of
schemes, the “size” of this series can serve as a “descriptional complexity
measure” of the function. This has lead to a fully enriched study of the
descriptive complexity of functions. This schematic approach sharply contrasts
the one based on Turing machines as well as Boolean circuit families to
formulate the recursive functions. A similar approach taken in [27] aims at
capturing the polynomial-time computability of _quantum functions_ ,444This
notion should be distinguished from the same terminology used in [26], where
“quantum functions” mean mappings from binary strings to acceptance
probabilities of QTMs. each of which maps a finite-dimensional Hilbert space
to itself, in place of the aforementioned recursive functions. Unlike quantum
transitions of QTMs, the recursion schemes can provide a clear view of how
quantum transforms act on target quantum states in the Hilbert space.

Two important classes of quantum functions, denoted $\Box^{\mathrm{QP}}_{1}$
and $\widehat{\Box^{\mathrm{QP}}_{1}}$, were formulated in [27] from six
simple initial quantum functions and three basic construction schemes. The
major difference between $\Box^{\mathrm{QP}}_{1}$ and
$\widehat{\Box^{\mathrm{QP}}_{1}}$ is the permitted use of _quantum
measurement operations_ , which make quantum states collapse to classical
states with incurred probabilities. Unfortunately, this is a non-reversible
operation. Shown in [27] are a precise characterization of quantum polynomial-
time computability and a quantum analogue of the normal form theorem. A key in
his recursion schematic definition is an introduction of the _multi-qubit
quantum recursion scheme_ , which looks quite different in its formulation
from the corresponding classical recursion scheme. We will give its formal
definition in Section 3.1 as Scheme T. This quantum recursion scheme turns out
to be quite powerful so that it helps us capture the notion of quantum
polynomial-time computability.

There are a few but important advantages of using recursion schematic
definitions to introduce quantum computing over other quantum computational
models, such as QTMs and quantum circuits. The most significant advantage is
in fact that there is no use of the _well-formedness requirement_ of QTMs and
the _uniformity requirement_ of quantum circuit families. These natural but
cumbersome requirements are necessary to guarantee the unitary nature of QTMs
and the algorithmic generation of quantum circuit families. Recursion
schematic definitions, on the contrary, avoid such extra requirements and make
it much simpler to design a quantum algorithm given in the form of a quantum
function for solving a target combinatorial problem. This is because each
basic scheme embodies “well-formedness” and “uniformity” in its formulation.
In other words, the scheme produces only “well-formed” or “uniform” quantum
functions by applying the scheme directly to the existing quantum functions.
In fact, the schematic definition of [27] constitutes only six initial quantum
functions together with three basic construction schemes and this fact helps
us render a short procedural sequence of how to construct each target quantum
function. A descriptional aspect of the recursion schematic definition of [27]
can be a helpful guide to develop a suitable form of quantum programming
language [11]. It is worth mentioning that such a recursion schematic
definition was made possible because of an extensional use of the bra and ket
notations. See Section 2.3 for detailed explanations.

A schematic approach of [27] to quantum computability has exhibited a great
possibility of treating quantum computable functions in such a way that is
quite different from the traditional ways with QTMs and quantum circuit
families. Recursion schemes lead us to the descriptional complexity of quantum
functions. Concerning the recursion schematic definitions, numerous questions
still remain unanswered. It is important and also imperative to expand the
scope of our research to various resource-bounded quantum computing. In a
similar vein, we wish to turn our attention to a “limited” form of quantum
computing, which can be naturally implemented by small runtime-restricted QTMs
as well as families of depth-bounded quantum circuits, and we wish to examine
how the schematic approach of [27] copes with such quantum computing.

Of practical importance, resource-bounded computability has been studied in
the classical setting based on various computational models, including
families of Boolean circuits and time-bounded (classical) Turing machines (or
TMs, for short). Among all reasonable resource bounds, we are particularly
keen to _(poly)logarithmic time_. The logarithmic-time (abbreviated as
logtime) computability may be one of the most restricted but meaningful,
practical resource-bounded computabilities and it was discussed earlier by
Buss [8] and Barrington, Immerman, and Straubing [1] in terms of TMs equipped
with index tapes to access particular locations of input symbols. Here, we
denote by $\mathrm{DLOGTIME}$ (resp., $\mathrm{NLOGTIME}$) the class of
decision problems solvable by logtime deterministic (resp., nondeterministic)
TMs. The logtime computability has played a central role in characterizing a
uniform notion of constant-depth Boolean circuit families. As shown in [1],
logtime computability is also closely related to the first-order logic with
the special predicate $BIT$. As slightly more general resource-bounded
computability, _polylogarithmic-time_ computability has been widely studied in
the literature. Numerous polylogarithmic-time (abbreviated as polylogtime)
algorithms were developed to solve, for example, the matrix chain ordering
problem [7] and deterministic graph construction [12]. There were also studies
on data structures that support polylog operations [16] and probabilistic
checking of polylog bits of proofs [2]. We denote by $\mathrm{PPOLYLOGTIME}$
the complexity class of decision problems solvable by polylogtime
probabilistic TMs with unbounded-error probability.

In the setting of quantum computing, we are able to take a similar approach
using resource-bounded QTMs. A quantum analogue of $\mathrm{DLOGTIME}$, called
$\mathrm{BQLOGTIME}$, was lately discussed in connection to an oracle
separation between $\mathrm{BQP}$ and the polynomial hierarchy in [20]. In
this work, however, we are interested in polylogtime-bounded quantum
computations, and thus we wish to look into the characteristics of quantum
polylogtime computability. Later in Section 5.1, we formally describe the
fundamental model of _polylogtime QTMs_ as a quantum analogue of classical
polylogtime TMs. These polylogtime QTMs naturally induce the corresponding
bounded-error complexity class $\mathrm{BQPOLYLOGTIME}$. In Section 5.2,
$\mathrm{BQPOLYLOGTIME}$ is shown to differ in computational power from
$\mathrm{NLOGTIME}$ as well as $\mathrm{PPOLYLOGTIME}$.

###  1.2 Our Challenges in This Work

We intend to extend the scope of the existing research on resource-bounded
quantum computability by way of an introduction of a small set of recursion
schemes defining for runtime-restricted quantum computability. In particular,
we look into quantum polylogtime computability and seek out an appropriate
recursion schematic definition to exactly capture such computability. Since
$\Box^{\mathrm{QP}}_{1}$ and $\widehat{\Box^{\mathrm{QP}}_{1}}$ capture
quantum polynomial-time computability, it is natural to raise a question of
how we capture quantum polylogtime computability in a similar fashion.

As noted earlier, the multi-qubit quantum recursion scheme of [27] is capable
of precisely capturing quantum polynomial-time computability. A basic idea of
this quantum recursion scheme is, starting with $n$ qubits at each round of
recursion, to modify the first $k$ qubits and continue to the next round only
with the rest of the qubits after discarding the first $k$ qubits. This
recursive process slowly consumes the entire $n$ qubits and finally grinds to
halt after linearly-many recursive rounds. To describe limited quantum
computability, in contrast, how can we weaken the quantum recursion scheme?
Our attempt in this work is to speed up this recursive process significantly
by discarding a bundle of $\lceil n/2\rceil$(or $\lfloor n/2\rfloor$) qubits
from the entire $n$ qubits at each round. Such a way of halving the number of
qubits at each recursive round makes the recursive process terminate
significantly faster; in fact, ending in at most $\lceil\log{n}\rceil$
recursive rounds. For this very reason, we intend to call this weakened
recursive process the _(code-controlled) fast quantum recursion scheme_.

Although the fast quantum recursion scheme is significantly weaker in power
than the quantum recursion scheme of [27], the scheme still generates numerous
interesting and useful quantum functions, as listed in Lemmas 3.3–3.7 and
3.13–4.2. More importantly, it is possible to implement the binary search
strategy, which has been a widely-used key programming technique. We call the
set of all quantum functions generated from eight initial quantum functions
and two construction schemes together with the fast quantum recursion scheme
by $EQS$ (elementary quantum schemes) in Section 3. This class $EQS$ turns out
to precisely characterize quantum polylogtime computability (Theorems
5.4–5.5).

To cope with polylogtime computability, we need an appropriate encoding of
various types of “objects” (such as numbers, graphs, matrices, tape symbols)
into qubits of the same length and also another efficient way of decoding the
original “objects” from those encoded qubits. For this purpose, we introduce
in Section 3.2 a code-skipping scheme, which recognizes encoded segments to
skip them one by one. This scheme in fact plays a key role in performing the
fast recursion scheme.

Throughout this work, we try to promote much better understandings of
resource-bounded quantum computing in theory and in practice.

#### New Materials after the Preliminary Report.

The current work corrects and significantly alters the preliminary report
[29], particularly in the following points. Five schemes, which constitute
$EQS$, in the preliminary report have been modified and reorganized, and thus
they look slightly different in their formulations. In particular, Scheme V is
introduced to establish a precise characterization of quantum functions
computable by polylogtime QTMs.

Beyond the scope of the preliminary report [29], this work further looks into
another restricted quantum algorithmic procedure, known as the _divide-and-
conquer strategy_ in Section 6. A key idea behind this strategy is to
inductively split an given instance into small pieces and then inductively
assemble them piece by piece with an appropriate modification. This new scheme
helps us capture the parity function, which requires more than polylogtime
computation. This fact implies that this new scheme is not “realized” in the
framework of $EQS$.

##  2 Preparation: Notions and Notation

We will briefly explain basic notions and notation used in this work.

###  2.1 Numbers, Strings, and Languages

The notations $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ denote respectively
the sets of all integers, of all rational numbers, and of all real numbers. In
particular, we set $\bar{\mathbb{Q}}=\mathbb{Q}\cap[0,1]$. The _natural
numbers_ are nonnegative integers and the notation $\mathbb{N}$ expresses the
set of those numbers. We further write $\mathbb{N}^{+}$ to express the set
$\mathbb{N}-\\{0\\}$. For two integers $m,n$ with $m\leq n$,
$[m,n]_{\mathbb{Z}}$ denotes the _integer interval_
$\\{m,m+1,m+2,\ldots,n\\}$. In particular, we abbreviate $[1,n]_{\mathbb{Z}}$
as $[n]$ if $n\geq 1$. Moreover, $\mathbb{C}$ denotes the set of all complex
numbers. We denote $\lceil\cdot\rceil$ and $\lfloor\cdot\rfloor$ for the
ceiling function and the floor function, respectively. In this work, all
_polynomials_ have nonnegative integer coefficients and all _logarithms_ are
taken to the base $2$. For convenience, we set $\log{0}=0$. Moreover, we
define $\mathrm{ilog}(n)$ and $\mathrm{iloglog}(n)$ to be
$\lceil\log{n}\rceil$ and $\lceil\log\log{n}\rceil$ for any $n\in\mathbb{N}$,
respectively. The notation $\imath$ denotes $\sqrt{-1}$ and $e$ is the base of
natural logarithms. Given a complex number $\alpha$, $\alpha^{*}$ denotes the
_complex conjugate_ of $\alpha$. As for a nonempty set of quantum amplitudes,
which is a subset of $\mathbb{C}$, we use the notation $K$.

A nonempty finite set of symbols (or letters) is called an _alphabet_ and a
sequence of such symbols from a fixed alphabet $\Sigma$ is called a _string_
over $\Sigma$. The total number of occurrences of symbols in a string $x$ is
the _length_ of $x$ and is denoted $|x|$. The _empty string_ $\lambda$ is a
unique string of length $0$. A collection of those strings over $\Sigma$ is a
_language_ over $\Sigma$. Throughout this work, we deal only with _binary
strings_ , which are sequences of 0s and 1s. Given a number $n\in\mathbb{N}$,
$\Sigma^{n}$ (resp., $\Sigma^{\leq n}$) denotes the set of all strings of
length exactly $n$ (resp., at most $n$). Let
$\Sigma^{*}=\bigcup_{n\in\mathbb{N}}\Sigma^{n}$ and
$\Sigma^{+}=\Sigma^{*}-\\{\lambda\\}$. Given a string $x$ and a bit
$b\in\\{0,1\\}$, the notation $\\#_{b}(x)$ denotes the total number of
occurrences of symbol $b$ in $x$. Due to the nature of quantum computation, we
also discuss “promise” decision problems. A pair $(A,R)$ of subsets of
$\Sigma^{*}$ is said to be a _promise (decision) problem_ over $\Sigma$ if
$A\cup R\subseteq\Sigma^{*}$ and $A\cap R=\varnothing$.

Given a number $n\in\mathbb{N}^{+}$, we need to partition it into two halves.
To describe the “left half” and the “right half” of $n$, we introduce two
special functions: $LH(n)=\lceil n/2\rceil$ and $RH(n)=\lfloor n/2\rfloor$.

For a function $f$, we write $f^{k}$ for the $k$ consecutive applications of
$f$ to an input. For example, $f^{2}(x)=f\circ f(x)=f(f(x))$ and
$f^{3}(x)=f\circ f\circ f(x)=f(f(f(x)))$. The functions $LH$ and $RH$ satisfy
the following property.

###### Lemma 2.1

Let $k,n\in\mathbb{N}^{+}$ be any two numbers. (1) If $n$ is in
$[2^{k-1}+1,2^{k}]_{\mathbb{Z}}$ (thus, $\lceil\log{n}\rceil=k$), then
$LH^{k}(n)=1$ holds. Moreover, if $k\geq 2$, then $LH^{k-1}(n)=2$. (2) If $n$
is in $[2^{k},2^{k+1}-1]_{\mathbb{Z}}$ (thus, $\lfloor\log{n}\rfloor=k$), then
$RH^{k}(n)=1$ holds. Moreover, if $k\geq 2$, then $RH^{k-1}(n)\in\\{2,3\\}$.

###### Proof.

(1) Consider a series: $n$, $LH(n)$, $LH^{2}(n)$, $\cdots$, $LH^{k}(n)$. It
follows that, for any number $n>2$, $n\in[2^{k-1}+1,2^{k}]_{\mathbb{Z}}$ iff
$LH(n)\in[2^{k-2}+1,2^{k-1}]_{\mathbb{Z}}$. Thus, we obtain
$LH^{k-1}(n)\in\\{2\\}$ and $LH^{k}(n)\in\\{1\\}$. When $n\geq 3$, the last
two numbers of the above series must be $2$ and $1$.

(2) In a similar fashion, let us consider a series: $n$, $RH(n)$, $RH^{2}(n)$,
$\ldots$, $RH^{k}(n)$. It then follows that
$n\in[2^{k},2^{k+1}-1]_{\mathbb{Z}}$ iff
$RH(n)\in[2^{k-1},2^{k}-1]_{\mathbb{Z}}$. We then obtain
$RH^{k-1}(n)\in[2,3]_{\mathbb{Z}}$ and $RH^{k}(n)\in\\{1\\}$. ∎

We assume the standard _lexicographical order_ on $\\{0,1\\}^{*}$:
$\lambda,0,1,00,01,10,11,000,\cdots$ and, based on this ordering, we assign
natural numbers to binary strings as $bin(0)=\lambda$, $bin(1)=0$, $bin(2)=1$,
$bin(3)=00$, $bin(4)=01$, $bin(5)=10$, $bin(6)=11$, $bin(7)=000$, etc. In
contrast, for a fixed number $k\in\mathbb{N}^{+}$, $bin_{k}(n)$ denotes the
lexicographically $n$th string in $\\{0,1\\}^{k}$ as long as $n\in[2^{k}]$.
For instance, we obtain $bin_{3}(1)=000$, $bin_{3}(2)=001$, $bin_{3}(3)=010$,
$bin_{3}(4)=011$, etc. Remember that $bin_{k}(0)$ is not defined.

###  2.2 Quantum States and Hilbert Spaces

We assume the reader’s familiarity with basic quantum information and
computation (see, e.g., textbooks [17, 13]). A basic concept in quantum
computing is a Hilbert space and unitary transformations over it. The _ket
notation_ $|\phi\rangle$ expresses a (column) vector in a Hilbert space and
its transposed conjugate is expressed as a (row) vector of the dual space and
is denoted by the _bra notation_ $\langle\phi|$. The notation
$\langle\psi|\phi\rangle$ denotes the _inner product_ of two vectors
$|\psi\rangle$ and $|\phi\rangle$. We use $I$ to denote the identity matrix of
an arbitrary dimension. A square complex matrix $U$ is called _unitary_ if $U$
satisfies $UU^{\dagger}=U^{\dagger}U=I$, where $U^{\dagger}$ is the transposed
conjugate of $U$.

A _quantum bit_ (or a _qubit_ , for short) is a linear combination of two
basis vectors $|0\rangle$ and $|1\rangle$. The notation ${\cal H}_{2}$
indicates the Hilbert space spanned by $|0\rangle$ and $|1\rangle$. More
generally, ${\cal H}_{2^{n}}$ refers to the Hilbert space spanned by the
computational basis $B_{n}=\\{|s\rangle\mid s\in\\{0,1\\}^{n}\\}$. Let ${\cal
H}_{\infty}=\bigcup_{n\in\mathbb{N}^{+}}{\cal H}_{2^{n}}$. Given a quantum
state $|\phi\rangle\in{\cal H}_{\infty}$, its _length_ $\ell(|\phi\rangle)$
denotes the minimum number $n\in\mathbb{N}$ satisfying that
$|\phi\rangle\in{\cal H}_{2^{n}}$. We use the generic notation ${\bf 0}$ to
denote the _null vector_ of an arbitrary dimension. As a special case, we set
$\ell({\bf 0})=0$ for the null vector ${\bf 0}$ (although ${\bf 0}$ belongs to
${\cal H}_{k}$ for any $k\in\mathbb{N}^{+}$). For convenience, we also set
$\ell(\alpha)=0$ for any scalar $\alpha\in\mathbb{C}$. For a quantum state
$|\phi\rangle$, if we make a measurement in the computational basis, then each
binary string $x$ of length $\ell(|\phi\rangle)$ is observed with probability
$|\langle x|\phi\rangle|^{2}$. Thus, $|\phi\rangle$ can be expressed as
$|0\rangle\langle 0|\phi\rangle+|1\rangle\langle 1|\phi\rangle$ and also as
$\sum_{x\in\\{0,1\\}^{n}}\langle x|\phi\rangle\otimes|x\rangle$, where
$|\phi\rangle\otimes|\psi\rangle$ is the _tensor product_ of $|\phi\rangle$
and $|\psi\rangle$. The _norm_ of $|\phi\rangle$ is defined as
$\sqrt{\langle\phi|\phi\rangle}$ and is denoted by $\||\phi\rangle\|$.

A _qustring of length $n$_ is a unit-norm quantum state in ${\cal H}_{2^{n}}$.
As a special case, the null vector is treated as the _qustring of length $0$_
(although its norm is $0$). Let $\Phi_{n}$ denote the set of all qustrings of
length $n$ and set $\Phi_{\infty}$ to be $\bigcup_{n\in\mathbb{N}}\Phi_{n}$.

Abusing the aforementioned notations of $LH(n)$ and $RH(n)$, we set
$LH(|\phi\rangle)=\lceil\ell(|\phi\rangle)/2\rceil$ and
$RH(|\phi\rangle)=\lfloor\ell(|\phi\rangle/2\rfloor$ for any quantum state
$|\phi\rangle\in{\cal H}_{\infty}$. It then follows that
$\ell(|\phi\rangle)=LH(|\phi\rangle)+RH(|\phi\rangle)$.

We are interested only in functions mapping ${\cal H}_{\infty}$ to ${\cal
H}_{\infty}$ and these functions are generally referred to as _quantum
functions on ${\cal H}_{\infty}$_ to differentiate from “functions” working
with natural numbers or strings. Such a quantum function $f$ is said to be
dimension-preserving (resp., _norm-preserving_) if
$\ell(|\phi\rangle)=\ell(f(|\phi\rangle))$ (resp.,
$\||\phi\rangle\|=\|f(|\phi\rangle)\|$) holds for any quantum state
$|\phi\rangle\in{\cal H}_{\infty}$.

###  2.3 Conventions on the Bra and the Ket Notations

To calculate the outcomes of quantum functions on ${\cal H}_{\infty}$, we take
advantage of making a purely symbolic treatment of the bra and the ket
notations together with the tensor product notation $\otimes$. We generally
follow [27] for the conventions on the specific usage of these notations. This
notational convention in fact helps us simplify the description of various
qubit operations. Since we greatly deviate from the standard usage of those
notations, hereafter, we explain how to use them throughout this work.

It is important to distinguish between the number $0$ and the null vector
${\bf 0}$. To del with the null vector ${\bf 0}$, we conveniently take the
following specific conventions concerning the operator “$\otimes$”. For any
$|\phi\rangle\in{\cal H}_{\infty}$, (i)
$0\otimes|\phi\rangle=|\phi\rangle\otimes 0={\bf 0}$ (scalar case), (ii)
$|\phi\rangle\otimes{\bf 0}={\bf 0}\otimes|\phi\rangle={\bf 0}$, and (iii) if
$|\psi\rangle$ is the null vector, then
$\langle\phi|\psi\rangle=\langle\psi|\phi\rangle={\bf 0}$. In the case of (i),
we extend the usage of $\otimes$ to even cover “scalar multiplication” to
simplify later calculations. Given two binary strings $u,s\in\\{0,1\\}^{+}$,
if $|s|=|u|$, then $\langle u|s\rangle=1$ if $u=s$, and $\langle u|s\rangle=0$
otherwise. On the contrary, when $|u|<|s|$, $\langle u|s\rangle$ denotes
$|z\rangle$ if $s=uz$ for a certain string $z$, and $0$ otherwise. By sharp
contrast, if $|u|>|s|$, then $\langle u|s\rangle$ always denotes ${\bf 0}$.
More generally, if
$|\phi\rangle=\sum_{u\in\\{0,1\\}^{n}}\sum_{s\in\\{0,1\\}^{m}}\alpha_{u,s}|u\rangle|s\rangle$
and $u_{0}\in\\{0,1\\}^{n}$, then $\langle u_{0}|\phi\rangle$ expresses the
quantum state $\sum_{s\in\\{0,1\\}^{m}}\alpha_{u_{0},s}|s\rangle$. For
instance, if $|\phi\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$, then
$\langle 0|\phi\rangle$ equals $\frac{1}{\sqrt{2}}|0\rangle$ and $\langle
1|\phi\rangle$ does $\frac{1}{\sqrt{2}}|1\rangle$. These notations $\langle
0|\phi\rangle$ and $\langle 1|\phi\rangle$ makes it possible to express any
qustring $|\phi\rangle$ as $|0\rangle\otimes\langle
0|\phi\rangle+|1\rangle\otimes\langle 1|\phi\rangle$. In a more general case
with $|\xi\rangle=\sum_{u\in\\{0,1\\}^{n}}\beta_{u}|u\rangle$,
$\langle\xi|\phi\rangle$ means $\sum_{u\in\\{0,1\\}^{n}}\beta_{u}^{*}\langle
u|\phi\rangle$, which equals
$\sum_{u\in\\{0,1\\}^{n}}\sum_{s\in\\{0,1\\}^{m}}\alpha_{u,s}\beta_{u}^{*}|s\rangle$.
Moreover, $|\phi\rangle$ can be expressed as
$\sum_{u\in\\{0,1\\}^{n}}\beta_{u}|u\rangle\otimes\langle u|\phi\rangle$. We
often express $|\phi\rangle\otimes|\psi\rangle$ as $|\phi\rangle|\psi\rangle$.
In particular, for strings $s$ and $u$, $|s\rangle\otimes|u\rangle$ is further
abbreviated as $|s,u\rangle$ or even $|su\rangle$. When $\langle
s|\phi\rangle$ is just a scalar, say, $\alpha\in\mathbb{C}$, the notation
$|s\rangle\otimes\langle s|\phi\rangle$ (or equivalently, $|s\rangle\langle
s|\phi\rangle$) is equal to $\alpha|s\rangle$.

We also expand the norm notation $\|\cdot\|$ for vectors in the following way.
For any quantum states $|\phi\rangle$ and $|\psi\rangle$ with
$\ell(|\phi\rangle)=\ell(|\psi\rangle)>0$, the notation
$\|\langle\phi|\psi\rangle\|$ is used to express the absolute value
$|\langle\phi|\psi\rangle|$. In general, for any scalar $\alpha\in\mathbb{C}$,
$\|\alpha\|$ denotes $|\alpha|$. This notational convention is quite useful in
handling the value obtained after making a measurement without worrying about
whether the resulting object is a quantum state or a scalar.

Later, we will need to encode (or translate) a series of symbols into an
appropriate qustring. In such an encoding, the empty string $\lambda$ is
treated quite differently. Notably, we tend to automatically translate
$|\lambda\rangle$ into the null vector ${\bf 0}$ unless otherwise stated.

##  3 A Recursion Schematic Definition of EQS

We will present a recursion schematic definition to formulate a class of
special quantum functions on ${\cal H}_{\infty}$ (i.e., from ${\cal
H}_{\infty}$ to ${\cal H}_{\infty}$), later called $EQS$. To improve the
readability, we first provide a skeleton system of $EQS$ and later we expand
it to the full-fledged system.

###  3.1 Skeleton EQS

As a starter, we discuss a “skeleton” of our recursion schematic definition
for “elementary” quantum functions, which are collectively called $EQS$
(elementary quantum schemes) in Definition 3.18, involving six initial quantum
functions and two construction schemes. All initial quantum functions were
already presented when defining $\Box^{\mathrm{QP}}_{1}$ and
$\widehat{\Box^{\mathrm{QP}}_{1}}$ in [27].

Throughout the rest of this work, we fix a nonempty amplitude set $K$ and we
often ignore the clear reference to $K$ as long as the choice of $K$ is not
important in our discussion.

###### Definition 3.1

The skeleton class $EQS_{0}$ is composed of all quantum functions constructed
by selecting the initial quantum functions of Scheme I and then inductively
applying Schemes II–III a finite number of times. In what follows,
$|\phi\rangle$ denotes an arbitrary quantum state in ${\cal H}_{\infty}$. When
the item 6) of Scheme I is not used, we denote the resulting class by
$\widehat{EQS}_{0}$.

  1. I.

The _initial quantum functions_. Let $\theta\in[0,2\pi)\cap K$ and
$a\in\\{0,1\\}$.

1) $I(|\phi\rangle)=|\phi\rangle$. (identity)

2) $PHASE_{\theta}(|\phi\rangle)=|0\rangle\\!\langle
0|\phi\rangle+e^{\imath\theta}|1\rangle\\!\langle 1|\phi\rangle$. (phase
shift)

3)
$ROT_{\theta}(|\phi\rangle)=\cos\theta|\phi\rangle+\sin\theta(|1\rangle\\!\langle
0|\phi\rangle-|0\rangle\\!\langle 1|\phi\rangle)$. (rotation around $xy$-axis
at angle $\theta$)

4) $NOT(|\phi\rangle)=|0\rangle\\!\langle 1|\phi\rangle+|1\rangle\\!\langle
0|\phi\rangle$. (negation)

5) $SWAP(|\phi\rangle)=\left\\{\begin{array}[]{ll}|\phi\rangle&\mbox{if
$\ell(|\phi\rangle)\leq 1$,}\\\ \sum_{a,b\in\\{0,1\\}}|ab\rangle\\!\langle
ba|\phi\rangle&\mbox{otherwise.}\end{array}\right.$ (swapping of 2 qubits)

6) $MEAS[a](|\phi\rangle)=|a\rangle\\!\langle a|\phi\rangle$. (partial
projective measurement)

  2. II.

The _composition scheme_. From $g$ and $h$, we define $Compo[g,h]$ as follows:

$Compo[g,h](|\phi\rangle)=g\circ h(|\phi\rangle)$ ($=g(h(|\phi\rangle))$).

  3. III.

The _branching scheme_.555We remark that $Branch[g,h]$ can be expressed as an
appropriate unitary matrix (if $g$ and $h$ are expressed as unitary matrices)
and thus it is a legitimate quantum operation to consider. From $g$ and $h$,
we define $Branch[g,h]$ as:

(i) $Branch[g,h](|\phi\rangle)=|\phi\rangle$ if $\ell(|\phi\rangle)\leq 1$,
(ii) $Branch[g,h](|\phi\rangle)=|0\rangle\otimes g(\langle
0|\phi\rangle)+|1\rangle\otimes h(\langle 1|\phi\rangle)$ otherwise.

Notice that the length function $\ell(|\phi\rangle)$ is not included as part
of $EQS_{0}$.

In Schemes II and III, the constructions of $Compo[g,h]$ and $Branch[g,h]$
need two quantum functions $g$ and $h$ that are assumed to have been already
constructed. To refer to these supporting quantum functions used in the
scheme, we call them the _ground (quantum) functions_ of $Compo[g,h]$ and
$Branch[g,h]$. In the case of a special need to emphasize $K$, then we write
$EQS_{K,0}$ and $\widehat{EQS}_{K,0}$ with a clear reference to $K$. It is
important ro remark that, for any $|\phi\rangle$ and $a\in\\{0,1\\}$,
$\ell(MEAS[a](|\phi\rangle))=\ell(|\phi\rangle)$.

We quickly provide simple examples of how to compute the functions of Schemes
I–III.

###### Example 3.2

For three bits $a,b,c\in\\{0,1\\}$, we obtain
$PHASE_{\pi}(|1\rangle)=-|1\rangle$ and
$PHASE_{\pi/2}(\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)=\frac{1}{\sqrt{2}}(|0\rangle+\imath|1\rangle)$,
$ROT_{\pi/4}(|0\rangle)=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ and
$ROT_{\pi/4}(|1\rangle)=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$,
$NOT(|a\rangle)=|1-a\rangle$, and $SWAP(|abc\rangle)=|bac\rangle$. We obtain
$MEAS[0](ROT_{\pi/4}(|00\rangle))=MEAS[0](\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes|0\rangle)=\frac{1}{\sqrt{2}}|00\rangle$.
For Scheme III, it is important to note that $Branch[g,g]$ is not the same as
$g$ itself. For example, $Branch[NOT,NOT](|b\rangle|\phi\rangle)$ equals
$|b\rangle\otimes NOT(|\phi\rangle)$ whereas $NOT(|b\rangle|\phi\rangle)$ is
just $|1-b\rangle|\phi\rangle$, where $b$ denotes any bit. Moreover, if
$|\phi\rangle=ROT_{\pi/4}(|0\rangle|0\rangle)$, then we obtain
$Branch[I,NOT](|\phi\rangle)=Branch[I,NOT](\frac{1}{\sqrt{2}}(|00\rangle+|10\rangle))=|0\rangle\otimes
I(\frac{1}{\sqrt{2}}|0\rangle)+|1\rangle\otimes
NOT(\frac{1}{\sqrt{2}}|0\rangle)=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$.

For later reference, let us review from [27] the _multi-qubit quantum
recursion scheme_ , which is a centerpiece of schematically characterizing
quantum polynomial-time computability. In this work, this special scheme is
referred to as Scheme T.

  * (T)

The _multi-qubit quantum recursion scheme_ [27]. Let $g$, $h$, $p$ be quantum
functions and let $k,t\in\mathbb{N}^{+}$ be numbers. Assume that $p$ is
dimension-preserving. For ${\cal F}_{k}=\\{f_{u}\\}_{u\in\\{0,1\\}^{k}}$, we
define $F\equiv kQRec_{t}[g,h,p|{\cal F}_{k}]$ as follows:

(i) $F(|\phi\rangle)=g(|\phi\rangle)$ if $\ell(|\phi\rangle)\leq t$,
(ii) $F(|\phi\rangle)=h(\sum_{u:|u|=k}|u\rangle\otimes f_{u}(\langle
u|\psi_{p,\phi}\rangle))$ otherwise,
where $|\psi_{p,\phi}\rangle=p(|\phi\rangle)$ and $f_{u}\in\\{F,I\\}$ for any
$u\in\\{0,1\\}^{k}$.

This quantum recursion scheme together with Schemes I–III given above and
another quantum function called $REMOVE$ (removal) defines the class
$\Box^{\mathrm{QP}}_{1}$, which constitutes all polynomial-time computable
quantum functions [27]. Although we do not consider $REMOVE$, we will
introduce in Section 3.2 a restricted form of $REMOVE$, called
$CodeREMOVE[\cdot]$.

Let us present a short list of typical quantum functions “definable” within
$EQS_{0}$; that is, those quantum functions are actually constructed from the
items 1)–5) of Scheme I and by Schemes II–III. As the first simple application
of Scheme I–III, we show how to construct the quantum function called
$Skip_{k}[\cdot]$.

###### Lemma 3.3

Let $g$ denote any quantum function in $EQS_{0}$ and let $k\in\mathbb{N}^{+}$.
The quantum function $Skip_{k}[g]$ is defined by
$Skip_{k}[g](|\phi\rangle)=|\phi\rangle$ if $\ell(|\phi\rangle)\leq k$, and
$\sum_{u:|u|=k}|u\rangle\otimes g(\langle u|\phi\rangle)$ otherwise. This
$Skip_{k}[g]$ is definable within $EQS_{0}$.

###### Proof.

We define the desired quantum function $Skip_{k}[g]$ by induction on
$k\in\mathbb{N}^{+}$. When $k=1$, we set $Skip_{1}[g]\equiv Branch[g,g]$.
Clearly, when $\ell(|\phi\rangle)>k$, we obtain
$Skip_{1}[g](|\phi\rangle)=Branch[g,g](|\phi\rangle)=\sum_{a\in\\{0,1\\}}|a\rangle\otimes
g(\langle a|\phi\rangle)$. For any index $k\geq 2$, we define $Skip_{k+1}[g]$
as $Branch[Skip_{k}[g],Skip_{k}[g]]$. It then follows that, if
$\ell(|\phi\rangle)>k+1$, then
$Skip_{k+1}[g](|x\rangle|\phi\rangle)=\sum_{a\in\\{0,1\\}}|a\rangle\otimes
Skip_{k}[g](\langle
a|\phi\rangle)=\sum_{a\in\\{0,1\\}}\sum_{s:|s|=k}|a\rangle|s\rangle\otimes
g(\langle s|\psi_{Skip_{k}[g],\langle
a|\phi\rangle}\rangle)=\sum_{s^{\prime}:|s^{\prime}|=k+1}|s^{\prime}\rangle\otimes
g(\langle s^{\prime}|\phi\rangle)$, as requested. ∎

###### Lemma 3.4

Fix $\theta\in[0,2\pi)\cap K$ and $i,j,k\in\mathbb{N}^{+}$ and $i<j$. Let
$|\phi\rangle$ be any quantum state in ${\cal H}_{\infty}$, let $a$, $b$, and
$c$ be any bits. The following quantum functions are definable by Schemes
I–III and thus in $EQS_{0}$.

  1. 1.

$CNOT(|\phi\rangle)=|\phi\rangle$ if $\ell(|\phi\rangle)\leq 1$ and
$CNOT(|\phi\rangle)=|0\rangle\langle 0|\phi\rangle+|1\rangle\otimes
NOT(\langle 1|\phi\rangle)$ otherwise. (controlled NOT)

  2. 2.

$GPS_{\theta}(|\phi\rangle)=e^{\imath\theta}|\phi\rangle$. (global phase
shift)

  3. 3.

$WH(|\phi\rangle)=\frac{1}{\sqrt{2}}|0\rangle\otimes(\langle
0|\phi\rangle+\langle
1|\phi\rangle)+\frac{1}{\sqrt{2}}|1\rangle\otimes(\langle
0|\phi\rangle-\langle 1|\phi\rangle)$. (Walsh-Hadamard transform)

  4. 4.

$Z_{1,\theta}(|\phi\rangle)=e^{\imath\theta}|0\rangle\langle
0|\phi\rangle+|1\rangle\langle 1|\phi\rangle$.

  5. 5.

$zROT_{\theta}(|\phi\rangle)=e^{\imath\theta}|0\rangle\langle
0|\phi\rangle+e^{-\imath\theta}|1\rangle\langle 1|\phi\rangle$. (rotation
around the $z$-axis)

  6. 6.

$C_{\theta}(|\phi\rangle)=|\phi\rangle$ if $\ell(|\phi\rangle)\leq 1$ and
$C_{\theta}(|\phi\rangle)=|0\rangle\langle 0|\phi\rangle+|1\rangle\otimes
ROT_{\theta}(\langle 1|\phi\rangle)$ otherwise. (controlled ROTθ)

  7. 7.

$CPHASE_{\theta}(|\phi\rangle)=|\phi\rangle$ if $\ell(|\phi\rangle)\leq 1$,
and
$CPHASE_{\theta}(|\phi\rangle)=\frac{1}{\sqrt{2}}\sum_{b\in\\{0,1\\}}(|0\rangle\langle
b|\phi\rangle+e^{\imath\theta b}|1\rangle\langle b|\phi\rangle)$ otherwise.
(controlled PHASE)

  8. 8.

$CSWAP(|a\rangle|\phi\rangle)=|0\rangle\otimes\langle
0|a\rangle|\phi\rangle+|1\rangle\otimes SWAP(\langle 1|a\rangle|\phi\rangle)$
(controlled SWAP)

  9. 9.

$LengthQ_{k}(|b\rangle|\phi\rangle)=|b\rangle|\phi\rangle$ if
$\ell(|\phi\rangle)<k$ and
$LengthQ_{k}(|b\rangle|\phi\rangle)=|1-b\rangle|\phi\rangle$ otherwise.
(length query)

  10. 10.

$SWAP_{i,j}(|\phi\rangle)=\sum_{a_{1}\cdots a_{j}\in\\{0,1\\}}|a_{1}\cdots
a_{i-1}a_{j}a_{i+1}\cdots a_{j-1}a_{i}a_{j+1}\cdots a_{n}\rangle\otimes\langle
a_{1}\cdots a_{i-1}a_{i}a_{i+1}\cdots a_{j-1}a_{j}a_{j+1}\cdots
a_{n}|\phi\rangle$ if $\ell(|\phi\rangle)\geq j$ and
$SWAP_{i,j}(|\phi\rangle)=|\phi\rangle$ otherwise, where
$n=\ell(|\phi\rangle)$.

###### Proof.

(1)–(5) These quantum functions are constructed in [27, Lemma 3.3]. (6) We set
$C_{\theta}\equiv Branch[I,ROT_{\theta}]$. (7) This was shown in [27, Lemma
3.6]. (8) We set $CSWAP$ to be $Branch[I,SWAP]$. This gives the equation
$CSWAP(|a\rangle|\phi\rangle)=|0\rangle\otimes I(\langle
0|a\rangle|\phi\rangle)+|1\rangle\otimes SWAP(\langle
1|a\rangle|\phi\rangle)$.

(9) Let $h\equiv Compo[Branch[NOT,NOT],SWAP]$. For simplicity, we write
$g\circ f$ in place of $Compo[g,f]$. The desired quantum function
$LengthQ_{1}$ is set to be $SWAP\circ Skip_{1}[SWAP]\circ Skip_{1}[h]\circ
SWAP$. It then follows that $LengthQ_{1}(|b\rangle)=|b\rangle$ and
$LengthQ_{1}(|b\rangle|\phi\rangle)=|1-b\rangle|\phi\rangle$. Letting $k\geq
2$, assume that $LengthQ_{k-1}$ has been already defined. We then define
$LengthQ_{k}$ as $SWAP\circ Skip_{1}[Branch[LengthQ_{k-1},LengthQ_{k-1}]]\circ
SWAP$.

(10) Fix $i=1$ and take $j>i$. Notice that $SWAP_{1,2}$ coincides with $SWAP$
of Scheme I. The target quantum function $SWAP_{1,j}$ is defined as follows.
Firstly, we define $SWAP_{k,k+1}$ for any fixed constant $k\geq 1$. This is
done by setting $SWAP_{k,k+1}$ to be $Skip_{k-1}[SWAP]$. For any $i,j\geq 1$
with $i<j$, we define $MOVE_{i,j}$ to be $SWAP_{i,i+1}\circ
SWAP_{i+1,i+2}\circ\cdots\circ SWAP_{j-1,j}$. It then follows that
$MOVE_{1,j-1}^{-1}$ equals $SWAP_{j-2,j-1}\circ SWAP_{j-3,j-2}\circ\cdots\circ
SWAP_{1,2}$. We further define $SWAP_{1,j}$ as $MOVE_{i,j}\circ
MOVE_{1,j-1}^{-1}$. Finally, we set $SWAP_{i,j}$ to be
$Skip_{i-1}[SWAP_{1,j-i}]$. ∎

###### Lemma 3.5

Fix $i,j,k\in\mathbb{N}^{+}$ with $k\geq 2$ and $i<j$, and let $|\phi\rangle$
denote any quantum state in ${\cal H}_{\infty}$. The following quantum
functions are definable by Schemes I–III and thus in $EQS_{0}$.

  1. 1.

$SecSWAP^{(k)}_{i,j}(|x_{1}\rangle|x_{2}\rangle\cdots|x_{i-1}\rangle|x_{i}\rangle|x_{i+1}\rangle\cdots|x_{j-1}\rangle|x_{j}\rangle|\phi\rangle)=|x_{1}\rangle|x_{2}\rangle\cdots|x_{i-1}\rangle|x_{j}\rangle|x_{i+1}\rangle\cdots|x_{j-1}\rangle|x_{i}\rangle|\phi\rangle$
for any $x_{1},x_{2},\ldots,x_{i},\ldots,x_{j}\in\\{0,1\\}^{k}$. (section
SWAP)

  2. 2.

$SecMOVE^{(k)}_{i,j}(|x_{1}\rangle|x_{2}\rangle\cdots|x_{i-1}\rangle|x_{i}\rangle|x_{i+1}\rangle\cdots|x_{j}\rangle|\phi\rangle)=|x_{1}\rangle|x_{2}\rangle\cdots|x_{i-1}\rangle|x_{i+1}\rangle\cdots|x_{j}\rangle|x_{i}\rangle|\phi\rangle$
for any $x_{1},x_{2},\ldots,x_{i},\ldots,x_{j}\in\\{0,1\\}^{k}$. (section
move)

###### Proof.

(1) Notice that $|x_{1}x_{2}\cdots x_{i-1}|=(i-1)k$ and $|x_{1}x_{2}\cdots
x_{j-1}|=(j-1)k$. For convenience, we write $i_{k}$ for $(i-1)k$ and $j_{k}$
for $(j-1)k$. It suffices to define $SecSWAP^{(k)}_{i,j}$ to be
$SWAP_{i_{k}+1,j_{k}+1}\circ SWAP_{i_{k}+2,j_{k}+2}\circ\cdots\circ
SWAP_{i_{k}+k,j_{k}+k}$.

(2) This quantum function is set to be $SecSWAP^{(k)}_{j-1,j}\circ\cdots\circ
SecSWAP^{(k)}_{i+1,i+2}\circ SecSWAP^{(k)}_{i,i+1}$. ∎

Hereafter, we construct more quantum functions in $EQS_{0}$.

###### Lemma 3.6

Consider $COPY_{1}$ that satisfies
$COPY_{1}(|a\rangle|\phi\rangle)=\sum_{s\in\\{0,1\\}}|a\oplus
s\rangle|s\rangle\langle s|\phi\rangle$ for any quantum state
$|\phi\rangle\in{\cal H}_{\infty}$ and any bit $a$. More generally, for each
fixed constant $k\geq 2$, let
$COPY_{k}(|x\rangle|\phi\rangle)=\sum_{z\in\\{0,1\\}^{k}}|x\oplus
z\rangle|z\rangle\langle z|\phi\rangle$ for any quantum state
$|\phi\rangle\in{\cal H}_{\infty}$ and any $k$-bit string $x$, where $x\oplus
z$ denotes the bitwise XOR. These quantum functions are all definable using
Schemes I–III.

###### Proof.

We inductively define $COPY_{k}$ for any index $k\geq 1$. In the case of
$k=1$, we set $COPY_{1}$ to be $SWAP\circ CNOT\circ SWAP$. It then follows
that $COPY_{1}(|a\rangle|\phi\rangle)=SWAP\circ CNOT\circ
SWAP(|a\rangle|\phi\rangle)=SWAP\circ
CNOT(\sum_{s\in\\{0,1\\}}|s\rangle|a\rangle\otimes\langle
s|\phi\rangle)=\sum_{s\in\\{0,1\\}}SWAP(|s\rangle|a\oplus
s\rangle\otimes\langle s|\phi\rangle)=\sum_{s\in\\{0,1\\}}|a\oplus
s\rangle\langle s|\phi\rangle$.

Let $k\geq 2$. Assume by induction hypothesis that $COPY_{k-1}$ has been
already defined. The quantum function $COPY_{k}(|x\rangle|\phi\rangle)$ is
described as follows. We first apply $SWAP_{[2,k]}\equiv SWAP_{2,3}\circ
SWAP_{3,4}\circ\cdots\circ SWAP_{k-1,k}$ to $|x\rangle|\phi\rangle$. We then
apply $COPY_{1}$ and $Skip_{2}[COPY_{k-1}]$. Finally, we apply
$SWAP_{[2,k]}^{-1}$. ∎

Let us construct the basic quantum functions $g_{AND}$ and $g_{OR}$, which
“mimic” the behaviors of the two-bit operations $AND$ and $OR$, using only
Schemes I–III.

###### Lemma 3.7

There exist two quantum functions $g_{AND}$ and $g_{OR}$ that satisfy the
following. Let $x,y\in\\{0,1\\}$ and $b\in\\{0,1\\}$. (1) $AND(x,y)=b$ iff
$\|\langle b|\psi_{0xy}^{(AND)}\rangle\|=1$, where
$|\psi_{0xy}^{(AND)}\rangle=g_{AND}(|0\rangle|x\rangle|y\rangle)$. (2)
$OR(x,y)=b$ iff $\|\langle b|\psi_{0xy}^{(OR)}\rangle\|=1$, where
$|\psi_{0xy}^{(OR)}\rangle=g_{OR}(|0\rangle|x\rangle|y\rangle)$. These quantum
functions are defined by Schemes I–III.

###### Proof.

Recall $SWAP_{i,j}$ and $COPY_{1}$ respectively from Lemmas 3.4 and 3.6. We
define $g_{OR}$ to be $SWAP_{1,3}\circ CSWAP\circ COPY_{1}$. By our
definitions, for any $x,y\in\\{0,1\\}$, we obtain
$g_{OR}(|0\rangle|x\rangle|y\rangle)=\langle
0|x\rangle|y\rangle|x\rangle|0\rangle+\langle
1|x\rangle|x\rangle|y\rangle|1\rangle$. Thus, it follows that
$g_{OR}(|0\rangle|0\rangle|y\rangle)=|y\rangle|0\rangle|0\rangle$ and
$g_{OR}(|0\rangle|1\rangle|y\rangle)=|1\rangle|y\rangle|1\rangle$.

Next, we define $g_{AND}$ to be $SWAP_{1,3}\circ SWAP_{2,3}\circ CSWAP\circ
COPY_{1}$. It then follows that $g_{AND}(|0\rangle|x\rangle|y\rangle)=\langle
0|x\rangle|x\rangle|y\rangle|0\rangle+\langle
1|x\rangle|y\rangle|x\rangle|1\rangle$. From this equality, we obtain
$g_{AND}(|0\rangle|0\rangle|y\rangle)=|0\rangle|y\rangle|0\rangle$ and
$g_{AND}(|0\rangle|1\rangle|y\rangle)=|y\rangle|1\rangle|1\rangle$. ∎

For later use, we define another quantum function, which splits the entire
input qubits into two halves and then swaps them. We do not intend to include
the quantum function to our system but it will be used to support the
description of a new scheme given in Section 3.2. Remark that, to construct
this quantum function, we need Schemes I–III together with the quantum
recursion (Scheme T). Recall the left-half function $LH$ and the right-half
function $RH$ from Section 2.1.

  1. *)

$HalfSWAP(|\phi\rangle)=\left\\{\begin{array}[]{ll}|\phi\rangle&\hskip
14.22636pt\mbox{if $\ell(|\phi\rangle)\leq 1$,}\\\
\sum_{s:|s|=LH(|\phi\rangle)}\langle s|\phi\rangle\otimes|s\rangle&\hskip
14.22636pt\mbox{otherwise.}\end{array}\right.$

The _inverse_ of $HalfSWAP$ is $HalfSWAP^{-1}$, which actually matches the
quantum function obtained from $HalfSWAP$ by replacing $LH(|\phi\rangle)$ in
its definition with $RH(|\phi\rangle)$. In the case where $\ell(|\phi\rangle)$
is even, $HalfSAWP\circ HalfSWAP(|\phi\rangle)$ equals $|\phi\rangle$ since
$LH(|\phi\rangle)=RH(|\phi\rangle)$.

###### Example 3.8

Consider a quantum state $|\phi\rangle=\sum_{u:|u|=3}\alpha_{u}|u\rangle$,
which is
$\alpha_{000}|000\rangle+\alpha_{001}|001\rangle+\alpha_{010}|010\rangle+\alpha_{011}|011\rangle+\cdots+\alpha_{111}|111\rangle$.
Note that $LH(|\phi\rangle)=\lceil\ell(|\phi\rangle)/2\rceil=2$ and
$RH(\ell(|\phi\rangle))=\lfloor\ell(|\phi\rangle)/2\rfloor=1$. Since $\langle
s|\phi\rangle=\sum_{u:|u|=3}\alpha_{u}\langle s|u\rangle$, it then follows
that $HalfSWAP(|\phi\rangle)=\sum_{s:|s|=2}\sum_{u:|u|=3}\alpha_{u}\langle
s|u\rangle\otimes|s\rangle$, which equals
$\alpha_{000}|000\rangle+\alpha_{001}|100\rangle+\alpha_{010}|001\rangle+\alpha_{011}|101\rangle+\cdots+\alpha_{111}|111\rangle$.

###  3.2 Binary Encoding of Various Types of Objects

All quantum functions in Section 3.1 take only “single” quantum states in
${\cal H}_{\infty}$ as their inputs. For practical applications of these
quantum functions, we need to further deal with a problem that consists of
various types of “objects”, such as numbers, graphs, matrices, tape symbols,
etc. For this purpose, it is imperative to set up an appropriate _binary
encoding_ to transform those objects into a single quantum state with the help
of designated “separators”. In the polynomial-time setting [27], the scheme of
quantum recursion (Scheme T) is powerful enough to handle several inputs
altogether as a single encoded quantum state in a way similar to multiple
tapes of a Turing machine being simulated by a single-tape Turing machine with
only polynomial overhead. However, since we aim at capturing quantum
polylogtime computability instead, we cannot take the same approach to cope
with multiple inputs. We thus need to ponder how to circumvent this
difficulty. As our solution to this problem, we introduce “extra” schemes that
help us handle intended binary encodings.

Since each QTM uses multiple tapes with their associated tape heads, these
tapes hold possibly different qubits and their tape heads move separately.
This is an advantage of the QTM model. However, since each quantum function
takes only one quantum state as its input, we therefore need to encode many
objects into a single quantum state.

In what follows, we attempt to design an encoding (or a translation) of
various types of objects into binary strings of the same fixed length so that
a series of these encoded objects forms a large-dimensional quantum state.
Each “segment” of such a quantum state representing one encoded object is
referred to as a _section_ , and this fixed-length encoding makes it possible
to work with each section separately.

Let us describe our encoding scheme for eight symbols in
$\\{0,1,2,{\dashv},B,H,S,T\\}$, where $\dashv$, $B$, $H$, $S$, and $T$
respectively stand for an “ending”, a “blank”, a “head”, a “separator”, and a
“time”. With the use of three bits, we set $\hat{0}=000$, $\hat{1}=001$,
$\hat{B}=010$, $\hat{\dashv}=011$, $\hat{2}=111$, $\hat{H}=100$,
$\hat{S}=110$, and $\hat{T}=101$. Given a binary string $s=s_{1}s_{2}\cdots
s_{k}$, the notation $\tilde{s}^{(-)}$ denotes
$\hat{s}_{1}\hat{s}_{2}\cdots\hat{s}_{k}$ and $\widetilde{s}$ denotes
$\tilde{s}^{(-)}\hat{\dashv}$. For convenience, we also define
$\widetilde{\lambda}$ to be $\hat{\dashv}$. This makes us encode, for example,
the number $8$ into
$\widetilde{bin(8)}=\widetilde{001}=\hat{0}\hat{0}\hat{1}\hat{\dashv}$ while
$\widetilde{bin_{3}(2)}$ also equals $\widetilde{001}$. Given an arbitrary
quantum state $|\phi\rangle$ in ${\cal H}_{\infty}$, we finally define its
encoding $|\tilde{\phi}\rangle$ as
$\sum_{s:|s|=\ell(|\phi\rangle)}|\tilde{s}\rangle\langle s|\phi\rangle$. Note
that $\ell(|\tilde{\phi}\rangle)=3\ell(|\phi\rangle)+3$.

To mark the end of a series of encoded objects, we use a designated separator,
say, $r_{0}$ in $\\{0,1\\}^{+}$. We fix such $r_{0}$ in the following
discussion. Since such a series of encoded objects has length proportional to
the section size $|r_{0}|$, any encoding $x$ satisfies $|x|=k|r_{0}|$ for an
appropriate number $k\in\mathbb{N}^{+}$. It is therefore possible to partition
$x$ section-wise as $x_{1}x_{2}\cdots x_{k}$ with $|x_{i}|=|r_{0}|$ for any
$i\in[k]$. In particular, we require that no $x_{i}$ matches $r_{0}$. For
convenience, we say that $x$ _section-wise contains no $r_{0}$_ if $x_{i}\neq
r_{0}$ holds for all indices $i\in[k]$. Let
$NON_{r_{0}}=\\{x\in\\{0,1\\}^{+}\mid|x|\equiv
0\>(\mathrm{mod}\>|r_{0}|),\text{ $x$ section-wise contains no $r_{0}$ }\\}$.
Similarly, we set $NON_{r_{0}}(|\phi\rangle)=\\{x\in NON_{r_{0}}\mid\langle
xr_{0}|\phi\rangle\neq{\bf 0}\\}$. In particular, when $r_{0}=\hat{2}$, we
omit $r_{0}$ from $NON_{r_{0}}$ and $NON_{r_{0}}(|\phi\rangle)$.

###### Example 3.9

Fix $r_{0}\in\\{0,1\\}^{+}$. Choose strings
$x_{1},x_{2},x_{3}\in\\{0,1\\}^{|r_{0}|}$ satisfying $x_{i}\neq r_{0}$ for all
$i\in[3]$, and consider
$|\psi\rangle=|x_{1}x_{2}x_{3}\rangle|r_{0}\rangle|\phi\rangle$,
$|\psi^{\prime}\rangle=|x_{1}x_{2}r_{0}x_{3}\rangle|\phi\rangle$, and
$|\psi^{\prime\prime}\rangle=|x_{1}r_{0}x_{2}x_{3}\rangle|\phi\rangle$. We
then obtain $NON_{r_{0}}(|\psi\rangle)=\\{x_{1}x_{2}x_{3}\\}$,
$NON_{r_{0}}(|\psi^{\prime}\rangle)=\\{x_{1}x_{2}\\}$, and
$NON_{r_{0}}(|\psi^{\prime\prime}\rangle)=\\{x_{1}\\}$. By contrast, when
$|\psi\rangle$ has the form
$(\alpha|x_{1}\rangle|r_{0}\rangle+\beta|x_{2}\rangle|r_{0}\rangle)|\phi\rangle$,
$NON_{r_{0}}(|\psi\rangle)$ equals $\\{x_{1},x_{2}\\}$.

As another example, if $x=0111$ and $r_{0}=\hat{2}$, then
$\widetilde{x}=\hat{0}\hat{1}\hat{1}\hat{1}\hat{\dashv}$. Clearly, we obtain
$|\widetilde{x}|\equiv 0\>(\mathrm{mod}\>|r_{0}|)$ and thus
$NON_{r_{0}}(|\widetilde{x}\rangle|r_{0}\rangle|\phi\rangle)=\\{\widetilde{x}\\}$.

We then need a quantum function that splits an input into sections and apply
“section-wise” two pre-determined quantum operations. We actually introduce
two slightly different _code skipping schemes_ described below. We do not
unconditionally include them to $EQS$ but we use them in a certain restricted
situation, which will be discussed later. Such a restriction is in fact
necessary because these schemes are too powerful in use for quantum
polylogtime computability.

  1. *)

The _code skipping scheme_. From $g$, $h$ and $r_{0}\in\\{0,1\\}^{+}$, we
define $CodeSKIP_{+}[r_{0},g,h]$ and $CodeSKIP_{-}[r_{0},g,h]$ as follows:

    1. (i)

$CodeSKIP_{+}[r_{0},g,h](|\phi\rangle)=\left\\{\begin{array}[]{ll}|\phi\rangle\hskip
110.96574pt\mbox{if $NON_{r_{0}}(|\phi\rangle)=\varnothing$,}&\\\ \sum_{x\in
NON_{r_{0}}(|\phi\rangle)}(g(|xr_{0}\rangle)\otimes h(\langle
xr_{0}|\phi\rangle))\hskip 2.84526pt\mbox{otherwise.}&\end{array}\right.$

    2. (ii)

$CodeSKIP_{-}[r_{0},g,h](|\phi\rangle)=\left\\{\begin{array}[]{ll}|\phi\rangle\hskip
110.96574pt\mbox{if $NON_{r_{0}}(|\phi\rangle)=\varnothing$,}&\\\ \sum_{x\in
NON_{r_{0}}(|\phi\rangle)}(g(|x\rangle)\otimes h(\langle x|\phi\rangle))\hskip
19.91692pt\mbox{otherwise.}&\end{array}\right.$

The difference between $CodeSKIP_{+}[r_{0},g,h]$ and $CodeSKIP_{-}[r_{0},g,h]$
looks subtle but becomes clear in the following example. When
$|\phi\rangle=|x\rangle|r_{0}\rangle|y\rangle$ with $|x|=|r_{0}|$ and $x\neq
r_{0}$, it follows that
$CodeSKIP_{+}[r_{0},g,h](|\phi\rangle)=g(|xr_{0}\rangle)\otimes h(|y\rangle)$
but $CodeSKIP_{-}[r_{0},g,h](|\phi\rangle)=g(|x\rangle)\otimes
h(|r_{0}y\rangle)$. These schemes are not interchangeable in many
applications.

Notice that, when $h=I$ in the above scheme, $CodeSKIP_{+}[r_{0},g,I]$ and
$CodeSKIP_{-}[r_{0},g,I]$ are query-independent.

Here, we present a few more examples.

###### Example 3.10

Let $g=ROT_{\pi/4}$ and $h=NOT$. Let $r_{0}=0^{5}$ and let
$|\phi\rangle=|x_{1}x_{2}\rangle|r_{0}\rangle|x_{3}x_{4}\rangle|r_{0}\rangle|\psi\rangle$
for binary strings $x_{i}=bin_{5}(i)$ and a qustring $|\psi\rangle$. Since
$NON_{r_{0}}(|\phi\rangle)=\\{x_{1}x_{2}\\}$, we obtain
$CodeSKIP_{+}[r_{0},g,h](|\phi\rangle)=ROT_{\pi/4}(|x_{1}x_{2}r_{0}\rangle)\otimes
NOT(|x_{3}x_{4}r_{0}\rangle|\psi\rangle)$.

Let
$|\phi^{\prime}\rangle=\alpha|x_{1}r_{0}\rangle|\psi_{1}\rangle+\beta|x_{2}r_{0}\rangle|\psi_{2}\rangle$
with $|x_{1}|=|x_{2}|=|r_{0}|$ and $x_{1},x_{2}\notin\\{r_{0}\\}$. Note that
$NON_{r_{0}}=\\{x_{1},x_{2}\\}$. It then follows that
$CodeSKIP_{+}[r_{0},g,h](|\psi^{\prime}\rangle)=\alpha
g(|x_{1}r_{0}\rangle)\otimes h(|\psi_{1}\rangle)+\beta
g(|x_{2}r_{0}\rangle)\otimes h(|\psi_{2}\rangle)$.

We wish to recall the two useful quantum functions $REMOVE$ (removal) and
$REP$ (replacement) introduced in [27]. We introduce the “code-controlled”
versions of them. Let $r_{0}\in\\{0,1\\}^{+}$ be a separator.

  1. (i) $CodeREMOVE[r_{0}](|\phi\rangle)=\left\\{\begin{array}[]{ll}|\phi\rangle\hskip 133.72795pt\mbox{if $NON_{r_{0}}(|\phi\rangle)=\varnothing$,}&\\\ \sum_{x\in NON_{r_{0}}(|\phi\rangle)}\sum_{a\in\\{0,1\\}}(\langle a|x\rangle\otimes|ar_{0}\rangle\otimes\langle xr_{0}|\phi\rangle)\hskip 2.84526pt\mbox{o.w.}&\end{array}\right.$

  2. (ii) $CodeREP[r_{0}](|\phi\rangle)=\left\\{\begin{array}[]{ll}|\phi\rangle\hskip 147.95433pt\mbox{if $NON_{r_{0}}(|\phi\rangle)=\varnothing$,}&\\\ \sum_{x\in NON_{r_{0}}(|\phi\rangle)}\sum_{u:|u|=|x|-1}(\langle u|x\rangle\otimes|ur_{0}\rangle\otimes\langle xr_{0}|\phi\rangle)\hskip 2.84526pt\mbox{o.w.}&\end{array}\right.$

A quantum function $g$ is called _query-independent_ if, in the process of
constructing $g$, on any input of the form $|xr_{0}\rangle|\phi\rangle$, any
quantum function that appears in this process does not directly access
$|\phi\rangle$ and does not depend on $|\phi\rangle$. This implies that
$g(|xr_{0}\rangle|\phi\rangle)=g(|xr_{0}\rangle)\otimes|\phi\rangle$ for any
$x$ and $|\phi\rangle$. Using this terminology, the quantum functions
$CodeREMOVE[r_{0}]$ and $CodeREP[r_{0}]$ are query-independent.

###  3.3 Code-Controlled Fast Quantum Recursion Scheme

Let us introduce a new scheme, called Scheme IV, which is a variant of the
multi-qubit quantum recursion scheme (Scheme T) geared up with the code
skipping schemes in Section 3.2. Recall that, in Scheme T, we inductively
discard $k$ qubits from an input quantum state $|\phi\rangle$ until we consume
all qubits except for the last $t$ qubits. Unlike Scheme T, since our access
to input qubits is quite limited, we need to split the whole input into two
separate parts, which play quite different roles as we will see.

Before introducing the complexity class $EQS$, for each quantum function $f$
in $EQS_{0}$, we define its “code-controlled” version $f^{*}$ by setting
$f^{*}(|xr_{0}\rangle|\phi\rangle)=|xr_{0}\rangle|\phi\rangle$ if $|x|\leq 2$,
$\ell(|\phi\rangle)\leq 1$, or $|x|>|r_{0}|\mathrm{ilog}(\ell(|\phi\rangle))$,
and $f^{*}(|xr_{0}\rangle|\phi\rangle)=f(|xr_{0}\rangle)\otimes|\phi\rangle$
otherwise. In the rest of this work, it is convenient to identify $f$ with
$f^{*}$. It is important to note that $f^{*}$ does not access $|\phi\rangle$
in $|xr_{0}\rangle|\phi\rangle$ because $f$ accesses only the first and/or the
second qubit.

In the fast quantum recursion, on the contrary, we discard a half of the
second part of input quantum state $|xr_{0}\rangle\otimes|\phi\rangle$. By
halving the input at each step, this recursive process quickly terminates.

###### Definition 3.11

We introduce the following scheme.

  1. IV.

The _code-controlled fast quantum recursion scheme_. From quantum functions
$d$, $g$, $h$, a number $t\in\mathbb{N}^{+}$, a string
$r_{0}\in\\{0,1\\}^{+}$, ${\cal
P}_{|r_{0}|}=\\{p_{u}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$, and ${\cal
F}_{|r_{0}|}=\\{f_{u}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$ (where $d$ is not defined
using $MEAS[\cdot]$ but $d$ and $h$ may be defined using $CodeSKIP_{+}[\cdot]$
and $CodeSKIP_{-}[\cdot]$), we define $F\equiv CFQRec_{t}[r_{0},d,g,h|{\cal
P}_{|r_{0}|},{\cal F}_{|r_{0}|}]$ as follows:

(i) $F(|xr_{0}\rangle|\phi\rangle)=g(|xr_{0}\rangle|\phi\rangle)$ if
$x=\lambda$, $\ell(|\phi\rangle)\leq t$, or $|x|>|r_{0}|k$,
(ii) $F(|xr_{0}\rangle|\phi\rangle)\\\ \noindent\hskip
28.45274pt=\sum_{u:|u|=|r_{0}|}\sum_{v:|v|=\ell(\langle
u|xr_{0}\rangle)}(h(|u\rangle|v\rangle)\otimes p_{u}^{-1}(\langle
v|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle))$ otherwise,
where $k=\mathrm{ilog}(\ell(|\phi\rangle))$, $x\in NON_{r_{0}}$,
$|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle=\sum_{s:|s|=m(|\phi\rangle)}(f_{u}(\langle
u|x^{\prime}r_{0}\rangle\otimes|s\rangle)\otimes\langle
s|\psi_{p_{u},\phi}\rangle)$, $d(|xr_{0}\rangle)=|x^{\prime}r_{0}\rangle$ with
$x^{\prime}\in NON_{r_{0}}$, $|\psi_{p_{u},\phi}\rangle=p_{u}(|\phi\rangle)$,
and $f_{u}\in\\{F,I\\}$. Moreover, $p_{u}$ and $m(\cdot)$ must satisfy that
either $p_{u}=I$ and $m=LH$, or $p_{u}=HalfSWAP$ and $m=RH$. In the other case
where an input, say, $|y\rangle$ to $F$ satisfies
$NON_{r_{0}}(|y\rangle)=\varnothing$, we automatically set
$F(|y\rangle)=|y\rangle$. For readability, the prefix term “code-controlled”
is often dropped and $|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle$ is
expressed briefly as $|\zeta_{u,p_{u},\phi}\rangle$ as long as
$x^{\prime}r_{0}$ is clear from the context.

The quantum functions $d,g,h$ in the above definition are called _ground
(quantum) functions_ of $F$. If $g$ is query-independent, Scheme IV is said to
be _query-independent_.

Although the above description of the conditions (i)–(ii) in Scheme IV refers
to a classical string $xr_{0}$, when we plug in any quantum state
$|\psi\rangle=\sum_{x}\alpha_{x}|xr_{0}\rangle\otimes|\phi_{x}\rangle$ to $F$,
we obtain the result $\sum_{x}\alpha_{x}F(|xr_{0}\rangle|\phi_{x}\rangle)$.

As a special case of Scheme IV, when $r_{0}=1$, Item (ii) has the following
simple form:

(ii′)
$F(|0^{n}1\rangle|\phi\rangle)=\sum_{v:|v|=n}h(|0\rangle\otimes|v\rangle)\otimes
p_{0}^{-1}(\langle v|\zeta_{0,p_{0},\phi}^{(0^{n}1)}\rangle)$,

where
$|\zeta_{0,p_{0},\phi}^{(0^{n}1)}\rangle=\sum_{s:|s|=m(|\phi\rangle)}(f_{0}(|0^{n-1}1\rangle\otimes|s\rangle)\otimes\langle
s|\psi_{p_{0},\phi}\rangle)$.

Since $p_{u}\in\\{I,HalfSWAP\\}$ and $|x^{\prime}|=|x|$, it follows that
$\ell(|\psi_{u,p_{u},\phi}\rangle)=\ell(|\phi\rangle)$,
$\ell(|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle)=\ell(\langle
u|x^{\prime}r_{0}\rangle)+\ell(|\phi\rangle)$, and $\ell(\langle
v|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle)=\ell(|\phi\rangle)$. In
Item (ii), since the size $|s|$ is exactly $LH(|\phi\rangle)$ (or
$RH(|\phi\rangle)$), $f_{u}$ takes inputs of length
$(\ell(|x^{\prime}r_{0}\rangle)-|r_{0}|)+\lceil\ell(|\phi\rangle)/2\rceil$ (or
$(\ell(|x^{\prime}r_{0}\rangle)-|r_{0}|)+\lfloor\ell(|\phi\rangle)/2\rfloor$).
Hence, within $\lceil\log{\ell(|\phi\rangle)}\rceil$ recursive steps, the
whole process terminates.

To understand Scheme IV better, we provide in Example 3.12 a simple example of
how to calculate the quantum function $F\equiv CFQRec_{t}[r_{0},d,g,h|{\cal
P}_{|r_{0}|},{\cal F}_{|r_{0}|}]$ step by step.

###### Example 3.12

In this example, we wish to show how to calculate the quantum function
$F\equiv CFQRec_{t}[r_{0},d,g,h|{\cal P}_{|r_{0}|},{\cal F}_{|r_{0}|}]$
defined with the parameters $t=1$, $r_{0}=1$, $d=I$, and $g\equiv I$.
Furthermore, $h$ is defined as $h(|01\rangle)=|11\rangle$ and
$h(|010^{m}1\rangle)=|10^{m+1}1\rangle$ for any $m\in\mathbb{N}$. We further
set $p_{0}=HalfSWAP$, $p_{1}=I$, $f_{0}=F$, and $f_{1}=I$. Let
$x\in\\{0\\}^{*}$ and $|\phi\rangle\in{\cal H}_{\infty}$. In what follows, we
will calculate $F(|x1\rangle|\phi\rangle)$ in a “bottom-up” fashion.

(1) We start with the base case. If $x=\lambda$, then
$F(|1\rangle|\phi\rangle)=g(|1\rangle|\phi\rangle)=|1\rangle|\phi\rangle$. If
$x=0^{m}1$ with $m\geq 1$ and $\ell(|\phi\rangle)\leq 1$, then
$F(|0^{m}1\rangle|\phi\rangle)=g(|0^{m}1\rangle|\phi\rangle)=|0^{m}1\rangle|\phi\rangle$.

(2) Hereafter, we assume that $x\neq\lambda$ and $\ell(|\phi\rangle)\geq 2$.
For simplicity, let $|\phi\rangle$ denote $|u\rangle$ for a certain string
$u\in\\{0,1\\}^{*}$. When $u=u_{1}u_{2}\cdots u_{n}$ and $1\leq i<j\leq n$, we
use the succinct notation $u_{[i,j]}$ to express the string
$u_{i}u_{i+1}\cdots u_{j}$.

(a) We first calculate $F(|01\rangle|u\rangle)$ for $u=u_{1}u_{2}u_{3}u_{4}$.
Since $|u\rangle=|u_{[1,2]}\rangle|u_{[3,4]}\rangle$, we obtain
$p_{0}(|u\rangle)=|u_{[3,4]}\rangle|u_{[1,2]}\rangle$. We also obtain
$|\zeta_{0,p_{0},u}\rangle=F(|1\rangle|u_{[3,4]}\rangle)\otimes|u_{[1,2]}\rangle=|1\rangle\otimes|u_{[3,4]}\rangle|u_{[1,2]}\rangle$
by (1), and thus $F(|01\rangle|u\rangle)$ equals
$h(|0\rangle\otimes|1\rangle)\otimes
p_{0}^{-1}(|u_{[3,4]}\rangle|u_{[1,2]}\rangle)$, which is
$|11\rangle|u_{[1,2]}\rangle|u_{3,4]}\rangle=|11\rangle|u\rangle$.

(b) Next, we calculate $F(|001\rangle|u^{\prime}\rangle)$ for
$u^{\prime}=u_{1}u_{2}\cdots u_{8}$. Note that
$|\zeta_{0,p_{0},u^{\prime}}\rangle=F(|01\rangle|u^{\prime}_{[5,8]}\rangle)\otimes|u^{\prime}_{[1,4]}\rangle=|11\rangle\otimes|u^{\prime}_{[5,8]}\rangle|u^{\prime}_{[1,4]}\rangle$
by (a). From this, we obtain
$F(|001\rangle|u^{\prime}\rangle)=h(|0\rangle\otimes|11\rangle)\otimes
p_{0}^{-1}(|u^{\prime}_{[5,8]}\rangle|u^{\prime}_{[1,4]}\rangle)=|101\rangle|u^{\prime}\rangle$.

###  3.4 Power of Scheme IV

In what follows, we intend to show the usefulness of Scheme IV by applying it
to define the quantum function $SIZE$ that calculates the value
$\mathrm{ilog}(\ell(|\phi\rangle))$ if this value does not exceed input size
$m$. More formally, for any $|\phi\rangle\in{\cal H}_{\infty}$ and
$m\in\mathbb{N}^{+}$, we define $SIZE_{1}$ as
$SIZE_{1}(|0^{m}1\rangle|\phi\rangle)=|0^{k}1\rangle|0^{m-k-1}1\rangle|\phi\rangle$
if $\ell(|\phi\rangle)\leq 2^{m-1}$, where
$k=\mathrm{ilog}(\ell(|\phi\rangle))$, and
$SIZE_{1}(|0^{m}1\rangle|\phi\rangle)=|0^{m}1\rangle|\phi\rangle$ otherwise.
More generally, for any $r_{0}\notin\\{0\\}^{*}$ with $|r_{0}|\geq 1$, we
define $SIZE_{r_{0}}$ as
$SIZE_{r_{0}}(|0^{m|r_{0}|}r_{0}\rangle|\phi\rangle)=|0^{k|r_{0}|}r_{0}\rangle|0^{(m-k-1)|r_{0}|}r_{0}\rangle|\phi\rangle$.

For convenience, we use the notation $EQS_{0}+IV$ to express the set of
quantum functions constructed by applying Schemes I–IV.

###### Lemma 3.13

Let $r_{0}\notin\\{0\\}^{*}$ with $|r_{0}|\geq 1$. The above quantum function
$SIZE_{r_{0}}$ can be definable within $EQS_{0}+IV$.

###### Proof.

We first prove the lemma for the simple case of $r_{0}=1$. Given
$m\in\mathbb{N}^{+}$ and $|\phi\rangle\in{\cal H}_{\infty}$, let
$|\xi\rangle=|0^{m}1\rangle|\phi\rangle$. Recall the quantum function
$LengthQ_{1}$ from Lemma 3.4 and, for simplicity, write $g$ for $LengthQ_{1}$.
It then follows that $g(|1\rangle)=|1\rangle$ and
$g(|0^{m}1\rangle)=|10^{m-1}1\rangle$ if $m\geq 1$. We denote by $F$ the
quantum function $CFQRec_{1}[1,I,g,I|\\{p_{0},p_{1}\\},\\{f_{0},f_{1}\\}]$
with the parameters $f_{0}=F$, $f_{1}=I$, and $p_{0}=p_{1}=I$.

If either $m=0$ or $\ell(|\phi\rangle)\leq 1$, then $F(|1\rangle|\phi\rangle)$
equals $g(|1\rangle)\otimes|\phi\rangle=|1\rangle|\phi\rangle$. Hereafter, we
assume that $m\geq 1$ and $\ell(|\phi\rangle)\geq 2$. By induction hypothesis,
we obtain
$F(|0^{m-1}1\rangle\otimes|s\rangle)=|0^{k-1}1\rangle|0^{m-k-1}1\rangle|\phi\rangle$
if $\ell(|s\rangle)\leq 2^{m-2}$ and $k-1=\mathrm{ilog}(\ell(|s\rangle))$.
Starting with $|\xi\rangle$, $F(|0^{m}1\rangle|\phi\rangle)$ equals
$|0\rangle\otimes\sum_{s:|s|=LH(|\phi\rangle)}F(|0^{m-1}1\rangle\otimes|s\rangle)\otimes\langle
s|\phi\rangle=|0\rangle\otimes|0^{k-1}1\rangle|0^{m-k-1}1\rangle|\phi\rangle=|0^{k}1\rangle|0^{m-k-1}1\rangle|\phi\rangle$.

The general case of $r_{0}\neq 1$ is similarly handled. The desired quantum
function $SIZE_{1}$ is therefore set to be $F$. ∎

Given an input of the form $|xr_{0}\rangle|\phi\rangle$, it is possible to
apply any quantum function $g$ in $EQS_{0}$ only to the first segment
$|xr_{0}\rangle$ with keeping the second segment $|\phi\rangle$ intact. This
can be done by the use of Scheme IV as follows.

###### Lemma 3.14

For any $r_{0}\in\\{0,1\\}^{+}$ and any $g\in\widehat{EQS}_{0}$ satisfying
$g(|r_{0}\rangle\otimes|\phi\rangle)=g(|r_{0}\rangle)\otimes|\phi\rangle$,
there exists a quantum function $F$ definable within $EQS_{0}+IV$ such that
$F(|xr_{0}\rangle|\phi\rangle)=g(|xr_{0}\rangle)\otimes|\phi\rangle$ for any
$x\in NON_{r_{0}}$ and any $|\phi\rangle\in{\cal H}_{\infty}$.

###### Proof.

Let ${\cal P}_{|r_{0}|}=\\{p_{u}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$ with $p_{u}=I$
for all $u$’s and ${\cal F}_{|r_{0}|}=\\{f_{u}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$.
Recall the quantum function $Skip_{k}[g]$ from Lemma 3.3. For a given
$g\in\widehat{EQS}_{0}$, we set $h\equiv g\circ Skip_{|r_{0}|}[g^{-1}]$.
Notice that $h$ is in $\widehat{EQS}_{0}$ because $g^{-1}$ exists in
$\widehat{EQS}_{0}$ (as shown in Lemma 4.3). The desired quantum function $F$
is defined by Scheme IV as $F\equiv CFQRec_{1}[r_{0},I,g,h|{\cal
P}_{|r_{0}|},{\cal F}_{|r_{0}|}]$. Here, we take $f_{u}=F$ for all
$u\in\\{0,1\\}^{|r_{0}|}$. We then obtain
$F(|r_{0}\rangle|\phi\rangle)=g(|r_{0}\rangle|\phi\rangle)=g(|r_{0}\rangle)\otimes|\phi\rangle$.

Assume by induction hypothesis that
$F(|xr_{0}\rangle|\phi\rangle)=g(|xr_{0}\rangle)\otimes|\phi\rangle$. Let us
consider $F(|axr_{0}\rangle|\phi\rangle)$ for $a\in\\{0,1\\}^{|r_{0}|}\cap
NON_{r_{0}}$. It then follows that
$|\zeta_{a,I,\phi}^{(xr_{0})}\rangle=\sum_{s:|s|=LH(|\phi\rangle)}(F(|xr_{0}\rangle\otimes|s\rangle)\otimes\langle
s|\phi\rangle)=\sum_{s:|s|=LH(|\phi\rangle)}(g(|xr_{0}\rangle)\otimes|s\rangle\langle
s|\phi\rangle)=g(|xr_{0}\rangle)\otimes|\phi\rangle$. Hence, we obtain
$F(|axr_{0}\rangle|\phi\rangle)=\sum_{v:|v|=|xr_{0}|}(h(|a\rangle|v\rangle)\otimes\langle
v|\zeta_{a,I,\phi}^{(xr_{0})}\rangle)=\sum_{v:|v|=|xr_{0}|}(h(|a\rangle|v\rangle)\otimes\langle
v|\psi_{g,xr_{0}}\rangle\otimes|\phi\rangle)=h(|a\rangle|\psi_{g,xr_{0}}\rangle)\otimes|\phi\rangle$
since $|v|=|xr_{0}|$, where $|\psi_{g,xr_{0}}\rangle=g(|xr_{0}\rangle)$. Note
that $h(|a\rangle\otimes g(|xr_{0}\rangle))=g(|a\rangle\otimes
g^{-1}(g(|xr_{0}\rangle))=g(|axr_{0}\rangle)$. ∎

As shown in Proposition 3.15, Scheme IV turns out to be so powerful that it
generates quantum functions, which can modify the first segment
$|xr_{0}\rangle$ $\mathrm{ilog}(\ell(|\phi\rangle))$ times for any given input
of the form $|xr_{0}\rangle|\phi\rangle$.

Let $h$ be any quantum function defined by Schemes I–III. Consider a quantum
function $\hat{h}$ defined inductively as

$(*)\hskip 14.22636pt\hat{h}(|r_{0}\rangle)=|r_{0}\rangle\hskip
8.53581pt\text{ and }\hskip
8.53581pt\hat{h}(|xr_{0}\rangle)=\sum_{u:|u|=|r_{0}|}h(|u\rangle\otimes\hat{h}(\langle
u|xr_{0}\rangle))$

for any $x\in NON_{r_{0}}$ with $x\neq\lambda$. This construction looks
similar to Scheme T but it is not supported in our system $EQS_{0}+IV$.
Nevertheless, as shown in Proposition 3.15, whenever the length of an input
qustring $|xr_{0}\rangle$ is “short” enough compared to another supplemental
input qustring $|\phi\rangle$, it may be possible to “realize” this scheme
within $EQS_{0}+IV$.

As a concrete example of the above function $\hat{h}$, we consider
$CodeSKIP_{+}[r_{0},g,I]$ (as well as $CodeSKIP_{-}[r_{0},g,I]$) for a norm-
preserving quantum function $g$. To see this, we set $h$ to be $g\circ
Skip_{|r_{0}|}[g^{-1}]$ and take $\hat{h}$ defined from $h$ by the scheme (*).
Here, we wish to claim that this quantum function $\hat{h}$ coincides with
$CodeSKIP_{+}[r_{0},g,I]$. Initially, we obtain
$CodeSKIP_{+}[r_{0},g,I](|r_{0}\rangle)=|r_{0}\rangle=\hat{h}(|r_{0}\rangle)$
by (*). For any two strings $a,x\in NON_{r_{0}}\cap\\{0,1\\}^{+}$ with
$|a|=|r_{0}|$, it follows from (*) that
$\hat{h}(|axr_{0}\rangle)=\sum_{u:|u|=|r_{0}|}h(|u\rangle\otimes\hat{h}(\langle
u|axr_{0}\rangle))=h(|a\rangle\otimes
CodeSKIP_{+}[r_{0},g,I](|xr_{0}\rangle))=h(|a\rangle\otimes
g(|xr_{0}\rangle))=g\circ Skip_{|r_{0}|}[g^{-1}](|a\rangle\otimes
g(|xr_{0}\rangle))=g(|axr_{0}\rangle)$.

The quantum function $\hat{h}$ given by (*) may not be constructed by the use
of Schemes I–IV since the $k$-qubit quantum recursion scheme is required. For
relatively “short” inputs, however, it is possible to compute the value of
$\hat{h}$ within the existing system $EQS_{0}+IV$.

###### Proposition 3.15

For a quantum function $h$ in $EQS_{0}$, let $\hat{h}$ satisfy the
aforementioned condition (*). There exists a quantum function $F$ definable
within $EQS_{0}+IV$ such that, for any $(x,|\phi\rangle)$ with $x\in
NON_{r_{0}}$ and $|\phi\rangle\in{\cal H}_{\infty}$, if
$|x|\leq|r_{0}|\log{\ell(|\phi\rangle)}$, then
$F(|xr_{0}\rangle|\phi\rangle)=\hat{h}(|xr_{0}\rangle)\otimes|\phi\rangle$
hold. However, there is no guarantee that $F(|xr_{0}\rangle|\phi\rangle)$
matches $\hat{h}(|xr_{0}\rangle)\otimes|\phi\rangle$ when
$|x|>|r_{0}|\log\ell(|\phi\rangle)$.

###### Proof.

Assume that $|x|\leq|r_{0}|\log{\ell(|\phi\rangle)}$. Consider the quantum
function $F\equiv CFQRec_{|r_{0}|-1}[r_{0},I,g,h|{\cal P}_{|r_{0}|},{\cal
F}_{|r_{0}|}]$, where ${\cal
P}_{|r_{0}|}=\\{p_{u}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$ and ${\cal
F}_{|r_{0}|}=\\{f_{u}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$ with $p_{u}\equiv I$ and
$f_{u}\equiv F$ for all $u\in\\{0,1\\}^{|r_{0}|}$. We show the proposition by
induction on the number of applications of $F$. In the base case, we obtain
$F(|r_{0}\rangle|\phi\rangle)=|r_{0}\rangle|\phi\rangle=\hat{h}(|r_{0}\rangle)\otimes|\phi\rangle$
since $\hat{h}(|r_{0}\rangle)=|r_{0}\rangle$ by (*). Next, we consider any
string $ax$ with $a\in\\{0,1\\}^{|r_{0}|}\cap NON_{r_{0}}$ and $x\in
NON_{r_{0}}$. We obtain
$F(|xr_{0}\rangle|\phi\rangle)=\hat{h}(|xr_{0}\rangle)\otimes|\phi\rangle$ by
induction hypothesis. It thus follows that
$F(|axr_{0}\rangle|\phi\rangle)=\sum_{v:|v|=|xr_{0}|}(h(|a\rangle\otimes|v\rangle)\otimes\langle
v|\zeta_{a,I,\phi}^{(xr_{0})}\rangle)$, where
$|\zeta_{a,I,\phi}^{(xr_{0})}\rangle=\sum_{s:|s|=LH(|\phi\rangle)}(F(|xr_{0}\rangle\otimes|s\rangle)\otimes\langle
s|\phi\rangle)$. Since
$F(|xr_{0}\rangle|\phi\rangle)=\hat{h}(|xr_{0}\rangle)\otimes|\phi\rangle$,
$|\zeta_{a,I,\phi}^{(xr_{0})}\rangle$ equals
$\sum_{s:|s|=LH(|\phi\rangle)}(\hat{h}(|xr_{0}\rangle)\otimes|s\rangle\otimes\langle
s|\phi\rangle)=\hat{h}(|xr_{0}\rangle)\otimes|\phi\rangle$. Let
$|\psi_{\hat{h},xr_{0}}\rangle=\hat{h}(|xr_{0}\rangle)$. We then obtain
$F(|axr_{0}\rangle|\phi\rangle)=\sum_{v:|v|=|xr_{0}|}(h(|a\rangle\otimes|v\rangle)\otimes\langle
v|\psi_{\hat{h},xr_{0}}\rangle)\otimes|\phi\rangle$. This implies
$F(|axr_{0}\rangle|\phi\rangle)=h(|a\rangle\otimes\hat{h}(|xr_{0}\rangle))\otimes|\phi\rangle=\hat{h}(|axr_{0}\rangle)\otimes|\phi\rangle$
by the definition of $\hat{h}$. ∎

Since $CodeSKIP_{+}[\cdot]$ is realized by the recursive construction of (*),
Proposition 3.15 allows us to use $CodeSKIP_{+}[\cdot]$ freely as if it is a
quantum function in $EQS_{0}+IV$.

###### Corollary 3.16

There exists a quantum function $F$ definable within $EQS_{0}+IV$ such that
$F(|xr_{0}\rangle|\phi\rangle)=CodeSKIP_{+}[r_{0},g,I](|xr_{0}\rangle|\phi\rangle)$
if $|x|\leq|r_{0}|\log{\ell(|\phi\rangle)}$.

###  3.5 Elementary Quantum Schemes

Formally, let us introduce $\widehat{EQS}$ and $EQS$. For this purpose, we
have already explained Schemes I–IV. Now, we wish to add the final piece of
construction scheme, called Scheme V, which intuitively supports successive
$\mathrm{ilog}(\ell(|\phi\rangle))$-applications of $Compo[g,g]$ for a
“single” quantum function $g$ to $|xr_{0}\rangle|\phi\rangle$.

###### Definition 3.17

We introduce the following scheme.

  1. V.

The _logarithmically-many composition scheme_. From $g$, we define $LCompo[g]$
as follows:

(i) $LCompo[g](|xr_{0}\rangle|\phi\rangle)=|xr_{0}\rangle\otimes|\phi\rangle$
if $x=\lambda$, $\ell(|\phi\rangle)\leq 1$, or $|x|>|r_{0}|k$,
(ii) $LCompo[g](|xr_{0}\rangle|\phi\rangle)=g^{k}(|xr_{0}\rangle|\phi\rangle)$
otherwise,
where $x\in NON_{r_{0}}$ and $k=\mathrm{ilog}(\ell(|\phi\rangle))$.

When $g$ is query-independent, we say that Scheme V is _query-independent_. We
remark that query-independent Scheme V is actually redundant because
Proposition 3.15 helps us realize $LCompo[g]$ by an application of Scheme IV.

###### Definition 3.18

The class $EQS$ is the smallest set of (code-controlled) quantum functions
that contains the quantum functions of Scheme I and is closed under Schemes
II–V. Similarly, $\widehat{EQS}$ is defined with no use of the item 6) of
Scheme I.

Note that any quantum function $F$ in $EQS$ is constructed by sequential
applications of Schemes I–V. Such a finite series is referred to as a
_construction history_ of $F$. The length of this construction history serves
as a _descriptive complexity measure_ of $F$. Refer to [27] for more
discussions.

##  4 Quantum Functions Definable within EQS

In Section 3.5, we have introduced the system $\widehat{EQS}$ as well as
$EQS$. In this section, we will study the basic properties of the quantum
functions in $\widehat{EQS}$ and $EQS$ and show several useful quantum
functions and extra schemes that are definable within $EQS$. One of the most
important properties we can show is an implementation of a simple “binary
search strategy” in $EQS$.

###  4.1 Basic Properties of $\widehat{EQS}$

The only difference between $\widehat{EQS}$ and $EQS$ is the free use of item
6) (quantum measurement) of Scheme I. Since $\widehat{EQS}$ does not involve
quantum measurement, we naturally expect that $\widehat{EQS}$ enjoys the
unitary nature of quantum computation described in the following two lemmas,
Lemmas 4.1–4.3.

###### Lemma 4.1

Any quantum function in $\widehat{EQS}$ is dimension-preserving and norm-
preserving.

###### Proof.

Let us check Schemes I–V separately to verify the lemma. Note that the items
1)–5) of Scheme I are obviously dimension-preserving and norm-preserving. The
lemma was already shown for Schemes II–III in [27]. Hereafter, we focus on
Scheme IV. Let $F\equiv CFQRec_{t}[r_{0},g,h|{\cal P}_{|r_{0}|},{\cal
F}_{|r_{0}|}]$. It is easy to check that $HalfSWAP$ is dimension-preserving
and norm-preserving. By induction hypothesis, we assume that $g$ and $h$ as
well as the quantum functions in ${\cal P}_{|r_{0}|}$ are dimension-preserving
and norm-preserving. In what follows, we argue by way of induction on the
input length of $F$ that $F$ is dimension-preserving and norm-preserving. If
either $x=\lambda$ or $\ell(|\phi\rangle)\leq t$, then we obtain
$\ell(F(|xr_{0}\rangle|\phi\rangle))=\ell(g(|xr_{0}\rangle|\phi\rangle))=\ell(|xr_{0}\rangle|\phi\rangle)$
and
$\|F(|xr_{0}\rangle|\phi\rangle)\|=\|g(|xr_{0}\rangle|\phi\rangle)\|=\||xr_{0}\rangle|\phi\rangle\|$.

Let us consider the case where $x\neq\lambda$ and $\ell(|\phi\rangle)>t$. We
obtain $\ell(h(|u\rangle|v\rangle)\otimes p_{u}^{-1}(\langle
v|\zeta_{u,p_{u},\phi}\rangle))=\ell(|u\rangle)+\ell(|v\rangle\langle
v|\zeta_{u,p_{u},\phi}\rangle)=\ell(|xr_{0}\rangle)-|r_{0}|+\ell(|\zeta_{u,p_{u},\phi}\rangle)$.
Thus, $\ell(|\zeta_{u,p_{u},\phi}\rangle)=\ell(\sum_{s}F(\langle
u|xr_{0}\rangle|s\rangle)\otimes\langle
s|\psi_{p_{u},\phi}\rangle)=\ell(\langle u|xr_{0}\rangle|\phi\rangle)$. By
induction hypothesis, we obtain $\ell(F(\langle
u|xr_{0}\rangle|s\rangle))=\ell(\langle u|xr_{0}\rangle|s\rangle)$. It then
follows that
$\ell(F(|xr_{0}\rangle|\phi\rangle))=\ell(\sum_{u}\sum_{v}h(|u\rangle|v\rangle)\otimes
p_{u}^{-1}(\langle
v|\zeta_{u,p_{u},\phi}\rangle))=\ell(|xr_{0}\rangle|\phi\rangle)$. The
property of norm-preserving is similarly proven.

For Scheme V, it is obvious that, if $g$ is dimension-preserving and norm-
preserving, then so is $g^{k}$ for any number $k\in\mathbb{N}^{+}$. Thus,
$LCompo[g]$ satisfies the lemma. ∎

We present useful construction schemes that are definable within $EQS$.

###### Lemma 4.2

Let $k\in\mathbb{N}^{+}$ and let ${\cal
G}_{k}=\\{g_{u}\\}_{u\in\\{0,1\\}^{k}}$ be a series of $EQS$-functions. The
following quantum functions all belong to $EQS$. The lemma also holds even if
$EQS$ is replaced by $\widehat{EQS}$. Let $|\phi\rangle$ be any quantum state
in ${\cal H}_{\infty}$ and let $x\in\\{0,1\\}^{k}$.

  1. 1.

$Compo[{\cal G}_{k}](|\phi\rangle)=g_{s_{1}}\circ g_{s_{2}}\circ\cdots\circ
g_{s_{2^{k}}}(|\phi\rangle)$. (multiple composition)

  2. 2.

$Branch_{k}[{\cal G}_{k}](|\phi\rangle)=|\phi\rangle$ if
$\ell(|\phi\rangle)<k$ and $Branch_{k}[{\cal
G}_{k}](|\phi\rangle)=\sum_{s:|s|=k}|s\rangle\otimes g_{s}(\langle
s|\phi\rangle)$ otherwise.

###### Proof.

(1)–(2) The above schemes were shown in [27, Lemma 3.6] to be valid for
$\Box^{\mathrm{QP}}_{1}$ and $\widehat{\Box^{\mathrm{QP}}_{1}}$, and their
argument also work for $EQS$ and $\widehat{EQS}$. ∎

As a quick example of $Branch_{k}[{\cal G}_{k}]$, we recall the quantum
function $Skip_{k}[g]$ from Lemma 3.3. It is clear that $Skip_{k}[g]$ is
simply defined to be $Branch_{k}[\\{g_{u}\\}_{u\in\\{0,1\\}^{k}}]$ with
$g_{u}=g$ for all $u\in\\{0,1\\}^{k}$.

For any given quantum function, when there exists another quantum function $g$
satisfying $f\circ g(|\phi\rangle)=g\circ f(|\phi\rangle)=|\phi\rangle$ for
any $|\phi\rangle\in{\cal H}_{\infty}$, we express this $g$ as $f^{-1}$ (or
$f^{\dagger}$) and call it the _inverse (function)_ of $f$.

###### Lemma 4.3

For any quantum function $g$ in $\widehat{EQS}$, its inverse function $g^{-1}$
exists in $\widehat{EQS}$. Moreover, if $g$ is in $\widehat{EQS}_{0}$, then
$g^{-1}$ is also in $\widehat{EQS}_{0}$

###### Proof.

For Scheme I, it easily follows that $PHASE_{\theta}^{-1}=PHASE_{-\theta}$,
$ROT_{\theta}^{-1}=ROT_{-\theta}$, $NOT^{-1}=NOT$, and $SWAP^{-1}=SWAP$. For
Scheme II, $Compo[g,h]^{-1}$ is $Compo[h^{-1},g^{-1}]$. For Scheme III, it
suffices to set $Branch[g,h]^{-1}$ to be $Branch[g^{-1},h^{-1}]$. For Scheme
IV, let $F\equiv CFQRec_{t}[r_{0},d,g,h|{\cal P}_{|r_{0}|},{\cal
F}_{|r_{0}|}]$. If $x=\lambda$, $\ell(|\phi\rangle)\leq t$, or $|x|>|r_{0}|k$
with $k=\mathrm{ilog}(\ell(|\phi\rangle))$, then we set $F^{-1}\equiv g^{-1}$.
In this case, we obtain $F^{-1}\circ
F(|xr_{0}\rangle|\phi\rangle)=F^{-1}(g(|xr_{0}\rangle|\phi\rangle))=g^{-1}\circ
g(|xr_{0}\rangle|\phi\rangle)=|xr_{0}\rangle|\phi\rangle$. Assuming otherwise,
we define $F^{-1}$ to be the consecutive applications of two quantum
functions: $h^{-1}$ and $G\equiv CFQRec_{t}[r_{0},d^{-1},g^{-1},I|{\cal
P}_{|r_{0}|},{\cal F}^{-1}_{|r_{0}|}]$, where ${\cal
F}^{-1}_{|r_{0}|}=\\{f_{u}^{-1}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$. It is important
to note that we do not use ${\cal
P}_{|r_{0}|}^{-1}=\\{p_{u}^{-1}\\}_{u\in\\{0,1\\}^{|r_{0}|}}$ in place of
${\cal P}_{|r_{0}|}$ in the definition of $G$. Let us show that $F^{-1}\circ
F(|xr_{0}\rangle|\phi\rangle)=|xr_{0}\rangle|\phi\rangle$. Assume that
$F(|xr_{0}\rangle|\phi\rangle)$ has the form
$\sum_{u:|u|=|r_{0}|}\sum_{v:|v|=\ell(\langle
u|xr_{0}\rangle)}(h(|u\rangle|v\rangle)\otimes p_{u}^{-1}(\langle
v|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle))$. We first apply $h^{-1}$
to the first $|xr_{0}|$ qubits and then obtain
$\sum_{u:|u|=|r_{0}|}\sum_{v:|v|=\ell(\langle
u|xr_{0}\rangle)}|u\rangle|v\rangle\otimes p_{u}^{-1}(\langle
v|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle))$. To this quantum state,
we further apply $G$. By an application of $p_{u}$ to $p_{u}^{-1}(\langle
v|\zeta^{(x^{\prime}r_{0})}_{u,p_{u},\phi}\rangle)$, we obtain
$\sum_{u:|u|=|r_{0}|}\sum_{v:|v|=\ell(\langle
u|xr_{0}\rangle)}|u\rangle|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle$.
Recall that
$|\zeta_{u,p_{u},\phi}^{(x^{\prime}r_{0})}\rangle=\sum_{s:|s|=m(|\phi\rangle)}(f_{u}(\langle
u|x^{\prime}r_{0}\rangle\otimes|s\rangle)\otimes\langle
s|\psi_{p_{u},\phi}\rangle)$. An application of $f_{u}^{-1}$ to $f_{u}(\langle
u|x^{\prime}r_{0}\rangle\otimes|s\rangle)$ leads to
$\sum_{u:|u|=|r_{0}|}\langle
u|x^{\prime}r_{0}\rangle\otimes|\psi_{p_{u},\phi}\rangle$. Since
$|x^{\prime}r_{0}\rangle=d(|xr_{0}\rangle)$, by applying $d^{-1}$ and
$p_{u}^{-1}$, we finally obtain $|xr_{0}\rangle\otimes|\phi\rangle$. For
Scheme V, it suffices to set $LCompo[g]^{-1}$ to be $LCompo[g^{-1}]$.

The above argument also proves the second part of the lemma. ∎

###  4.2 Section-Wise Handling of Binary Encoding

We have discussed the binary encodings of various objects in Section 3.2. We
further explore the characteristics of quantum functions that handle these
binary encodings.

Given $k$ encoded strings
$\widetilde{x_{1}},\widetilde{x_{2}},\ldots,\widetilde{x_{k}}$, we merge them
into a single string of the form
$\widetilde{x_{1}}\widetilde{x_{2}}\cdots\widetilde{x_{k}}\hat{2}$, where
$\hat{2}$ serves as an endmarker. Let $k\geq 2$ and let ${\cal
G}=\\{g_{i}\\}_{i\in[k]}$ denote a series of $k$ quantum functions. We then
consider a simultaneous application of all quantum functions in ${\cal G}$,
$MultiApp_{k}[{\cal G}]$, given as:

$\displaystyle MultiApp_{k}[\hat{2},{\cal
G}](|\widetilde{x_{1}}\widetilde{x_{2}}\cdots\widetilde{x_{k}}\hat{2}\rangle|\phi\rangle)$
$\displaystyle=$ $\displaystyle\hskip
5.69054ptg_{1}(|\widetilde{x_{1}}\rangle)\otimes
g_{2}(|\widetilde{x_{2}}\rangle)\otimes\cdots\otimes
g_{k}(|\widetilde{x_{k}}\hat{2}\rangle)\otimes|\phi\rangle.$

###### Lemma 4.4

For any $k\geq 2$ and any series ${\cal G}=\\{g_{i}\\}_{i\in[k]}$ of $k$
quantum functions, the above quantum function $MultiApp_{k}[\hat{2},{\cal G}]$
is definable from ${\cal G}$ and the code skipping scheme.

###### Proof.

Let ${\cal G}=\\{g_{i}\\}_{i\in[k]}$ be any series of $k$ quantum functions,
not necessarily in $EQS$. For brevity, let $\bar{r}_{0}=\hat{\dashv}$ and
$r_{0}=\hat{2}$. The quantum function $MultiApp_{k}[\hat{2},{\cal G}]$ can be
constructed from ${\cal G}$ by applying $CodeSKIP_{+}[\cdot]$ in the following
inductive way. Initially, we set $G_{[k,k]}\equiv
CodeSKIP_{+}[r_{0},g_{k},I]$. Let $X_{k}=\widetilde{x_{k}}$
($=\widehat{x_{k}}\hat{\dashv}$). Since
$NON_{r_{0}}(|X_{k}\rangle|r_{0}\rangle|\phi\rangle)=\\{X_{k}\\}$, we obtain
$G_{[k,k]}(|X_{k}\rangle|r_{0}\rangle|\phi\rangle)=g_{k}(|X_{k}\rangle|r_{0}\rangle)\otimes|\phi\rangle$.
Let $i\in[k-1]$ and set
$X_{i+1}=\widetilde{x_{i+1}}\widetilde{x_{i+2}}\cdots\widetilde{x_{k}}$. We
assume by induction hypothesis that
$G_{[i+1,k]}(|X_{i+1}\rangle|r_{0}\rangle|\phi\rangle)=g_{i+1}(|\widetilde{x_{i+1}}\rangle)\otimes
g_{i+2}(|\widetilde{x_{i+2}}\rangle)\otimes\cdots\otimes
g_{k}(|\widetilde{x_{k}}\rangle|r_{0}\rangle)\otimes|\phi\rangle$. We then
define $G_{[i,k]}\equiv CodeSKIP_{+}[\bar{r}_{0},g_{i},G_{[i+1,k]}]$. Since
$NON_{\bar{r}_{0}}(|X_{i}\rangle|r_{0}\rangle|\phi\rangle)=\\{\widehat{x_{i}}\\}$,
it follows that
$G_{[i,k]}(|X_{i}\rangle|r_{0}\rangle|\phi\rangle)=g_{i}(|\widehat{x_{i}}\bar{r}_{0}\rangle)\otimes
G_{[i+1,k]}(|X_{i+1}\rangle|r_{0}\rangle|\phi\rangle)=g_{i}(|\widetilde{x_{i}}\rangle)\otimes
g_{i+1}(|\widetilde{x_{i+1}}\rangle)\otimes\cdots\otimes
g_{k}(|\widetilde{x_{k}}\rangle|r_{0}\rangle)\otimes|\phi\rangle$.

The desired quantum function $MultiApp_{k}[r_{0},{\cal G}]$ therefore equals
$G_{[1,k]}$. ∎

By Lemma 4.4, we can construct $MultiApp_{k}[\hat{2},{\cal G}]$ from ${\cal
G}=\\{g_{i}\\}_{i\in[k]}$ and $CodeSKIP_{+}[r_{0},g,h]$. Since
$CodeSKIP_{+}[r_{0},g,h]$ stays outside of $EQS$, $MultiApp_{k}[\hat{2},{\cal
G}]$ in general does not belong to $EQS$. However, as the next lemma ensures,
we can use $MultiApp_{k}[\hat{2},{\cal G}]$ as if it is an $EQS$ function
under certain circumstances.

###### Lemma 4.5

Let $k\in\mathbb{N}^{+}$ and let ${\cal G}=\\{g_{i}\\}_{i\in[k]}$ be any
series of $k$ quantum functions in $EQS$. There exists a quantum function $F$
in $EQS$ such that
$F(|\hat{S}\widetilde{x}_{1}\widetilde{x}_{2}\cdots\widetilde{x}_{k}\hat{2}\rangle|\phi\rangle)=MultiApp_{k}[\hat{2},{\cal
G}](|\hat{S}\widetilde{x}_{1}\widetilde{x}_{2}\cdots\widetilde{x}_{k}\hat{2}\rangle|\phi\rangle)$
as long as
$|\hat{S}\widetilde{x}_{1}\widetilde{x}_{2}\cdots\widetilde{x}_{k}\hat{2}|\leq|\hat{2}|\log{\ell(|\phi\rangle)}$.
However, the equality may not hold if
$|\hat{S}\widetilde{x}_{1}\widetilde{x}_{2}\cdots\widetilde{x}_{k}\hat{2}|>|\hat{2}|\log{\ell(|\phi\rangle)}$.

###### Proof.

Let ${\cal G}=\\{g_{i}\\}_{i\in[k]}$ be as in the premise of the lemma. The
desired quantum function $F$ is defined to be $CFQRec_{1}[\hat{2},I,I,h|{\cal
P}_{3},{\cal F}_{3}]$, where ${\cal P}_{3}=\\{p_{u}\\}_{u\in\\{0,1\\}^{3}}$
with $p_{u}=I$ for all $u\in\\{0,1\\}^{3}$ and ${\cal
F}_{3}=\\{f_{u}\\}_{u\in\\{0,1\\}^{3}}$ with $f_{u}=F$ for all
$u\in\\{0,1\\}^{3}$. Moreover, $h$ is set to be
$Branch_{3}[\\{h_{u}\\}_{u\in\\{0,1\\}^{3}}]$ with $h_{\hat{S}}\equiv
MultiApp_{k}[\hat{2},{\cal G}]$ and $h_{u}\equiv I$ for any $u\neq\hat{S}$.
Since
$|\hat{S}\widetilde{x}_{1}\widetilde{x}_{2}\cdots\widetilde{x}_{k}\hat{2}|\leq|\hat{2}|\log{\ell(|\phi\rangle)}$,
in the following recursive process of computing $F$, it suffices to start with
$F(|\hat{2}\rangle|\phi^{\prime}\rangle)$ with
$\ell(|\phi^{\prime}\rangle)\geq 1$.

For each index $i\in[k]$, we abbreviate
$\widetilde{x_{i}}\widetilde{x_{i+1}}\cdots\widetilde{x_{k}}$ as $X_{i}$. Fix
$i\in[k]$ arbitrarily and assume that
$F(|X_{i}\hat{2}\rangle|\phi\rangle)=|X_{i}\hat{2}\rangle|\phi\rangle$. Note
that $|\zeta_{u,I,\phi}\rangle=\sum_{s:|s|=LH(|\phi\rangle)}(F(\langle
u|X_{i-1}\hat{2}\rangle|s\rangle)\otimes\langle s|\phi\rangle)$. If
$u=\widetilde{x_{i-1}}$, then
$|\zeta_{u,I,\phi}\rangle=\sum_{s:|s|=LH(|\phi\rangle)}(F(\langle
u|X_{i-1}\hat{2}\rangle|s\rangle)\otimes\langle
s|\phi\rangle)=\sum_{s:|s|=LH(|\phi\rangle)}(F(|X_{i}\hat{2}\rangle|s\rangle)\otimes\langle
s|\phi\rangle)=\sum_{s:|s|=LH(|\phi\rangle)}(|X_{i}\hat{2}\rangle|s\rangle\otimes\langle
s|\phi\rangle)=|X_{i}\hat{2}\rangle|\phi\rangle$. Thus, we obtain
$F(|X_{i}\hat{2}\rangle|\phi\rangle)=\sum_{u:|u|=|\hat{2}|}(h(|\widetilde{x_{i-1}}\rangle|X_{i}\hat{2}\rangle)\otimes\langle
X_{i}\hat{2}|\zeta_{\widetilde{x_{i-1}},I,\phi}\rangle=|X_{i-1}\hat{2}\rangle|\phi\rangle$.
Finally, we consider the case of
$|\hat{S}\rangle|X_{1}\hat{2}\rangle|\phi\rangle$. We then obtain
$F(|\hat{S}\rangle|X_{1}\hat{2}\rangle|\phi\rangle)=h(|\hat{S}\rangle|X_{1}\hat{2}\rangle)\otimes\langle
X_{1}\hat{2}|\zeta_{\hat{S},I,\phi}\rangle$. Since
$|\zeta_{\hat{S},I,\phi}\rangle=|X_{1}\hat{2}\rangle\otimes|\phi\rangle$, it
follows that
$F(|\hat{S}\rangle|X_{1}\hat{2}\rangle|\phi\rangle)=h(|\hat{S}\rangle|X_{1}\hat{2}\rangle)\otimes\langle
X_{1}\hat{2}|X_{1}\hat{2}\rangle|\phi\rangle=h(|\hat{S}\rangle|X_{1}\hat{2}\rangle)\otimes|\phi\rangle=Branch_{3}[\\{h_{u}\\}_{u\in\\{0,1\\}^{3}}](|\hat{S}\rangle|X_{1}\hat{2}\rangle)\otimes|\phi\rangle=MultiApp_{k}[\hat{2},{\cal
G}](|\hat{S}\rangle|X_{1}\hat{2}\rangle)\otimes|\phi\rangle$. ∎

In a certain limited case, it is possible to make a repeated application of
any quantum function within $EQS_{0}+IV$ (as well as $EQS$). To describe our
result, let us recall the 3-bit encodings of $\hat{T}$ and $\hat{S}$, which
respectively represent “time” and “separator”.

###### Proposition 4.6

Let $r_{0}\in\\{0,1\\}^{+}$ and let $g$ be any quantum function definable
within $EQS_{0}+IV$ (resp., $EQS$). There exists a quantum function $F$
definable within $EQS_{0}+IV$ (resp., $EQS$) such that, for any $|\phi\rangle$
and $x$, if $\ell(|\phi\rangle)\leq 1$, then
$F(|\hat{T}^{\>m(|\phi\rangle)}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle)=|\hat{T}^{\>m(|\phi\rangle)}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle$,
and otherwise,
$F(|\hat{T}^{\>m(|\phi\rangle)}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle)=|\hat{T}^{\>m(|\phi\rangle)}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)}(|x\hat{2}\rangle)\otimes|\phi\rangle$, where
$m(|\phi\rangle)=\mathrm{ilog}(\ell(|\phi\rangle))$.

###### Proof.

Let $F$ denote the desired quantum function. Note that
$|\hat{T}|=|\hat{S}|=3$. We set ${\cal P}_{3}=\\{p_{u}\\}_{u\in\\{0,1\\}^{3}}$
with $p_{u}=I$ for all $u\in\\{0,1\\}^{3}$, ${\cal
F}_{3}=\\{f_{u}\\}_{u\in\\{0,1\\}^{3}}$ with $f_{u}=F$ for all
$u\in\\{0,1\\}^{3}$, and ${\cal G}=\\{g_{u}\\}_{u\in\\{0,1\\}^{3}}$ with
$g_{\hat{T}}=CodeSKIP_{+}[\hat{S},I,g]$, and $g_{u}=I$ for all other indices
$u\in\\{0,1\\}^{3}-\\{\hat{T}\\}$. We then define $h$ to be $Branch_{3}[{\cal
G}]$. Finally, $F$ is defined by $F\equiv CFQRec_{1}[\hat{2},I,I,h|{\cal
P}_{3},{\cal F}_{3}]$.

For any index $i\in[0,m(|\phi\rangle)]_{\mathbb{Z}}$, we set
$z_{i}=\hat{T}^{m(|\phi\rangle)-i}$ . If $\ell(|\phi\rangle)\leq 1$, then we
obtain
$F(|z_{i}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle)=|z_{i}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle$
for any $i\in[0,m(|\phi\rangle)]_{\mathbb{Z}}$. Assume that
$\ell(|\phi\rangle)\geq 2$. Let $i\in[0,m(|\phi\rangle)]_{\mathbb{Z}}$ and set
$y=z_{i}\hat{S}x$. By induction hypothesis, we assume that
$F(|z_{i+1}\hat{S}\rangle|x\hat{2}\rangle|s\rangle=|z_{i+1}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i-1}(|x\hat{2}\rangle)\otimes|\phi\rangle$. Let us consider
the value $F(|z_{i}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle$. Note that
$h(|z_{i}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i}(|x\hat{2}\rangle))=CodeSKIP_{+}[\hat{S},I,g](|z_{i}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i}(|x\hat{2}\rangle))=|z_{i}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i-1}(|x\hat{2}\rangle)$. It thus follows that
$F(|z_{i}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle=\sum_{u:|u|=|\hat{2}|}\sum_{v:|v|=\ell(\langle
u|y\hat{2}\rangle)}(h(|u\rangle\otimes|v\rangle)\otimes\langle
v|\zeta_{u,I,\phi}\rangle)$, where $|\zeta_{u,I,\phi}\rangle$ is calculated as
follows. If $u\neq\hat{T}$, then $|\zeta_{u,I,\phi}\rangle={\bf 0}$.
Otherwise, $|\zeta_{u,I,\phi}\rangle$ equals
$\sum_{s:|s|=LH(|\phi\rangle)}(F(\langle
u|z_{i}\hat{S}\rangle|x\hat{2}\rangle\otimes|s\rangle)\otimes\langle
s|\phi\rangle)=\sum_{s:|s|=LH(|\phi\rangle)}(F(|z_{i+1}\hat{S}\rangle|x\hat{2}\rangle\otimes|s\rangle)\otimes\langle
s|\phi\rangle)=\sum_{s:|s|=LH(|\phi\rangle)}h(|z_{i+1}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i-1}(|x\hat{2}\rangle)\otimes|s\rangle\langle
s|\phi\rangle)=|z_{i+1}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i-1}(|x\hat{2}\rangle)\otimes|\phi\rangle$. Therefore, we
obtain
$F(|z_{i}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle)=|z_{i}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)-i}(|x\hat{2}\rangle)\otimes|\phi\rangle$. In particular,
when $i=0$, we conclude that
$F(|\hat{T}^{\>m(|\phi\rangle)}\hat{S}\rangle|x\hat{2}\rangle|\phi\rangle)=|\hat{T}^{\>m(|\phi\rangle)}\hat{S}\rangle\otimes
g^{m(|\phi\rangle)}(|x\hat{2}\rangle)\otimes|\phi\rangle$. ∎

###  4.3 Implementing the Binary Search Strategy

The strength of Scheme IV is further exemplified by an implementation of a
simple _binary search_ algorithm. Given any string $x\in\\{0,1\\}^{k}$ with
$k\geq 1$, assume that $x$ equals $bin_{k}(m)$ for a certain number
$m\in[2^{k}]$. For any $s$ with $|s|=2^{k}$ and $b\in\\{0,1\\}$, $BinSearch$
satisfies the following equality:
$BinSearch(|\widetilde{x}\rangle|\hat{b}\rangle|\hat{2}\rangle|s\rangle)=|\widetilde{x}\rangle|\widehat{b\oplus
s_{m}}\rangle|\hat{2}\rangle|s\rangle$, where $s_{m}$ is the $m$th bit of $s$.
This quantum function finds the $m$th bit of $s$ and extracts its bit $s_{m}$
from $s$ by way of modifying $|\hat{b}\rangle$ to $|\widetilde{b\oplus
s_{m}}\rangle$.

###### Theorem 4.7

The above quantum function $BinSearch$ is definable within $EQS_{0}+IV$.

###### Proof.

We remark that the length of $s$ given to
$BinSearch(|\widetilde{x}\rangle|\hat{b}\rangle|\hat{2}\rangle|s\rangle)$ is a
power of $2$. In this proof, we intend to use the quantum functions
$SecSWAP^{(3)}_{i,j}$ and $COPY_{1}$ from Lemmas 3.5(1) and 3.6, respectively.
Given any strings $x=x_{1}x_{2}\cdots x_{k}$, $s=s_{1}s_{2}\cdots s_{2^{k}}$,
and $b\in\\{0,1\\}$ associated with the number $m\in[2^{k}]$ satisfying
$x=bin_{k}(m)$, we define the quantum function $g$ by setting
$g(|{\hat{\dashv}}\rangle|\hat{b}\rangle|\hat{2}\rangle|s_{m}\rangle)=|{\hat{\dashv}}\rangle|\widehat{b\oplus
s_{m}}\rangle|\hat{2}\rangle|s_{m}\rangle$. Notice that $\hat{b}=00b$ and
$\widehat{b\oplus s_{m}}=00b^{\prime}$ with $b^{\prime}=b\oplus s_{m}$. It is
possible to realize $g$ by simply setting $g\equiv SWAP_{7,10}\circ
Skip_{5}[COPY_{1}]\circ SWAP_{7,10}$ since
$COPY_{1}(|b\rangle|s_{m}\rangle|w\rangle)=|b\oplus
s_{m}\rangle|s_{m}\rangle|w\rangle$ for any $w$. Let $p_{\hat{0}}\equiv I$,
$p_{\hat{1}}\equiv HalfSWAP$, and $p_{u}=I$ for all indices
$u\in\\{0,1\\}^{3}-\\{\hat{0},\hat{1}\\}$. We then define $F$ to be
$CFQRec_{1}[\hat{2},I,g,I|{\cal P}_{3},{\cal F}_{3}]$, where ${\cal
P}_{3}=\\{p_{u}\\}_{u\in\\{0,1\\}^{3}}$ and ${\cal
F}_{3}=\\{f_{u}\\}_{u\in\\{0,1\\}^{3}}$ with $f_{u}=F$ for all
$u\in\\{0,1\\}^{3}$. Now, our goal is to verify that $F$ indeed matches
$BinSearch$.

For any string $s\in\\{0,1\\}^{+}$ whose length is a power of $2$ and for any
number $m\in[|s|]$, we explain how to find the $m$th bit $s_{m}$ of $s$. We
first split $s$ into the left part and the right part of $s$ having lengths
$LH(|s|)$ and $RH(|s|)$, respectively. We assign $0$ to the left part and $1$
to the right part and we call the left part by $s_{0}$ and the right part by
$s_{1}$. Starting $s_{0}$ (resp., $s_{1}$), we further split it into the left
part, called $s_{00}$ (resp., $s_{10}$), and the right part, called $s_{01}$
(resp., $s_{11}$). Inductively, we repeat this process until the target
strings become single symbols. In the end, a string
$x\in\\{0,1\\}^{\mathrm{ilog}(|s|)}$ is assigned to the single symbol obtained
by a series of the above-described processes. We denote this unique symbol by
$s_{x}$. If $x=bin_{\mathrm{ilog}(|s|)}(m)$, then $s_{x}$ coincides with the
desired bit $s_{m}$. We treat $x$ as the binary representation of an index of
the symbol $s_{x}$ in $s$.

Let $X_{k+1}=\hat{\dashv}$ and let
$X_{i}=\widehat{x_{i}}\widehat{x_{i+1}}\cdots\widehat{x_{k}}\hat{\dashv}$ for
any index $i\in[k]$. Given $s$, we split it into two parts as
$s=s^{(r)}s^{(l)}$ with $|s^{(r)}|=LH(|s|)$ and $|s^{(l)}|=RH(|s|)$. We set
$m_{1}=m$ and, for each index $i\in[2,k]_{\mathbb{Z}}$, we take the number
$m_{i}$ satisfying $bin_{k-i+1}(m_{i})=x_{i}x_{i+1}\cdots x_{k}$. Note that
$s_{m_{i}}=s^{(r)}_{m_{i+1}}$ if $x_{i}=1$, and $s_{m_{i}}=s^{(l)}_{m_{i+1}}$
otherwise. When $\ell(|s\rangle)=1$, we conclude that
$F(|X_{k+1}\rangle|\hat{b}\hat{2}\rangle|s\rangle)=g(|X_{k+1}\rangle|\hat{b}\hat{2}\rangle|s\rangle)=g(|\hat{\dashv}\rangle|\hat{b}\rangle|\hat{2}\rangle|s\rangle)=|\hat{\dashv}\rangle|\widehat{b\oplus
s}\rangle|\hat{2}\rangle|s\rangle=BinSearch(|X_{k+1}\rangle|\hat{b}\hat{2}\rangle|s\rangle)$.
Next, we assume that $\ell(|s\rangle)=i\geq 2$. By induction hypothesis, we
obtain
$F(|X_{i+1}\rangle|\hat{b}\hat{2}\rangle|s^{(r)}\rangle)=|X_{i+1}\rangle|\hat{u}\rangle|\hat{2}\rangle|s^{(r)}\rangle$
with $u=b\oplus s^{(r)}_{m_{i+1}}$ if $x_{i}=1$, and
$F(|X_{i+1}\rangle|\hat{b}\hat{2}\rangle|s^{(l)}\rangle)=|X_{i+1}\rangle|\hat{v}\rangle|\hat{2}\rangle|s^{(l)}\rangle$
with $v=b\oplus s^{(l)}_{m_{i+1}}$ otherwise. In the case of $u=1$, since
$|\psi_{p_{\hat{u}},s}\rangle=HalfSWAP(|s\rangle)$, it follows that
$|\zeta_{\hat{u},p_{\hat{u}},s}\rangle=\sum_{t:|t|=RH(|s|)}(F(|X_{i+1}\rangle|\hat{b}\hat{2}\rangle|t\rangle)\otimes\langle
t|s^{(r)}s^{(l)}\rangle)=|X_{i+1}\rangle|\hat{u}\rangle|\hat{2}\rangle|s^{(l)}\rangle$.
Therefore, when $x_{i}=1$, we obtain
$F(|X_{i}\rangle|\hat{b}\hat{2}\rangle|s\rangle)=|x_{i}\rangle|X_{i+1}\rangle|\hat{u}\rangle|\hat{2}\rangle|s\rangle=BinSearch(|X_{i}\rangle|\hat{b}\hat{2}\rangle|s\rangle)$.
In contrast, when $x_{i}=0$, we obtain
$F(|X_{i}\rangle|\hat{b}\hat{2}\rangle|s\rangle)=|x_{i}\rangle|X_{i+1}\rangle|\hat{v}\rangle|\hat{2}\rangle|s\rangle=BinSearch(|X_{i}\rangle|\hat{b}\hat{2}\rangle|s\rangle)$.

As a result, we conclude that $F=BinSearch$, as requested. ∎

Hereafter, we demonstrate how to use the quantum function $BinSearch$. For
this purpose, we first show the following.

###### Corollary 4.8

Given $|\phi\rangle\in{\cal H}_{\infty}$ and $x=bin_{k}(m)$ for
$k\in\mathbb{N}^{+}$ and $m\in[2^{k}]$, if $|\phi\rangle$ is of the form
$\sum_{s:|s|=2^{k}}\alpha_{s}|s\rangle$, where $s=s_{1}s_{2}\cdots s_{2^{k}}$,
then we set
$Bit(|0^{5}\rangle|b\rangle|\widetilde{x}\rangle|\phi\rangle)=\sum_{s:|s|=2^{k}}\alpha_{s}|0^{5}\rangle|b\oplus
s_{m}\rangle|\widetilde{x}\rangle|s\rangle$, where $s_{m}$ is the $m$th bit of
$s$. This quantum function $Bit$ is definable within $EQS_{0}+IV$.

###### Proof.

Recall the quantum function $Skip_{k}[g]$ from lemma 3.3. We first change
$|0^{5}\rangle|b\rangle|\widetilde{x}\rangle|\phi\rangle$ into
$|\hat{b}\rangle|\hat{2}\rangle|\widetilde{x}\rangle|\phi\rangle$ by applying
$h\equiv SWAP_{1,4}\circ SWAP_{2,5}\circ SWAP_{3,6}\circ Skip_{2}[NOT]\circ
Skip_{1}[NOT]\circ NOT$.

Consider the quantum function $f$ defined by
$f(|\phi\rangle)=\sum_{z:|z|=6}\langle z|\phi\rangle\otimes|z\rangle$ for all
$|\phi\rangle\in{\cal H}_{\infty}$. This $f$ satisfies the following recursive
property: $f(|x\rangle|\hat{\dashv}\rangle)=SecSWAP^{(3)}_{1,3}\circ
SecSWAP^{(3)}_{2,4}(|u_{1}u_{2}\rangle\otimes f(\langle
u_{1}u_{2}|x{\hat{\dashv}}\rangle))$, where $x=u_{1}u_{2}x^{\prime}$ with
$|u_{1}|=|u_{2}|=3$.

Lemma 3.15 makes it possible to realize the quantum function $F$ that
satisfies
$F(|\hat{b}\rangle|\hat{2}\rangle|\widetilde{x}\rangle\otimes|\phi\rangle)=f(|\hat{b}\rangle|\hat{2}\rangle|\widetilde{x}\rangle)\otimes|\phi\rangle$,
which equals
$|\widetilde{x}\rangle|\hat{b}\rangle|\hat{2}\rangle|\phi\rangle$. We then
apply $BinSearch$ to
$|\widetilde{x}\rangle|\hat{b}\rangle|\hat{2}\rangle|s\rangle$ to obtain
$|\widetilde{x}\rangle|\widehat{b\oplus
s_{m}}\rangle|\hat{2}\rangle|s\rangle$. We then apply
$f^{-1}(|\widetilde{x}\rangle|\widehat{b\oplus
s_{m}}\rangle|\hat{2}\rangle|s\rangle)=|\widehat{b\oplus
s_{m}}\rangle|\hat{2}\rangle|\widetilde{x}\rangle|s\rangle$. Finally, we apply
$h^{-1}$ to $|\widehat{b\oplus
s_{m}}\rangle|\hat{2}\rangle|\widetilde{x}\rangle|s\rangle$ and obtain
$|0^{5}\rangle|b\oplus s_{m}\rangle|\widetilde{x}\rangle|s\rangle$. Therefore,
$Bit$ can be defined by Scheme I–IV. ∎

As the second application of $BinSearch$, we wish to “count” the number of 0s
and 1s in an input string in a quantum-mechanical fashion. It is impossible to
do so deterministically in polylogarithmic time. Fix a constant
$\varepsilon\in[0,3/4)$ and consider the _promise decision problem_
$MAJPDP_{\varepsilon}$, in which we determine whether or not the total number
of $0$s in $x$ is at least $\sqrt{1-\varepsilon}|x|$ or the total number of
$1$s is at least $\sqrt{1-\varepsilon}|x|$. Formally, $MAJPDP_{\varepsilon}$
is expressed as $(A_{\varepsilon},B_{\varepsilon})$, where
$A_{\varepsilon}=\\{x\in\\{0,1\\}^{*}\mid\\#_{1}(x)\geq\sqrt{1-\varepsilon}|x|\\}$
and
$B_{\varepsilon}=\\{x\in\\{0,1\\}^{*}\mid\\#_{0}(x)\geq\sqrt{1-\varepsilon}|x|\\}$.
We demonstrate the existence of a quantum function in $EQS$ that “solves” this
promise problem $MAJPDP_{\varepsilon}$ in the following sense.

###### Proposition 4.9

Let $\varepsilon$ be any constant in $[0,3/4)$. There exists a quantum
function $F$ in $EQS_{0}+IV$ such that, for any $x\in\\{0,1\\}^{*}$, (1) if
$x\in A_{\varepsilon}$, then $\|\langle 1|\psi_{F,x}\rangle\|^{2}\geq
1-\varepsilon$ and (2) if $x\in B_{\varepsilon}$, then $\|\langle
0|\psi_{F,x}\rangle\|^{2}\geq 1-\varepsilon$, where
$|\psi_{F,x}\rangle=F(|0^{3k}\rangle|\hat{\dashv}\rangle|x\rangle)$ with
$k=\mathrm{ilog}(|x|)$.

To prove this proposition, we need to show how to produce a superposition of
all “indices” of a given input. This can be done by recursively applying $WH$
to $|0^{3k}\rangle|\hat{\dashv}\rangle$ as shown below.

###### Lemma 4.10

There exists a quantum function $G$ in $EQS_{0}+IV$ such that, for any
$n\in\mathbb{N}^{+}$ and any $|\phi\rangle\in{\cal H}_{\infty}$,
$G(|0^{3k}\rangle|\hat{\dashv}\rangle\otimes|\phi\rangle)=\frac{1}{\sqrt{2^{k}}}\sum_{x:|x|=k}|\widetilde{x}\rangle|\phi\rangle$,
provided that $k=\mathrm{ilog}(\ell(|\phi\rangle))$.

###### Proof.

Consider the quantum function
$\hat{h}(|0^{3k}\rangle|\hat{\dashv}\rangle)=\frac{1}{\sqrt{2^{k}}}\sum_{x:|x|=k}|\widetilde{x}\rangle$.
This function $\hat{h}$ satisfies the following recursive property:
$\hat{h}(|\hat{\dashv}\rangle)=|\hat{\dashv}\rangle$ and
$\hat{h}(|0^{3}\rangle|w\hat{\dashv}\rangle)=h(|0^{3}\rangle\otimes\hat{h}(|w\hat{\dashv}\rangle))$
for any string $w$, where $h\equiv
Branch_{2}[\\{g_{u}\\}_{u\in\\{0,1\\}^{2}}]$ with $g_{00}=WH$ and $g_{u}=I$
for all indices $u\in\\{0,1\\}^{2}-\\{00\\}$. In what follows, we quickly
check that this property holds. Assume that
$\hat{h}(|0^{3k}\rangle|\hat{\dashv}\rangle)=\frac{1}{\sqrt{2^{k}}}\sum_{x:|x|=k}|\widetilde{x}\rangle$.
The value $\hat{h}(|0^{3k+3}\rangle|\hat{\dashv}\rangle)$ is calculated by
$h(|0^{3}\rangle\otimes\hat{h}(|0^{3k}\rangle|\hat{\dashv}\rangle))=|00\rangle\otimes
g(|0\rangle\otimes\hat{h}(|0^{3k}\rangle|\hat{\dashv}\rangle))=|00\rangle\otimes\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes\hat{h}(|0^{3k}\rangle|\hat{\dashv}\rangle)=\frac{1}{\sqrt{2}}(|\hat{0}\rangle+|\hat{1}\rangle)\otimes\frac{1}{\sqrt{2^{k}}}\sum_{x:|x|=3k}|\widetilde{x}\rangle=\frac{1}{\sqrt{2^{k+1}}}\sum_{y:|y|=k+1}|\widetilde{y}\rangle$.

By Proposition 3.15, there exists a quantum function $G$ in $EQS_{0}+IV$ for
which
$G(|0^{3k}\rangle|\hat{\dashv}\rangle\otimes|\phi\rangle)=\hat{h}(|0^{3k}\rangle|\hat{\dashv}\rangle)\otimes|\phi\rangle$,
where $k=\mathrm{ilog}(\ell(|\phi\rangle))$. This completes the proof. ∎

With the help of Lemma 4.10, we provide the proof of Proposition 4.9.

Proof of Proposition 4.9.  Consider
$MAJPDP_{\varepsilon}=(A_{\varepsilon},B_{\varepsilon})$ defined above. We
wish to construct a quantum function, say, $F$ in $EQS_{0}+IV$ that “solves”
$MAJPDP_{\varepsilon}$ in the lemma’s sense. Recall the quantum function $G$
of Lemma 4.10. Since $G$ is norm-preserving, $G^{-1}$ exists by Lemma 4.3.

We start with
$|\phi_{x}\rangle=|0^{6}\rangle|0^{3k}\rangle|\hat{\dashv}\rangle|x\rangle$,
where $k=\mathrm{ilog}(|x|)$, and apply $Skip_{6}[G]$ to generate
$\frac{1}{\sqrt{2^{k}}}\sum_{u:|u|=k}|\widetilde{u}\rangle|x\rangle|0^{6}\rangle$.
We then move $|0^{6}\rangle$ to the front and obtain
$\frac{1}{\sqrt{2^{k}}}\sum_{u:|u|=k}|0^{6}\rangle|\widetilde{u}\rangle|x\rangle$.
We further apply $Bit$ to the resulting quantum state and obtain
$\frac{1}{\sqrt{2^{k}}}\sum_{u:|u|=k}|0^{5}\rangle|x_{m(u)}\rangle|\widetilde{u}\rangle|x\rangle$,
where $x_{m(u)}$ is the $m(u)$-th bit of $x$ if $u=bin_{k}(m(u))$. We change
it to
$|\gamma_{x}\rangle=\frac{1}{\sqrt{2^{k}}}\sum_{u:|u|=k}|\widetilde{u}\rangle|x\rangle|0^{5}\rangle|x_{m(u)}\rangle$
and then apply $G^{-1}$. We denote the resulting quantum state by
$|\beta_{x}\rangle$. Letting $|\xi\rangle=|0^{3k}\rangle|\hat{\dashv}\rangle$,
we consider $\langle\xi|\beta_{x}\rangle$. Note that
$|\beta_{x}\rangle=G^{-1}(|\gamma_{x}\rangle)$ is equivalent to
$G(|\beta_{x}\rangle)=|\gamma_{x}\rangle$. It thus follows that
$\langle\xi|\beta_{x}\rangle$ equals $\langle\psi_{G,\xi}|\gamma_{x}\rangle$,
which is further calculated to
$(\frac{1}{\sqrt{2^{k}}}\sum_{v:|v|=k}\langle\widetilde{v}|)\cdot(\frac{1}{\sqrt{2^{k}}}\sum_{u:|u|=k}|\widetilde{u}\rangle|x\rangle|0^{5}\rangle|x_{m(u)}\rangle)=\frac{1}{2^{k}}|x\rangle|0^{5}\rangle|x_{m(u)}\rangle$,
where $|\psi_{G,\xi}\rangle=G(|\xi\rangle)$.

After removing the last qubit to the front, we obtain a unique quantum state,
say, $|\eta_{x}\rangle$. Finally, we measure the first qubit of
$|\eta_{x}\rangle$ in the computational basis. Let $b_{x}=1$ if $x\in
A_{\varepsilon}$ and $b_{x}=0$ if $x\in B_{\varepsilon}$. If $x\in
A_{\varepsilon}\cup B_{\varepsilon}$, then $b_{x}$ satisfies that $\|\langle
b_{x}|\eta_{x}\rangle\|^{2}\geq(\frac{1}{2^{k}}\sum_{u}\langle
b_{x}|x_{m(u)}\rangle)^{2}=(\frac{\\#_{b_{x}}(x)}{2^{k}})^{2}\geq(\sqrt{1-\varepsilon})^{2}=1-\varepsilon$
because of the promise given by $(A_{\varepsilon},B_{\varepsilon})$. $\Box$

##  5 Relationships to Quantum Computability

Throughout Section 3, we have studied basic properties of quantum functions in
$EQS$. In this section, we will look into relationships of these quantum
functions to other platforms of limited computability, in particular, a model
of polylogarithmic-time Turing machine.

###  5.1 Runtime-Restricted Quantum Turing Machines

We wish to describe a computational model of _quantum Turing machine_ (or QTM,
for short) that runs particularly in polylogarithmic time. For this purpose,
we need to modify a standard model of QTM defined in [6, 19, 24] structurally
and behaviorally. This new model also expands the classical model of
(poly)logtime Turing machine (TM) discussed in [1]. Notice that quantum
polylogtime computability was discussed based on uniform quantum circuit
families. For this model, refer to [20] and references therein.

A _(random-access) QTM_ 666This model is also different from the “log-space
QTMs” of [28], which are equipped with “garbage” tapes onto which any unwanted
information is discarded to continue their quantum computation. (or just a
_QTM_ in this work) is equipped with a random-access read-only input tape,
multiple rewritable work tapes of $O(\log{n})$ cells, and a rewritable index
tape of exactly $\mathrm{ilog}(n)+1$ cells, where $n$ refers to the length of
an input. The index tape indicates the cell location (or address) of the input
tape, specifying which qubit of a given input we wish to access. This QTM $M$
is formally expressed as
$(Q,\Sigma,\\{\rhd,\lhd\\},\delta,q_{0},Q_{acc},Q_{rej})$, where $Q$ is a
finite set of inner states, $\Sigma=\\{0,1\\}$ is an alphabet, $\rhd$ and
$\lhd$ are endmarkers, $\delta$ is a quantum transition function, $q_{0}$
($\in Q)$ is the initial (inner) state, and $Q_{acc}$ (resp., $Q_{rej}$)
($\subseteq Q$) is a set of accepting (resp., rejecting) states. We use an
additional convention that the input tape and the index tape, and all the work
tapes have two endmarkers to mark the usable areas of these tapes. This in
fact helps the machine understand the “size” of a given input. A polylogtime
QTM $M$ begins with an input qustring $|\phi\rangle$ given on the input tape
marked by the endmarkers. Let
$|\phi\rangle=\sum_{x\in\Sigma^{n}}\alpha_{x}|x\rangle$ with
$n\in\mathbb{N}^{+}$ and $\alpha_{x}\in\mathbb{C}$ for all $x$’s.

Recall from Section 2.1 the binary encoding of natural numbers. Let
$k_{n}=\mathrm{ilog}(n)$. To access the tape cell indexed by $m$, $M$ first
produces the binary string $bin_{k_{n}}(m)$ on the index tape with an
auxiliary bit $b$ and then enters a designated _query state_ , say,
$q_{query}$ in $Q$. If the index tape contains
$|bin_{k_{n}}(m)\rangle|b\rangle$, then this quantum state becomes
$|bin_{k_{n}}(m)\rangle|b\oplus x_{(m)}\rangle$ as the consequence of the
query, where $x_{(m)}$ is the $m$th input symbol of each input
$x\in\Sigma^{+}$. With the proper use of work tapes, we assume that, while
writing $|bin_{k_{n}}(m)\rangle|b\rangle$ until entering a query state, the
tape head never moves to the left and, whenever it writes a non-blank symbol,
it must move to the right.

Concerning a random access to an input, the classical polylogtime TMs take the
following convention [1, 23]: after each query process, the index tape remains
unerased and the corresponding tape head does not automatically return to the
start cell. Therefore, for the next query, the machine must overwrite a new
query word over the previous query word on the index tape. In a single step,
the input-tape head jumps to the target bit $x_{(m)}$ of the input specified
by the index-tape content $bin_{k_{n}}(m)$

The quantum transition function $\delta$ takes a quantum transition of the
form
$\delta(q,\sigma,\tau_{1},\tau_{2},\ldots,\tau_{c})=\sum_{r}\alpha_{r}|p,\xi,\eta_{1},\eta_{2},\ldots,\eta_{c},d,d^{\prime}_{1},d^{\prime}_{2},\ldots,d^{\prime}_{c}\rangle$,
where
$r=(p,\xi,\eta_{1},\eta_{2},\ldots,\eta_{c},d,d^{\prime}_{1},d^{\prime}_{2},\ldots,d^{\prime}_{c})$,
which indicates that, if $M$ is in inner state $q$ reading $\sigma$ on the
index tape and $(\tau_{1},\tau_{2},\ldots,\tau_{c})$ on the work tape, then,
in a single step, with transition amplitude $\alpha_{r}$, $M$ changes $q$ to
$p$, writes $\xi$ over $\sigma$ moving the input-tape head in direction
$d\in\\{-1,+1\\}$, and writes $\eta_{i}$ over $\tau_{i}$ moving the $i$th
work-tape head in direction $d^{\prime}_{i}\in\\{-1,+1\\}$. For practicality,
we can limit the scope of transition amplitudes of QTMs. In this work, we
allow only the following two forms of quantum transitions:
$\delta(q,\sigma,\tau_{1},\tau_{2},\ldots,\tau_{c})=\cos\theta|p_{1},\xi_{1},\eta_{11},\eta_{12},\ldots,\eta_{1c},d_{1},d^{\prime}_{11},d^{\prime}_{12},\ldots,d^{\prime}_{1c}\rangle+\sin\theta|p_{2},\xi_{2},\eta_{21},\eta_{22},\ldots,\eta_{2c},d_{2},d^{\prime}_{21},d^{\prime}_{22},\ldots,d^{\prime}_{2c}\rangle$
and
$\delta(q,\sigma,\tau_{1},\tau_{2},\ldots,\tau_{c})=e^{\imath\theta}|p,\xi,\eta_{1},\eta_{2},\ldots,\eta_{c},d,d^{\prime}_{1},d^{\prime}_{2},\ldots,d^{\prime}_{c}\rangle$
(based on the universality of a set of quantum gates of [3]).

A QTM is required to satisfy the so-called “well-formedness condition” (see,
e.g., [24, 26]) to guarantee that the behaviors of the QTM obeys the law of
quantum physics. A _surface configuration_ of $M$ on an input $x$ of length
$n$ is an element $(q,u,r,w_{1},s_{1},w_{2},s_{2},\ldots,w_{c},s_{c})$ of
$Q\times\\{\triangleright u\triangleleft\mid
u\in\\{0,1,B\\}^{k_{n}+1}\\}\times[0,k_{n}+2]_{\mathbb{Z}}\times(\\{\triangleright
w\triangleleft\mid
w\in\\{0,1,B\\}^{k_{n}}\\}\times[0,k_{n}+1]_{\mathbb{Z}})^{c}$, which depicts
the circumstance where $M$ is in inner state $q$, scanning the $r$th bit of
the index tape content $u$, and the $s_{i}$th bit of the $i$th work tape
content $w_{i}$. The _time-evolution operator_ of $M$ on the input $x$ is a
map from superpositions of surface configurations of $M$ on $x$ to other
superpositions of surface configurations resulting by a single application of
$\delta$ of $M$. A QTM $M$ is said to be _well-formed_ if its time-evolution
operator of $M$ preserves the $\ell_{2}$-norm.

At every step, we first apply $\delta$ to a superposition of surface
configurations and then perform a measurement in the halting (inner) states
(i.e., either accepting states or rejecting states). If $M$ is not in a
halting state, we move to the next step with the quantum state obtained by
tracing out all halting surface configurations. Generally, QTMs can
“recognize” sets of qustrings.

For convenience, we modify $M$ slightly so that $M$ produces $1$ (resp., $0$)
in the first cell of the first work tape when $M$ enters a designated final
state (in place of accepting/rejecting states). We say that $M$ _produces $b$
with probability $\gamma$_ if, after $M$ halts, we observe $b$ as an outcome
of $M$ with probability $\gamma$.

We call $M$ _polylogarithmic time_ (or _polylogtime_) if we force $M$ to stop
its application of $\delta$ after $O(\log^{k}{n})$ steps for a certain
constant $k\in\mathbb{N}^{+}$, not depending on inputs. We do not require that
all computation paths to terminate within the specified time.

Let us consider a language $L$ over $\\{0,1\\}$ that satisfies the following
condition: there are a constant $\varepsilon\in[0,1/2)$ and a polylogtime QTM
$M$ whose amplitude set is $K$ such that (i) for any input $x\in L$, $M$
accepts $x$ with probability at least $1-\varepsilon$ and (ii) for any
$x\notin L$, $M$ rejects $x$ with probability at least $1-\varepsilon$. These
conditions are referred to as _bounded-error probability_. The notation
$\mathrm{BQPOLYLOGTIME}_{K}$ denotes the collection of all such languages $L$.

###  5.2 Computational Complexity of Polylogtime QTMs

We begin with a discussion on the computational complexity of polylogtime
QTMs. Recall that input tapes of these machines are read-only and accessed by
way of writing cell locations onto index tapes.

In the classical setting, the notation $\mathrm{DLOGTIME}$ was used in [1] to
express the family of all languages recognized by logtime DTMs. Similarly, we
denote the nondeterministic variant of $\mathrm{DLOGTIME}$ by
$\mathrm{NLOGTIME}$. With the use of classical probabilistic TMs (or PTMs), we
say that a PTM $M$ recognizes a language $L$ _with unbounded-error
probability_ if, for any $x\in L$, $M$ accepts it with probability more than
$1/2$ and, for any $x\notin L$, $M$ rejects with probability at least $1/2$.
We further define $\mathrm{PPOLYLOGTIME}$ by unbounded-error polylogtime PTMs.

###### Theorem 5.1

$\mathrm{BQPOLYLOGTIME}_{\bar{\mathbb{Q}}}\subsetneqq\mathrm{PPOLYLOGTIME}$
and $\mathrm{NLOGTIME}\nsubseteq\mathrm{BQPOLYLOGTIME}_{\mathbb{C}}$.

For the proof of Theorem 5.1, nevertheless, we first verify the following
impossibility result of the parity function and the OR function by polylogtime
QTMs, where the parity function, $Parity$, is defined by
$Parity(x)=\bigoplus_{i=1}^{n}x_{i}$ and the OR function, $OR$, is defined by
$OR(x)=\max\\{x_{i}\mid i\in[n]\\}$ for any number $n\in\mathbb{N}^{+}$ and
any $n$-bit string $x=x_{1}x_{2}\ldots x_{n}$.

###### Lemma 5.2

The parity function and the OR function cannot be computed by any polylogtime
QTM with bounded-error probability.

###### Proof.

This proof comes from a result on the quantum query complexity gap between
quantum and deterministic query complexities of the parity function. Assume
that a polylogtime QTM computes the parity function with bounded-error
probability.

As done in Lemma 4.10, it is possible to produce in polylog time a
superposition of all indices of the input-tape cells by repeatedly applying
$WH$ to $|0^{\mathrm{ilog}(n)}\rangle$. This helps us access all input bits
quantumly at once with the equal probability. Since the input tape is read-
only, this type of input access can be realized as a _(black-box) quantum
query model_ used in the study of quantum query complexity.

In such a (black-box) quantum query model, we run the following quantum
algorithm on a binary input $x$. We prepare a series of unitary
transformations $U_{0},U_{1},\ldots,U_{k-1},U_{k}$ and a special oracle
transformation $Q_{x}$ that changes $|bin_{k}(m)\rangle|\phi\rangle$ to
$(-1)^{x_{(m)}}|bin_{k}(m)\rangle|\phi\rangle$, where $x_{(m)}$ is the $m$th
bit of $x$. Initially, we start with a simple initial quantum state
$|\psi_{0}\rangle=|0^{m}\rangle$. We then compute
$U_{k}Q_{x}U_{k-1}Q_{x}\cdots U_{1}Q_{x}U_{0}|\psi_{0}\rangle$. Finally, we
measure the resulting quantum state in the computational basis. The number $k$
indicates the number of queries of this algorithm.

###### Claim 5.3

Any polylogtime QTM can be simulated by a (black-box) quantum query model with
$O(\log{n})$ queries.

###### Proof.

Recall that a polylogtime QTM has a read-only input tape, which holds an input
string. Whenever the QTM makes a query on the $i$th position, the machine
immediately receives the information on the $i$th bit of the input string. We
view the input tape as an oracle in a (black-box) quantum query model and we
further view this query process of the QTM as a procedure of forming a
superposition of query words indicating input-bit positions and receiving
answers to the queries from the oracle.

When $M$ changes $|bin_{k}(m)\rangle|b\rangle$ to $|bin_{k}(m)\rangle|b\oplus
x_{(m)}\rangle$ in a query process, we simulate this transformation using the
(black box) quantum query model as follows. Let
$|\phi\rangle=|bin_{k}(m)\rangle$. Starting with $|\phi\rangle|b\rangle$,
apply $WH$, apply $CQ_{x}$ (Controlled-$Q_{x}$), apply $WH$, and swap back the
registers, where $CQ_{x}(|0\rangle|\phi\rangle)=|0\rangle|\phi\rangle$ and
$CQ_{x}(|1\rangle|\phi\rangle)=(-1)^{x_{(m)}}|1\rangle|\phi\rangle$. We then
obtain $|b\oplus x_{(m)}\rangle|\phi\rangle$, as requested. Since the given
QTM makes only $O(\log{n})$ queries, we can transform this QTM to a query
model of $O(\log{n})$ queries. ∎

By Claim 5.3, the parity function requires only $O(\log{n})$ queries in the
(black box) quantum query model. However, it is shown in [4] that, for the
parity function of $n$ Boolean variables, $n/2$ queries are necessary in the
bounded-error quantum query model (while $n$ queries are necessary in the
deterministic query model). This is obviously a contradiction. The case of the
OR function can be similarly handled. ∎

Let us return to Theorem 5.1. Using Lemma 5.2, we can prove the theorem below.
The core of its proof is founded on a simulation result of one-tape linear-
time QTMs in [22, Section 8].

Shown in [22, Lemma 8] is how to simulate a one-tape well-formed stationary
QTM running in linear time on an appropriate one-tape probabilistic Turing
machine (or a PTM) in linear time. In a similar vein, we can simulate
polylogtime QTMs on polylogtime PTMs.

Proof of Theorem 5.1.  Let us take an arbitrary language $L$ in
$\mathrm{BQPOLYLOGTIME}_{\bar{\mathbb{Q}}}$ and consider a polylogtime QTM $M$
that recognizes $L$ with bounded-error probability. We intend to show that
$L\in\mathrm{PPOLYLOGTIME}$. We first modify $M$ in the following way. We
prepare two extra work tapes. One of them is used as an internal clock by
moving a tape head always to the right. To avoid any unwanted interference
after a computation halts prematurely, we use the other extra tape as a
“garbage tape”, to which $M$ dumps all information produced at the time of
entering halting states, so that $M$ continues its operation without actually
halting. Lemma 8 of [22] shows the existence of a constant
$d\in\mathbb{N}^{+}$ and an NTM $N$ such that $d^{\mathrm{Time}_{M}(x)}\cdot
p_{M}(x)=\\#N(x)-\\#\overline{N}(x)$ for every $x$, where $\\#N(x)$ (resp.,
$\\#\overline{N}(x)$) denotes the total number of accepting (resp., rejecting)
computation paths of $N$ on input $x$. This equality holds for polylogtime
machines. The desired polylogtime PTM is obtained from $N$ by assigning an
equal probability to all nondeterministic transitions.

The OR function can be computed by the polylogtime NTM that writes an
arbitrary number, say $i$ on an index tape, queries the $i$th bit $x_{i}$ of
an input $x$, and accepts exactly when $x_{i}$ is $1$. Thus, the OR function
belongs to $\mathrm{NLOGTIME}$. The separation between
$\mathrm{BQPOLYLOGTIME}_{\bar{\mathbb{Q}}}$ and $\mathrm{NLOGTIME}$ comes from
Lemma 5.2. Since $\mathrm{PPOLYLOGTIME}$ includes $\mathrm{NLOGTIME}$, we also
obtain the separation between $\mathrm{BQPOLYLOGTIME}_{\bar{\mathbb{Q}}}$ and
$\mathrm{PPOLYLOGTIME}$. $\Box$

###  5.3 Comparison between EQS and BQPOLYLOGTIME

In what follows, we discuss a close relationship between quantum functions
definable within $EQS$ and quantum functions computable by polylogtime QTMs
despite numerous differences between $EQS$ and polylogtime QTMs. One such
difference is that input tapes of QTMs are read-only whereas quantum functions
in $EQS$ can freely modify their inputs. In the following two theorems
(Theorems 5.4 and 5.5), however, we can establish the “computational”
equivalence between polylogtime QTMs and quantum functions in $EQS$.

To make the later simulation process simpler, we first modify a polylogtime
QTM so that it uses the binary alphabet on all work tapes and on an index tape
by encoding each non-binary tape symbol into a binary one using an
appropriately chosen encoding scheme. This makes it possible to assume that
the QTM should hold superpositions $|\phi\rangle$ of binary strings on its
input tape. For convenience, a QTM that satisfies these conditions is called
_normalized_.

###### Theorem 5.4

Any normalized polylogtime QTM $M$ with $c$ work tapes can be simulated by an
appropriate quantum function $F$ in $EQS$ in the sense that, for any
$b\in\\{0,1\\}$, $\alpha\in[0,1]$, and $|\phi\rangle\in\Phi_{\infty}$, $M$
takes input $|\phi\rangle$ and finally produces $b$ with probability $\alpha$
exactly when $\|\langle b|\psi_{F,\xi_{\phi}}\rangle\|^{2}=\alpha$ holds,
where
$|\xi_{\phi}\rangle=|\hat{S}\rangle|\widetilde{B^{k}}\rangle^{\otimes(c+1)}|\hat{2}\rangle\otimes|\phi\rangle$
with $k=\mathrm{ilog}(\ell(|\phi\rangle))$ and
$|\psi_{F,\xi_{\phi}}\rangle=F(|\xi_{\phi}\rangle)$.

###### Proof.

Let $M$ denote any polylogtime QTM equipped with a read-only input tape, a
rewritable index tape, and a single rewritable work tape. We further assume
that $M$ is normalized. For readability, we deal only with the case where $M$
has a single work tape. A general case of $c$ work tapes can be handled in a
similar but naturally generalized way. Assume that $M$’s input tape holds a
superposition $|\phi\rangle$ of binary inputs with $\ell(|\phi\rangle)\geq 4$
and that $M$ runs in time at most $\mathrm{ilog}(\ell(|\phi\rangle))^{e}$ for
a fixed constant $e\geq 1$. For convenience, let
$k=\mathrm{ilog}(\ell(|\phi\rangle))$. We denote by $Q$ the set of all inner
states of $M$. Since $Q$ is finite, without loss of generality, $Q$ is of the
form $\\{bin_{3t^{\prime}}(i)\mid i\in[2^{3t^{\prime}}]\\}$ for an appropriate
constant $t^{\prime}\in\mathbb{N}^{+}$. We set the initial state $q_{0}$ to be
$bin_{3t^{\prime}}(1)$. For each $q\in Q$, since $q$ is expressed as a binary
string, we can encode it into the string $\widetilde{q}^{(-)}$ defined in
Section 3.2.

We treat the content of each tape (except for the input tape) as a code block
of the desired quantum function $F$. We maintain the content of the index tape
and the work tape as a part of two appropriate qustrings. We intend to
simulate each move of $M$ on $|\phi\rangle$ by applying an appropriately
defined quantum function.

Since $M$’s computation is a series of surface configurations of $M$, we thus
need to “express” such a surface configuration using a single quantum state.
Initially, $M$’s index tape holds $B^{k}{\lhd}$ and $M$’s work tape holds
$B^{kt}{\lhd}$ for a fixed constant $t\in\mathbb{N}^{+}$. Let $w$ and $z$
denote respectively the contents of the index tape and the work tape without
the right endmarker ${\lhd}$ and let $q$ be any inner state of $M$. Associated
with $(q,w,z)$, we describe the current surface configuration as
$q\\#w_{1}Hw_{2}\\#z_{1}Hz_{2}$ with $w=w_{1}w_{2}$ and $z=z_{1}z_{2}$ by
including a designated symbol $H$ and $M$’s inner state, where $H$ is used to
indicate the locations of the index-tape head and the work-tape head, which
are scanning the leftmost symbols of $w_{2}$ and $z_{2}$, respectively. Assume
that these two tape heads are respectively scanning tape symbols $\eta$ and
$\sigma$ on the index tape and the work tape, where $w_{2}=\eta x_{2}$ and
$z_{2}=\sigma y_{2}$. For technical reason, we slightly modify the above
description of a surface configuration and express it as
$w_{1}HBx_{2}\\#z_{1}HBy_{2}\\#q\eta\sigma$ by inserting the extra symbol $B$.
To refer to this special form, we call it a _modified (surface)
configuration_. In particular, the suffix $q\eta\sigma$ is called a
_transition status_.

By Lemma 4.5, it suffices for us to focus on each block of encoded tape
content. The modified configuration
$w_{1}HBx_{2}\\#z_{1}HBy_{2}\\#q\eta\sigma$ is encoded into the quantum state
$|\widetilde{w_{1}}^{(-)}\hat{H}\hat{B}\widetilde{x}\rangle|\widetilde{z_{1}}^{(-)}\hat{H}\hat{B}\widetilde{y}\rangle|\widetilde{q}^{(-)}\hat{\eta}\hat{\sigma}\rangle|\hat{\dashv}\rangle$.
We conveniently refer to it as the _encoded (surface) configuration_. Note
that
$|\widetilde{q}^{(-)}\hat{\eta}\hat{\sigma}|=6t^{\prime}+6=6(t^{\prime}+1)$.
Notice that the modified initial configuration is of the form
$HB^{k}\\#HB^{kt}\\#q_{0}BB$ and its encoding is of the form
$|\hat{H}\widetilde{B^{k}}\rangle|\hat{H}\widetilde{B^{kt}}\rangle|\widetilde{q_{0}}^{(-)}\hat{B}\hat{B}\rangle|\hat{\dashv}\rangle$.

A _run_ of $M$ from the initial surface configuration to halting surface
configurations can be simulated using the fast quantum recursion. To explain
this simulation, for convenience, we split each move of $M$ into three
separate “phases”: (1) a tape content change, (2) an input access by a query,
and (4) an output production. We consider those three different phases of $M$
separately. In phase (3), we use Scheme V to repeat phases (1) and (2)
$\mathrm{ilog}(\ell(|\phi\rangle))$ times. Finally, we combine (1)–(4) into a
single quantum function.

(1) The first case to consider is that $M$ modifies multiple tapes (except for
the input tape) by a single move. We begin with paying our attention to the
case of the modification of the index tape and describe how to simulate this
tape-symbol modification. As our convention, a tape head changes a tape symbol
and then moves to an adjacent cell in a single step. Namely, in a single step,
$M$ locally changes $w_{1}Hw_{2}\\#z_{1}Hz_{2}\\#q\eta\sigma$ to its successor
$w^{\prime}_{1}Hw^{\prime}_{2}\\#z^{\prime}_{1}Hz^{\prime}_{2}\\#q^{\prime}\eta^{\prime}\sigma^{\prime}$
by applying $\delta$. This process can be expressed by a quantum function
defined as follows.

Consider $M$’s transition of the form
$\delta(q,\eta_{2},\sigma_{2})=\sum_{r}\alpha_{r}|p,\xi_{2},\tau_{2},d,d^{\prime}\rangle$,
where $r$ takes the form
$(q,\eta_{2},\sigma_{2},p,\xi_{2},\tau_{2},d,d^{\prime})$. This transition
means that the index-tape head changes $\eta_{2}$ to $\xi_{2}$ and moves in
direction $d$ and that the work-tape head changes $\sigma_{2}$ to $\tau_{2}$
and moves in direction $d^{\prime}$. To simulate this step, it suffices to
focus on four consecutive cells whose second cell is being scanned by the tape
head. For convenience, we call such a series an _$H$ -block_. Let
$\eta_{1}HB\eta_{3}$ and $\sigma_{1}HB\sigma_{3}$ denote two series of
$H$-blocks and let $q\eta_{2}\sigma_{2}$ denote the current transition status.

(a) We make an application of Scheme IV in the following fashion. Let
$v=(q,\eta_{2},\sigma_{2},p,\xi_{2},\tau_{2},d,d^{\prime})$. We first change
$|\widetilde{q}^{(-)}\hat{\eta_{2}}\hat{\sigma_{2}}\rangle$ to
$|\widetilde{p}^{(-)}\hat{B}\hat{B}\rangle$ by remembering
$(\xi_{2},\tau_{2},d,d^{\prime})$ in the form of different quantum functions
$g_{u}$, which are controlled by $Branch[\\{g_{u}\\}_{u}]$. We then search for
an $H$-block of the form $|\hat{\eta_{1}}\hat{H}\hat{B}\hat{\eta_{3}}\rangle$
and change it to $|\hat{H}\hat{\eta_{1}}\hat{\xi_{2}}\hat{\eta_{3}}\rangle$ if
$d=-1$ and to $|\hat{\eta_{1}}\hat{\xi_{2}}\hat{H}\hat{\eta_{3}}\rangle$ if
$d=+1$. Similarly, we change
$|\hat{\sigma_{1}}\hat{H}\hat{B}\hat{\sigma_{3}}\rangle$ according to the
value of $d^{\prime}$. These changes can be made by an appropriate quantum
function, say, $F_{v,d}$. This quantum function $F_{v,d}$ is realized in the
following fashion.

Let us consider the case of $\tau_{2}\in\\{0,1\\}$. We introduce
$f_{B,\tau_{2}}$ that satisfies
$f_{B,\tau_{2}}(|\hat{B}\rangle|\hat{H}\rangle)=|\hat{\tau_{2}}\rangle|\hat{H}\rangle$.
This quantum function $f_{B,\tau_{2}}$ is constructed as $f_{B,\tau_{2}}\equiv
Branch_{3}[\\{g^{\prime}_{u}\\}_{u\in\\{0,1\\}^{3}}]\circ