# Branch Sequentialization in Quantum Polytime

Emmanuel Hainry, Romain Péchoux, Mário Alberto Machado da Silva

► To cite this version:

Emmanuel Hainry, Romain Péchoux, Mário Alberto Machado da Silva. Branch Sequentialization in Quantum Polytime. FSCD 2025, Jul 2025, Birmingham, United Kingdom. 10.4230/LIPIcs.FSCD.2025.22. hal-04823282v4

HAL Id: hal-04823282

https://inria.hal.science/hal-04823282v4

Submitted on 23 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Branch Sequentialization in Quantum Polytime

Emmanuel Hainry

Romain Péchoux

Mário Silva

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

September 23, 2025

`{hainry,pechoux,mmachado}@loria.fr`

## Abstract

Quantum algorithms leverage the use of quantumly-controlled data in order to achieve computational advantage. This implies that the programs use constructs depending on quantum data and not just classical data such as measurement outcomes. Current compilation strategies for quantum control flow involve compiling the branches of a quantum conditional, either in-depth or in-width, which in general leads to circuits of exponential size. This problem is coined as the branch sequentialization problem. We introduce and study a compilation technique for avoiding branch sequentialization on a language that is sound and complete for quantum polynomial time, thus, improving on existing polynomial-size-preserving compilation techniques.

# 1 Introduction

## 1.1 Motivation

Quantum computing is an emerging paradigm of computation, where quantum physical phenomena such as entanglement and superposition are used to obtain an advantage over classical computation. A testament to the richness of the field is the variety of computational models: quantum Turing machines [6], quantum circuits [31, 26], measurement-based quantum computation [7, 12], linear optical circuits [21], among others.

In recent decades, a lot of effort has been put into developing high-level quantum programming languages that allow programmers to abstract away from the technicalities of these low-level models [27, 3]. Toward that end, several verification techniques such as type systems [15] or categorical approaches for reasoning about program semantics [4, 19] have been studied and developed to ensure the physical reality of compiled programs, for example, by ensuring that they satisfy the properties of quantum mechanics such as the no-cloning theorem [1] and unitarity [14].

An important line of research in this area involves checking polytime termination of quantum programs [11, 29, 17], by showing that any program can be simulated by a polytime quantum Turing machine (QTM). As a consequence of Yao's Theorem [31], demonstrating that polynomial-time QTMs are computationally equivalent to uniform and poly-sized quantum circuit families, such programs can be instantiated by a uniform family of quantum circuits of polynomial size, i.e., with a polynomial number of qubits and gates. However, direct compilation techniques often fail to ensure this property, due to the use of quantum branching, where the flow in a conditional is determined by the state of a qubit.

As an illustrative example, consider a quantum case, of the shape

$$ \mathbf{qcase} \ q_1, \dots, q_k \ \mathbf{of} \ \{i \to S_i\}_{i \in \{0,1\}^k}, $$

which executes the superposition of the unitary transformations $U_i$ implemented by statements $S_i$, depending on the state $|i\rangle$ of the control qubits $q_1, \dots, q_k$. This statement can be simulated by a QTM that, depending on $k$ symbols in its tape, performs the instructions of different QTMs $M_i$ in superposition. Consequently, its runtime is the maximum runtime among all $M_i$ ([6, Branching Lemma]). Instantiating this qcase statement on quantum circuits can be done sequentially (in-depth) or in parallel (in-width). An in-depth encoding consists in applying each controlled-$U_i$ gate sequentially, thus implementing the unitary transformation $\sum_{i \in \{0,1\}^k} |i\rangle\langle i| \otimes U_i$. The depth of the
resulting circuit is the sum of the depths of all $U_i$, which is exponential in the number $k$ of control qubits. An alternative strategy, inspired by QRAM, allows for the execution of each $U_i$ in parallel in the circuit, using controlled swaps to perform routing of qubit addresses in linear depth on the number of control qubits. Since in this case the unitaries are parallelized, the circuit depth is the maximum among the depths of $U_i$, but this strategy results in circuits where the width scales as the sum of the complexities of $U_i$. Consequently, this parallelization requires a number of ancillas that grows exponentially on the number of control qubits. In summary, any implementation, that is agnostic about the structure of each $U_i$, should incur such an exponential cost, as each **qcase** corresponds to the preparation of an arbitrary quantum state [34, 16].

Automatic implementations of quantum conditionals therefore produce circuits with a size that scales with the sum (rather than the maximum) of the complexity of each branch. This problem, coined *branch sequentialization* in [32], leads, in many cases, to an exponential blow-up in circuit complexity, forcing the programmer to rewrite and optimize their code in order to make use of the program structure and improve the complexity bound. A challenging issue is, therefore, to develop quantum programming languages that avoid branch sequentialization by ensuring the correct circuit complexity for quantum control statements while providing full use of quantum control to the programmer [32, 33].

## 1.2 Contribution

This paper solves the above issue by introducing a programming language, called PBP for Polynomially Branching Program, with quantum case and first-order recursive procedures, on which compilation of quantum conditional does not lead to an exponential blow-up in circuit size. Our main contributions are as follows:

* We introduce a compilation strategy **compile** (Figures 7 and 8) into quantum circuits, show its soundness (Theorem 1), and show that it avoids branch sequentialization on PBP (Theorem 2), a language with restrictions on recursive calls to procedures. Toward that end, we formally define the time complexity $Time_P: \mathbb{N} \to \mathbb{N}$ of a program P (Definition 1) as a map from the number $n$ of qubits to the maximal number of procedures called during a program execution on the Hilbert space $\mathbb{C}^{2^n}$. The time complexity of a **qcase** statement is precisely the maximum of the time complexity of its branches and we show that branch sequentialization is avoided as the circuits generated by **compile** have size bounded asymptotically by the time complexity of the compiled program (Theorem 2).

* A natural question concerns the expressive power of language PBP. We also solve this issue by showing that PBP is sound and complete for quantum polynomial time (Theorem 3). Consequently, any polytime quantum algorithm can be encoded by a PBP program. We illustrate the methodology through well-known examples such as the program QFT realizing the quantum Fourier transform (Example 5).

* We also discuss asymptotic bounds for a strict extension of PBP, where the reduction in the input sorted set passed to procedure calls can be arbitrary. We show that this extension only increases the circuit complexity of the no-branch-sequentialization case by a linear factor (Theorem 4).

* We also show that **compile** strictly improves on existing compilation strategies on first-order quantum programs with quantum case [17] by a polynomial speedup of arbitrarily large degree (Table 1).

## 1.3 A bird's-eye view of our compilation strategy

We will now consider a simple illustrating example where branch sequentialization can exponentially worsen the size complexity of the compiled circuit, and show how our compilation strategy can preserve a polynomial bound.

The program **PAIRS** defined in Figure 1 consists in a simple call to procedure **pairs** (line 10) on a list $\bar{q}$ of unique qubits. Let $|\bar{q}|$ be the number of qubits in $\bar{q}$. By language design, the procedure **pairs** immediately terminates whenever $|\bar{q}| = 0$. The procedure enters a quantum case (line 3) when $|\bar{q}| \ge 2$, otherwise it applies a NOT gate to the single qubit (line 9). On line 3, the program will branch depending on the state $\bar{q}[1,2]$ of the first two qubits in $\bar{q}$. Out of all four cases (lines 4-7), **pairs** only
<figure><img src="image_2.png" /><figcaption>Figure 2: Compilation strategies.</figcaption></figure>

performs an operation when the first two qubits are in state $|00\rangle$ or $|11\rangle$, in which case it performs a recursive call on $\bar{q} \ominus [1, 2]$, the list obtained by removing the first and second qubits of $\bar{q}$.

Given an input state $|xy\rangle$, with $x \in \{0, 1\}^*$ and $y \in \{0, 1\}$, `pairs` will apply a NOT gate to the last qubit $y$ if and only if $x$ is a string in the language $(00|11)^*$. Since `pairs` performs at most one call per branch, and consumes 2 qubits from its input while doing so, its time complexity is in $O(|\bar{q}|)$, when taking the `qcase` complexity as the maximum of each branch.

We now discuss the circuit compilation of `pairs`, when $|\bar{q}| \ge 2$. In Figure 2, we give three strategies (**a**), (**b**), and (**c**), exemplifying different approaches. Strategies (**a**) and (**b**) are automatic compilation strategies, which ignore the inner structure of the program – the fact that the body of the two non-skip branches of the `qcase` are identical and therefore encode the same unitary transformation.

1. `decl pairs(\bar{q}){`

2. `if |\bar{q}| \ge 2 then`

3. `qcase \bar{q}[1, 2] of {`

4. `00 \to call pairs(\bar{q} \ominus [1, 2]);`

5. `01 \to skip;`

6. `10 \to skip;`

7. `11 \to call pairs(\bar{q} \ominus [1, 2]);`

8. `}`

9. `else \bar{q}[1] *= NOT;}`

10. `:: call pairs(\bar{q});`

<caption>Figure 1: Program PAIRS.</caption>

Figure 2(**a**) represents an in-depth strategy, whereas Figure 2(**b**) implements an in-width strategy, making use of different registers $r_{00}$ and $r_{11}$, both initialized to $|0^{|\bar{q}|-2}\rangle$ to perform each branch in parallel and then recombine the results in the same register. These two implementations require two recursive calls to `pairs` and, consequently, their size complexity is the sum of the complexities of the two branches. These two strategies are performing branch sequentialization and, in both cases, the compiled circuit has size exponential in $|\bar{q}|$. In contrast, Figure 2(**c**) avoids this exponential blow-up, making use of the fact that the two branches are identical. This strategy is able to *merge* the recursive calls into a single procedure call with the use of one ancilla. This is precisely the type of strategy used by our compilation algorithm `compile` (Section 3). Although this example is relatively simple due to similar recursive calls, `compile` allows to deal with more involved situations, by merging recursive calls on different parameters.

## 1.4 Related work

Resource optimization in low-level models of quantum computation is a well-studied subject. Given a specific quantum circuit, it is possible to reduce its number of gates (or at least its number of non-Clifford gates) via techniques such as gate substitution and graph rewriting [25, 23, 20, 13]. The study of resource optimization in the asymptotic scenario is a relatively young research area as it involves reasoning about families of circuits and program structure. Different implicit characterizations of quantum complexity classes have been developed using a lambda-calculus [11], function algebras [29, 30] and a first-order programming language [17]. The last of these provided a compilation strategy into quantum circuits with bounds on the circuit size based on the syntactic restrictions placed on the programs.

Compilation strategies for the quantum control statement (also called quantum switch case or quantum multiplexer) have been studied, for instance, in state preparation [22], appearing in quantum machine learning [18] and Hamiltonian simulation [8]. These techniques either focus on optimizing number of qubits (circuit width) [34] or circuit depth [28], but in all cases correspond to circuits of exponential size. In order to improve on these bounds, one must restrict the set of programs to those
that admit an efficient implementation, which can be deduced from the program structure. Optimized compilation techniques in that scenario can then be judged on expressivity and completeness: how easily can one write a program while ensuring the syntactical restrictions? Do these restrictions encompass all efficient programs? The field of implicit computational complexity is particularly well-suited to answer these questions [9, 10].

## 2 First-Order Programming Language with Quantum Case

In this section, we introduce a programming language with quantum control and first-order recursive procedures. After introducing its syntax and semantics, we introduce a restriction PBP (for Polynomially Branching Programs) on which branch sequentialization can be avoided.

<table><caption>Figure 3: Syntax of programs.</caption><tr><td>(Integers)</td><td>i,j,k</td><td>::=</td><td>x | n | i &plusmn; n | s|</td></tr><tr><td>(Booleans)</td><td>b</td><td>::=</td><td>i &ge; i | ... | b &and; b | ...</td></tr><tr><td>(Qubits)</td><td>q</td><td>::=</td><td>s[i]</td></tr><tr><td>(Sorted sets)</td><td>s</td><td>::=</td><td>q&#773; | s &ominus; [i]</td></tr><tr><td>(Statements)</td><td>S</td><td>::=</td><td><b>skip</b>; | q *:= U<sup>f</sup>(j); | S S | <b>if</b> b <b>then</b> S else S<br>| <b>qcase</b> q <b>of</b> {0 &rarr; S, 1 &rarr; S} | <b>call</b> <b>proc</b>(s);</td></tr><tr><td>(Procedure declarations)</td><td>D</td><td>::=</td><td>&epsilon; | <b>decl</b> <b>proc</b>(q&#773;){S}, D</td></tr><tr><td>(Programs)</td><td>P(q&#773;)</td><td>::=</td><td>D::: S</td></tr></table>

### 2.1 Syntax of Programs

The language includes four basic datatypes for expressions, whose corresponding expressions are described in Figure 3. (i) *Integers*: Integer expressions are variables x, constant $n \in \mathbb{N}$, an addition by a constants $i \pm n$, or the size $|s|$ of a sorted set $s$. (ii) *Booleans*: Such expressions b are defined in a standard way. (iii) *Qubit*: qubits expressions are of the shape $s[i]$ which denotes the i-th qubit in sorted set $s$. (iv) *Sorted sets*: lists of unique (i.e., non-duplicable) qubit pointers. Sorted-set expressions s are either variables $\bar{q}$ or $s \ominus [i]$, the sorted set $s$ where the i-th element has been removed. Let $s[i_1, ..., i_n]$ be a shorthand for $s[i_1], ..., s[i_n]$. We also define syntactic sugar for pointing to the n-th last qubit in a sorted set, by defining for any $n \ge 1$, $\bar{q}[-n] \triangleq \bar{q}(|\bar{q}| - n + 1]$.

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

Let Procedures be an enumerable set of procedure names. We write $proc \in P$ to denote that $proc$ appears in $P$. Each procedure of name $proc \in P$ is defined by a (unique) procedure declaration `decl proc(\bar{q}){S} \in D`, which takes a sorted set $\bar{q}$ as input parameter and executes the procedure statement $S$. We sometimes write $S^{proc}$ to explicitly refer to the procedure statement $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 $q *:= U^f(j)$, $U^f(j)$ is a unitary transformation that can take an integer $j$ and a polynomial-time approximable $[2]$ total function $f \in \mathbb{Z} \to [0, 2\pi)$ as optional arguments. The $f$ and $i$ can be omitted when they are not useful, as in a NOT gate.

The quantum conditional `qcase s[i] of {0 \to S_0, 1 \to S_1}` allows branching by executing statements $S_0$ and $S_1$ in superposition according to the state of qubit $s[i]$. The procedure call `call proc(s)` runs procedure $proc$ with sorted set expression $s$. The quantum conditional can be extended to multiple qubits in a standard way as used in Figure 1.

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:

$$ 
\begin{align*}
\text{CNOT}(q_1, q_2) &\triangleq \text{qcase } q_1 \text{ of } \{0 \to \text{skip}; 1 \to q_2 *:= \text{NOT;}\} \\
\text{SWAP}(q_1, q_2) &\triangleq \text{CNOT}(q_1, q_2) \text{ CNOT}(q_2, q_1) \text{ CNOT}(q_1, q_2) \\
\text{CPHASE}(q_1, q_2, i) &\triangleq \text{qcase } q_1 \text{ of } \{0 \to \text{skip}; 1 \to q_2 *:= \text{Ph}^{\lambda x \cdot \pi/2^{x-1}}(i); \}
\end{align*}
$$
<figure><img src="image_3.png" /><figcaption>Figure 4: Semantics of statements.</figcaption></figure>

Given a program $P \triangleq D :: S$, the call relation $\rightarrow_P \subseteq$ Procedures $\times$ Procedures is defined for any two procedures $proc_1, proc_2 \in P$ as $proc_1 \rightarrow_P proc_2$ whenever $proc_2 \in S^{proc_1}$. The relation $\ge_P$ is then the transitive closure of $\rightarrow_P$, and $\sim_P$ denotes the equivalence relation where $proc_1 \sim_P proc_2$ if $proc_1 \ge_P proc_2$ and $proc_2 \ge_P proc_1$ both hold. A procedure $proc$ is recursive whenever $proc \sim_P proc$ holds. The strict order $>_P$ is defined as $proc_1 >_P proc_2$ if $proc_1 \ge_P proc_2$ and $proc_1 \not>_P proc_2$ both hold.

## 2.2 Semantics of Programs

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

<figure><img src="image_4.png" /></figure>

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

<figure><img src="image_5.png" /></figure>

$(e, l) \Downarrow_{\llbracket \tau \rrbracket} v$ holds when expression $e$ of type $\tau$ evaluates to the value $v \in \llbracket \tau \rrbracket$ under the context $l \in \mathcal{L}(\mathbb{N})$. $l$ is simply the sorted set of qubit pointers into consideration when evaluating $e$. For instance, we have that $(\bar{q}[2], [1, 4, 5]) \Downarrow_N 4$ (the second qubit has index 4), $(\bar{q} \ominus [4], [1, 4, 5]) \Downarrow_{\mathcal{L}(\mathbb{N})} []$ ($[]$ is used for errors on type $\mathcal{L}(\mathbb{N})$), $(\bar{q}[4], [1, 4, 5]) \Downarrow_N 0$ (index 0 encodes error on type $\mathbb{N}$), and $(\bar{q} \ominus [3], [1, 4, 5]) \Downarrow_{\mathcal{L}(\mathbb{N})} [1, 4]$ (the third qubit has been removed).

Let $\mathcal{H}_{2^n}$ denote the Hilbert space of $n$ qubits $\mathbb{C}^{2^n}$, $\mathcal{P}(\mathbb{N})$ denote the powerset of $\mathbb{N}$.

A configuration $c$ over $n$ qubits is of the shape $(S, |\psi\rangle, A, l)$, for some statement $S \in$ Statements $\cup \{\tau, \perp\}$, $\tau$ and $\perp$ being two special symbols denoting termination and error, respectively, $|\psi\rangle$ is a quantum state in $\mathcal{H}_{2^n}$, where $A \in \mathcal{P}(\mathbb{N})$ is the set of accessible qubit pointers, and where $l \in \mathcal{L}(\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 $D :: S$ on input state $|\psi\rangle \in \mathcal{H}_{2^n}$ is $c_{\text{init}}(|\psi\rangle) \triangleq (S, |\psi\rangle, \{1, \dots, n\}, [1, \dots, n])$. A final configuration can be defined in the same way as $c_{\text{final}}(|\psi\rangle) \triangleq (\tau, |\psi\rangle, \{1, \dots, n\}, [1, \dots, n])$.
<figure><img src="image_6.png" /><figcaption>Figure 5: Program QFT for the quantum Fourier transform.</figcaption></figure>

Each unitary transformation $U$ of a unitary application $\bar{q}[i] * = U^f(j)$, comes with a function $[[U]]$ assigning a unitary matrix $[[U]](f)(n) \in \mathbb{C}^{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 $[[\text{Ph}]](f)(n) \triangleq (\begin{smallmatrix} 1 & 0 \\ 0 & e^{if(n)} \end{smallmatrix})$. The other basic unary gates are the NOT and the $R_Y$ gate.

The big-step semantics $\xrightarrow{\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$, $\langle \psi |$ for the conjugate transpose of $| \psi \rangle$, or given a dimension $m$, $|k\rangle_n \triangleq I_{2^{n-1}} \otimes |k\rangle \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 **qcase** $s[i] \text{ of } \{0 \to S_0, 1 \to S_1\}$, statements $S_0$ and $S_1$ cannot access $s[i]$.

**Definition 1.** *The time complexity Time<sub>P</sub>: $\mathbb{N} \to \mathbb{N}$ of a program P $\triangleq$ D : S is defined by*

$$ \text{Time}_{\text{P}}(n) \triangleq \max_{|\phi\rangle \in \mathcal{H}_{2^n}, c_{\text{init}}(|\phi\rangle) \xrightarrow{m} c_{\text{final}}(|\phi'\rangle)} \{m \in \mathbb{N} \mid \exists |\phi'\rangle \in \mathcal{H}_{2^n}, c_{\text{init}}(|\phi\rangle) \xrightarrow{m} c_{\text{final}}(|\phi'\rangle)\}. $$

Intuitively, when $c \xrightarrow{m} c'$ 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 $[[P]](|\psi\rangle) = |\psi'\rangle$, whenever $c_{\text{init}}(|\psi\rangle) \xrightarrow{m} c_{\text{final}}(|\psi'\rangle)$ holds for some $m$. If the program $P$ terminates on any input (i.e., always reaches a final configuration) then $[[P]]$ is a total function on quantum states.

**Example 1.** *For the program PAIRS of Figure 1, $\text{Time}_{\text{PAIRS}}(n) = \lfloor \frac{n}{2} \rfloor + 1$ since each procedure call removes two qubits until it reaches a sorted set $\bar{q}$ such that $|\bar{q}| \le 1$ (depending on whether $n$ is odd or even) and for both sizes there are no more procedure calls.*

## 2.3 Polynomial Branching Programs

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 $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 $P$ is introduced.

**Definition 2.** *Given a program P, the width of a procedure proc $\in P$, denoted $\text{width}_P(\text{proc})$, is defined as $\text{width}_P(\text{proc}) \triangleq w_P^{\text{proc}}(S^{\text{proc}})$, where $w_P^{\text{proc}}(S)$ is defined inductively as follows:*
$$
\begin{align*}
w_P^{\text{proc}}(\text{skip};) &\triangleq 0 \\
w_P^{\text{proc}}(q * = U^f(i);) &\triangleq 0, \\
w_P^{\text{proc}}(S_1 S_2) &\triangleq w_P^{\text{proc}}(S_1) + w_P^{\text{proc}}(S_2), \\
w_P^{\text{proc}}(\text{if } b \text{ then } S_0 \text{ else } S_1) &\triangleq \max(w_P^{\text{proc}}(S_0), w_P^{\text{proc}}(S_1)), \\
w_P^{\text{proc}}(\text{qcase } q \text{ of } \{0 \to S_0, 1 \to S_1\}) &\triangleq \max(w_P^{\text{proc}}(S_0), w_P^{\text{proc}}(S_1)), \\
w_P^{\text{proc}}(\text{call } \text{proc'}(s);) &\triangleq \begin{cases} 1 & \text{if } \text{proc} \sim_P \text{proc'}, \\ 0 & \text{otherwise.} \end{cases}
\end{align*}
$$

Let WIDTH$_{≤}$₁ be the set of programs with procedures of width at most 1.

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 may be exponential
for such programs by definition of the width for conditional and quantum case.

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. Let BASIC denote the set of
programs where each call to a procedure is performed either on the variable $\bar{q}$ or on a unique sorted
set $s$ that is fixed for the whole program.

**Definition 3 (Polynomially Branching Programs).** The set PBP of polynomially branching programs is defined as PBP $\triangleq$ WF $\cap$ WIDTH$_{\le 1}$ $\cap$ BASIC.

Notice that PBP is strictly included in the programming language of [17], that roughly corresponds
to WF $\cap$ WIDTH$_{\le 1}$, where procedure calls can take an extra integer parameter.

**Example 2.** The QFT program written in Figure 5 is in PBP. Indeed, the program QFT is in BASIC as calls are only performed on either $\bar{q}$ or $\bar{q} \ominus [-1]$. It is also in WF as all recursive calls are performed on parameter $\bar{q} \ominus [-1]$. Finally, it is in WIDTH$_{\le 1}$ as width$_{QFT}$(qft) = width$_{QFT}$(rot) = width$_{QFT}$(shift) = 1.

The restriction to programs in PBP does not impact negatively the expressive power of our study
from an extensional viewpoint as, by Theorem 3, PBP is sound and complete for the class FBQP of
functions in $\{0,1\}^* \to \{0,1\}^*$, i.e., functions that can be approximated with at least 2/3 probability
by a quantum Turing machine running in polynomial time [6, 29].

3 Compilation Strategy

We now present the compilation algorithm from WF $\cap$ WIDTH$_{\le 1}$ to quantum circuits based on the
merging strategy of Figure 2(c). Compilation is restricted to programs in WF $\cap$ WIDTH$_{\le 1}$ for two
reasons. The well-foundedness criterion WF ensures that the compilation always terminates. The
restriction to WIDTH$_{\le 1}$ prevents exponential blow-up. Note however that, in Theorem 2, the PBP
restrictions are required to avoid the branch sequentialization problem.

3.1 Anchoring and Merging

A control structure `cs` is a partial map in $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 N$ and $k \in \{0,1\}$, let `cs[n := k]` be the control structure obtained from `cs` by setting

<figure><img src="image_7.png" /><figcaption>Figure 6: Anchoring and merging.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 7: Rewrite rules of compile.</figcaption></figure>

$cs(n) = k$. We denote by $dom cs$ the domain of the control structure and by $\cdot$, the control structure such that $dom(\cdot) = \emptyset$.

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 6 as rewrite rules on quantum circuits for a procedure call *call proc(s)*, *cs* denoting the control structure corresponding to the (possibly nested) quantum cases, where the procedure call occurs. $a_k^{proc}$ represents the ancilla introduced (in case of anchoring) or reused (in case of merging). The integer *k* refers to the number $|s|$ of qubits in the procedure call. The grey box materializes the controlled statements left to compile.

## 3.2 The compile Algorithm

Let controlled statements be pairs of the shape $(cs, S)$, for some control structure *cs* and some statement *S*. In the compilation process, controlled statements $(cs, S)$ are used to represent a statement *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 7. Generating the circuit corresponding to the program $P = D :: S$ will consist in running **compile** on the controlled statement $(\cdot, S)$ for a fixed list of qubits pointers $[1, \dots, n]$ (hence, an input of fixed size *n*). We denote by **compile**(P, *n*) the circuit obtained for program *P* on size *n*. The algorithm standardly generates the quantum circuit corresponding to a $WF \cap WIDTH \le 1$ program inductively on the statement *S*. Indeed, in the rules of Figure 7 when **compile** is called on a given controlled statement $(cs, S)$, an inductive call to **compile** is performed on controlled statements whose statements are sub-statements of *S*. The two base case 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_P^{proc}(S^{proc}) > 0$), **compile** calls the **optimize** subroutine to perform anchoring and merging. This call to **optimize** is highlighted in Figure 7 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 8. This subroutine takes two input parameters:

* a first list *l* of controlled statements, the ones to be optimized,

* a second list of controlled statements, called *contextual list* and denoted by $\mathcal{N}$, consisting in controlled statements that are orthogonal to those in *l* and do not contain recursive procedure calls.

As described by the last rule of Figure 7, each initial call to **optimize** is performed on the singleton
<figure><img src="image_9.png" /><figcaption>Figure 8: Rewrite rules of **optimize**.</figcaption></figure>

list containing one controlled statement $(cs, S^{\text{proc}}\{s/\bar{q}\})$ and a contextual circuit equal to the identity circuit.

In Figure 8, the rules are applied by considering the first controlled statement in the list $l$. We just specify the most interesting case below:

* for a controlled statement $(cs, S_1 S_2)$, two distinct rules can be applied. In the first scenario, where $w_P^{\text{proc}}(S_1) = 1$, we have that $S_1$ contains a recursive procedure call and $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, S_1)$ or $(cs, S_2)$ to perform the optimization and, append the compiled circuit of the other controlled statement to the left or to the right.

* for a controlled statement with an **if** statement, we precompute the boolean value $b$ (the value is computable), and according to whether the corresponding branch contains a recursive call or not, we either add it to $l$ or concatenate its compiled circuit to the contextual circuit.

* for a controlled statement with a **qcase** statement, one or two of the branches are added to the list $l$ depending on whether they are both recursive or not.

* for a controlled statement with a procedure call **call proc''**($s$); we perform either anchoring or merging depending on whether the ancilla $a_{|s|}^{\text{proc}''}$ exists or not.

* when the list of control statement is empty (i.e., $l = []$), we compute the contextual list of controlled statements. This list is rearranged into lists of statements that are mutually recursive and compiled by a call to **optimize**. Such a partition is important to perform merging of
procedures with a recursion level lower than that of proc, and we give further explanation on how it is performed in Appendix B.

## 3.3 Soundness of the algorithm

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 7), 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 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$, $cs'$ be two control structures. We say that $cs$ and $cs'$ are orthogonal if there exists $i \in \text{dom}(cs) \cap \text{dom}(cs')$ such that $cs(i) = 1 - cs'(i)$. Two controlled statements are orthogonal if their control structures are orthogonal.

**Lemma 1.** *During the compilation of a PBP program P, for each optimization of a (recursive) procedure proc, all controlled statements in the union of list $l$ and the contextual list $l_M$ are pairwise orthogonal.*

This invariant ensures the validity of **optimize**, and the soundness of the compilation algorithm. It is also a consequence of the $WIDTH_{\le 1}$ restriction in PBP, as by the definition of width, at most one recursive call may appear per branch of a recursive procedure. This ensures that two recursive calls on a given procedure always occur in orthogonal branches and can be simply combined in the same ancilla. Given a circuit $C$, we define its semantics $[C]$ naturally as the composition of the semantics of each gate.

**Theorem 1 (Soundness of compilation).** *Given a PBP program P and a quantum state $|\psi\rangle \in \mathcal{H}_{2^n}$ we have that $[\text{compile}(P, n)](|\psi\rangle) = [\text{P}](|\psi\rangle)$.*

## 3.4 Illustrating Example

We illustrate the compilation process with the program REC, of Figure 9. Notice that REC is in WF $\cap$ $WIDTH_{\le 1}$ but does not belong to PBP, as the procedure rec performs two recursive calls on different sorted sets $\bar{q} \ominus [1]$ and $\bar{q} \ominus [1, 2]$. 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 $\square$ the procedure statement $S^{\text{rec}}$ and by the dotted box $\overline{\square}$ the statement **call rec(s)**. Applying rewrite rules to the statement of rec we obtain the transitions:

1. **decl rec(\bar{q}) {**
2.   **if** $|\bar{q}| > 2$ **then**
3.     **qcase** $\bar{q}[1]$ **of** {
4.       $0 \to$ **call** rec($\bar{q} \ominus [1]$);
5.       $1 \to$ **qcase** $\bar{q}[2]$ **of** {
6.         $0 \to$ **skip**;
7.         $1 \to$ **call** rec($\bar{q} \ominus [1, 2]$);
8.       }
9.     }
10.  **else** $\bar{q}[1]$ $*=$ U; }
11. **::** **call** rec(\bar{q});

<figure><img src="image_10.png" /><figcaption>Figure 9: Program REC.</figcaption></figure>

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

One important thing to notice in Figure 10 is that the compilation strategy does not avoid branch sequentialization *locally* but rather *asymptotically* in the construction of the circuit. In other words,
<figure><img src="image_11.png" /><figcaption>Figure 10: Example of anchoring and merging for the program REC in Figure 9.</figcaption></figure>

the `qcase` statement in rule `rec` does generate two instances of $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.

# 4 Main Results

## 4.1 No Branch Sequentialization

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 $\#C$ denote its size, i.e., number of gates and wires.

**Theorem 2 (No branch sequentialization).** Given a program $P \in \text{PBP}$ and input $n \in \mathbb{N}$, we have that $\#\text{compile}(P, n) = O(\text{Time}_P(n))$ holds.

One may notice that, in the rules of **compile** (Figure 7), the compilation of a `qcase` statement generates two controlled statements in sequence. Similarly, the rule of **optimize** (Figure 8) for `qcase` statements appends two controlled statements to the list $l$ 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.
<figure><img src="image_12.png" /><figcaption>Figure 11: Merging orthogonal controlled statements.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 12: Implementation of a controlled permutation in log-depth.</figcaption></figure>

**Example 3.** By Theorem 2 and Example 1, we have that $\#\text{compile}(\text{PAIRS}, n) = O(n)$.

## 4.2 Polynomial-Time Soundness and Completeness

Having shown in Theorem 2 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, WIDTH$_{≤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\}^* \to \{0,1\}^*$ 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 $\mathcal{F}$ of programs, $[[\mathcal{F}]]$ denotes the set of functions given by $[[P]] \circ f$, where $P \in \mathcal{F}$, $f$ is a polytime padding function, and $\circ$ is the standard function composition. For any $p \in (\frac{1}{2}, 1]$, we denote by $[[\mathcal{F}]]_{\ge p}$ the set of functions in $[[\mathcal{F}]]$ that approximate a classical function with probability at least $p$.

**Theorem 3 (Soundness and Completeness).** $[[\text{PBP}]]_{\ge \frac{2}{3}} = \text{FBQP}$.

## 4.3 Extension to Programs in WF $\cap$ WIDTH$_{≤1}$

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 WF $\cap$ WIDTH$_{≤1}$), merging can be 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 11. If we allow for parallelization of gates in the circuit, this can be done in logarithmic depth, as shown in Lemma 2. An example of a controlled permutation is shown in Figure 12, where vertical dashed lines separate time slices where gates can be applied simultaneously.

**Lemma 2.** Any controlled permutation on $n$ qubits can be performed with a quantum circuit of size $O(n)$ and depth $O(\log n)$.
An extension of compile with controlled-swapping as in Figure 11 used for merging procedures ensures the following bound for WF ∩ WIDTH≤₁ programs.

**Theorem 4.** For $P \in \text{WF} \cap \text{WIDTH}_{\le 1}$, compile($P, n$) results in a circuit with $O(\log(n) \cdot \text{Time}_P(n))$ depth and $O(n \cdot \text{Time}_P(n))$ size.

## 4.4 Comparison with Existing Work

The compile algorithm strictly improves upon the size bounds of other compilation algorithms [17], as illustrated by Table 1. In some cases, such as Examples 5 and 4 given in Appendix D, 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 5), we consider the problem of detecting whether an input string contains substrings $y_1, \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 $\Theta(n^{3k})$. The problem Sum($r$), given in Example 6, consists of checking if an input $x = x_1 \dots x_n$ satisfies $\sum_{i=1}^n x_i = r$.

<table><caption>Table 1: Circuit size complexity bounds.</caption><thead><tr><th rowspan="2">Problem</th><th rowspan="2">Example</th><th colspan="2">Circuit complexity</th></tr><tr><th>[17]</th><th>compile</th></tr></thead><tbody><tr><td>Full Adder</td><td>Example 4</td><td>Θ(n)</td><td>Θ(n)</td></tr><tr><td>Quantum Fourier Transform</td><td>Example 2</td><td>Θ(n<sup>2</sup>)</td><td>Θ(n<sup>2</sup>)</td></tr><tr><td>*k*-Chained Substrings</td><td>Example 5</td><td>Θ(n<sup>3k</sup>)</td><td>Θ(n)</td></tr><tr><td>Sum(r), r ≥ 1</td><td>Example 6</td><td>Θ(n<sup>r</sup>)</td><td>Θ(n)</td></tr></tbody></table>

# 5 Conclusions and Future Work

The quantum control statement, while being a central component of programming languages with quantum control flow, usually incurs a remarkable slowdown in the program complexity in any automatic implementation, which poses a problem to the quantum programmer. In this paper, we have demonstrated that such a slowdown can be avoided by restricting the program structure. This was achieved using techniques from quantum implicit computational complexity, which allow not only to selectively reason about efficient programs (polytime soundness) but also to ensure that the techniques are sufficient in principle for any program (polytime completeness).

PBP is then the first quantum programming language with a compilation strategy that ensures that the quantum control statement can be compiled onto a circuit whose size (i.e., number of gates and wires) is bounded asymptotically by the maximum of the time complexity of its branches. While this language is extensionally complete for FBQP and expressive enough to write quantum algorithms such as QFT or Full Adder in a natural way, it would be interesting to investigate in what ways its expressive power can be improved, and how different languages can also be shown to avoid branch sequentialization.

# 6 Acknowledgments

This work is supported by the Plan France 2030 through the PEPR integrated project EPiQ ANR-22- PETQ-0007 and the HQI platform ANR-22-PNCQ-0002; and by the European projects NEASQC and HPCQS.

# References

[1] Samson Abramsky. No-cloning in categorical quantum mechanics. *Semantic Techniques in Quantum Computation*, pages 1–28, 2009.
[2] Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang. Quantum computability. *SIAM Journal on Computing*, 26(5):1524-1540, 1997. doi:10.1137/S0097539795293639

[3] Thorsten Altenkirch and Jonathan Grattage. A functional quantum programming language. In *20th Annual IEEE Symposium on Logic in Computer Science (LICS'05)*, pages 249–258. IEEE, 2005.

[4] John Baez. Quantum quandaries: a category-theoretic perspective. *The structural foundations of quantum gravity*, pages 240–265, 2006.

[5] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. *Physical review A*, 52(5):3457, 1995.

[6] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. *SIAM Journal on Computing*, 26(5):1411-1473, 1997. doi:10.1137/S0097539796300921.

[7] Hans J. Briegel, David E. Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. *Nature Physics*, 5(1):19-26, 2009. doi:10.1038/nphys1157.

[8] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. *Quantum Information & Computation*, 12(11-12):901-924, 2012.

[9] Andrea Colledan and Ugo Dal Lago. Circuit width estimation via effect typing and linear dependency. In *European Symposium on Programming*, pages 3–30. Springer, 2024.

[10] Andrea Colledan and Ugo Dal Lago. Flexible type-based resource estimation in quantum circuit description languages. *Proceedings of the ACM on Programming Languages*, 9(POPL):1386–1416, 2025.

[11] Ugo Dal Lago, Andrea Masini, and Margherita Zorzi. Quantum implicit computational complexity. *Theoretical Computer Science*, 411(2):377-409, 2010. doi:10.1016/j.tcs.2009.07.045.

[12] Vincent Danos and Elham Kashefi. Determinism in the one-way model. *Physical Review A*, 74(5):052310, 2006. doi:10.1103/PhysRevA.74.052310.

[13] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.TQC.2020.11.

[14] Alejandro Díaz-Caro, Mauricio Guillermo, Alexandre Miquel, and Benoît Valiron. Realizability in the unitary sphere. In *2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)*, pages 1–13. IEEE, 2019.

[15] Peng Fu, Kohei Kishida, and Peter Selinger. Linear dependent type theory for quantum programming languages. In *Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science*, pages 440–453, 2020.

[16] David Gosset, Robin Kothari, and Kewen Wu. Quantum state preparation with optimal T-count. *arXiv preprint arXiv:2411.04790*, 2024.

[17] Emmanuel Hainry, Romain Péchoux, and Mário Silva. A programming language characterizing quantum polynomial time. In *Foundations of Software Science and Computation Structures*, pages 156–175. Springer, 2023. doi:10.1007/978-3-031-30829-1_8

[18] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum Algorithm for Linear Systems of Equations. *Physical Review Letters*, 103(15), October 2009. doi:10.1103/physrevlett.103.150502.

[19] Chris Heunen and Jamie Vicary. *Categories for Quantum Theory: an introduction*. Oxford University Press, 2019.
[20] Aleks Kissinger and John van de Wetering. Reducing the number of non-Clifford gates in quantum circuits. *Phys. Rev. A*, 102, 022406, Aug 2020. doi:10.1103/PhysRevA.102.022406.

[21] Emanuel Knill, Raymond Laflamme, and Gerard J. Milburn. A scheme for efficient quantum computation with linear optics. *Nature*, 409(6816):46-52, Jan 2001. doi:10.1038/35051009.

[22] Gui-Lu Long and Yang Sun. Efficient scheme for initializing a quantum register with an arbitrary superposed state. *Phys. Rev. A*, 64:014303, Jun 2001. URL: https://link.aps.org/doi/10.1103/PhysRevA.64.014303, doi:10.1103/PhysRevA.64.014303.

[23] D. Maslov, G.W. Dueck, D.M. Miller, and C. Negrevergne. Quantum Circuit Simplification and Level Compaction. *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, 27(3):436-444, March 2008. doi:10.1109/tcad.2007.911334.

[24] Christopher Moore and Martin Nilsson. Parallel Quantum Computation and Quantum Codes. *SIAM Journal on Computing*, 31(3):799-815, 2001. doi:10.1137/S0097539799355053.

[25] Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. *npj Quantum Information*, 4(1):23, May 2018. doi:10.1038/s41534-018-0072-4.

[26] Michael A. Nielsen and Isaac L. Chuang. *Quantum Computation and Quantum Information: 10th Anniversary Edition*. Cambridge University Press, 2011.

[27] Peter Selinger. Towards a quantum programming language. *Mathematical Structures in Computer Science*, 14(4):527-586, 2004.

[28] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis. *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, 42(10):3301-3314, 2023.

[29] Tomoyuki Yamakami. A Schematic Definition of Quantum Polynomial Time Computability. *J. Symb. Log.*, 85(4):1546-1587, 2020. doi:10.1017/jsl.2020.45.

[30] Tomoyuki Yamakami. Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability. In *Agata Ciabattoni, Elaine Pimentel, and Ruy J. G. B. de Queiroz, editors, Logic, Language, Information, and Computation*, pages 88-104, Cham, 2022. Springer International Publishing. doi:10.1007/978-3-031-15298-6_6.

[31] Andrew Chi-Chih Yao. Quantum circuit complexity. In *Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science*, pages 352-361, 1993. doi:10.1109/SFCS.1993.366852.

[32] Charles Yuan and Michael Carbin. Tower: Data Structures in Quantum Superposition. *Proceedings of the ACM on Programming Languages*, 6(OOPSLA2):259-288, Oct 2022. doi:10.1145/3563297.

[33] Charles Yuan, Agnes Villanyi, and Michael Carbin. Quantum Control Machine: The Limits of Control Flow in Quantum Programming. *Proceedings of the ACM on Programming Languages*, 8(OOPSLA1):1-28, 2024.

[34] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum state preparation with optimal circuit depth: Implementations and applications. *Physical Review Letters*, 129(23):230504, 2022.
## A Semantics of expressions

$$ 
\begin{array}{r@{\quad}l@{\quad}l@{\quad}l}
\frac{(e, l) \Downarrow_{[\tau_1]} m}{(e \ \mathrm{op} \ d, l) \Downarrow_{[\mathrm{op}]]([\tau_1], [\tau_2])} \Downarrow_{[\mathrm{op}]](m, n)} & \mathrm{(Op)} & \frac{(i, l) \Downarrow_Z n}{(\mathrm{U}^f(i), l) \Downarrow_{C^{2 \times 2}} \Downarrow_{[\mathrm{U}^f]}}(n)} & \mathrm{(Unit)} \\[1.5em]
\frac{}{(n, l) \Downarrow_Z n} & \mathrm{(Cst)} & \frac{(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s \ominus [i], l) \Downarrow_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_{k-1}, x_{k+1}, \dots, x_m]} & \mathrm{(Rm_\epsilon)} \\[1.5em]
\frac{(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_n]}{(|s|, l) \Downarrow_Z n} & \mathrm{(Size)} & \frac{(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s \ominus [i], l) \Downarrow_{\mathcal{L}(\mathbb{N})} []} & \mathrm{(Rm_\xi)} \\[1.5em]
\frac{}{\bar{(q, l)} \Downarrow_{\mathcal{L}(\mathbb{N})} l} & \mathrm{(Var)} & \frac{(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s[i], l) \Downarrow_N x_k} & \mathrm{(Qu_\epsilon)} \\[1.5em]
\frac{(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s[i], l) \Downarrow_N 0} & & \frac{(i, l) \Downarrow_Z k \notin [1, m]}{(s[i], l) \Downarrow_N x_k} & \mathrm{(Qu_\xi)}
\end{array}
$$

<caption>Figure 13: Semantics of expressions.</caption>

## B Compilation

In this appendix, we describe the **compile** and **optimize** routines in more detail. For simplicity, we provide here the algorithm for programs in PBP. The version for WF ∩ WIDTH$_{≥}$₁ uses additional control swaps in the **optimize** subroutine and is described in Section 4.3. The full definition of compile (Algorithm 1) takes four inputs: a program P ∈ WF ∩ WIDTH$_{≤}$₁, a list of qubit pointers l and a control structure cs. We make use of the following syntactic sugar to denote the initial call to compile:

$$ \mathbf{compile}(P, n) \triangleq \mathbf{compile}(P, [1, \dots, n], \cdot), $$

where P is the program to be compiled, [1, ..., n] is list of qubit pointers (initially all qubits), · is an empty control structure, and {} an empty dictionary.

The aim of compile is to generate the quantum circuit corresponding to P on n qubits inductively on the program statement of P. When the analyzed statement is a recursive procedure call, compile calls the optimize subroutine (Algorithm 2) to perform an optimization of the generated quantum circuit via anchoring and merging. optimize has the same inputs as compile with the addition of a list of controlled statements l$_{Cst}$ and the name proc of the procedure under analysis.

As described in Subsection 3.2, optimize manages a contextual list l$_{M}$ of controlled statements that do not contain recursive procedure calls. At the end of optimize, we rearrange the contextual list in the following way. Let l$_{M}$ = [(cs$_{1}$, S$_{1}$, l$_{1}$), ..., (cs$_{k}$, 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. This transformation, denoted seq, can be described inductively:

$$ 
\begin{align*}
\mathit{seq}(cs, \mathbf{skip}; l) &\triangleq [] \\
\mathit{seq}(cs, q * = \mathit{U}^f(j); l) &\triangleq [(cs, q * = \mathit{U}^f(j); l)], \\
\mathit{seq}(cs, S_1, S_2, l) &\triangleq \mathit{seq}(cs, S_1, l)@\mathit{seq}(cs, S_1, l), \\
\mathit{seq}(cs, \mathbf{if} \ b \ \mathbf{then} \ S_{\mathbf{true}} \ \mathbf{else} \ S_{\mathbf{false}}, l) &\triangleq \mathit{seq}(cs, S_b, l), \quad \text{if } (b, l) \Downarrow_B b, \\
\mathit{seq}(cs, \mathbf{qcase} \ q \ \mathbf{of} \ \{0 \to S_0, 1 \to S_1\}, l) &\triangleq \mathit{seq}(cs[n := 0], S_0, l)@\mathit{seq}(cs[n := 1], S_1, l) \quad \text{if } (q, l) \Downarrow_N n, \\
\mathit{seq}(cs, \mathbf{call} \ \mathit{proc}(s); l) &\triangleq [(cs, \mathbf{call} \ \mathit{proc}(s); l)].
\end{align*}
$$
**Algorithm 1 (compile)**

Input: ($D :: S, l, cs$) $\in$ Programs $\times \mathcal{L}(\mathbb{N}) \times (\mathbb{N} \to \{0, 1\})$

1: **if** S = **skip**; **then**
2: &nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ 1
3: &nbsp;&nbsp;&nbsp;&nbsp;▷ Identity circuit

3:
4: **else if** S = q $\ast$= U$^f$(j); **and** (q, l) $\downarrow_{\mathbb{N}}$ n and (U$^f$(j), l) $\downarrow_{\mathbb{C}^{2 \times 2}}$ M **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ M(cs, [n])
6: &nbsp;&nbsp;&nbsp;&nbsp;▷ Controlled gate

6:
7: **else if** S = S₁ S₂ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ compile(D :: S₁, l, cs) ◦ compile(D :: S₂, l, cs)
9: &nbsp;&nbsp;&nbsp;&nbsp;▷ Composition

9:
10: **else if** S = **if** b **then** S<sub>true</sub> **else** S<sub>false</sub> and (b, l) $\downarrow_{\mathbb{B}}$ b **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ compile(D :: S<sub>b</sub>, l, cs)
12: &nbsp;&nbsp;&nbsp;&nbsp;▷ Conditional

12:
13: **else if** S = qcase s[i] of {0 $\to$ S<sub>0</sub>, 1 $\to$ S<sub>1</sub>} and (s[i], l) $\downarrow_{\mathbb{N}}$ n **then**
14: &nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ compile(D :: S<sub>0</sub>, l, cs[n := 0]) ◦ compile(D :: S<sub>1</sub>, l, cs[n := 1])
15: &nbsp;&nbsp;&nbsp;&nbsp;▷ Quantum case

15:
16: **else if** S = **call** proc(s); **and** (s, l) $\downarrow_{\mathcal{L}(\mathbb{N})}$ [] **then**
17: &nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ 1
18: &nbsp;&nbsp;&nbsp;&nbsp;▷ Nil call

18:
19: **else if** S = **call** proc(s); **and** (s, l) $\downarrow_{\mathcal{L}(\mathbb{N})}$ l' $\neq$ [] **then**
20: &nbsp;&nbsp;&nbsp;&nbsp;**if** w<sub>P</sub><sup>proc</sup>(S<sup>proc</sup>) = 0 **then**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ compile(D :: S<sup>proc</sup>, l', cs)
22: &nbsp;&nbsp;&nbsp;&nbsp;**else**
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C $\leftarrow$ optimize(D, [(cs, S<sup>proc</sup>, l)], proc)

23:
24: **end if**
25: **end if**
26: **return** C

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 $\mathcal{L}$, we denote by procedure_split($\mathcal{L}$) the list $[\mathcal{L}_0, \mathcal{L}_1, \dots, \mathcal{L}_m]$ where, for $proc_1, \dots, proc_m$ are procedures that are not mutually recursive.

$$
\begin{align*}
\mathcal{L}_0 &\triangleq \{(cs, S, l) \in \mathcal{L} : \nexists \text{ proc such that } w_P^{\text{proc}}(S^{\text{proc}}) = 1 \text{ and } w_P^{\text{proc}}(S) = 1\}. \\
\mathcal{L}_{\text{proc}_i} &\triangleq \{(cs, S, l) \in \mathcal{L} : w_P^{\text{proc}_i}(S) = 1\}, \quad i = 1, \dots, m.
\end{align*}
$$

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 list $l_M$ in the following way:

<figure><img src="image_14.png" /></figure>

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

C Proofs

**Theorem 1 (Soundness of compilation).** *Given a PBP program P and a quantum state $|\psi\rangle \in \mathcal{H}_{2^n}$ we have that $\llbracket \text{compile}(P, n) \rrbracket(|\psi\rangle) = \llbracket \text{P} \rrbracket(|\psi\rangle)$.*

*Proof.* By induction on the structure of the PBP program P = D :: S. One can check by inspection of each case that the **compile** rules for non-recursive statements corresponds to the straightforward circuit semantics of quantum programs.

Likewise, the rewriting rules of **optimize**, given in Figure 8, can be easily checked using the orthogonality invariant of Lemma 1. For instance, consider the case of the sequential statement
**Algorithm 2 (optimize)** Build circuit for recursive procedure *proc*

**Inputs:** (D, *l*<sub>Cst</sub>, *proc*) ∈ Decl × 𝒰(Cst × 𝒰(ℝ)) × Procedures

1: $C_L \leftarrow 1$; $C_R \leftarrow 1$; $C_M \leftarrow 1$; $l_M \leftarrow []$; Anc$\leftarrow \{\}$; P $\leftarrow D$ :: **skip**;

2: **while** $l_{Cst} \neq []$ **do**

3:   ($cs, S, l$) $\leftarrow$ hd($l_{Cst}$); $l_{Cst} \leftarrow tl(l_{Cst})$

4:

5: **if** S = S<sub>1</sub> S<sub>2</sub> **then**

6:   **if** $w_P^{\text{proc}}(S_1) = 1$ **then**

7:   $l_{Cst} \leftarrow l_{Cst}[(cs, S_1, l)]$; $C_R \leftarrow \text{compile}(D \:: S_1, l, cs) \circ C_R$

8:   **else**

9:   $l_{Cst} \leftarrow l_{Cst}[(cs, S_2, l)]$; $C_L \leftarrow C_L \circ \text{compile}(D \:: S_1, l, cs)$

10: **end if**

11: **end if**

12:

13: **if** S = **if** b **then** S<sub>true</sub> **else** S<sub>false</sub> **and** (b, l) $\Downarrow_B$ b **then**

14:   **if** $w_P^{\text{proc}}(S_b) = 1$ **then**

15:   $l_{Cst} \leftarrow l_{Cst}[(cs, S_b, l)]$

16:   **else**

17:   $l_M \leftarrow l_M[(cs, S_b, l)]$

18: **end if**

19: **end if**

20:

21: **if** S = **qcase** q of {0 → S<sub>0</sub>, 1 → S<sub>1</sub>} and (q, l) $\Downarrow_N$ n **then**

22:   **if** $w_P^{\text{proc}}(S_0) = 1$ **and** $w_P^{\text{proc}}(S_1) = 1$ **then**

23:   $l_{Cst} \leftarrow l_{Cst}[(cs[n := 0], S_0, l), (cs[n := 1], S_1, l)]$

24:   **else if** $w_P^{\text{proc}}(S_1) = 0$ **then**

25:   $l_{Cst} \leftarrow l_{Cst}[(cs[n := 0], S_0, l)]$; $l_M \leftarrow l_M[(cs[n := 1], S_1, l)]$

26:   **else if** $w_P^{\text{proc}}(S_0) = 0$ **then**

27:   $l_{Cst} \leftarrow l_{Cst}[(cs[n := 1], S_1, l)]$; $l_M \leftarrow l_M[(cs[n := 0], S_0, l)]$

28: **end if**

29: **end if**

30:

31: **if** S = **call** *proc*'(s) ; and (s, l) $\Downarrow_{\mathcal{L}(N)}$ l' $\neq$ [] **then**

32:   **if** (*proc*', |*l*'|) ∈ Anc **then**

33:     **Let** a = Anc[*proc*', |*l*'|] **in** /* compatible procedure exists: merging */

34:     $C_L \leftarrow C_L \circ \text{NOT}(cs, a)$;

35:     $C_R \leftarrow \text{NOT}(cs, a) \circ C_R$;

36:   **else**

37:     a $\leftarrow$ **new** ancilla() /* no compatible procedure: anchoring */

38:     Anc[*proc*', |*l*'|] $\leftarrow$ a;

39:     $C_L \leftarrow C_L \circ \text{NOT}(cs, a)$; $C_R \leftarrow \text{NOT}(cs, a) \circ C_R$;

40:   $l_{Cst} \leftarrow l_{Cst}[(\cdot[a = 1], S^{\text{proc}}', l')]$

41: **end if**

42: **end if**

43: **end while**

44: $T = \max_{(cs,S,l) \in l_M} (|\sec cs, S, l|)$

45: **for** $1 \le t \le T$ **do**

46:   $\mathcal{L} \leftarrow \bigcup_{(cs,S,l) \in l_M} \sec cs, S, l)[t]$

47:   $\mathcal{L}_0, \dots, \mathcal{L}_m$ = procedure\_split($\mathcal{L}$) /* m = number of recursive procedure families */

48:   $C_M \leftarrow C_M \circ (\circ_{(cs,S,l) \in \mathcal{L}_0} \text{compile}(D \:: S, l, cs)) \circ (\circ_{i=1}^m \text{optimize}(D, \mathcal{L}_i, \text{proc}_i))$

49: **end for**

50: **return** $C_L \circ C_M \circ C_R$
S = S₁ S₂. In the case where $w_P^{proc}(S_1) = 1$, we can derive the rule for the statement with the following steps:

<figure><img src="image_15.png" /></figure>

where (a) corresponds to the definition of the sequential statement, in (b) we make use of the fact that (cs, S₂) is orthogonal to all controlled statements in *l* and therefore can be commuted in the circuit, and in step (c) we likewise make use of orthogonality, in this case with the controlled statements in the contextual list. Other case can be inspected to follow a short sequence of steps, such as described for the sequential statement.

For instance, in the case of anchoring, we consider the following composition of rules

<figure><img src="image_16.png" /></figure>

where, likewise, (a) corresponds to the typical circuit semantics of a procedure call (with an added
anchoring ancilla), and (b) and (c) make use of the orthogonality of `cs` with the right side of the
circuit. The validity of merging and also be checked:

<figure><img src="image_17.png" /></figure>

Step (a) can be seen as the definition of the procedure call. Since we are in the merging scenario, a similar procedure call has already been performed and is anchored to its corresponding ancilla. Without loss of generality (since all controlled statements in *l* are orthogonal and therefore commute) we assume that this call appears at the end of *l* (we reuse the name *l* in the circuit rewriting here as an abuse of notation). Rule (b) simply indicates that since *cs* is orthogonal to other control structures in *l*, we may move the controlled statements so that they are adjacent, and where we apply step (c) to perform merging. Since *cs* is orthogonal to $[a_{|s|}^{proc} = 1]$ the control is added to the ancilla as expected. Finally, orthogonality of *cs* with other control structures means that we may move the two controlled-NOTs to the edges of the circuit.

Finally, we consider the validity of the rule for the contextual circuit. Consider a list of mutually-
orthogonal controlled statements, where the sequential form of (csᵢ, Sᵢ) is given by the lists of con-
trolled statements l₁⁽¹⁾, ..., lᵢ⁽¹⁾, then we have that:

<figure><img src="image_18.png" /></figure>

The final step comes from the fact that all $l_j^{(1)}$ are orthogonal to $cs_2, \dots, cs_k$ since they include $cs_1$.
Using the sequential form of ($cs_2, S_2$), we perform the following transitions:

<figure><img src="image_19.png" /></figure>

where we make use of the orthogonality between $l_j^{(1)}$ and $l_{j'}^{(2)}$. Performing the same transitions for ($cs_3, S_3$), ..., ($cs_k, S_k$), we obtain the following arrangement:
<figure><img src="image_20.png" /></figure>

Given a certain $1 \le j \le t$, we have that all controlled statements in $\cup_{i=1}^k l_j^{(i)}$ (that is, all controlled statements occurring in time $j$) are pairwise orthogonal. Therefore, we may rearrange their order according to their recursivity, and in doing so we may consider each time separately. For instance, in time 1, let $\mathcal{L} \triangleq \cup_{i=1}^k l_1^{(i)}$, and let $\mathit{proc}_1, \mathit{proc}_2, \dots, \mathit{proc}_m$ denote procedures belonging to different recursion families. Then, we perform the following partition:

$$ \mathcal{L}_0 \triangleq \{(cs, S) \in \mathcal{L} : \nexists \mathit{proc} \text{ such that } w_{\mathit{P}}^{\mathit{proc}}(S^{\mathit{proc}}) = 1 \text{ and } w_{\mathit{P}}^{\mathit{proc}}(S) = 1\}. $$

$$ \mathcal{L}_i \triangleq \{(cs, S) \in \mathcal{L} : w_{\mathit{P}}^{\mathit{proc}_i}(S) = 1\}, \quad i = 1, \dots, m. $$

By the definition of the sequential form of each controlled statement, we note that the partition is well-defined (e.g. there are no statements containing calls to more than one procedure). Therefore, we are able to rearrange $\mathcal{L}$ and perform calls to **optimize** in the following way:

<figure><img src="image_21.png" /></figure>

Performing this operation on each time block and composing the circuits we obtain the rule given in Section 3. This concludes the proof. □

We introduce the notion of rank of a procedure for use in the proof of Theorem 2.

**Definition 4 (Rank).** Set $\max(\emptyset) \triangleq 0$. Given a program P, the rank of a procedure $\mathit{proc} \in P$, denoted $rk_P(\mathit{proc})$, is defined as follows:

$$ rk_P(\mathit{proc}) \triangleq \begin{cases} 0, & \text{if } \neg(\exists \mathit{proc'}, \mathit{proc} \ge_P \mathit{proc'}), \\ \max_{\mathit{proc} \ge_P \mathit{proc'}} \{rk_P(\mathit{proc'})\}, & \text{if } \exists \mathit{proc'}, \mathit{proc} \ge_P \mathit{proc'} \wedge \neg(\mathit{proc} \sim_P \mathit{proc}), \\ 1 + \max_{\mathit{proc} >_P \mathit{proc'}} \{rk_P(\mathit{proc'})\}, & \text{if } \mathit{proc} \sim_P \mathit{proc}. \end{cases} $$

**Theorem 2 (No branch sequentialization).** Given a program P ∈ PBP and input n ∈ N, we have that $\#\mathit{compile}(P, n) = O(\mathit{Time}_P(n))$ holds.

*Proof.* The theorem can be shown by structural induction on the program body. All cases are straightforward except the one of the quantum control case. We make use of the following two facts regarding PBP programs:

(a) The size of the circuit is directly proportional to its total number of unique procedure calls (in the sense required for merging), and

(b) a recursive procedure call results in $O(n)$ unique calls to procedures of the same rank. This is because unique calls may only differ on procedure name (of which there is a constant amount) or input size (for which there is a linear number of possibilities).

Consider a quantum control statement $S = \mathit{qcase} \ q \ \mathit{of} \ \{0 \to S_0, 1 \to S_1\}$ appearing in **optimize** in the context of a recursive procedure $\mathit{proc}$. By (a), the circuit size for $S_0$ and $S_1$ are proportional to the (total) number of procedure calls in each statement, separately. We check that the number of ancillas created for $S$ is bounded by the maximum number of ancillas between $S_0$ and $S_1$.

We proceed by induction on the rank $r$ of the procedure. The base case of $r = 1$ is given by (b), and so we may consider $r > 1$. For the inductive case, we consider two scenarios:

* $w_{\mathit{proc}}^{\mathit{P}}(S_0) = w_{\mathit{proc}}^{\mathit{P}}(S_1) = 1$. In this case, both $S_0$ and $S_1$ are of rank $r$, and all their recursive procedure calls may be merged. Therefore, the asymptotic number of such calls is bounded between the maximum between $S_0$ and $S_1$ (consider that, if there is no overlap between the ancillas needed, their number is still bounded linearly). Applying the IH on the procedures of rank $r-1$ we obtain the desired result.
• $w_{proc}^P(S_0) = 0$ and $w_{proc}^P(S_1) = 1$. In this case, $S_0$ contains calls to procedures of rank $r' < r$ whereas $S_1$ contains calls to procedures of rank $r$. According to **optimize**, statement $S_0$ is kept in the contextual circuit until no more statements are recursive relative to **proc**. The statements of rank $r'$ which are present in $S_0$ are then merged with the equivalent procedures that were derived from $S_1$ and also added to $l_M$. The number of procedures of rank $r'$ is bounded asymptotically by the maximum between those in $S_0$ and $S_1$, therefore we obtain our result. $\square$

**Theorem 3 (Soundness and Completeness).** $[[PBP]]_{\ge \frac{2}{3}} = \text{FBQP.}$

*Proof.* Since PBP $\not\subseteq$ WF $\cap$ WIDTH$_{\le 1}$ $\not\subseteq$ PFOQ, with PFOQ the language of [17], we have that $[[PBP]] \subseteq [[WF \cap WIDTH_{\le 1}]] \subseteq [[PFOQ]]$ and, by PFOQ soundness [17, Theorem 3], it also holds that $[[PBP]]_{\ge \frac{2}{3}} \subseteq \text{FBQP}$. Completeness can be proven by showing that PBP can simulate the function algebra in [29], known to be complete for quantum polynomial time. The proof can be done using the same construction as in [17, Theorem 5]. $\square$

**Lemma 2.** *Any controlled permutation on $n$ qubits can be performed with a quantum circuit of size $O(n)$ and depth $O(\log n)$.*

*Proof.* Any permutation can be written as the composition of two sets of disjoint transpositions, and therefore any permutation can be performed in constant time, using two time steps [24]. To perform a controlled permutation, it suffices to create $O(n)$ ancillas with the correct controlled state, which can be done in $O(\log n)$ depth with $O(n)$ gates. $\square$

# D Examples of Table 1

**Example 4 (Quantum Full Adder).** Let ADD denote the following PBP program, where the following syntactic sugar:

$$ \text{TOF}(q_1, q_2, q_3) \triangleq \textbf{qcase } q_1 \textbf{ of } \{0 \to \textbf{skip}; 1 \to \text{CNOT}(q_2, q_3)\} $$

encodes the Toffoli gate, i.e. the multi-controlled NOT gate.

1. **decl fullAdder(\bar{q}) {**
2.   **if** |\bar{q}| > 3 **then** /* \bar{q}[1] = a, \bar{q}[2] = b, \bar{q}[-2] = |0⟩ and \bar{q}[-1] = c_in */
3.     TOF(\bar{q}[1], \bar{q}[2], \bar{q}[-2])
4.     CNOT(\bar{q}[1], \bar{q}[2])
5.     TOF(\bar{q}[2], \bar{q}[-1], \bar{q}[-2]) /* c_out = (a ⋅ b) ⊕ (c_in ⋅ (a ⊕ b)) */
6.     CNOT(\bar{q}[2], \bar{q}[-1]) /* s = a ⊕ b ⊕ c_in */
7.     CNOT(\bar{q}[1], \bar{q}[2])
8.     **call** fullAdder(\bar{q} ⊖ [1, 2, -1]);
9.     **else** skip; }
10. **::** **call** fullAdder(\bar{q});**

Given a carry-in bit $c_{in}$, we have that $[[\text{ADD}]](|a_n b_n \dots a_1 b_1 0^n c_{in}|) = |a_n b_n \dots a_1 b_1 c_{out} s_1 \dots s_n⟩$, where $c_{out}$ encodes the carry-out bit and $s_i$ encodes the i-th sum bit. Given that **fullAdder** performs one recursive call to an input containing three fewer qubits, we have that $\text{Time}_{\text{ADD}}(n) = \lfloor \frac{n}{3} \rfloor + 1$.

**Example 5 (k-Chained Substrings).** Consider a program for detecting a substring 001 occurring $k$ times in an input. For the case $k = 1$, we define a program with procedures $a_i$, $b_i$, $c_i$, $d_i$ and $\oplus$, with the graph:

<figure><img src="image_22.png" /></figure>

The two outgoing edges of a node indicate the two branches of a **qcase** statement in the corresponding procedure, controlled on the first input qubit. We denote by $\mathcal{F}_i$ the diagram containing nodes $a_i$, $b_i$,
$c_i$ and $d_i$ and all edges between them. Procedures consist only of a **qcase** statement, for the exception of $⊕$:

```pascal
decl a_i(\q) { qcase \q[1] of {0 \to call b_i(\q \ominus [1]); , 1 \to call a_i(\q \ominus [1]); } },
decl b_i(\q) { qcase \q[1] of {0 \to call c_i(\q \ominus [1]); , 1 \to call b_i(\q \ominus [1]); } },
decl c_i(\q) { qcase \q[1] of {0 \to call c_i(\q \ominus [1]); , 1 \to call d_i(\q \ominus [1]); } },
decl d_i(\q) { qcase \q[1] of {0 \to call d_i(\q \ominus [1]); , 1 \to call ⊕(\q \ominus [1]); } },
decl ⊕(\q) { \q[\q[-1] *:= NOT; }
```

The program body is a call to procedure $a_i$ on input $\bar{q}$, which results in a program that performs the transformation $|\bar{x}y\rangle \mapsto |\bar{x}(y \oplus b)\rangle$ where $b \in \{0,1\}$ is 1 if and only if $\bar{x}$ contains at least 1 instance of 001 as a substring.

For a general $k$, we consider the program $P_k$ defined by

$$F_1 \xrightarrow{1} F_2 \xrightarrow{1} \dots \xrightarrow{1} F_k \xrightarrow{1} \bigoplus$$

where an arrow from $F_i$ to $F_{i+1}$ indicates an arrow from $d_i$ to $a_{i+1}$. The final program then consists of a call to procedure $a_1$ on input $\bar{q}$. It is easy to check that $P_k \in \text{PBP}$, and that $\text{Time}_{P_k}(n) = n$, for any $k$.

**Example 6.** Let $\text{Sum}(r)$ be the decision problem of checking if an input bitstring $x \in \{0,1\}^n$ satisfies $\sum_{i=1}^n x_i = r$. For instance, if $r=3$, we may define a program $\text{SUM}_3$ as:

1. **decl zero(\q)** { **qcase \q[1] of** {0 \to call zero(\q \ominus [1]); , 1 \to call one(\q \ominus [1]); } },
2. **decl one(\q)** { **qcase \q[1] of** {0 \to call one(\q \ominus [1]); , 1 \to call two(\q \ominus [1]); } },
3. **decl two(\q)** { **qcase \q[1] of** {0 \to call two(\q \ominus [1]); , 1 \to call three(\q \ominus [1]); } },
4. **decl three(\q)** {
5.   **if** |\q| = 1 **then**
6.     **call** ⊕(\q);
7.   **else**
8.     **qcase** \q[1] **of** {0 \to call three(\q \ominus [1]); , 1 \to skip; } },
9.   **decl** ⊕(\q) { \q[\q[-1] *:= NOT; }
10. **::** call zero(\q);

We have that $\text{Time}_{\text{SUM}_3}(n) = n$.