1.1 Recursion schematic definitions that capture quantum computability

Over the four decades, the study of quantum computing has made 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 are linear combinations of basic quantum states expressing classical strings, 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 (Reference Benioff1980), Deutsch (Reference Deutsch1985, Reference Deutsch1989Reference Deutsch), and Yao (Reference Yao1993) as quantum analogs of Turing machines and Boolean circuits. Those models have been used in a theoretical study of quantum computing within the area of computational complexity theory since their introduction. The quantum Turing machine (QTM) model is a natural quantum extension of the classical Turing machine (TM) model, which has successfully served for decades as a basis to theoretical aspects of computer science. The basic formulation of the QTM modelFootnote ¹ used today attributes to Bernstein and Vazirani (Reference Bernstein and Vazirani1997). 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 (Yamakami, Reference Yamakami2020), 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 (Reference Kleene1936, Reference Kleene1943) 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., (Soare, Reference Soare1996) 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 ones based on Turing machines as well as Boolean circuit families to formulate the recursive functions. A similar approach taken by Yamakami (Reference Yamakami2020) aims at capturing the polynomial-time computability of quantum functions,Footnote ² 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 by Yamakami (Reference Yamakami2020) from six 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 by Yamakami (Reference Yamakami2020) are a precise characterization of quantum polynomial-time computability and a quantum analog 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 so powerful that it has helped us capture the notion of quantum polynomial-time computability.

There are a few but important advantages of using recursion schematic definitions to introduce the notion of quantum computation 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 construction of quantum circuit families. Recursion schematic definitions, on the contrary, avoid such extra requirements and make it much simpler to design a quantum algorithm in the form of a quantum function for solving a target combinatorial problem. This is because each basic scheme naturally embodies “well-formedness” and “uniformity” in its formulation. More accurately, the scheme produces only “well-formed” and “uniform” quantum functions by way of applying the scheme directly to the existing quantum functions. In fact, the schematic definition of Yamakami (Reference Yamakami2020) 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 Yamakami (Reference Yamakami2020) has become a helpful guide to develop even a suitable form of quantum programming language (Hainry et al., Reference Hainry and Péchoux2023). It is worth mentioning that such a recursion schematic definition has been made possible because of an extensional use of the bra and ket notations. See Section 2.3 for detailed explanations.

A schematic approach of Yamakami (Reference Yamakami2020) to quantum computing 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 further lead us to the descriptional complexity of quantum functions. Concerning such 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 this work, we particularly 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 small depth-bounded quantum circuits, and we further wish to examine how the schematic approach of Yamakami (Reference Yamakami2020) copes with such restricted 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 (Reference Buss1987) and Barrington et al. (Reference Barrington, Immerman and Straubing1990) in terms of TMs equipped with index tapes to access particular locations of input symbols. Hereafter, 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 by Barrington et al. (Reference Barrington, Immerman and Straubing1990), 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 (abbreviated as polylogtime) computability has been widely studied in the literature. Numerous polylogtime algorithms were developed to solve, for example, the matrix chain ordering problem (Bradford et al., Reference Bradford, Rawlins and Shannon1994) and deterministic graph construction (Holm et al., Reference Holm, de Lichtenberg and Thorup2001). There were also studies on data structures that support polylog operations (Munro, Reference Munro1984) and probabilistic checking of polylog bits of proofs (Babai et al., Reference Babai, Fortnow, Levin and Szegedy1991). 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, nevertheless, we are able to take a similar approach using resource-bounded QTMs. A quantum analog of $\mathrm{DLOGTIME}$, called $\mathrm{BQLOGTIME}$, was lately discussed in connection to an oracle separation between $\mathrm{BQP}$ and the polynomial hierarchy in (Raz and Tal, Reference Raz and Tal2022). 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 analog 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 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}}$ precisely capture quantum polynomial-time computability, it is natural to raise a question of how we can capture quantum polylogtime computability in a similar fashion.

As noted earlier, the multi-qubit quantum recursion scheme of Yamakami (Reference Yamakami2020) is capable of precisely capturing quantum polynomial-time computability. A basic idea of this quantum recursion scheme is, starting with $n$ qubits, to modify at each round of recursion the first $k$ qubits and continue to the next round 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 Yamakami (Reference Yamakami2020), the scheme still generates numerous interesting and useful quantum functions, as listed in Lemmas 4–8 and 15–22. 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 six initial quantum functions and three 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 33–34).

To cope with polylogtime computability, we need an appropriate encoding of various types of “objects” (such as numbers, graphs, matrices, and tape symbols) into qubits of an equal 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 Conference Report. The current work corrects and significantly alters the preliminary conference report (Yamakami, Reference Yamakami2022b), 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 (Yamakami, Reference Yamakami2022b), 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 after an appropriate modification. This new scheme helps us capture the parity function, which requires more than polylogtime quantum computation. This fact implies that this new procedure is not “realized” in the framework of $EQS$.

2.1 Numbers, strings, and languages

The notations $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ respectively denote 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 denote the set $\mathbb{N}-\{0\}$. For two integers $m,n$ with $m\leq n$, $[m,n]_{\mathbb{Z}}$ indicates the integer interval $\{m,m+1,m+2,\ldots, n\}$. In particular, we abbreviate $[1,n]_{\mathbb{Z}}$ as $[n]$ when $n\geq 1$. In addition, $\mathbb{C}$ denotes the set of all complex numbers. We use the notations $\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$. We further 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. To circumvent any cumbersome description to avoid the special case of $n=0$, we intentionally set $\mathrm{ilog}(0)=\mathrm{iloglog}(0)=0$. The notation $\imath$ denotes $\sqrt{-1}$ and $e$ does 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 given 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 the 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$. Intuitively, $A$ and $R$ are, respectively, composed of accepted strings and rejected strings. When $A\cup R=\Sigma ^*$, $(A,R)$ becomes $(A,\Sigma ^*-A)$, and this can be identified with the language $A$.

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$ and a number $k\in \mathbb{N}^{+}$, 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.

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 lexicographically the $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 whereas $bin(0)$ means $\lambda$.

2.2 Quantum States and Hilbert spaces

We assume the reader’s familiarity with basic quantum information and computation (see, e.g., textbooks (Kitaev et al., Reference Kitaev, Shen and Vyalyi2002; Neilsen and Chuang, Reference Nielsen and Chuang2016). 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 the generic notation $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$.

The generic notation $\boldsymbol{0}$ is used to denote the null vector of an arbitrary dimension. A quantum bit (or a qubit, for short) is a linear combination of two basis vectors $| 0 \rangle$ and $| 1 \rangle$. The notation $\mathscr{H}_2$ indicates the Hilbert space spanned by $| 0 \rangle$ and $| 1 \rangle$. More generally, $\mathscr{H}_{2^n}$ refers to the Hilbert space spanned by the computational basis $B_n=\{| s \rangle \mid s\in \{0,1\}^n\}$. For convenience, we write $\mathscr{H}_{\infty }$ for the collection of all quantum states in $\mathscr{H}_{2^n}$ for any $n\in \mathbb{N}^{+}$. Remember that $\mathscr{H}_{\infty }$ does not form a Hilbert space. Given a non-zero quantum state $| \phi \rangle \in \mathscr{H}_{\infty }$, its length $\ell (| \phi \rangle )$ denotes a unique number $n\in \mathbb{N}$ for which $| \phi \rangle \in \mathscr{H}_{2^n}$. We stress that the length of $| \phi \rangle$ is defined only for a quantum state residing in $\mathscr{H}_{\infty }$. As a special case, we set $\ell (\boldsymbol{0})=0$ for the null vector $\boldsymbol{0}$ (although $\boldsymbol{0}$ belongs to $\mathscr{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} | x \rangle \otimes \langle x | \phi \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 $\|| \phi \rangle \|$.

A qustring of length $n$ is a unit-norm quantum state in $\mathscr{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$. Clearly, $\Phi _{n}\subseteq \mathscr{H}_{2^n}$ holds for all $n\in \mathbb{N}^{+}$. We then set $\Phi _{\infty }$ to be the collection of all qustrings of length $n$ for any $n\in \mathbb{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 \mathscr{H}_{\infty }$. It then follows that $\ell (| \phi \rangle )=LH(| \phi \rangle )+RH(| \phi \rangle )$.

We are interested only in functions mapping $\mathscr{H}_{\infty }$ to $\mathscr{H}_{\infty }$, and these functions are generally referred to as quantum functions on $\mathscr{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 \mathscr{H}_{\infty }$.

2.3 Conventions on the bra and the ket notations

To calculate the outcomes of quantum functions on $\mathscr{H}_{\infty }$, we must 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 (Yamakami, Reference Yamakami2020) for the conventions on the specific usage of these notations. These notational conventions in fact help us simplify the description of various qubit operations in later sections. 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 $\boldsymbol{0}$. To deal with the null vector, we conveniently take the following specific conventions concerning the operator “$\otimes$”. For any $| \phi \rangle \in \mathscr{H}_{\infty }$, (i) $0\otimes | \phi \rangle = | \phi \rangle \otimes 0 =\boldsymbol{0}$ (scalar case), (ii) $| \phi \rangle \otimes \boldsymbol{0} = \boldsymbol{0}\otimes | \phi \rangle =\boldsymbol{0}$, and (iii) if $| \psi \rangle$ is the null vector, then $\langle \phi | \psi \rangle = \langle \psi | \phi \rangle =\boldsymbol{0}$. In the case of (i), we here extend the standard 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|\lt |s|$, $\langle u | s \rangle$ expresses the quantum state $| z \rangle$ if $s=uz$ for a certain string $z$, and $0$ otherwise. By sharp contrast, if $|u|\gt |s|$, then $\langle u | s \rangle$ always denotes $\boldsymbol{0}$. More generally, if $| \phi \rangle =\sum _{u\in \{0,1\}^n}\sum _{s\in \{0,1\}^m} \alpha _{u,s}| u \rangle \otimes | 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$ together make 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 abbreviate $| \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 to scalars in the following way. For any quantum states $| \phi \rangle$ and $| \psi \rangle$ with $\ell (| \phi \rangle ) = \ell (| \psi \rangle )\gt 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 $\boldsymbol{0}$ unless otherwise stated.

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 Definition20, 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 (Yamakami, Reference Yamakami2020).

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

We remark that all quantum functions in Items 1)–4) and 6) in Scheme I directly manipulate only the first qubit of $| \phi \rangle$ and that $SWAP$ manipulates the first two qubits of $| \phi \rangle$. All other qubits of $| \phi \rangle$ are intact. Notice that the length function $\ell (| \phi \rangle )$ is not included as part of $EQS_0$. Since $| \phi \rangle$ is always taken from $\mathscr{H}_{\infty }$, the value $\ell (| \phi \rangle )$ is uniquely determined from $| \phi \rangle$. It is also important to remark that, for any $| \phi \rangle$ and $a\in \{0,1\}$, $\ell (MEAS[a](| \phi \rangle )) = \ell (| \phi \rangle )$.

In Schemes II and III, the constructions of $Compo[g,h]$ and $Branch[g,h]$ need two quantum functions, $g$ and $h$, which are assumed to have been already constructed in their own construction processes. 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$, we write $EQS_{K,0}$ and $\widehat{EQS}_{K,0}$ with a clear reference to $K$.

We quickly provide simple examples of how to compute the quantum functions induced by appropriate applications of Schemes I–III.

For later reference, let us review from Yamakami (Reference Yamakami2020) 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.

1. (T) The multi-qubit quantum recursion scheme (Yamakami, Reference Yamakami2020). Let $g$, $h$, $p$ be quantum functions and let $k,t\in \mathbb{N}^{+}$ be numbers. Assume that $p$ is dimension-preserving. For $\mathscr{F}_k=\{f_u\}_{u\in \{0,1\}^k}$, we define $F\equiv kQRec_t[g,h,p|\mathscr{F}_k]$ as follows:

   1. (i) $F(| \phi \rangle ) = g(| \phi \rangle )\qquad\qquad\qquad\qquad\qquad\qquad$ if $\ell (| \phi \rangle )\leq t$,

   2. (ii) $F(| \phi \rangle ) = h( \sum _{u:|u|=k} | u \rangle \otimes f_u ( \langle u | \psi _{p,\phi } \rangle ))\qquad$ 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 function class $\Box ^{\mathrm{QP}}_{1}$, which constitutes all polynomial-time computable quantum functions (Yamakami, Reference Yamakami2020). Although we do not consider $REMOVE$ here, its restricted form, called $CodeREMOVE[\cdot ]$, will be introduced in Section 3.2.

Let us present a short list of typical quantum functions “definable” within $EQS_0$; that is, those quantum functions are actually constructed from Items 1)–5) of Scheme I and by finitely many applications of Schemes II–III. As the first simple application of Scheme I–III, we demonstrate how to construct the special quantum function called $Skip_k[\cdot ]$.

Hereafter, let us construct more quantum functions in $EQS_0$.

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.

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 this quantum function to our system, but it will be used to support the description of a new scheme given in Section 3.2. We remark that, to construct this quantum function, we need Schemes I–III together with the quantum recursion Scheme T. By recalling the left-half function $LH$ and the right-half function $RH$ from Section 2.1, let us introduce $HalfSWAP$ as

1. *) $HalfSWAP(| \phi \rangle ) = \left \{ \begin{array}{ll} | \phi \rangle & \quad if \mbox{$\ell (| \phi \rangle )\leq 1$,} \\ \sum _{s:|s|=LH(| \phi \rangle )} \langle s | \phi \rangle \otimes | s \rangle & \quad {otherwise.} \end{array}\right .$

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

3.2 Binary encoding of various types of objects

All quantum functions discussed in Section 3.1 take only “single” quantum states in $\mathscr{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, and tape symbols. 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 over quantum functions. For our purpose, nevertheless, it is imperative to set up an appropriate binary encoding to transform multiple objects into a single quantum state with an appropriate use of designated “separators”. In the polynomial-time setting (Yamakami, Reference Yamakami2020), 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 a multiple-tape QTM being simulated by a single-tape QTM 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 to expand the scope of our quantum functions. As a feasible solution to this problem, we introduce “extra” schemes that help us handle intended binary encodings.

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 larger-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 take the following abbreviations: $\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_1s_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 $\mathscr{H}_{\infty }$, we finally define its encoding $| \tilde{\phi } \rangle$ as $\sum _{s:|s|=\ell (| \phi \rangle )} | \tilde{s} \rangle \langle s | \phi \rangle$. Notice 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. We make each series of encoded objects have length proportional to the section size $|r_0|$, and thus any encoding $x$ satisfies $|x|=k|r_0|$ for an appropriate, fixed number $k\in \mathbb{N}^{+}$. This helps us partition $x$ section-wise as $x_1x_2\cdots x_k$ with $|x_i|=|r_0|$ for all indices $i\in [k]$. We also demand that no $x_i$ should match $r_0$. Here, 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 0 \}$. For convenience, when $r_0=\hat{2}$, we tend to omit $r_0$ from $NON_{r_0}$ and $NON_{r_0}(| \phi \rangle )$.

We then need a quantum function that splits an input into sections and apply “section-wise” two predetermined 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 to use for quantum polylogtime computability.

1. *) The code skipping schemes. 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}{l@{\quad}r} | \phi \rangle & if \mbox{$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 )) & {otherwise.} \end{array}\right .$

   2. (ii) $CodeSKIP_{-}[r_0,g,h](| \phi \rangle ) = \left \{ \begin{array}{l@{\quad}r} | \phi \rangle & if \mbox{$NON_{r_0}(| \phi \rangle ) = \varnothing $,} \\ \sum _{x\in NON_{r_0}(| \phi \rangle )} ( g( | x \rangle ) \otimes h( \langle x | \phi \rangle )) & {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_0y \rangle )$. These schemes are not interchangeable in most applications.

A quantum function $g$ is said to be query-independent if, in the process of constructing $g$, for any input of the form $| xr_0 \rangle | \phi \rangle$, any quantum function that appears in this construction process does not directly access $| \phi \rangle$ and thus it does not depend on $| \phi \rangle$. This instantly implies that $g(| xr_0 \rangle | \phi \rangle ) = g(| xr_0 \rangle )\otimes | \phi \rangle$ for any $x$ and $| \phi \rangle$. Using this terminology, when $h=I$ in the code skipping schemes, $CodeSKIP_{+}[r_0,g,I]$ and $CodeSKIP_{-}[r_0,g,I]$ are query-independent.

Here, we present a few more examples of $CodeSKIP_{+}$.

We wish to recall the two useful quantum functions $REMOVE$ (removal) and $REP$ (replacement) introduced by Yamakami (Reference Yamakami2020). 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}{l} | \phi \rangle \qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ \ if \mbox{$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 ) \quad {otherwise.} \end{array}\right .$

2. (ii) $CodeREP[r_0](| \phi \rangle ) = \left \{ \begin{array}{l} | \phi \rangle \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ if \mbox{$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 ) \quad {otherwise.} \end{array}\right .$

Notice that the quantum functions $CodeREMOVE[r_0]$ and $CodeREP[r_0]$ are query-independent.

We wish to include a simple example of $CodeREMOVE$ and $CodeREP$.

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 (at most) $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 formally 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|\gt |r_0|\mathrm{ilog}(\ell (| \phi \rangle ))$, and $f^*(| xr_0 \rangle | \phi \rangle ) = f(| xr_0 \rangle )\otimes | \phi \rangle$ otherwise, for any $x\in \{0,1\}^*$ and any $| \phi \rangle \in \mathscr{H}_{\infty }$. 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$ by its definition.

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.

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 description of Items (i)–(ii) in Scheme IV concerns only with a classical string $xr_0$, whenever any quantum state $| \psi \rangle =\sum _{x}\alpha _x| xr_0 \rangle \otimes | \phi _x \rangle$ is plugged in to $F$, we obtain the result $\sum _{x}\alpha _x F(| xr_0 \rangle | \phi _x \rangle )$.

Since $p_u\in \{I,HalfSWAP\}$ and $|x'|=|x|$, it follows that $\ell (| \psi _{u,p_u,\phi } \rangle ) = \ell (| \phi \rangle )$, $\ell (| \zeta _{u,p_u,\phi }^{(x'r_0)} \rangle ) = \ell (\langle u | x'r_0 \rangle ) + \ell (| \phi \rangle )$, and $\ell (\langle v | \zeta _{u,p_u,\phi }^{(x'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'r_0 \rangle )-|r_0|)+\lceil \ell (| \phi \rangle )/2 \rceil$ (or $(\ell (| x'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.

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

(ii$'$) $F(| 0^n1 \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^n1)} \rangle ))$,

where $| \zeta _{0,p_0,\phi }^{(0^n1)} \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 )$.

At this moment, it is worth remarking the usage of the length function $\ell (\cdot )$. In Scheme IV, the input quantum state $| xr_0 \rangle | \phi \rangle$ is reduced to $\langle u | x'r_0 \rangle | s \rangle$ (with $|s|=m_u(| \phi \rangle )$ and $|u|=|r_0|$) so that we can inductively apply $F$ (when $f_u=F$) to it. The length $\ell (| \phi \rangle )$ then becomes $\ell (| s \rangle )$, and thus the conditional execution of Item (i) depends on the value $\ell (| s \rangle )$.

To understand Scheme IV better, we provide in Example14 a simple example of how to calculate the quantum function $F\equiv CFQRec_t[r_0,d,g,h | \mathscr{P}_{|r_0|},\mathscr{F}_{|r_0|}]$ step by step.

3.4 Power of Scheme IV

In what follows, we intend to show the usefulness of Scheme IV by applying it to construct a quantum function, which calculates the logarithmic value of (part of) input size. Formally, for any $| \phi \rangle \in \mathscr{H}_{\infty }$ and $m\in \mathbb{N}^{+}$, we define $SIZE_1$ as $SIZE_1(| 0^m1 \rangle | \phi \rangle ) = | 0^k1 \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^m1 \rangle | \phi \rangle ) = | 0^m1 \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$. The choice of $0^{m|r_0|}$ here is only for simplicity.

For brevity, we intend to use the notation $EQS_0+IV$ to express the set of quantum functions constructed by applying Schemes I–IV.

Given an input of the form $| xr_0 \rangle | \phi \rangle$, it is possible to apply any quantum function $g$ in $EQS_0$ 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 in the following way.

As shown in Proposition18, 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

\begin{equation*} (*) \:\:\: \hat {h}(| r_0 \rangle ) = | r_0 \rangle \text { and }\hat {h}(| xr_0 \rangle ) = \sum _{u:|u|=|r_0|}h( | u \rangle \otimes \hat {h}( \langle u | xr_0 \rangle )) \end{equation*}

for any $x\in NON_{r_0}$ with $x\neq \lambda$. This recursive construction scheme (*) looks similar to Scheme T but it is not supported in our system $EQS_0+IV$. Nevertheless, as shown in Proposition18, 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$.

The quantum function $\hat{h}$ given by the recursive scheme (*) may not be constructed by the only 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$.

Since $CodeSKIP_{+}[\cdot ]$ can be realized by the recursive construction scheme (*), Proposition18 allows us to use $CodeSKIP_{+}[\cdot ]$ freely as if it is a quantum function in $EQS_0+IV$.

3.5 Elementary quantum schemes

Formally, let us introduce $\widehat{EQS}$ and $EQS$. We have already explained Schemes I–IV. Now, we wish to add the final piece of construction schemes, called Scheme V, which intuitively supports successive $\mathrm{ilog}(\ell (| \phi \rangle ))$ applications of $Compo[g,g]$ for a given quantum function $g$ taking $| xr_0 \rangle | \phi \rangle$ as an input.

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

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 (Yamakami, Reference Yamakami2020) for more discussions.

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 three lemmas, Lemmas 21–23.

We further discuss two useful construction schemes, which are definable within $\widehat{EQS}$.

As a quick example of $Branch_k[\mathscr{G}_k]$, let us recall the quantum function $Skip_k[g]$ from Lemma4. It is obvious 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 \mathscr{H}_{\infty }$, we express this $g$ as $f^{-1}$ (or sometimes $f^{\dagger }$) and call it the inverse (function) of $f$.

4.2 Section-wise handling of binary encoding

We have discussed in Section 3.2 the binary encodings of various objects usable as part of inputs. We further explore the characteristics of quantum functions that can 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 $\mathscr{G}=\{g_i\}_{i\in [k]}$ denote a series of $k$ quantum functions. We then consider a simultaneous application of all quantum functions in $\mathscr{G}$, $MultiApp_k[\mathscr{G}]$, given as

\begin{eqnarray*} &{MultiApp_k[\hat{2},\mathscr{G}] (| \widetilde{x_1} \widetilde{x_2} \cdots \widetilde{x_k}\hat{2} \rangle | \phi \rangle )} \\ &\qquad \qquad = g_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 . \end{eqnarray*}

By Lemma24, we can construct $MultiApp_k[\hat{2},\mathscr{G}]$ from $\mathscr{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},\mathscr{G}]$ in general does not belong to $EQS$. However, as the next lemma ensures, we can use $MultiApp_k[\hat{2},\mathscr{G}]$ as if it is an $EQS$ function under certain circumstances.

To describe our result, let us recall the 3-bit encoding of $\hat{S}$, which indicates “separator”.

In a certain limited case, Lemma25 makes possible a repeated application of any quantum function within $EQS_0+IV$ (as well as $EQS$). Let us recall the notation $\hat{T}$, which indicates “time”.

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\}$, the quantum function $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 $| \widehat{b\oplus s_{(m)}} \rangle$.