Quantum Programming in Polylogarithmic Time

Quantum computing is a field of research, which is drawing a great amount of interest as it leverages quantum superposition and interference to obtain computational advantage. The development of quantum programming languages is thus a key issue, which raises major technical and conceptual challenges to ensure their physicality. In order to check that quantum programs can be compiled and executed on a quantum computer, one has to design restrictions and constraints implying that quantum programs do not break the laws of quantum mechanics, for example, no-cloning of data and unitarity of operators. In addition, there is a need to tame their complexity in order to ensure their feasibility. By feasibility, we mean that quantum executions do not use too many ancillary qubits and run in tractable time.

Taking inspiration from the classical world, this kind of issue has lead to the definition and study of several quantum polynomial time classes. One of the most striking examples of such classes is bqp, the quantum analog of the class of bounded-error probabilistic polynomial time problems bpp. By Yao’s theorem [23], bqp corresponds exactly to what can be computed by uniform families of quantum circuits of polynomial size. This class, as well as its extension to functions, fbqp, have been characterized through various means, including function algebras [19] and first-order programs [12].

A natural question is then to study subpolynomial complexity classes. As for classical programs, it allows to express notions of parallel complexity, which is highly relevant in the quantum setting where program superpositions can be viewed as a kind of parallelism with interferences. Parallelization can be used to reduce the maximum number of operations performed in total on each qubit. This is particularly challenging as qubit fidelity, i.e., the ability of qubits to align with their intended states through time and unitary operations, is a bottleneck of quantum computation [14]. While polynomial time algorithms performed in sequence are useful in the fewer qubits, higher fidelity setting [12], parallelized computation becomes more interesting in the case of more qubits, lower fidelity [15], as the total number of operations on individual qubits, and their necessary coherence time, scale more slowly. Moreover, separation results between those small complexity classes could lead to a proof of the quantum advantage, as constant depth quantum circuits have been shown to be strictly more powerful than their classical counterparts [5].

In the literature, polylogarithmic (polylog) time has been introduced and studied on Quantum Random-Access Turing Machine (QRATM) [10]. As in the classical case, this definition uses random-access machines, as opposed to standard quantum Turing machines, because of the sub-linearity of time: although the machine cannot read its entire input, it can access any input bit or qubit. On quantum models, polylog time corresponds to problems that a QRATM can solve in a polylog number of steps, leading to the definition of the complexity class fbqpolylog [20, 21] of functions computable with bounded-error in quantum polylog time.

A main open problem is to design programming languages characterizing such a polylog class abstracting from the low-level considerations (machines, uniformity conditions, etc.) [22].

This paper makes a first step towards solving this problem. Towards that end, we introduce a quantum programming language with first-order recursive procedures, named plp for PolyLog Programs (Figure 1), on which we obtain the following results:

• $\mathrm{■}$

  plp programs are terminating (Theorem 7) and reversible (Theorem 8).

• $\mathrm{■}$

  plp is sound for fbqpolylog (Theorem 10), i.e., each plp program computes a function in fbqpolylog. Soundness relies on the use of a bounded recursion scheme for procedures to enforce the required polylog time properties, as illustrated by the binary search and square-log examples of Figure 4.

• $\mathrm{■}$

  plp is complete for fbqpolylog (Theorem 10), i.e., each function of this complexity class is computed by a plp program. Completeness is shown by a direct encoding of polylog QRATM in plp.

• $\mathrm{■}$

  plp is also sound but not complete for qnc. For soundness, we outline a compilation algorithm that from a plp program and its input size outputs a quantum circuit of polylog depth and polynomial size, i.e., circuits computing functions in qnc (Theorem 13). There is an implementation of this algorithm available at https://gitlab.inria.fr/mmachado/pfoq-compiler, whose compiler works for programs even beyond the plp fragment, namely non-polylog programs. Completeness does not hold (Theorem 19) as it is well-known that fbqpolylog is strictly included in qnc.

Different characterizations of quantum complexity classes have been obtained for polynomial time using, non-exhaustively, lambda-calculus [8], function algebra [19], and a first-order programming language [12]. A characterization of bqpolylog based on a function algebra has been provided in [20, 21], where a fast quantum recursion scheme is used to ensure that programs terminate in polylogarithmic time. Our work employs a similar bounded recursion scheme, using a simple divide-and-conquer strategy on qubits. This characterization can be seen as simpler and more natural approach since an imperative first-order programming language is more accessible to the typical programmer. Similar divide-and-conquer strategies have been explored in quantum computation not only for the purpose of finding quantum advantage [5, 6] but also to leverage classically-inspired techniques in the quantum scenario, where reversibility and unitarity must be satisfied [18, 17]. Our work is mostly focused on this second aspect, where the objective is to balance the expressivity of a quantum programming language with the statically-verifiable properties of its programs, namely unitarity, time complexity, as well as circuit size and depth.

The considered language is a quantum programming language with first-order recursive procedures whose syntax is provided in Figure 1. There are four basic types $\tau$ for expressions:

1. 1.

   Integer expressions are variables $\mathrm{x}$, constant $k\in \mathbb{N}$, arithmetic operations like $\mathrm{i}\pm k$ or $\mathrm{i}/2$,¹¹1The semantics of $/2$ will be defined as the ceiling of the result, hence it preserves the set of integers. as well as the size $|\mathrm{l}|$ of a list of qubits $\mathrm{l}$.

2. 2.

   Boolean expressions are defined in a standard way.

3. 3.

   Qubit lists are lists of unique (i.e., non-duplicable) qubit pointers. A qubit list expression $\mathrm{l}$ is either a variable $\overline{\mathrm{q}}$, the first (respectively second) half ${\mathrm{l}}^{\boxminus }$ (resp. ${\mathrm{l}}^{⊞}$) of the qubit list $\mathrm{l}$, or a list $\mathrm{l}\ominus \text{[}\mathrm{i}\text{]}$ where the $\mathrm{i}$-th element of $\mathrm{l}$ has been removed. We will also use some syntactic sugar for removing multiple elements of a list with $\mathrm{l}\ominus \text{[}{\mathrm{i}}_1,\mathrm{\dots },{\mathrm{i}}_k\text{]}$.

4. 4.

   Qubit expressions are of the shape $\mathrm{l}\text{[}\mathrm{i}\text{]}$, which denotes the $\mathrm{i}$-th qubit in $\mathrm{l}$. We also define syntactic sugar for pointing to the $n$-th last qubit in a list, by defining for any $n\ge 1$, $\overline{\mathrm{q}}\text{[}-n\text{]}\triangleq \overline{\mathrm{q}}\text{[}\left|\overline{\mathrm{q}}\right|-n+1\text{]}$.

Throughout the paper, $\mathrm{e}$, $\mathrm{d}$, $\mathrm{\dots }$ will denote arbitrary expressions of any type. Given a syntactic object $t$, let $Var(t)$ be the set of qubit variables used in $t$, e.g., $Var(\overline{\mathrm{q}}\ominus [2,3])=\{\overline{\mathrm{q}}\}$ is the set of qubit variables in the expression $\overline{\mathrm{q}}\ominus [2,3]$.

A program $\mathrm{P}\triangleq \mathrm{D}::\mathrm{S}$ is defined in Figure 1 as a list of (possibly recursive) procedure declarations $\mathrm{D}$, followed by a program statement $\mathrm{S}$. We assume that $Var(\mathrm{S})\subseteq Var(\mathrm{P})$ holds. In what follows, it will be convenient to order the set $Var(\mathrm{P})=\{{\overline{\mathrm{q}}}_1,\mathrm{\dots },{\overline{\mathrm{q}}}_m\}$ by to fix a precise memory representation of quantum states.

Let Procedures be an enumerable set of procedure names $\mathrm{proc}$. We write $\mathrm{proc}\in \mathrm{P}$ to denote that $\mathrm{proc}$ appears in $\mathrm{P}$. Each procedure of name $\mathrm{proc}\in \mathrm{P}$ is defined by a unique procedure declaration $\text{decl }\mathrm{proc}({\overline{\mathrm{q}}}_1,\mathrm{\dots },{\overline{\mathrm{q}}}_n)\{\mathrm{S}\}\in \mathrm{D}$, which takes the lists of qubits ${\overline{\mathrm{q}}}_i$ as parameters. It always holds that $Var(\mathrm{S})\subseteq \{{\overline{\mathrm{q}}}_1,\mathrm{\dots },{\overline{\mathrm{q}}}_n\}$. We will sometimes write ${\mathrm{S}}^{\mathrm{proc}}$ to explicitly state that $\mathrm{S}$ is the statement of $\mathrm{proc}$.

Statements include the no-op instruction, (single-qubit) unitary application, sequences, conditional, quantum case, and procedure calls. For sake of universality [4], in a unitary application $\mathrm{q}\text{*=}{\mathrm{U}}^g(\mathrm{i});$, the unitary transformation ${\mathrm{U}}^g(\mathrm{i})\in {𝕂}^{2\times 2}$ can take an integer $\mathrm{i}$ and a function $g\in \mathbb{Z}\to [0,2\pi )$ as optional arguments²²2In the case of quantum polynomial time, Adleman et al. [1] showed how the choice of amplitudes can affect the expressivity of classes such as bqp, requiring the restriction of polynomial-time approximable complex amplitudes. How the set of amplitudes influences the class fbqpolylog remains an open question, as discussed in [20, 21], and so we abstain from the use of the entire set of complex numbers and instead use a field $𝕂$ which may refer to, for instance, polynomial-time approximable complex amplitudes., and we omit them when they are of no use. As we shall see in next section, unitary transformations will be restricted to phase gate, rotation gates, and NOT gate.

The quantum conditional $\text{qcase }\mathrm{q}\text{ of }\{0\to {\mathrm{S}}_0,1\to {\mathrm{S}}_1\}$ allows branching by executing statements ${\mathrm{S}}_0$ and ${\mathrm{S}}_1$ in superposition according to the state of qubit $\mathrm{q}$. When we want to treat cases on multiple qubits, we will sometimes simplify the nested qcases, for example $\text{qcase }{\mathrm{q}}_1,{\mathrm{q}}_2\text{ of }\{00\to {\mathrm{S}}_{00},01\to {\mathrm{S}}_{01},10\to {\mathrm{S}}_{10},11\to {\mathrm{S}}_{11}\}$ is a shorthand notation for

In each procedure call $\text{call }\mathrm{proc}({\mathrm{l}}_1,\mathrm{\dots },{\mathrm{l}}_n);$, the no-cloning theorem of quantum mechanics imposes the restriction that $\forall i\ne j,Var({\mathrm{l}}_i)\ne Var({\mathrm{l}}_j)$.

The syntax of Figure 1 can be used to define typical quantum computing primitives such as controlled-NOT, swap, as well as Toffoli gates, as syntactic sugar:

Let $𝔹\triangleq \{0,1\}$ denote the set of Booleans and $ℒ(\mathbb{N})$ denote the set of lists of natural numbers, $[]$ being the empty list. We interpret basic types as follows:

Qubits are interpreted as integers (pointers) and qubit lists are interpreted as lists of pointers. Each $\mathrm{op}\in \{\pm ,/2,\ge ,\wedge ,\mathrm{\dots }\}$ of arity $n$ comes with a basic type signature $\mathrm{op}::{\tau }_1\times \mathrm{\dots }\times {\tau }_n\to \tau$ and computes a fixed total function $⟦\mathrm{op}⟧\in ⟦{\tau }_1⟧\times \mathrm{\dots }\times ⟦{\tau }_n⟧\to ⟦\tau ⟧$. We set $\mathrm{op}({\tau }_1,\mathrm{\dots },{\tau }_n)\triangleq \tau$. For example, $⟦/2⟧\triangleq m\mapsto \lceil m/2\rceil$. Constants $k$ are treated as particular operators of arity $0$. Given a program $\mathrm{P}$, for each basic type $\tau$, the semantics of expressions is described standardly in Figure 2 as a function

$(\mathrm{e},f){\Downarrow }_{⟦\tau ⟧}v$ holds when expression $\mathrm{e}$ of type $\tau$ evaluates to the value $v\in ⟦\tau ⟧$ under the context $f\in Var(\mathrm{P})\to ℒ(\mathbb{N})$. The context $f$ is just a map from each program input to a list of qubit pointers taken into consideration when evaluating $\mathrm{e}$. For instance, we have that $(\overline{\mathrm{q}}\text{[}2\text{]},\overline{\mathrm{q}}\mapsto [1,4,5]){\Downarrow }_{\mathbb{N}}4$ (the second qubit is of index $4$), $(\overline{\mathrm{q}}\ominus \text{[}4\text{]},\overline{\mathrm{q}}\mapsto [1,4,5]){\Downarrow }_{ℒ(\mathbb{N})}[]$ ($[]$ is used for errors on type $ℒ(\mathbb{N})$), $(\overline{\mathrm{q}}\text{[}4\text{]},\overline{\mathrm{q}}\mapsto [1,4,5]){\Downarrow }_{\mathbb{N}}0$ (index $0$ is used for error on type $\mathbb{N}$), and $(\overline{\mathrm{q}}\ominus \text{[}3\text{]},\overline{\mathrm{q}}\mapsto [1,4,5]){\Downarrow }_{ℒ(\mathbb{N})}[1,4]$ (the third qubit has been removed).

Let ${\mathscr{H}}_{2^n}$ denote the Hilbert space ${ℂ}^{2^n}$ of $n$ qubits with tensor product $\otimes$ and let $𝒫(\mathbb{N})$ denote the powerset of $\mathbb{N}$. Given a program $\mathrm{P}$, let the length of $\mathrm{P}$ be a function mapping each qubit variable $\overline{\mathrm{q}}\in Var(\mathrm{P})$ to an integer $\text{len}(\overline{\mathrm{q}})\in \mathbb{N}$. We write ${\text{len}}_{\mathrm{P}}$ as a shorthand for ${\sum }_{\overline{\mathrm{q}}\in Var(\mathrm{P})}\text{len}(\overline{\mathrm{q}})$ and as a shorthand for .

A configuration $c$ of program $\mathrm{P}$ over ${\text{len}}_{\mathrm{P}}$ qubits is of the shape

where $\top$ and $\perp$ are two special symbols denoting termination and error, respectively, where $|\psi ⟩\in {\mathscr{H}}_{2^{{\text{len}}_{\mathrm{P}}}}$ is a quantum state, and where, for each qubit list $\overline{\mathrm{q}}\in Var(\mathrm{P})$, $A(\overline{\mathrm{q}})$ is the set of qubit pointers accessible from $\overline{\mathrm{q}}$ and $f(\overline{\mathrm{q}})$ is the list of qubit pointers assigned to $\overline{\mathrm{q}}$. Given a qubit $\mathrm{q}$ such that $Var(\mathrm{q})=\{\overline{\mathrm{q}}\}$, we write $A(\mathrm{q})$ as a shorthand for $A(\overline{\mathrm{q}})$ and we write $A_{\mathrm{q}\backslash \{n\}}$ for the function $A^{\prime }\in Var(\mathrm{P})\to 𝒫(\mathbb{N})$ defined by $A^{\prime }({\overline{\mathrm{q}}}^{\prime })\triangleq A({\overline{\mathrm{q}}}^{\prime }),$ $\forall {\overline{\mathrm{q}}}^{\prime }\ne \overline{\mathrm{q}}$, and $A^{\prime }(\overline{\mathrm{q}})\triangleq A(\overline{\mathrm{q}})\backslash \{n\}$.

Given a program $\mathrm{P}\triangleq \mathrm{D}::\mathrm{S}$, with $n={\text{len}}_{\mathrm{P}}$, let ${\text{Conf}}_n$ be the set of configurations over $n$ qubits. The initial configuration in ${\text{Conf}}_n$ on input state $|\psi ⟩\in {\mathscr{H}}_{2^n}$ is $c_{init}(|\psi ⟩)\triangleq (\mathrm{S},|\psi ⟩,\overline{\mathrm{q}}\mapsto \{1,\mathrm{\dots },\text{len}(\overline{\mathrm{q}})\},\overline{\mathrm{q}}\mapsto [1,\mathrm{\dots },\text{len}(\overline{\mathrm{q}})])$. A final configuration can be defined in the same way as $c_{final}(|\psi ⟩)\triangleq (\top ,|\psi ⟩,\overline{\mathrm{q}}\mapsto \{1,\mathrm{\dots },\text{len}(\overline{\mathrm{q}})\},\overline{\mathrm{q}}\mapsto [1,\mathrm{\dots },\text{len}(\overline{\mathrm{q}})])$.

Each unitary transformation $\mathrm{U}$ of a unitary application $\mathrm{q}\text{*=}{\mathrm{U}}^g(\mathrm{i});$ comes with a function $⟦\mathrm{U}⟧$ assigning a unitary matrix $⟦\mathrm{U}⟧(g)(n)\in {𝕂}^{2\times 2}$ to each integer $n$ and function $g\in \mathbb{Z}\to [0,2\pi )$. We restrict ourselves to three kinds of gates: the phase gate $Ph$, rotation gate ${\mathrm{R}}_{\mathrm{Y}}$ and $NOT$ gate $\mathrm{NOT}$, whose semantics is defined as follows:

The big-step semantics $\cdot \stackrel{}{⟶}\cdot$ is defined in Figure 3 as a relation in ${\bigcup }_{n\in \mathbb{N}}{\text{Conf}}_n\times {\text{Conf}}_n$. The symbols $\perp$ and $\top$ for error and termination, respectively, are terminal states: they cannot appear on the left-hand-side of a rule. In Figure 3, the function $A$ of accessible qubits is used to ensure that unitary operations on qubits can be physically implemented. For example, the statements ${\mathrm{S}}_0$ and ${\mathrm{S}}_1$ of a quantum branch $\text{qcase }\mathrm{q}\text{ of }\{0\to {\mathrm{S}}_0,\mathrm{\hspace{0.17em}1}\to {\mathrm{S}}_1\}$ cannot access the control qubit $\mathrm{q}$ to ensure reversibility. To avoid cumbersome use of nested conditionals in the program syntax, each procedure call on a (at least one) empty qubit list is semantically equivalent to a$\text{ skip};$ (see Figure 3).

We write $⟦\mathrm{P}⟧(|\psi ⟩)=|{\psi }^{\prime }⟩$, whenever $c_{init}(|\psi ⟩)\stackrel{}{⟶}{c}_{final}(|{\psi }^{\prime }⟩)$ holds. If the program $\mathrm{P}$ terminates on all inputs (i.e., always reaches a final configuration) then $⟦\mathrm{P}⟧$ is a total function on quantum states. Note that if a program terminates then it is obviously error-free (i.e., does not reach a configuration with a $\perp$) but the converse property does not hold. However, every program $\mathrm{P}$ can be efficiently transformed into an error-free program ${\mathrm{P}}_{\neg \perp }$ such that $\forall |\psi ⟩$, if $⟦\mathrm{P}⟧(|\psi ⟩)$ is defined then $⟦\mathrm{P}⟧(|\psi ⟩)=⟦{\mathrm{P}}_{\neg \perp }⟧(|\psi ⟩)$. This can be done, for instance, by checking the size of qubit lists before accessing them. Hence we will restrict ourselves to error-free programs in what follows.

When an input state is defined by different qubit lists, we denote them in subscript. For instance, for $x,y\in {\{0,1\}}^{\ast }$ and $m\in \mathbb{N}$, we have that ${|x⟩}_{{\overline{\mathrm{q}}}_1}{|y⟩}_{{\overline{\mathrm{q}}}_2}$ indicates state $|x⟩$ given as input to qubit list ${\overline{\mathrm{q}}}_1$, state $|y⟩$ given as input to qubit list ${\overline{\mathrm{q}}}_2$.

We now define some restrictions on the admissible programs to guarantee that they terminate in polylogarithmic time (i.e., each procedure cannot perform more than a polylogarithmic number of recursive calls in the input size) and that their total number of sequential procedure calls (i.e., calls that are not in superposition) is bounded polylogarithmically.

Towards that end, we define a relation between procedures to account for recursion. Given a program $\mathrm{P}\triangleq \mathrm{D}::\mathrm{S}$, the call relation ${\to }_{\mathrm{P}}\subseteq \text{Procedures}\times \text{Procedures}$ is defined for any two procedures ${\mathrm{proc}}_1,$ ${\mathrm{proc}}_2\in \mathrm{S}$ as ${\mathrm{proc}}_1{\to }_{\mathrm{P}}{\mathrm{proc}}_2$ whenever ${\mathrm{proc}}_2\in {\mathrm{S}}^{{\mathrm{proc}}_1}$. The relation ${⪰}_{\mathrm{P}}$ is then the transitive closure of ${\to }_{\mathrm{P}}$. The relation ${\sim }_{\mathrm{P}}$ is defined by ${\mathrm{proc}}_1{\sim }_{\mathrm{P}}{\mathrm{proc}}_2$ if ${\mathrm{proc}}_1{⪰}_{\mathrm{P}}{\mathrm{proc}}_2$ as well as ${\mathrm{proc}}_2{⪰}_{\mathrm{P}}{\mathrm{proc}}_1$ both hold. Finally, the relation ${\succ }_{\mathrm{P}}$ is defined as ${\mathrm{proc}}_1{\succ }_{\mathrm{P}}{\mathrm{proc}}_2$ if ${\mathrm{proc}}_1{⪰}_{\mathrm{P}}{\mathrm{proc}}_2$ and ${\mathrm{proc}}_1{\sim ̸}_{\mathrm{P}}{\mathrm{proc}}_2$ both hold. A procedure $\mathrm{proc}$ is recursive whenever $\mathrm{proc}{\sim }_{\mathrm{P}}\mathrm{proc}$ holds. Two procedures $\mathrm{proc}$ and ${\mathrm{proc}}^{\prime }$ are mutually recursive whenever $\mathrm{proc}{\sim }_{\mathrm{P}}{\mathrm{proc}}^{\prime }$ holds

This restriction can be viewed as a recursion scheme, which implies a polylogarithmic time bound on programs in half by ensuring that in every (mutually) recursive procedure call at least one of the input qubit lists is cut in half.

Now we impose a further condition on the number of sequential (mutually) recursive procedure calls. For that purpose, we define the width of a program $\mathrm{P}$ in the following way.

As we will see in next Section (Theorem 10), the restriction to plp programs ensures that they can be simulated by quantum random-access Turing machines running in polylogarithmic time.

Because of the half condition, programs in plp can be shown to be terminating.

To define the class fbqpolylog, we introduce the computational model of quantum random-access Turing machines (QRATMs) [20, 21]. fbqpolylog is not defined on standard quantum Turing machines because, due to its sub-linear time complexity, such a machine would not be able to access all of its input. Random-access machines solve part of the problem by allowing the machine to jump over its input.

A QRATM has a random access input tape, a log-space index tape, and $c$ work tapes and is then defined as a triplet $(Q,\mathrm{\Sigma },\delta )$, where $Q$ is a finite set of states containing an initial state $s_0$ and two (disjoint) subsets $Q_{\text{acc}}$ and $Q_{\text{rej}}$ for accepting and rejecting states, $\mathrm{\Sigma }=\{0,1,\mathrm{\#}\}$ is the tape alphabet, and the transition function $\delta$ is such that

This transition maps the state and read symbols on the index tape and work tapes to a function mapping each state, each written symbol, and each head move to an amplitude. Note that the input tape does not have a tape head, hence is not taken into account in this transition function.

To get access to any character of the input, a special transition of the machine is defined: when the machine is in a special state $s_{\text{query}}$, the cell of input tape corresponding to the binary number written on the index tape is swapped with the cell under the work tape head, and the machine transitions to a state $s_{\text{accept}}$. Note that, in contrast with [20, 21], the input tape is not read-only as we consider a class of functions rather than decision problems, hence having the modified input be part of the output is necessary. This allows for example to consider the identity function.

A pure configuration of a QRATM is a tuple $(s,w,w_0,w_1,\mathrm{\dots },w_c,z_0,z_1,\mathrm{\dots },z_c)\in Q\times \mathrm{\Sigma }_{}^{\ast }{}_{}{}^{2+c}\times {\mathbb{Z}}^{1+c}$ where $s$ is a state, $w$ the word written on the input tape, assumed to begin in cell $0$, $w_0$ is the word on the index tape, $w_1$, …, $w_c$ the words written on the work tapes, $z_0$ is the position of the index tape head, $z_1$, …, $z_c$ the tape head positions for the work tapes, all positions are relative to the first character of the word. The initial configuration for input $x$ is $\gamma (x)\triangleq (s_0,x,ϵ,\mathrm{\dots },0,\mathrm{\dots })$. We call a superposition of pure configurations a surface configuration. Surface configurations can be written as ${\sum }_r{\alpha }_r|r⟩$, with $r$ ranging over pure configurations, ${\alpha }_r\in ℂ$ is the amplitude associated with configuration $r$. QRATMs are also required to satisfy reversibility and well-formedness condition: a configuration may have only one predecessor, and the transition function must preserve the norm of configurations, that means that for all reachable surface configurations, ${\sum }_r{|{\alpha }_r|}^2=1$.

A QRATM halts in time $t$ on input $x$ if, starting from the initial configuration $\gamma (x)$, after $t$ steps, its surface configuration is a superposition of pure configurations in accepting states. If for all input $x$, a QRATM $M$ halts on input $x$ in time $T(|x|)$, we say that $M$ halts in time $T$. In particular, if there exists $k\in \mathbb{N}$ such that $M$ halts in time $O({\log }^k(n))$, $M$ halts in polylog time. If a QRATM halts, its output is defined as the linear combination of the words on the input tape and work tapes, using the previous notations, it corresponds to ${\sum }_r{\alpha }_r|w^r,w_0^r,w_1^r,\mathrm{\dots },w_c^r⟩$. Given a function $f:{\{0,1\}}^{\ast }\to {\{0,1\}}^{\ast }$, we say that a QRATM $M$ approximates $f$ with probability $p$ if for all input $x\in {\{0,1\}}^{\ast }$, starting from the initial configuration $\gamma (x)$, $M$ halts with an output ${\sum }_r{\alpha }_r|w^r,w_0^r,w_1^r,\mathrm{\dots },w_c^r⟩$ such that ${\sum }_{r\in Q_{acc}\times \{f(x)\}\times {\mathbb{Z}}^{2+c}}{|{\alpha }_r|}^2\ge p$.

Although a natural theoretical model for describing polylogarithmic time, QRATMs are problematic because they are too semantic in nature: to characterise their complexity, the time bound must be given explicit and their halting condition depends on the inner state of the machine, which is a semantic condition. This motivates the provided characterization in the next section.

We denote by $⟦\text{plp}⟧$ the set of functions computed by programs in plp. That is $⟦\text{plp}⟧\triangleq \{⟦\mathrm{P}⟧\mid \mathrm{P}\in \text{plp}\}$. A program $\mathrm{P}$ approximates function $f:{\{0,1\}}^{\ast }\to {\{0,1\}}^{\ast }$ with probability $p\in [0,1]$ if $\forall x\in {\{0,1\}}^{\ast },{|⟨f(x)|⟦\mathrm{P}⟧(x)⟩|}^2\ge p$, in other words if for all input, the output of $\mathrm{P}$ coincides with $f$ with probability at least $p$. The set of functions that can be approximated with probability at least $p$ is denoted by ${⟦\text{plp}⟧}_{\ge p}$.

The compilation algorithm takes as input a program $\mathrm{P}\in \text{plp}$ together with a list of the sizes $\overline{s}\triangleq [s_1,\mathrm{\dots },s_n]$ of its inputs. As in the semantics, the algorithm maintains a function that maps qubit list variables to lists of pointers to their qubits. Since the values of this function only depend on the size of the qubit variable, the generation of the circuit does not need to take qubit values into account.

The main compilation algorithm works by induction on the structure of the program statement. Compiling statements such as $\mathrm{l}[\mathrm{i}]\text{*=}{\mathrm{U}}^g(\mathrm{j});$ is straightforward: use the semantics to compute the wire number and which quantum gate to put into the circuit. Compiling a sequence is naturally done by composing the circuits obtained from compiling each statement. For compiling an if statement, note that Booleans only depend on constants and the size of qubit lists, and hence can be computed from the knowledge of list $\overline{s}$.

A qcase statement is compiled using controlled operations: consider $\text{qcase }\mathrm{l}[\mathrm{i}]\text{ of }\{0\to {\mathrm{S}}_0,1\to {\mathrm{S}}_1\}$, the circuit compiled for ${\mathrm{S}}_0$ should be controlled negatively on the wire computed for $\mathrm{l}[\mathrm{i}]$, the circuit compiled for ${\mathrm{S}}_1$ should be controlled positively on the same wire. To keep track of those controls, a structure is maintained that lists the control qubits and their state. The compilation of a non-recursive call consists in compiling the statement of the procedure after substituting its arguments by their expressions provided the qubit lists are non empty.

The only case that introduces complexity is that of recursive calls. A naive compilation strategy for recursive calls with a recursive procedure calling itself in both branches of a qcase, which is allowed by the ${\text{width}}_{\le 1}$ restriction, would yield a number of gates in the compiled circuit exponential in the recursion depth. To prevent this blow-up, the process (anchoring and merging) maintains a dictionary of ancillaries that associates an ancillary qubit to pairs of procedure names and sizes of the inputs: if the dictionary does not have a key for the considered procedure call, an anchoring ancillary is created, this ancillary is initialized through a multiple controlled-NOT (Toffoli gate) encoding the qcase control considered and used to control the quantum circuit of the procedure statement; if the key is present in the dictionary, this ancillary is updated with another Toffoli gate and the two procedure calls are automatically merged as illustrated in Figure 5. This strategy is sound as the ${\text{width}}_{\le 1}$ restriction ensures that two repeated calls always occur in orthogonal branches and can be simply combined in the same ancillary qubit.

To show the polylogarithmic depth bound on circuits implementing plp programs, we first need to demonstrate that merging in the context of plp can be done in polylogarithmic depth. Second, we show that the ${\text{width}}_{\ge 1}$ and half restrictions imply that the number of nested recursive procedure calls is polylogarithmically bounded.

In a plp program, a recursive procedure call always cuts one input qubit list in half. This means that the procedure will work either on the first half or on the second half of the qubit list. In the worst case, which is also the most typical, the procedure will be called recursively on each half depending on some condition. To avoid doubling the treatment of those calls, the anchoring and merging process merges those calls in such a way that the subcircuit for the procedure on half as many qubits is able to work on both halves. This implies conditionally swapping the two halves.

For instance, consider the SEARCH program in Figure 4 performing binary search. The procedure body of search, in the recursive case (i.e. where the input ${\overline{\mathrm{q}}}_1$ has size at least 4) consists of three (non-trivial) quantum cases. According to the state of the control qubits, we either (1) perform a recursive call to search on the second half of ${\overline{\mathrm{q}}}_1$, (2) apply a $NOT$ gate to ${\overline{\mathrm{q}}}_2$, or (3) perform a recursive call to search on the first half of ${\overline{\mathrm{q}}}_1$. Compiling these three branches in sequence incurs a recursive doubling of instances of search, as shown on the left circuit of Figure 5 where the circuit corresponding to the search procedure is symbolized by a gray box and a white box. This doubling can be avoided by merging the two calls to search in the same circuit, using controlled-swap gates (also called Fredkin gates). This new circuit, given on the right of Figure 5, contains only a single call to search. Note that two ancillas are used: one for controlling whether the recursive search is executed, the other for controlling the swapping between the first and second half. This accounts for a constant added cost for each recursive call. In addition, the cost of the controlled permutation between the first and second halves of ${\overline{\mathrm{q}}}_1$ should be taken into account.

Theorem 13 shows that programs in plp can be compiled to quantum circuits of polylog depth and polynomial size, which means that they compute operators in qnc. In this section, we show that plp is however not complete for qnc, thus recovering the known separation between fbqpolylog and qnc.

qnc is defined in [16] as the union for all $k\in \mathbb{N}$ of the classes of quantum unitary transformations that can be computed by a family of quantum circuits of depth $O({\log }^{k}n)$ with a polynomial number of ancillas. To compare with fbqpolylog, we define fbqnc (for Bounded-error qnc) as in [7] as the class of functions ${\{0,1\}}^{\ast }\to {\{0,1\}}^{\ast }$ that can be approximated with probability at least $2/3$ by a qnc transformation.

To study the relationship between plp and fbqnc, we use the query model of quantum computation which is the scenario in which one wishes to compute a function by making use of black boxes that are accessed via queries [2]. A black box performs a unitary transformation on the quantum state according to some oracle function $𝒪:{\{0,1\}}^{\ast }\to \{0,1\}$, where the operation is usually defined as $|\overline{x},y⟩\mapsto |\overline{x},y\oplus 𝒪(\overline{x})⟩$, which is considered to be performed in a single step.

Given a function $f$, we denote by $Q(f):\mathbb{N}\to \mathbb{N}$ the function that maps $n\in \mathbb{N}$ to the least number of queries necessary for a quantum algorithm to approximate $f$ with bounded-error on inputs of size $n$. The function $Q(f)$ gives a lower bound on the time complexity of approximating $f$. For instance, for the OR, AND, and PARITY defined as

we have that, while Grover’s algorithm [11] allows for a quadratic speedup in the query complexity of AND and OR, no speedup exists for PARITY.

In contrast to the lower bounds on the query complexity for AND, OR, and PARITY, we can show that there is an upper bound on the query complexity of functions approximable by programs in plp. This bound on quantum random-access Turing machines can be obtained by viewing the read-input transition as an oracle query as in [20, 21] and noting that the access to this oracle is bounded by the step-count of the QRATM.

Lemma 17 gives a polylogarithmic upper bound on the query complexity of functions in ${⟦\text{plp}⟧}_{\ge \frac{2}{3}}$. Lemmas 15 and 16 give lower bounds on the query complexity of AND, OR, and PARITY that are bigger than polylogarithms, hence proving that those functions are not in ${⟦\text{plp}⟧}_{\ge \frac{2}{3}}$ even though they can be approximated by circuits of polylogarithmic depth and polynomial size.

Combining this result with Theorem 13, we obtain a strict inclusion in fbqnc. Note that this strict inclusion is mandated by the well-known result that $\text{fbqpolylog}⊊\text{fbqnc}$.