Branch Sequentialization in Quantum Polytime

The language includes four basic datatypes for expressions, whose corresponding expressions are described in Figure 3.

• $\mathrm{■}$

  Integers: Integer expressions are variables $\mathrm{x}$, constant $n\in \mathbb{N}$, an addition by a constant $\mathrm{i}\pm n$, or the size $|\mathrm{s}|$ of a sorted set $\mathrm{s}$.

• $\mathrm{■}$

  Booleans: Such expressions $\mathrm{b}$ are defined in a standard way.

• $\mathrm{■}$

  Qubit: qubits expressions are of the shape $\mathrm{s}\text{[}\mathrm{i}\text{]}$ which denotes the $\mathrm{i}$-th qubit in sorted set $\mathrm{s}$.

• $\mathrm{■}$

  Sorted sets: lists of unique (i.e., non-duplicable) qubit pointers. Sorted-set expressions $\mathrm{s}$ are either variables $\overline{\mathrm{q}}$ or $\mathrm{s}\ominus \text{[}\mathrm{i}\text{]}$, the sorted set $\mathrm{s}$ where the $\mathrm{i}$-th element has been removed.

Let $\mathrm{s}\text{[}{\mathrm{i}}_1,\mathrm{\dots },{\mathrm{i}}_n\text{]}$ be a shorthand for $\mathrm{s}\text{[}{\mathrm{i}}_1\text{]},\mathrm{\dots },\mathrm{s}\text{[}{\mathrm{i}}_n\text{]}$. We also define syntactic sugar for pointing to the $n$-th last qubit in a sorted set, 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{]}$.

A program $\mathrm{P}\triangleq \mathrm{D}::\mathrm{S}$ is defined in Figure 3 as a list of (possibly recursive) procedure declarations $\mathrm{D}$, followed by a program statement $\mathrm{S}$.

Let Procedures be an enumerable set of procedure names. We write $\text{proc}\in \mathrm{P}$ to denote that proc appears in $\mathrm{P}$. Each procedure of name $\text{proc}\in \mathrm{P}$ is defined by a (unique) procedure declaration $\text{decl }\text{proc}(\overline{\mathrm{q}})\{\mathrm{S}\}\in \mathrm{D}$, which takes a sorted set $\overline{\mathrm{q}}$ as input parameter and executes the procedure statement $\mathrm{S}$. We sometimes write ${\mathrm{S}}^{\text{proc}}$ to explicitly refer to the procedure statement $\mathrm{S}$ of proc.

Statements include the no-op instruction, unitary application, sequences, conditional, quantum case, and procedures calls. For the sake of universality [5], in a unitary application $\mathrm{q}\text{*=}{\mathrm{U}}^f(\mathrm{j});$, ${\mathrm{U}}^f(\mathrm{j})$ is a unitary transformation that can take an integer $\mathrm{j}$ and a polynomial-time approximable [2] total function $f\in \mathbb{Z}\to [0,2\pi )$ as optional arguments. The $f$ and $\mathrm{i}$ can be omitted when they are not useful, as in a NOT gate.

The quantum conditional $\text{qcase }\mathrm{s}\text{[}\mathrm{i}\text{]}\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{s}[\mathrm{i}]$. The procedure call $\text{call }\text{proc}(\mathrm{s});$ runs procedure proc with sorted set expression $\mathrm{s}$. The quantum conditional can be extended to multiple qubits in a standard way as used in Figure 1: $\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 $\text{qcase }{\mathrm{q}}_1\text{ of }\{0\to \text{qcase }{\mathrm{q}}_2\text{ of }\{0\to {\mathrm{S}}_{00},1\to {\mathrm{S}}_{01}\},1\to \text{qcase }{\mathrm{q}}_2\text{ of }\{0\to {\mathrm{S}}_{10},1\to {\mathrm{S}}_{11}\}\}$.

We also make use of some syntactic sugar to describe statements encoding constant-time quantum operations. For instance, the CNOT, SWAP, as well as a controlled-phase shift gate are defined by:

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 $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>},$ $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}\in \mathrm{P}$ as $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}{\to }_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}$ whenever $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}\in {\mathrm{S}}^{\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="font-size:70\%;color:\#CA52D5;">1</span></sub>}}$. The relation ${⪰}_{\mathrm{P}}$ is then the transitive closure of ${\to }_{\mathrm{P}}$, and ${\sim }_{\mathrm{P}}$ denotes the equivalence relation where $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}{\sim }_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}$ if $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}{⪰}_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}$ and $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}{⪰}_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}$ both hold.

A procedure proc is recursive whenever $\text{proc}{\sim }_{\mathrm{P}}\text{proc}$ holds. The strict order ${\succ }_{\mathrm{P}}$ is defined as $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}{\succ }_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}$ if $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}{⪰}_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}$ and $\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">1</span></sub>}{\sim ̸}_{\mathrm{P}}\text{proc}\text{<sub class="ltx\_sub"><span class="ltx\_text" style="color:\#CA52D5;">2</span></sub>}$ both hold.

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

Qubits are interpreted as integers (pointers) and sorted sets are interpreted as lists of pointers. For each basic type $\tau$, the semantics of expressions, given in Figure 5, is described in a standard way as a function

$(\mathrm{e},l){\Downarrow }_{⟦\tau ⟧}v$ holds when expression $\mathrm{e}$ of type $\tau$ evaluates to the value $v\in ⟦\tau ⟧$ under the context $l\in ℒ(\mathbb{N})$. $l$ is simply the sorted set of qubit pointers considered when evaluating $\mathrm{e}$. For instance, we have that $(\overline{\mathrm{q}}\text{[}2\text{]},[1,4,5]){\Downarrow }_{\mathbb{N}}4$ (the second qubit has index $4$), $(\overline{\mathrm{q}}\ominus \text{[}4\text{]},[1,4,5]){\Downarrow }_{ℒ(\mathbb{N})}[]$ ($[]$ is used for errors on type $ℒ(\mathbb{N})$), $(\overline{\mathrm{q}}\text{[}4\text{]},[1,4,5]){\Downarrow }_{\mathbb{N}}0$ (index $0$ encodes error on type $\mathbb{N}$), and $(\overline{\mathrm{q}}\ominus \text{[}3\text{]},[1,4,5]){\Downarrow }_{ℒ(\mathbb{N})}[1,4]$ (third qubit removed).

Let ${\mathscr{H}}_{2^n}$ denote the Hilbert space of $n$ qubits ${ℂ}^{2^n}$ and $𝒫(\mathbb{N})$ denote the powerset of $\mathbb{N}$.

A configuration $c$ over $n$ qubits is of the shape $(\mathrm{S},|\psi ⟩,A,l)$, for some statement $\mathrm{S}\in \text{Statements}\cup \{\top ,\perp \})$, $\top$ and $\perp$ being two special symbols denoting termination and error, respectively, $|\psi ⟩$ is a quantum state in ${\mathscr{H}}_{2^n}$, where $A\in 𝒫(\mathbb{N})$ is the set of accessible qubit pointers, and where $l\in ℒ(\mathbb{N})$ is the list of qubit pointers under consideration. Let ${\text{Conf}}_n$, be the set of configurations over $n$ qubits. The initial configuration in ${\text{Conf}}_n$ of a program $\mathrm{D}::\mathrm{S}$ on input state $|\psi ⟩\in {\mathscr{H}}_{2^n}$ is $c_{init}(|\psi ⟩)\triangleq (\mathrm{S},|\psi ⟩,\{1,\mathrm{\dots },n\},[1,\mathrm{\dots },n])$. A final configuration can be defined in the same way as $c_{final}(|\psi ⟩)\triangleq (\top ,|\psi ⟩,\{1,\mathrm{\dots },n\},[1,\mathrm{\dots },n])$.

Each unitary transformation $\mathrm{U}$ of a unitary application $\overline{\mathrm{q}}\text{[}\mathrm{i}\text{]}\text{*=}{\mathrm{U}}^f(\mathrm{j});$, comes with a function $⟦\mathrm{U}⟧$ assigning a unitary matrix $⟦\mathrm{U}⟧(f)(n)\in {ℂ}^{2\times 2}$ to each integer $n$ and polynomial-time approximable total function $f\in \mathbb{Z}\to [0,2\pi )$. For example, the gates of the quantum Fourier transform can be defined by $R_n\triangleq ⟦\text{Ph}⟧(\lambda x.\pi /2^{x-1})(n)$ with . The other basic unary gates are the NOT and the $R_Y$ gate.

The big-step semantics $\cdot \stackrel{\cdot }{⟶}\cdot$ is defined in Figure 4 as a relation in ${\bigcup }_{n\in \mathbb{N}}{\text{Conf}}_n\times \mathbb{N}\times {\text{Conf}}_n$. Standard notations from quantum computation are used such as tensor product $\otimes$, $⟨\psi |$ for the conjugate transpose of $|\psi ⟩$, or given a dimension $m$, ${|k⟩}_n\triangleq I_{2^{n-1}}\otimes |k⟩\otimes I_{2^{m-n}}$ for $k\in \{0,1\}$. In Figure 4, the set $A$ of accessible qubits is used to ensure that unitary operations on qubits can be physically implemented. For example, to ensure reversibility, in a quantum branch $\text{qcase }\mathrm{s}\text{[}\mathrm{i}\text{]}\text{ of }\{0\to {\mathrm{S}}_0,\mathrm{\hspace{0.17em}1}\to {\mathrm{S}}_1\}$, statements ${\mathrm{S}}_0$ and ${\mathrm{S}}_1$ cannot access $\mathrm{s}\text{[}\mathrm{i}\text{]}$.

Intuitively, when $c\stackrel{m}{⟶}{c}^{\prime }$ holds, the time complexity $m$ is an integer corresponding to the maximum number of procedure calls performed over each (classical and quantum) branch during the evaluation of a configuration $c\in {\text{Conf}}_n$. We write $⟦\mathrm{P}⟧(|\psi ⟩)=|{\psi }^{\prime }⟩$, whenever $c_{init}(|\psi ⟩)\stackrel{m}{⟶}{c}_{final}(|{\psi }^{\prime }⟩)$ holds for some $m$. If the program $\mathrm{P}$ terminates on any input (i.e., always reaches a final configuration) then $⟦\mathrm{P}⟧$ is a total function on quantum states.

We define three restrictions on the programming language to consider only a strict subset, called pbp for Polynomial Branching Programs, on which branch sequentialization can be avoided. First, we define a well-foundedness criterion to consider only terminating programs. A program $\mathrm{P}$ is well-founded if each recursive procedure call removes at least one qubit in its parameter. wf denotes the set of well-founded programs. Then, we define a criterion to exclude programs with exponential runtime. Toward that end, the notion of width of a procedure proc in a program $\mathrm{P}$ is introduced.

Programs of width $1$ are inherently polynomial as they cannot perform an exponential number of procedure calls in sequence. However, the total number of calls in superposition (that is to say, across all branches of computation) may be exponential for such programs by the definition of the width for conditional and quantum case. For this reason, a compilation strategy whose circuits scale as the sum of the branches instead of their maximum can lead to circuits of exponential size.

Finally, for the purpose of our compilation process, we impose further syntactical conditions on programs. We restrict our attention to what we will call basic programs.

basic programs are programs whose procedure calls are restricted to the full qubit list or to a fixed qubit list expression. This restriction simplifies the treatment of recursive procedure calls during compilation.

Notice that pbp is strictly included in the programming language of [17], that roughly corresponds to $\text{wf}\cap {\text{width}}_{\le 1}$, where procedure calls can take an extra integer parameter. Since the language of [17] is polytime-sound, so is pbp (Theorem 11). The restriction to programs in pbp does not compromise the extensional completeness of the language as, by Theorem 11, pbp is complete for the class fbqp of functions in ${\{0,1\}}^{\ast }\to {\{0,1\}}^{\ast }$, i.e., functions that can be approximated with at least $2/3$ probability by a quantum Turing machine running in polynomial time [6, 29].

A control structure $cs$ is a partial map in $\mathbb{N}\to \{0,1\}$. Intuitively, $cs$ represents a map from qubit pointers to their control values for a controlled gate and will also be used as a shorthand notation in circuits. For $n\in \mathbb{N}$ and $k\in \{0,1\}$, let $cs[n:=k]$ be the control structure obtained from $cs$ by setting $cs(n)=k$. We denote by $dom(cs)$ the domain of the control structure and by $\cdot$, the control structure such that $dom(\cdot )=\mathrm{\varnothing }$.

During the compilation of the program statement, every recursive call is handled as follows: if it is the first call with this procedure name and input size, an ancilla is created and its procedure statement is compiled under a control on this ancilla (anchoring), otherwise this procedure call has already been compiled and the control structure of the new call is sent into the corresponding ancilla (merging). Anchoring and merging are represented in Figure 7 as rewrite rules on quantum circuits for a procedure call $\text{call }\text{proc}(\mathrm{s})$, $cs$ denoting the control structure corresponding to the (possibly nested) quantum cases, where the procedure call occurs.

$a_k^{\text{proc}}$ represents the ancilla introduced (in case of anchoring) or reused (in case of merging). The integer $k$ refers to the number $|\mathrm{s}|$ of qubits in the procedure call. The grey box materializes the controlled statements left to compile.

Let controlled statements be pairs of the shape $(cs,\mathrm{S})$, for some control structure $cs$ and some statement $\mathrm{S}$. In the compilation process, controlled statements $(cs,\mathrm{S})$ are used to represent a statement $\mathrm{S}$ that remains to be compiled into a quantum circuit $C$ together with a control structure $cs$, representing the qubits controlling the compiled circuit $C$. The compilation algorithm compile is described by the rewrite rules of Figure 8. Generating the circuit corresponding to the program $\mathrm{P}=\mathrm{D}::\mathrm{S}$ will consist in running compile on the controlled statement $(\cdot ,\mathrm{S})$ for a fixed list of qubits pointers $[1,\mathrm{\dots },n]$ (hence, an input of fixed size $n$). We denote by $\text{compile}(\mathrm{P},n)$ the circuit obtained for program $\mathrm{P}$ on size $n$. The algorithm standardly generates the quantum circuit corresponding to a $\text{wf}\cap {\text{width}}_{\le 1}$ program inductively on the statement $\mathrm{S}$. Indeed, in the rules of Figure 8 when compile is called on a given controlled statement $(cs,\mathrm{S})$, an inductive call to compile is performed on controlled statements whose statements are sub-statements of $\mathrm{S}$. The two base cases are the rules for the skip statement and the unitary application. In these cases, the compilation just outputs the identity circuit and a controlled gate computing the unitary, respectively. The rules for sequence and quantum case perform two inductive calls to compile on each branch of the statement. The rule for quantum case is the only rule that directly performs changes on the control structure. In the particular case of a call to a recursive procedure (i.e., when $w_{\mathrm{P}}^{\text{proc}}({\mathrm{S}}^{\text{proc}})>0$), compile calls the optimize subroutine to perform anchoring and merging. This call to optimize is highlighted in Figure 8 through the use of a shaded square , which takes the procedure name proc as superscript. We call this process the optimization of procedure proc.

The rewrite rules for the subroutine optimize on procedure proc are described in Figure 9. This subroutine takes two input parameters:

• $\mathrm{■}$

  a first list $l_{\mathrm{Cst}}$ of controlled statements, the ones to be optimized,

• $\mathrm{■}$

  a second list of controlled statements, called contextual list called $l_{\text{M}}$ and denoted by , consisting in controlled statements that are orthogonal to those in $l_{\mathrm{Cst}}$ and do not contain recursive procedure calls.

As described by the last rule of Figure 8, each initial call to optimize is performed on the singleton list containing one controlled statement $(cs,{\mathrm{S}}^{\text{proc}}\{\mathrm{s}/\overline{\mathrm{q}}\})$ and a contextual circuit equal to the identity circuit.

In Figure 9, the rules are applied by considering the first controlled statement in the list $l_{\mathrm{Cst}}$. We just specify the most interesting case below:

• $\mathrm{■}$

  For a controlled statement $(cs,{\mathrm{S}}_1{\mathrm{S}}_2)$, two distinct rules can be applied. In the first scenario, where $w_{\mathrm{P}}^{\text{proc}}({\mathrm{S}}_1)=1$, we have that ${\mathrm{S}}_1$ contains a recursive procedure call and ${\mathrm{S}}_2$ does not (this is a consequence of the ${\text{width}}_{\le 1}$ condition in pbp), or the converse. Depending on this, the rule select on which control statement $(cs,{\mathrm{S}}_1)$ or $(cs,{\mathrm{S}}_2)$ to perform the optimization and, append the compiled circuit of the other controlled statement to the left or to the right.

• $\mathrm{■}$

  For a controlled statement with an if statement, we precompute the boolean value $b$ (which only depends on classical values such as the integer input and the register size), and according to whether the corresponding branch contains a recursive call or not, we either add the controlled statement to $l_{\mathrm{Cst}}$ or the contextual list.

• $\mathrm{■}$

  For a controlled statement with a qcase statement, one or two of the branches are added to the list $l_{\mathrm{Cst}}$ depending on whether they are both recursive or not. The branch that is not recursive is added to the contextual list.

• $\mathrm{■}$

  For a controlled statement with a procedure call $\text{call }\text{proc’}(\mathrm{s});$ we perform either anchoring or merging depending on whether the ancilla $a_{|\mathrm{s}|}^{\text{proc’}}$ exists or not. In the case of merging, we include a controlled permutation of qubit addresses (as described in Lemma 12) in order to match the input qubits of the different procedures. Notice that, for basic programs, the input qubits will match and therefore this permutation is trivial, and merging is as described in Figure 7.

At the end of optimize, when $l_{\mathrm{Cst}}=[]$, we rearrange the contextual list in the following way. Let $[(c{s}_1,{\mathrm{S}}_1,l_1),\mathrm{\dots },(c{s}_k,{\mathrm{S}}_k,l_k)]$ be the state of the contextual list at the end of optimize. We may rewrite each controlled statement as a list of its atomic elements, with a transformation denoted seq. Let $(\mathrm{q},l){\Downarrow }_{\mathbb{N}}n$, then

This separation of statements allows for a partitioning according to the type of procedure call appearing in the statement. Given a list of controlled statements $ℒ$, we define the list $[{ℒ}_0,{ℒ}_1,\mathrm{\dots },{ℒ}_m]$ where, for procedures proc₁, …, proc_m that are not mutually recursive.

Given our choice of procedures and the controlled statements obtained from seq, this partition is well-defined. Performing these two partitions (first in terms of sequential order of statements, and then according to procedure calls), we are able to rewrite:

The different instances of optimize contain calls to procedures that are mutually recursive, which will allow for further anchoring and merging.

In this section, we discuss the validity of the compilation algorithm. One first observation should be that, given a pbp program, the compilation necessarily terminates. For instance, in compile (Figure 8), all rules besides the procedure call rewrite the controlled statement into either a circuit or into instances of compile of smaller statements. In the case of a procedure call, the rewriting of the procedure body produces a finite number of calls to procedures of lower recursive level.

In optimize, a recursive procedure will result in a finite number of calls to mutually recursive procedures – this is ensured by the well-foundedness condition wf, that requires that recursive procedure calls reduce the size of the input, therefore procedure calls either reduce the level of recursion or the number of available qubits.

The soundness of the compilation algorithm is ensured by an orthogonality invariant in optimize. Let $cs,c{s}^{\prime }$ be two control structures. We say that $cs$ and $c{s}^{\prime }$ are orthogonal if there exists $i\in \text{dom}(cs)\cap \text{dom}(c{s}^{\prime })$ such that $cs(i)=1-c{s}^{\prime }(i)$. Two controlled statements are orthogonal if their control structures are orthogonal.

We illustrate the compilation process with the program REC, of Figure 10. Notice that REC is in $\text{wf}\cap {\text{width}}_{\le 1}$ but does not belong to pbp, as the procedure rec performs two recursive calls on different sorted sets $\overline{\mathrm{q}}\ominus \text{[}1\text{]}$ and $\overline{\mathrm{q}}\ominus \text{[}1,2\text{]}$. This example thus illustrates that the compilation algorithm is not restricted to pbp.

Given that rec is a recursive procedure, its compilation is performed within optimize. We denote by the empty box the procedure statement ${\mathrm{S}}^{\text{rec}}$ and by the dotted box the statement $\text{call }\text{rec}(\mathrm{s});$. Applying rewrite rules to rec we obtain the transitions:

The first step is obtained by applying the rule of if statements, where we assume that $|\overline{\mathrm{q}}|>2$. Afterwards, we apply twice the rule for the qcase statement, adding the two qubits $\overline{\mathrm{q}}\text{[}1\text{]}$ and $\overline{\mathrm{q}}\text{[}2\text{]}$ to the control structure. Finally, the compilation of the skip statement corresponds to the empty circuit. We denote by $\stackrel{\text{rec}}{\to }$ the application of this sequence of rewrite rules, which is used in Figure 11.

One important thing to notice in Figure 11 is that the compilation strategy does not avoid branch sequentialization locally but rather asymptotically in the construction of the circuit. In other words, the qcase statement in rule rec does generate two instances of ${\mathrm{S}}^{\text{rec}}$ in the circuit in sequence, one for each branch. However, the merging of calls to rec on inputs of the same size ensures that only one instance per input size needs to be compiled, and therefore this strategy achieves linear complexity in the number of gates.

First, we show that the problem of branch sequentialization is solved in pbp. For that purpose, we show that the size of quantum circuit obtained through compiling a pbp program is bounded asymptotically by the time complexity of the program. As the time complexity is the maximum of the complexity of the two branches of a quantum case statement, the branch sequentialization problem is avoided on pbp programs, as the size of the circuit is asymptotically equal to its time semantics. Given a circuit $C$, let $\mathrm{\#}C$ denote its size, i.e., number of gates and wires.

One may notice that, in the rules of compile (Figure 8), the compilation of a qcase statement generates two controlled statements in sequence. Similarly, the rule of optimize (Figure 9) for qcase statements appends two controlled statements to the list $l_{\mathrm{Cst}}$ in the case where they are both recursive. This does not pose a problem as, anchoring and merging will ensure that the asymptotic complexity of this statement will be given by the maximum complexity of the branches.

Having shown in Theorem 9 that pbp programs can avoid branch sequentialization, we now turn to the question of whether they constitute an interesting fragment of quantum programs, given that it is restricted by the wf, ${\text{width}}_{\le 1}$ and basic conditions. We show that the set of pbp programs is sound and complete for quantum polynomial time via an implicit characterization of fbqp, i.e. the set of classical functions that can be approximated with bounded error by a polytime quantum Turing machine [30, 17].

Since the considered programming language does not allow for qubit creation, in order to define functions where the output is larger than the input, we make use of polytime padding. A polytime padding function is a function $f:{\{0,1\}}^{\ast }\to {\{0,1\}}^{\ast }$ computable by a (classical) polytime Turing machine such that $f(x)=xy$, for some $y$ depending only on the length of $x$ (and not the value of $x$). Given a set $ℱ$ of programs, $⟦ℱ⟧$ denotes the set of functions given by $⟦\mathrm{P}⟧\circ f$, where $\mathrm{P}\in ℱ$, $f$ is a polytime padding function, and $\circ$ is the standard function composition. For any $p\in (\frac{1}{2},1]$, we denote by ${⟦ℱ⟧}_{\ge p}$ the set of functions in $⟦ℱ⟧$ that approximate a classical function with probability at least $p$.

The basic restriction of pbp can be thought of as ensuring that qubits are consumed in a uniform way. As a consequence, any two procedure calls on inputs of size $n$ will correspond to precisely the same $n$ qubits. This guarantees that two compatible procedure calls can be merged simply by combining control structures in the same ancilla.

Without this constraint (i.e., on $\text{wf}\cap {\text{width}}_{\le 1}$), we can use precisely the same compilation strategy but where merging is done by control-swapping registers into a single procedure call. For $k$ instances of a procedure on input size $n$, this requires $k-1$ controlled swaps, each requiring $O(n)$ operations in the worst case. An example of merging two unitary gates $U$ with controlled-swaps is given in Figure 12. If we allow for parallelization of gates in the circuit, this can be done in logarithmic depth, as shown in Lemma 12. An example of a controlled permutation is shown in Figure 13, where vertical dashed lines separate time slices where gates can be applied simultaneously.

An extension of compile with controlled-swapping as in Figure 12 used for merging procedures ensures the following bound for $\text{wf}\cap {\text{width}}_{\le 1}$ programs.

The compile algorithm strictly improves upon the size bounds of other compilation algorithms [17], as illustrated by Table 1. These bounds can be empirically tested using the implementation of the compiler available at gitlab.inria.fr/mmachado/pfoq-compiler. In some cases, such as Examples 16 and 15 given in Appendix B, we find families of programs where the gap in complexity (i.e. the degree of the polynomial) can be made arbitrarily large.

In $k$-Chained Substrings (Example 16), we consider the problem of detecting whether an input string contains substrings $y_1,\mathrm{\dots },y_k$ appearing in that order. For a certain choice of substrings $y_i$, we define a pbp program of linear time complexity for which the compilation strategy in [17] results in circuits of size $\mathrm{\Theta }(n^{2k})$. The problem Sum($r$), given in Example 17, consists of checking if an input $x=x_1\mathrm{\dots }{x}_n$ satisfies ${\sum }_{i=1}^n{x}_i=r$.