# A Polytime Quantum Programming Language

Emmanuel Hainry, Romain Péchoux, Mário Silva

► To cite this version:

Emmanuel Hainry, Romain Péchoux, Mário Silva. A Polytime Quantum Programming Language. ACM Transactions on Quantum Computing, 2025, 7 (1), pp.1 - 32. 10.1145/3769851. hal-05419254

HAL Id: hal-05419254

https://inria.hal.science/hal-05419254v1

Submitted on 16 Dec 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
# A Polytime Quantum Programming Language

EMMANUEL HAINRY, ROMAIN PÉCHOUX, and MÁRIO SILVA, Université de Lorraine, CNRS, Inria, LORIA, France

As quantum computing emerges as a promising computational paradigm, quantum programming languages provide the tools that bridge the distance between abstract programming and its hardware implementation. In some cases, restricted programming languages may even provide an avenue for more efficient circuit compilation strategies.

In this work, we introduce FOQ, a first-order quantum programming language which allows for quantum control and recursion, and where a syntactically restricted subset of programs (PFOQ) is shown to be sound and complete for quantum polytime computation. This is achieved by bounding both the recursion depth and the branching width of programs, which we demonstrate to still be compatible with various interesting applications, such as quantum teleportation and the quantum Fourier transform.

PFOQ constitutes the first programming-language-based characterization of the quantum complexity class FBQP, and we provide a semantics-preserving compilation algorithm such that any PFOQ program can be compiled into a quantum circuit that grows polynomially on its number of input qubits, using an *anchoring-and-merging* technique to solve the problem of branch sequentialization.

**CCS Concepts: • Theory of computation → Quantum complexity theory; Complexity theory and logic.**

**ACM Reference Format:**

Emmanuel Hainry, Romain Péchoux, and Mário Silva. 2025. A Polytime Quantum Programming Language. *ACM Trans. Quantum Comput.* 7, 1, Article 4 (November 2025), 32 pages. https://doi.org/10.1145/3769851

# 1 Introduction

## 1.1 Background and Motivation

Quantum computation envisions the development of algorithms which leverage the laws of quantum physics in order to provide an advantage over classical strategies. This interest has lead to a plethora of examples where quantum programs, in theory, outperform what is achievable classically, such as integer factorization [Shor 1994], simulation of physical systems [Childs et al. 2018], search problems [Childs et al. 2003; Grover 1996], cryptography [Bennett and Brassard 2014; Ekert 1991] and teleportation [Bennett et al. 1993]. Similarly, different models of quantum computation have emerged, such as quantum Turing machines (QTMs) [Bernstein and Vazirani 1997; Ozawa and Nishimura 2000; Yamakami 1999], quantum circuits [Feynman 1982; Nielsen and Chuang 2011], measurement-based quantum computers [Briegel et al. 2009; Danos and Kashefi 2006] and circuit description languages [Ross 2015]. This variety of low-level models can be an asset in the creation of new algorithms but it can also be a difficulty for the developer when reasoning about the properties of their program.

The aim of quantum programming languages, starting with the seminal paper [Selinger 2004], is to allow the expressiveness required for creativity in algorithm development, while also restricting the user to instructions that are valid in a quantum computer, namely those that are reversible and, in particular, unitary. One may even aim for more than unitarity, and construct a programming language that ensures even more desirable properties, such as termination or time complexity

Authors' Contact Information: Emmanuel Hainry, hainry@loria.fr; Romain Péchoux, pechoux@loria.fr; Mário Silva, mmachado@loria.fr, Université de Lorraine, CNRS, Inria, LORIA, Nancy, France.
bounds. This is related to the field of *implicit computational complexity*, where one seeks to characterize complexity classes by placing syntactical restrictions (e.g. a type system) on programming languages or other paradigms of computation [Bellantoni and Cook 1992; Dal Lago 2011; Péchoux 2020].

In employing a restricted language, the developer is guaranteed that any program they write can be statically (and efficiently) verified to satisfy certain given properties. In this line of work, [Dal Lago et al. 2010] provided the first implicit characterization of the quantum polynomial-time classes for decision problems (EQP, BQP and ZQP). With no explicit mention of polynomial-time functions in its syntax, the authors in [Dal Lago et al. 2010] show that any term in their classically-controlled quantum lambda calculus can be evaluated in polynomial time. Conversely, any problem decidable by a QTM in polynomial time can be encoded into a corresponding term that simulates it.

Our work is greatly inspired by a result of [Yamakami 2020], who described a function algebra characterization of the class FBQP, i.e. functions which can be approximated to bounded-error probability by a QTM in polynomial time. In [Yamakami 2020], the author shows that with relatively simple constructions (base functions, composition, a quantum control case and a restricted recursion scheme) one can approximate precisely all the functions contained in FBQP.

To our knowledge, [Dal Lago et al. 2010; Yamakami 2020] constitute the only results concerning implicit characterizations of quantum polynomial time classes. This work focuses on two main areas of improvement: *implementation* and *expressivity*. While [Dal Lago et al. 2010; Yamakami 2020] both restrict their programs to those simulatable by a polytime QTM, they do not provide any *direct* compilation strategy which ensures polynomial size of the corresponding circuits. Given the constructive equivalence result between QTMs and quantum circuits in [Yao 1993], this is not a theoretical issue but more of a practical one: for a programming language, one would want a compilation strategy that preserves efficiency (i.e. polynomial time) without requiring an intermediate QTM representation. We provide such a compilation strategy in this work, and detail the circuit construction with examples.

From this point-of-view, our work can be seen as a contribution to the fields of *resource-aware* compilation techniques for quantum computation [Häner et al. 2020; Meuli et al. 2020; van de Wetering et al. 2025], and cost analysis of quantum programs [Avanzini et al. 2024, 2022; Colledan and Dal Lago 2024, 2025].

Regarding the second point, a language which is restricted to polynomial time should still aim to be as expressive as possible, to allow for creativity in algorithm design. While FOQ, the language introduced in this paper, and its polytime fragment PFOQ, are inspired by the function algebra in [Yamakami 2020], we claim that it is less constraining in algorithm design. To this end, we provide a number of notable examples which demonstrate FOQ and PFOQ's expressive power.

## 1.2 Contribution

This paper contains the following work:

* We introduce a quantum programming language, named FOQ, that includes first-order recursive procedures. The input of a FOQ program consists in a sorted set of qubits – a list of pairwise distinct qubit indexes – over which a program can apply its basic operations, corresponding to unary unitary operators, chosen to form a universal set of quantum gates.

* After showing that terminating FOQ programs are reversible (Theorem 1), we restrict programs to a strict subset, named PFOQ, for *polynomial time* FOQ. The restrictions put on PFOQ programs are tractable (i.e., can be decided in polynomial time, see Theorem 2), ensure that programs terminate on any input (Lemma 1), and prevent programs from having any exponential blow up (Lemma 2).
* We show that the class of functions computed by PFOQ programs is *sound* and *complete* for the quantum complexity class FBQP, which is the functional extension of *bounded-error quantum polynomial time*, known as BQP [Bernstein and Vazirani 1997], the class of decision problems solvable by a quantum computer in polynomial time with an error probability of at most 1/3 for all instances. Hence, PFOQ is, to our knowledge, the first programming language characterizing quantum polynomial time functions. Soundness (Theorem 3) is proved by showing that any PFOQ program can be simulated by a quantum Turing machine running in polynomial time [Bernstein and Vazirani 1997], and completeness (Theorem 6) is demonstrated by showing that PFOQ programs encompass Yamakami's function algebra, known to be FBQP-complete [Yamakami 2020].

* We describe a compilation algorithm, named **compile**, that for any PFOQ program P and input size n, outputs a circuit of polynomial size in n that simulates P on n qubits (Theorem 10). The **compile** algorithm is composed of two subroutines, Algorithms 1 and 2, which perform *anchoring* and *merging* of recursive calls to ensure polynomial time, as described in Section 5. We show that, in our setting, circuits can be efficiently computed and that the **compile** algorithm is tractable (Theorem 9).

This work is an extended version of [Hainry et al. 2023] presented at FoSSaCS 2023. This version contains all the proofs that the previous version could not contain, as well as the following further contributions:

* We prove that the compilation technique is semantics-preserving (Theorem 10) by using the fact that the orthogonality condition is an invariant property of **optimize** (Lemma 5).

* We describe how the **compile** algorithm and its subroutine **optimize** (Algorithm 2) tackle the problem identified in [Yuan and Carbin 2022] as *branch sequentialization*, the fact that the time complexity of a quantum branch in the circuit model is the sum of the branches and not the maximum. We show that this problem can be handled at the compiler level for any PFOQ program, and therefore we increase the space of quantum polytime programs that can be efficiently compiled into circuits.

* In Section 5.4, we detail a compilation example to give a better intuition of the **optimize** subroutine, which constitutes the difficult part of our compilation strategy.

The leading example for demonstrating the syntax and expressivity of PFOQ will be the quantum Fourier transform introduced in Example 1, with the additional example of quantum teleportation in Example 2 (see Section 2).

A software artifact that implements the compilation technique described in this work is available at https://gitlab.inria.fr/mmachado/pfoq-compiler.

# 2 First-order quantum programming language

## 2.1 Syntax and Well-Formedness

We consider a quantum programming language, called FOQ for First-Order Quantum programming language, that includes basic data types such as Integers, Booleans, Qubits, Operators, and Sorted Sets of qubits, which are lists of finite length where all elements are different. A FOQ program has the ability to call first-order (recursive) procedures taking a sorted set of qubits as a parameter. Their syntax is provided in Figure 1.

Let $x$ denote an integer variable and $\tilde{p}, \tilde{q}$ denote sorted sets variables. The size of the sorted set stored in $\tilde{q}$ will be denoted by $|\tilde{q}|$. We can refer to the $i$-th qubit in $\tilde{q}$ as $\tilde{q}[i]$, with $1 \le i \le |\tilde{q}|$. Hence, each non-empty sorted set variable $\tilde{q}$ can be viewed as a list $[\tilde{q}[1], \dots, \tilde{q}[|\tilde{q}|]]$. The empty sorted set, of size 0, will be denoted by `nil` and $\tilde{q} \ominus [i]$ will denote the sorted set obtained by removing the
<table><caption>Fig. 1. Syntax of FOQ programs.</caption><tr><td>(Integers)</td><td>i</td><td>n | x | i + n | i − n | |s|, with n ∈ N</td></tr><tr><td>(Booleans)</td><td>b</td><td>i > i | i ≥ i | i = i | b ∧ b | b ∨ b | ∄b</td></tr><tr><td>(Sorted Sets)</td><td>s</td><td>nil | ¯q | ¯p | s ⊖ [i]</td></tr><tr><td>(Qubits)</td><td>q</td><td>s[i]</td></tr><tr><td>(Operators)</td><td>U<sup>f</sup>(i)</td><td>NOT | R<sub>Y</sub><sup>f</sup>(i) | Ph<sup>f</sup>(i), with f ∈ Z → [0, 2π) ∩ R̃</td></tr><tr><td>(Statements)</td><td>S</td><td><b>skip</b> | q * = U<sup>f</sup>(i); | S S | <b>if b then S else S</b> | <b>qcase</b> q of {0 → S, 1 → S} | <b>call</b> proc[i](s);</td></tr><tr><td>(Procedure declarations)</td><td>D</td><td>ε | <b>decl</b> proc[x](¯p){S}, D</td></tr><tr><td>(Programs)</td><td>P(¯q)</td><td>D :: S</td></tr></table>

qubit of index *i* in ¯q. For notational convenience, we extend this notation by $\bar{q} \ominus [i_1, \dots, i_k]$, for the list obtained by removing the qubits of indexes $i_1, \dots, i_k$ in the sorted set $\bar{q}$.

The language also includes some constructs $U^f$ to represent (unary) unitary operators, for some total function $f \in \mathbb{Z} \to [0, 2\pi) \cap \mathbb{R}$. The function $f$ is required to be polynomial-time approximable: its output is restricted to $\tilde{\mathbb{R}}$, the set of real numbers that can be approximated by a Turing machine for any precision $2^{-k}$ in time polynomial in $k$ [Ko and Friedman 1982].

A FOQ program $P(\bar{q})$ consists of a sequence of *procedure declarations* $D$ followed by a *program statement* $S \in \text{Statements}$, $\varepsilon$ denoting the empty sequence. In what follows, we will sometimes refer to program $P(\bar{q})$ simply as $P$. Let $var(S)$ be the set of variables appearing in the statement $S$. Let $|P|$ be the size of program $P$, that is the total number of symbols in $P$.

A procedure declaration **decl** proc[x](\bar{p}){S} takes a sorted set parameter \bar{p} and some optional integer parameter x as inputs. S is called the *procedure statement*, proc is the *procedure name* and belongs to a countable set Procedures. We will write $S^{\text{proc}}$ to refer to S and proc $\in P$ holds if proc is declared in D.

Besides the no-op instruction **skip**, the most basic statement is the operation of an (unary) operator on a qubit ($q * = U^f(i)$). The considered operators are NOT, $R_Y^f(i)$, and Ph$^f(i)$.

Statements also include sequences, (classical) conditionals, *quantum cases*, and *procedure calls* which take an integer input *i* and a sorted subset of qubits *s* (**call** proc[i](s)). A quantum case **qcase** q of {0 → S<sub>0</sub>, 1 → S<sub>1</sub>} provides a quantum control feature that will execute statements S<sub>0</sub> and S<sub>1</sub> in superposition. For example, the *CNOT* gate on qubits $\bar{q}[i]$ and $\bar{q}[j]$, for $i, j \in \mathbb{N}, i \neq j$, can be simulated by the following statement:

$$ \text{CNOT}(\bar{q}[i], \bar{q}[j]) \triangleq \text{qcase } \bar{q}[i] \text{ of } \{0 \to \text{skip}, 1 \to \bar{q}[j] * = \text{NOT}; \}. $$

Throughout the paper, we restrict our study to *well-formed* programs, that is, programs $P = D :: S$ satisfying the following properties: $var(S) \subseteq \{\bar{q}\}; \forall \text{proc} \in P, var(S^{\text{proc}}) \subseteq \{x, \bar{p}\}$; procedure names declared in D pairwise are distinct; for each procedure call, the procedure name is declared in D.

## 2.2 Semantics

Let $\mathcal{H}_{2n}$ be the Hilbert space $\mathbb{C}^{2n}$ of $n$ qubits. We use Dirac notation to denote a quantum state $|\psi\rangle \in \mathcal{H}_{2n}$. Each $|\psi\rangle \in \mathcal{H}_{2n}$ can be written as a superposition of bitstrings of size $n$: $|\psi\rangle = \sum_{w \in \{0,1\}^n} \alpha_w |w\rangle$, with $\alpha_w \in \mathbb{C}$ and $\sum_w |\alpha_w|^2 = 1$. The length $\ell(|\psi\rangle)$ of the state $|\psi\rangle$ is $n$. Given two matrices $M, N$, we denote by $M^\dagger$ the transpose conjugate of $M$ and by $M \otimes N$ the tensor product of $M$ by $N$. $\langle\psi|$ is equal to $|\psi\rangle^\dagger$ and $|\psi\rangle\langle\phi|$ and $\langle\psi|\phi\rangle$ are respectively the outer and inner products of $|\psi\rangle$ with $|\phi\rangle$. Let
$I_n$ be the identity matrix in $\mathbb{C}^{n \times n}$. Given $m \le n$ and $i \in \{0, 1\}$, define $|i\rangle_m \triangleq I_{2^{m-1}} \otimes |i\rangle \otimes I_{2^{n-m}}$ and $\langle i|_m \triangleq (|i\rangle_m)^\dagger$.

A function $[[U^f]] \in \mathbb{Z} \to \tilde{\mathbb{C}}^{2 \times 2}$ is associated to each operator $U^f$ as follows:

$$[[\text{NOT}]](n) \triangleq \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad [[\text{R}_Y^f]](n) \triangleq \begin{pmatrix} \cos(f(n)) & -\sin(f(n)) \\ \sin(f(n)) & \cos(f(n)) \end{pmatrix}, \quad [[\text{Ph}^f]](n) \triangleq \begin{pmatrix} 1 & 0 \\ 0 & e^{if(n)} \end{pmatrix},$$

where $\tilde{\mathbb{C}}$ is the set of complex numbers whose real and imaginary parts are both in $\tilde{\mathbb{R}}$. This restriction corresponds to the set of transitions amplitudes allowed by efficient quantum Turing machines [Adleman et al. 1997; Bernstein and Vazirani 1997]. This property is ensured by the description of function $f$, which links the integer value given as input to the gate with the actual rotation angles. One can easily check that each matrix $M \triangleq [[U^f]](n) \in \tilde{\mathbb{C}}^{2 \times 2}$ is unitary, i.e., it satisfies $M^\dagger M = MM^\dagger = I_2$.

The choice of NOT, $R_Y^f(i)$, and $\text{Ph}^f(i)$ as basic operators is justified by the fact that, for the constant and polynomial-time approximable function $g \in \mathbb{Z} \to [0, 2\pi) \cap \tilde{\mathbb{R}}$ s.t. $g(x) = \pi/4$, these operators simulate the following set of one-qubit unitary gates

$$[[\text{NOT}]](n) = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad [[\text{R}_Y^g]](n) = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}, \quad [[\text{Ph}^g]](n) \triangleq \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix},$$

which, combined with a construction for controlled gates, is universal for quantum computing [Boykin et al. 1999]. For instance, the Hadamard gate can be easily derived as

$$H \triangleq \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = [[\text{NOT}]](n) \cdot [[\text{R}_Y^g]](n).$$

Let $\mathbb{B}$ be the set of Boolean values $b \in \{\text{false, true}\}$. For a given set $X$, let $\mathcal{L}(X)$ be the set of lists of elements in $X$. Let $l = [x_1, \dots, x_m]$, with $x_1, \dots, x_m \in X$, denote a list of $m$ elements in $\mathcal{L}(X)$ and $[]$ be the empty list (when $m=0$). For $l, l' \in \mathcal{L}(X)$, $l@l'$ denotes the concatenation of $l$ and $l'$. $hd(l)$ and $tl(l)$ represent the tail and the head of $l$, respectively. Lists of integers will be used to represent Sorted Sets. They contain pointers to qubits (i.e., indexes) in the global memory.

We interpret each basic data type $\tau$ as follows: $[[\text{Integers}] \triangleq \mathbb{Z}]$, $[[\text{Booleans}] \triangleq \mathbb{B}]$, $[[\text{SortedSets}] \triangleq \mathcal{L}(\mathbb{N})]$, $[[\text{Qubits}] \triangleq \mathbb{N}]$, and $[[\text{Operators}] \triangleq \tilde{\mathbb{C}}^{2 \times 2}]$. Each basic operation $\text{op} \in \{+, -, >, \ge, =, \wedge, \vee, \neg\}$ of arity $n$, with $1 \le n \le 2$, has a type signature $\tau_1 \times \dots \times \tau_n \to \tau$ fixed by the program syntax. For example, the operation $+$ has signature Integers $\times$ Integers $\to$ Integers. A total function $[[\text{op}] \in [\tau_1] \times \dots \times [\tau_n]] \to [\tau]$ is associated to each op.

For each basic type $\tau$, the reduction $\mathcal{U}_{[\tau]}$ is a map in $\tau \times \mathcal{L}(\mathbb{N}) \to [\tau]$. Intuitively, it maps an expression of type $\tau$ and a list of pointers in $\mathcal{L}(\mathbb{N})$ to the value of the expression in $[\tau]$. These reductions are defined in Figure 2, where $e$ and $d$ denote either an integer expression $i$ or a boolean expression $b$.

Note that, in rule (Rm<sub>ε</sub>), if we try to delete an undefined index then we return the empty list, and, in rule (Qu<sub>ε</sub>), if we try to access an undefined qubit index then we return the value 0 (defined indexes will always be positive).

We can define some syntactic sugar for useful instructions, such as the Hadamard gate $H$ and the swap gate. For instance, we can simulate the application of $H$ on $q$ by the following statement $q * = R_Y^g(0)$; $q * = \text{NOT}$, with the function $g$ defined by $g \in \mathbb{Z} \to [0, 2\pi) \cap \tilde{\mathbb{R}}$ s.t. $g(x) = \pi/4$. By abuse of notation, we will sometimes use $q * = H$; to denote this statement. Using CNOT, we can also define the SWAP operation swapping the states between two qubits $\bar{q}[i]$ and $\bar{q}[j]$, with $i, j \in \mathbb{N}, i \neq j$:

$$\text{SWAP}(\bar{q}[i], \bar{q}[j]) \triangleq \text{CNOT}(\bar{q}[i], \bar{q}[j]) \text{CNOT}(\bar{q}[j], \bar{q}[i]) \text{CNOT}(\bar{q}[i], \bar{q}[j]).$$
$$
\begin{array}{r@{\quad}l@{\qquad}l@{\qquad}l}
\frac{(e, l) \mathcal{U}_{[\tau_1]} m}{(e \ \mathrm{op} \ d, l) \mathcal{U}_{[\mathrm{op}]}([\tau_1], [\tau_2])} & \mathcal{U}_{[\tau_2]} n & \mathcal{U}_{[\tau_2]} n & \mathcal{U}_{[\tau_2]} n \\
\frac{(i, l) \mathcal{U}_{\mathcal{Z}} n}{(n, l) \mathcal{U}_{\mathcal{Z}} n} & \mathcal{U}_{\mathcal{Z}} n & \mathcal{U}_{\mathcal{Z}} n & \mathcal{U}_{\mathcal{Z}} n \\
\frac{(s, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s \ominus [i], l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_{k-1}, x_{k+1}, \dots, x_m]} & (i, l) \mathcal{U}_{\mathcal{Z}} k \in [1, m] & (i, l) \mathcal{U}_{\mathcal{Z}} k \notin [1, m] & (Rm \in) \\
\frac{(s, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_n]}{(|s|, l) \mathcal{U}_{\mathcal{Z}} n} & \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m] & (s \ominus [i], l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m] & (Rm \notin) \\
\frac{(s, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(\mathrm{nil}, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [l]} & (s, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m] & (i, l) \mathcal{U}_{\mathcal{Z}} k \in [1, m] & (Qu \in) \\
\frac{(s, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(\bar{q}, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} l} & (s, l) \mathcal{U}_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m] & (i, l) \mathcal{U}_{\mathcal{Z}} k \notin [1, m] & (Qu \notin) \\
& (s[i], l) \mathcal{U}_{\mathbb{N}} 0 & &
\end{array}
$$

<caption>Fig. 2. Semantics of expressions</caption>

Let $\top$ and $\bot$ be two special symbols for termination and error, respectively, and let $\diamond$ stand for a
symbol in $\{\top, \bot\}$. The set of configurations of dimension $2^n$, denoted $\text{Conf}_n$, is defined by

$$
\mathrm{Conf}_n \triangleq (\mathrm{Statements} \cup \{\top, \bot\}) \times \mathcal{H}_{2^n} \times \mathcal{P}(\mathbb{N}) \times \mathcal{L}(\mathbb{N}),
$$

with $\mathcal{P}(\mathbb{N})$ being the powerset over $\mathbb{N}$. A configuration $c = (S, |\psi\rangle, A, l) \in \text{Conf}_n$ contains a statement $S$ to be executed (provided that $S \notin \{\top, \bot\}$), a quantum state $|\psi\rangle$ of length $n$, a set $A$ containing the indexes of qubits that are allowed to be accessed by statement $S$, and a list $l$ of qubit pointers.

The program big-step semantics —, described in Figure 3, is defined as a relation in ⋃<sub>n∈N</sub> Conf<sub>n</sub>× Conf<sub>n</sub>. In the rules of Figure 3, — is annotated by an integer, called level. For example, the level of the conclusion in the (Call<sub>1</sub>) rule is 1. The level is used to count the total number of procedure calls that are not in superposition (i.e., in distinct branches of a quantum case).

We now give a brief intuition on the rules of Figure 3. Rules (Asg⊥) and (Asg⊤) evaluate the
application of a unitary operator, corresponding to U<sup>f</sup>(j), to a qubit s[i]. For that purpose, they
evaluate the index n of s[i] in the global memory. Rule (Asg⊥) deals with the error case, where the
corresponding qubit is not allowed to be accessed. Rule (Asg⊤) deals with the success case: the
new quantum state is obtained by applying the result of tensoring the evaluation of U<sup>f</sup>(j) to the
right index. Rules (Seq<sub>◦</sub>) and (Seq⊥) evaluate the sequence of statements, depending on whether
an error occurs or not. The (If) rule deals with classical conditionals in a standard way. The three
rules (Case⊤), (Case⊥), and (Case<sub>‡</sub>) evaluate the qubit index n of the control qubit s[i]. Then they
check whether this index belongs to the set of accessible qubits (is n in A?). If so, intuitively, the
two statements S<sub>0</sub> and S<sub>1</sub> are evaluated in superposition, on the projected state ⟨0|<sub>n</sub>|ψ⟩ and ⟨1|<sub>n</sub>|ψ⟩,
respectively. During these evaluations, the index n cannot be accessed anymore. The rule (Call<sub>1</sub>)
treats the base case of a procedure call when the sorted set parameter is empty. In the non-empty
case, rule (Call<sub>◦</sub>) evaluates the sorted set parameter s to l' and the integer parameter x to n. It
returns the result of evaluating the procedure statement S<sup>proc</sup>{n/x}, where n has been substituted
to x, with regards to the updated qubit pointers list l'.

For a given program P = D :: S and a given quantum state |ψ⟩ ∈ H<sub>2n</sub>, the initial configuration
for input |ψ⟩ is c<sub>init</sub>(|ψ⟩) ≜ (S, |ψ⟩, {1, ..., n}, [1, ..., n]) ∈ Conf<sub>n</sub>. A program is error-free if there
$$ (\mathbf{skip}, |\psi\rangle_A, l) \xrightarrow{0} (\tau, |\psi\rangle_A, l) \qquad (\text{Skip}) $$

$$ \frac{(s[i], l) \downarrow_N n \notin A}{(s[i] * U^f(j), |\psi\rangle_A, l) \xrightarrow{0} (\perp, |\psi\rangle_A, l)} \qquad (\text{Asg}_\perp) $$

$$ \frac{(s[i], l) \downarrow_N n \in A \quad (U^f(j), l) \downarrow_{C^{2 \times 2}} M}{(s[i] * U^f(j), |\psi\rangle_A, l) \xrightarrow{0} (\tau, I_{2^{n-1}} \otimes M \otimes I_{2^l(|\psi\rangle)^{-n}}, |\psi\rangle_A, l)} \qquad (\text{Asg}_\tau) $$

$$ \frac{(S_1, |\psi\rangle_A, l) \xrightarrow{m_1} (\tau, |\psi'\rangle_A, l) \quad (S_2, |\psi'\rangle_A, l) \xrightarrow{m_2} (\diamond, |\psi''\rangle_A, l)}{(S_1 S_2, |\psi\rangle_A, l) \xrightarrow{m_1+m_2} (\diamond, |\psi''\rangle_A, l)} \qquad (\text{Seq}_\diamond) $$

$$ \frac{(S_1, |\psi\rangle_A, l) \xrightarrow{m} (\perp, |\psi\rangle_A, l)}{(S_1 S_2, |\psi\rangle_A, l) \xrightarrow{m} (\perp, |\psi\rangle_A, l)} \qquad (\text{Seq}_\perp) $$

$$ \frac{(b, l) \downarrow_B b \in \mathbb{B} \quad (S_b, |\psi\rangle_A, l) \xrightarrow{m_b} (\diamond, |\psi'\rangle_A, l)}{(\mathbf{if} \ \mathbf{but} \ \mathbf{true} \ \mathbf{else} \ \mathbf{false}, |\psi\rangle_A, l) \xrightarrow{m_b} (\diamond, |\psi'\rangle_A, l)} \qquad (\text{If}) $$

$$ \frac{(s[i], l) \downarrow_N n \in A \quad \forall k \in \{0, 1\}, (S_k, |\psi\rangle_A \setminus \{n\}, l) \xrightarrow{m_k} (\tau, |\psi_k\rangle_A \setminus \{n\}, l)}{(\mathbf{qcase} \ s[i] \ \mathbf{of} \ \{0 \to S_0, 1 \to S_1\}, |\psi\rangle_A, l) \xrightarrow{\max_{k \in \{0,1\}} m_k} (\tau, \sum_{k \in \{0,1\}} |k\rangle_n \langle k|_n |\psi_k\rangle_A, l)} \qquad (\text{Case}_\tau) $$

$$ \frac{(s[i], l) \downarrow_N n \in A \quad \forall k \in \{0, 1\}, (S_k, |\psi\rangle_A \setminus \{n\}, l) \xrightarrow{m_k} (\diamond_k, |\psi_k\rangle_A \setminus \{n\}, l) \quad \perp \in \{\diamond_0, \diamond_1\}}{(\mathbf{qcase} \ s[i] \ \mathbf{of} \ \{0 \to S_0, 1 \to S_1\}, |\psi\rangle_A, l) \xrightarrow{\max_{k \in \{0,1\}} m_k} (\perp, |\psi\rangle_A, l)} \qquad (\text{Case}_\perp) $$

$$ \frac{(s[i], l) \downarrow_N n \notin A}{(\mathbf{qcase} \ s[i] \ \mathbf{of} \ \{0 \to S_0, 1 \to S_1\}, |\psi\rangle_A, l) \xrightarrow{0} (\perp, |\psi\rangle_A, l)} \qquad (\text{Case}_\perp) $$

$$ \frac{(s, l) \downarrow_{\mathcal{L}(\mathcal{N})} l' \neq [] \quad (i, l) \downarrow_{\mathcal{Z}} n \quad (\mathbf{S}^{\text{proc}}\{n/x\}, |\psi\rangle_A, l') \xrightarrow{m} (\diamond, |\psi'\rangle_A, l')}{(\mathbf{call} \ \mathbf{proc}[i](s), |\psi\rangle_A, l) \xrightarrow{m+1} (\diamond, |\psi'\rangle_A, l)} \qquad (\text{Call}_\diamond) $$

$$ \frac{(s, l) \downarrow_{\mathcal{L}(\mathcal{N})} []}{(\mathbf{call} \ \mathbf{proc}[i](s), |\psi\rangle_A, l) \xrightarrow{1} (\tau, |\psi\rangle_A, l)} \qquad (\text{Call}_[]) $$

<caption>Fig. 3. Semantics of statements.</caption>

is no initial configuration $c_{init}(|\psi\rangle)$ such that $c_{init}(|\psi\rangle) \to (\perp, |\psi'\rangle_A, l)$. We write $\llbracket P \rrbracket(|\psi\rangle) = |\psi'\rangle$, whenever $c_{init}(|\psi\rangle) \xrightarrow{m} (\tau, |\psi'\rangle_A, l)$ holds for some $m$. $(\tau, |\psi'\rangle_A, l)$ is called a terminal configuration. Let $\mathcal{H} \triangleq \bigcup_n \mathcal{H}_{2^n}$, a program terminates if $\llbracket P \rrbracket$ is a total function in $\mathcal{H} \to \mathcal{H}$. Note that if a program terminates then it is obviously error-free but the converse property does not hold. Every program $P$ can be efficiently transformed into an error-free program $P_{\neg\perp}$ such that $\forall |\psi\rangle$ if
<figure><img src="image_2.png" /><figcaption>Fig. 4. Circuit for the quantum Fourier transform.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 5. PFOQ program QFT for the quantum Fourier transform.</figcaption></figure>

[[P]](|ψ⟩) is defined then [[P]](|ψ⟩) = [[P_⊥]](|ψ⟩). For example, an assignment s[i] *= U<sup>f</sup>(j); can be transformed into the conditional statement **if** ((0 < i) ∧ (i ≤ |s|)) **then** s[i] *= U<sup>f</sup>(j); **else skip**.

EXAMPLE 1 (QUANTUM FOURIER TRANSFORM). A notable example of a quantum algorithm is the Quantum Fourier Transform (QFT), used as a subroutine in Shor's algorithm [Shor 1994], and whose quantum circuit is provided in Figure 4, with R<sub>n</sub> ≜ [[Ph<sup>λx·π/2<sup>x-1</sup></sup>]]<sub>n</sub>, for n ≥ 2. After iterating the application of Hadamard and controlled R<sub>n</sub> gates, the circuit performs a permutation of qubits using swap gates.

Note that $\lambda x \cdot \pi / 2^{x-1}$ is a total function in $\mathbb{Z} \to [0, 2\pi) \cap \tilde{\mathbb{R}}$ that is polynomial-time approximable. The circuit of Figure 4 can be simulated for any number of qubits $|q|$ by the FOQ program QFT provided in Figure 5.

EXAMPLE 2 (TELEPORTATION). If Alice and Bob share n EPR states, they can teleport any n-length state between their labs [Bennett et al. 1993]. The delayed measurement version of the quantum teleportation circuit can be encoded as a FOQ program.

We consider an input state of length n, and we extend it with 2n qubits in state $|0\rangle^{\otimes 2n}$. We can then create a FOQ program that transforms each pair $|00\rangle$ into an EPR state and then performs the teleportation for each qubit. An example of such a code is the program of Figure 6. As we will see later, the circuit of Figure 7 is obtained by compiling the FOQ program of Figure 6.

In Figure 7, the ground symbol represents which qubits would be measured in the end, and output wires $x_i$ denote the teleported qubits. For $1 \le i \le n$, we have that the i-th qubit of the input appears in position $3n - 2(i - 1)$ of the final state.
```pascal
decl createBell(p) {
    if |p| ≥ 3 :
        p[[p] - 1] *= H;
        CNOT(p[[p] - 1], p[[p]])
    call createBell(p ⊖ [1, |p| - 1, |p|]);
    else skip; },
}

decl teleport(p) {
    if |p| ≥ 3 :
        CNOT(p[1], p[[p] - 1])
        p[1] *= H;
        CNOT(p[[p] - 1], p[[p]])
    qcase p[1] of {0 → skip; 1 → p[[p]] *= Phλx.π(0); }
        call teleport(p ⊖ [1, |p| - 1, |p|]);
    else skip; } ::
}

call createBell(q); call teleport(q);
```

<figure><img src="image_4.png" /><figcaption>Fig. 7. Circuit for quantum teleportation.</figcaption></figure>

## 2.3 Derivation Tree and Level

Given a configuration $c$ with regards to a fixed program $P$, $\pi_P \succ c \to c'$ denotes the *derivation tree* of $P$ that describes the evolution of $c$ into a terminal configuration $c'$. This tree is only defined if the program terminates, and is obtained by applying the rules of Figures 2 and 3 on configuration $c$ with respect to $P$. We write $\pi$ instead of $\pi_P \succ c \to c'$ when $P$, $c$ and $c'$ are clear from the context. We will write $\pi \sqsubseteq \pi'$ to denote that $\pi$ is a subtree of $\pi'$.

In the case of a terminating computation $\pi \succ c \to c'$, we can define a level $m \in \mathbb{N}$ such that $c \xrightarrow{m} c'$ holds. In this case, the level of $\pi$ is defined as $\text{lv}_{\pi} \triangleq m$. Given a terminating FOQ program $P$, level$_P$ is a total function in $\mathbb{N} \to \mathbb{N}$ defined as level$_P(n) \triangleq \max_{|\psi\rangle \in \mathcal{H}_{2n}} \text{lv}_{\pi_P \succ c_{init}(|\psi\rangle)}$.

Intuitively, level$_P(n)$ corresponds to the maximal number of non-superposed procedure calls in any program execution on an input of length $n$.

**EXAMPLE 3.** Consider the program QFT of Example 1. Assume temporarily that QFT terminates (this will be shown in Example 4). For all $n \in \mathbb{N}$, level$_{QFT}(n) = \frac{(n+1)(n+2)}{2} + \lfloor \frac{n}{2} \rfloor + 1$. Indeed, on sorted sets of size $n$, procedure qft is called recursively $n + 1$ times and makes $n + 1$ calls to procedure rot
on sorted sets of size $n$, $n-1, \dots$, and $1$. On sorted sets of size $n$, rot performs $n$ recursive calls. Hence the total number of calls to rot is equal to $\sum_{i=1}^n i$. Finally, on a sorted set of size $n$, procedure inv does $\lfloor \frac{n}{2} \rfloor + 1$ recursive call.

A program $P$ is reversible if it terminates and there exists a program $P^{-1}$ such that $\llbracket P^{-1} \rrbracket \circ \llbracket P \rrbracket = \text{Id}$.

**THEOREM 1.** *All terminating FOQ programs are reversible.*

**PROOF.** We show this by induction on the structure of the program. Let $P = D :: S$ be a program that terminates. Define $P^{-1} \triangleq (D :: S)^{-1}$ inductively as

$$ 
\begin{align*}
(D :: S)^{-1} &\triangleq D^{-1} :: S^{-1} \\
(\mathbf{decl} \ proc[x](\bar{p})\{S\}, D)^{-1} &\triangleq \mathbf{decl} \ proc[x](\bar{p})\{S^{-1}\}, D^{-1} \\
\varepsilon^{-1} &\triangleq \varepsilon \\
\mathbf{skip};^{-1} &\triangleq \mathbf{skip}; \\
(q * = U^f(i);)^{-1} &\triangleq q * = (U^f(i))^\dagger; \\
(S_1 S_2)^{-1} &\triangleq S_2^{-1} S_1^{-1} \\
(\mathbf{if} \ \mathbf{b} \ \mathbf{then} \ S_{\mathbf{true}} \ \mathbf{else} \ S_{\mathbf{false}})^{-1} &\triangleq \mathbf{if} \ \mathbf{b} \ \mathbf{then} \ S_{\mathbf{true}}^{-1} \ \mathbf{else} \ S_{\mathbf{false}}^{-1} \\
(\mathbf{qcase} \ q \ \mathbf{of} \ \{0 \to S_0, 1 \to S_1\})^{-1} &\triangleq \mathbf{qcase} \ q \ \mathbf{of} \ \{0 \to S_0^{-1}, 1 \to S_1^{-1}\} \\
(\mathbf{call} \ proc[i](s);)^{-1} &\triangleq \mathbf{call} \ proc[i](s);,
\end{align*}
$$

with $\text{NOT}^\dagger \triangleq \text{NOT}$, $R_Y^f(i)^\dagger \triangleq R_Y^{-f}(i)$, and $\text{Ph}^f(i)^\dagger \triangleq \text{Ph}^{-f}(i)$. $P^{-1}$ terminates and is such that for all $|\psi\rangle, \llbracket P^{-1} \rrbracket(\llbracket P \rrbracket(|\psi\rangle)) = |\psi\rangle$. $\square$

# 3 Polynomial time soundness

In this section, we restrict the set of FOQ programs to a strict subset, named PFOQ, that is sound for the quantum complexity class FBQP. For this, we define two criteria: a criterion ensuring that a program terminates and a criterion preventing a terminating program from having an exponential runtime.

## 3.1 Polynomial-Time First Order Quantum Programs

Given two statements $S, S'$, we write $S \in S'$ to mean that $S$ is a substatement of $S'$ and $\text{proc} \in S$ holds if there are $i$ and $s$ such that **call** $\text{proc}[i](s) \in S$. Given a program $P = D :: S$, we define the relation $>_{P} \subseteq$ Procedures $\times$ Procedures by $\text{proc}_1 >_{P} \text{proc}_2$ if $\text{proc}_2 \in S^{\text{proc}_1}$, for any two procedures $\text{proc}_1, \text{proc}_2 \in S$. Put simply, the relation $>_{P} \text{proc}_1 \text{proc}_2$ means that for procedures $\text{proc}_1$ and $\text{proc}_2$ defined in program $P$, $\text{proc}_1$ performs a call to $\text{proc}_2$.

Using this relation, we can define a partial order on procedures for a given program, by defining $\succeq_P$ as the transitive and reflexive closure of $>_{P}$. Given a procedure $\text{proc}_1$ in a program $P$, the procedures $\text{proc}_i$ that satisfy $\text{proc}_1 \succeq_P \text{proc}_i$ are precisely those that can be called from an original call to $\text{proc}_1$.

Furthermore, we define the equivalence relation $\sim_P$ as $\text{proc}_1 \sim_P \text{proc}_2$ if $\text{proc}_1 \succeq_P \text{proc}_2$ and $\text{proc}_2 \succeq_P \text{proc}_1$ both hold. This gives us a generalized notion of mutual recursion between procedures. We also define the strict order $>_{P}$ as $\text{proc}_1 >_{P} \text{proc}_2$ if $\text{proc}_1 \succeq_P \text{proc}_2$ and $\text{proc}_1 \prec_P \text{proc}_2$ both hold. Example 4 showcases these relations and the partial order $\succeq_P$ for the QFT program (Example 1).

**DEFINITION 1.** Let $\mathbf{wf}$ be the set of FOQ programs $P$ that are error-free and satisfy the well-foundedness constraint:

$$ \forall \text{proc} \in P, \forall \mathbf{call} \ \text{proc}'[i](s) \in S^{\text{proc}}, \text{proc} \sim_P \text{proc}' \Rightarrow \exists k > 0, \exists i_1, \dots, i_k, s = \bar{p} \ominus [i_1, \dots, i_k]. $$

**LEMMA 1.** *If $P \in \mathbf{wf}$, then $P$ terminates.*
PROOF. For a given program P, we define a lexicographical partial order between configurations whose statements are procedure calls.

$$ (\mathbf{call} \ \mathbf{proc}[i](s), |\psi\rangle_A, l) \gg_P (\mathbf{call} \ \mathbf{proc}'[i')(s'), |\psi'\rangle_{A'}, l') $$

if $(\mathbf{proc} \succ_P \mathbf{proc}') \lor (\mathbf{proc} \sim_P \mathbf{proc}' \land n_s > n_{s'})$, provided that $(|s|, l) \Downarrow_N n_s$ and $(|s'|, l') \Downarrow_N n_{s'}$.

Given $\pi \triangleright (\mathbf{call} \ \mathbf{proc}[i](s), |\psi\rangle_A, l)$ and $\pi' \triangleright (\mathbf{call} \ \mathbf{proc}'[i')(s'), |\psi'\rangle_{A'}, l')$, we show that if $\pi' \le \pi$ then it holds that

$$ (\mathbf{call} \ \mathbf{proc}[i](s), |\psi\rangle_A, l) \gg_P (\mathbf{call} \ \mathbf{proc}'[i')(s'), |\psi'\rangle_{A'}, l'). $$

Consider a program $P \in \mathbf{wf}$. Assume that $\pi' \le \pi$, then it holds that $\mathbf{proc} \ge_P \mathbf{proc}'$. Hence, either $\mathbf{proc} \succ_P \mathbf{proc}'$ or $\mathbf{proc} \sim_P \mathbf{proc}'$. In this latter case, by transitivity of $\sim_P$, $s' = \bar{p} \ominus [i_1, \dots, i_k]$, for some $k > 0$. It implies that the evaluation of $|s'|$ is strictly smaller than the evaluation of $|s|$, by transitivity. We conclude by observing that $\gg_P$ is a well-founded order.

□

EXAMPLE 4. Consider the program QFT of Example 1. The statements of the procedure declarations define the following relation: qft $>_{QFT}$ qft, qft $>_{QFT}$ rot, rot $>_{QFT}$ rot, and inv $>_{QFT}$ inv. Consequently, qft $\sim_{QFT}$ qft, rot $\sim_{QFT}$ rot, inv $\sim_{QFT}$ inv, and qft $>_{QFT}$ rot hold. For each call to an equivalent procedure, we check that the argument decreases: $\bar{p} \ominus [1]$ in qft, $\bar{p} \ominus [2]$ in rot, and $\bar{p} \ominus [1, |\bar{p}|]$ in inv. Consequently, QFT $\in \mathbf{wf}$. We deduce from Lemma 1 that QFT terminates.

We now add a further restriction on mutually recursive procedure calls for guaranteeing polynomial time using a notion of width.

DEFINITION 2. Given a program P and a procedure proc $\in P$, the width of proc in P, noted width<sub>P</sub>(proc), is defined as width<sub>P</sub>(proc) $\triangleq$ $w_P^{\text{proc}}(S^{\text{proc}})$, where $w_P^{\text{proc}}(S)$ is the width of the procedure proc in P relative to statement S, defined inductively as:

$$ \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 then Strue else Sfalse}) &\triangleq \max(w_P^{\text{proc}}(S_{\text{true}}), w_P^{\text{proc}}(S_{\text{false}})), \\ w_P^{\text{proc}}(\text{qcase q 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 proc}[i](s);) &\triangleq \begin{cases} 1 & \text{if } \mathbf{proc} \sim_P \mathbf{proc}', \\ 0 & \text{otherwise.} \end{cases} \end{align*} $$

Importantly, this notion of width should not be mistaken with that of circuit width, which refers to the number of qubits in a circuit. In this case, it is analogous to a “branching factor” which accounts for how many recursive calls in sequence can be performed by a single procedure call.

DEFINITION 3 (PFOQ). PFOQ is the set of programs defined as:

$$ \text{PFOQ} \triangleq \{P \mid P \in \mathbf{wf} \land \forall \mathbf{proc} \in P, \text{width}_P(\mathbf{proc}) \le 1\}. $$

If $P \in \text{PFOQ}$, then we call $P$ a PFOQ program.

EXAMPLE 5. In the program of Example 1, $\text{width}_{\text{QFT}}(q\text{ft}) = \text{width}_{\text{QFT}}(\text{rot}) = \text{width}_{\text{QFT}}(\text{inv}) = 1$, since qft $>_{\text{QFT}}$ rot holds. Since QFT $\in \mathbf{wf}$, by Example 4, we conclude that QFT is a PFOQ program.

We now show that the level of a PFOQ program is bounded by a polynomial in the length of its input. We will start by defining the notion of rank of a procedure and rank of a program.
**DEFINITION 4 (RANK OF A PROCEDURE).** Given a FOQ program P, the rank of a procedure in P is defined as:

$$ 
\begin{array}{l@{\qquad}l}
rk(\mathit{proc}) & \stackrel{\sim}{=} 0 & \mathit{if} \ \mathit{\nexists} \ \mathit{proc}' \ \mathit{proc}' \ \mathit{proc} >_{\mathit{P}} \mathit{proc}' \\
rk(\mathit{proc}) & \stackrel{\sim}{=} \max\{rk(\mathit{proc}') + 1 \mid \mathit{proc} >_{\mathit{P}} \mathit{proc}'\} & \mathit{otherwise.}
\end{array}
$$

**DEFINITION 5 (RANK OF A PROGRAM).** The rank of program P is defined by

$$ rk(P) \stackrel{\sim}{=} \max_{\mathit{proc} \in P} rk(\mathit{proc}). $$

**LEMMA 2.** For any PFOQ program P, we have that $\mathit{level}_P(n) = O(n^{rk(P)+1})$.

**PROOF.** Consider a PFOQ program P = D :: S. We show the result by induction on the rank of procedure calls in S. Take **call** proc[i](s) ∈ S. If $rk(\mathit{proc}) = 0$ and the procedure is not recursive then there is only 1 call to a procedure. If the procedure is recursive, it can be called at most once in each branch of a quantum case statement. Hence there can be at most $n + 1$ such calls in the full quantum case branch of the derivation tree and it holds that $\mathit{level}_{D::call} \mathit{proc}[i](s)(n) = O(n)$.

Induction hypothesis: assume that any procedure proc' such that $rk(\mathit{proc}') \le k$ satisfies

$$ \mathit{level}_{D::call \ \mathit{proc}'}[i](s)(n) = O(n^{k+1}). $$

Consider a procedure proc such that $rk(\mathit{proc}) = k + 1$. If the procedure is not recursive then it can call a constant number (bounded by the size of the program) of procedures of strictly smaller rank. By induction hypothesis,

$$ \mathit{level}_{D::call \ \mathit{proc}[i](s)}(n) = \sum_{\mathit{proc}' <_{\mathit{pproc}} \mathit{proc}} O(n^{rk(\mathit{proc}')} + 1) = O(n^{rk(\mathit{proc})}). $$

If the procedure is recursive, it can be called at most once in each branch of a quantum case statement. Hence there can be at most $n + 1$ such calls in the full quantum case branch of the derivation tree. Moreover, each of these calls can perform a constant number of calls to procedures of strictly smaller rank. Consequently,

$$ \mathit{level}_{D::call \ \mathit{proc}[i](s)}(n) = O(n) + \sum_{i=0}^{n} \sum_{\mathit{proc}' <_{\mathit{pproc}} \mathit{proc}} O(n^{rk(\mathit{proc}')} + 1) = O(n^{rk(\mathit{proc})+1}). $$

We observe that for a program P = D :: S₁ ... Sk, it holds that

$$ \mathit{level}_P(n) = O\left(\sum_{i=1}^{k} \mathit{level}_{D::S_i}(n)\right) = O(n^{rk(P)+1}). $$

This concludes the proof. □

Moreover, checking whether a program is in PFOQ is tractable.

**THEOREM 2.** For each FOQ program P, it can be decided in time $O(|P|^2)$ whether $P_{\neg \perp} \in \text{PFOQ}$.

**PROOF.** Any FOQ program P can be transformed in time $O(|P|)$ into an equivalent error-free program $P_{\neg \perp}$ of size $O(|P|)$. Then, checking that $P_{\neg \perp} \in \text{PFOQ}$ amounts to checking that $P_{\neg \perp} \in \text{WF}$ and that $\forall \mathit{proc} \in P_{\neg \perp}$, $\text{width}_{P_{\neg \perp}}(\mathit{proc}) \le 1$.

First, we can compute the recursion relations $\sim_P, \ge_P$, and $>_P$, in time $O(|P|^2)$. Then, checking that all recursive calls reduce the size of the input qubit list and computing the width of each procedure can be done at the same time, by traversing the structure of each procedure statement in linear time. Consequently, both conditions can be checked in time $O(|P|^2)$. □
## 3.2 Quantum Turing Machines and the Class of Polytime Quantum Functions

Following [Bernstein and Vazirani 1997], a k-tape Quantum Turing Machine (QTM), with $k \ge 1$, is defined by a triplet $(\Sigma, Q, \delta)$ where

* $\Sigma$ is a finite alphabet including a blank symbol #,

* $Q$ is a finite set of states with an initial state $s_0$ and a final state $s_T \neq s_0$,

* $\delta$ is the quantum transition function in $Q \times \Sigma^k \to (Q \times \Sigma^k \times \{L, N, R\})^k \to \tilde{C}$, with $\{L, N, R\}$ being the set of possible movements of a head on a tape.

Each tape of the QTM is two-way infinite and contains cells indexed by $\mathbb{Z}$. A QTM successfully terminates if it reaches a superposition of only the final state $s_T$. A QTM is said to be *well-formed* if the transition function $\delta$ preserves the norm of the superposition (or, equivalently, if the time evolution of the machine is unitary). The starting position of the tape heads is the *start cell*, the cell indexed by 0. If the machine terminates with all of its tape heads back on the start cells, it is usually called *stationary*. We will use *stationary* in the case where the machine terminates with its input tape head in the first cell, and all other tape heads in the rightmost non-blank cell. This notion differs from the definition of stationary QTM in [Yamakami 2020] but it can be shown to be equivalent. We will further refer to a QTM as being *in normal form* if the only transitions from the final state $s_T$ are towards the initial state $s_0$. These will be important conditions for the composition and branching constructions of QTMs. If a QTM is well-formed, stationary, and in normal form, we will call it *conservative* [Yamakami 2020].

A configuration $\gamma$ of a k-tape QTM is a tuple $(s, \bar{w}, \bar{n})$, where $s$ is a state in $Q$, $\bar{w}$ is a k-tuple of words in $\Sigma^*$, and $\bar{n}$ is a k-tuple of indexes (head positions) in $\mathbb{Z}$. An initial (resp. final) configuration $\gamma_{init}$ (resp. $\gamma_{fin}$) is a configuration of the shape $(s_0, \bar{w}, \bar{0})$ (resp. $(s_T, \bar{w}, \bar{0})$). We use $\gamma(w)$ to denote a configuration $\gamma$ where the word $w$ is written on the input/output tape. Following [Bernstein and Vazirani 1997], we write $S$ to represent the inner-product space of finite complex linear combinations of configurations of the QTM $M$ with the Euclidean norm. A QTM $M$ defines a linear time operator $U_M : S \to S$ that outputs a superposition of configurations $\sum_i \alpha_i |y_i\rangle$ obtained by applying a single-step transition of $M$ to a configuration $|\gamma\rangle$ (i.e., $U_M|\gamma\rangle = \sum_i \alpha_i |y_i\rangle$). Let $U_M^t$, for $t \ge 1$, be the $t$-steps transition obtained from $U_M$ as follows: $U_M^1 \triangleq U_M$ and $U_M^{t+1} \triangleq U_M \circ U_M^t$. Given a quantum state $|\psi\rangle = \sum_{w \in \{0,1\}^n} \alpha_w |w\rangle$ and a configuration $\gamma$, let $\gamma(|\psi\rangle) \triangleq \sum_{w \in \{0,1\}^n} \alpha_w |\gamma(w)\rangle$.

A quantum function $f: \mathcal{H} \to \mathcal{H}$ is computed by the QTM $M$ in time $t$ for an input $|\psi\rangle \in \mathcal{H}$ if $U_M^t(\gamma_{init}(|\psi\rangle)) = \gamma_{fin}(f(|\psi\rangle))$. Given $T: \mathbb{N} \to \mathbb{N}$ and a quantum function $f$, we say that the QTM $M$ computes $f$ in time $T$ if for inputs of length $n$, $M$ computes $f$ in time $T(n)$.

**DEFINITION 6.** Given two functions $f: \{0, 1\}^* \to \{0, 1\}^*$, $F: \mathcal{H} \to \mathcal{H}$, and a value $p \in [0, 1]$, we say that $f$ is computed by $F$ with probability $p$ if $\forall x \in \{0, 1\}^*$, $|\langle f(x)|F(|x\rangle)|^2 \ge p$.

**DEFINITION 7 (FBQP, [BERNSTEIN AND VAZIRANI 1997]).** A function $f \in \{0, 1\}^* \to \{0, 1\}^*$ is in FBQP iff there exist a QTM $M$ and a polynomial $P \in \mathbb{N}[X]$ such that $M$ computes $f$ in time $P$ with probability $\frac{2}{3}$.

The class FBQP is the functional extension of the complexity class BQP, where we only consider functions $f \in \{0, 1\}^* \to \{0, 1\}$.

A function $f \in \{0, 1\}^* \to \{0, 1\}^*$ has a polynomial bound $P \in \mathbb{N}[X]$ if $\forall n \in \mathbb{N}, \forall x \in \{0, 1\}^n, \exists k \le P(n)$, $f(x) \in \{0, 1\}^k$. Functions in FBQP have a polynomial bound as the size of their output is smaller than the polynomial time bound.
## 3.3 Proof of Soundness

We show that QTMs can simulate the function computed by any terminating FOQ program. The time complexity of this simulation depends on the length of the input quantum state and on the level of the considered program.

**LEMMA 3.** For any terminating FOQ program P, there exists a conservative QTM M that computes $[[P]]$ in time $O(n + n \times \text{level}_P(n))$.

**PROOF.** Consider a terminating FOQ program P = D :: S. We build a 4-tape QTM M computing $[[P]]$ inductively on the statement S. Fix $\Sigma \triangleq \{0, 1, #, \|, &\}$, where # is the blank symbol and where $\|$ and & are special separation symbols for encoding stacks. The input tape $t_{in}$ of M contains a word in $\{0, 1, #\}^n$ encoding the quantum state. The 3 working tapes are $t_{call}$, $t_l$, and $t_K$ for storing the integer values of a procedure call, the list of qubit pointers, and intermediate classical computations, respectively, as words in $\Sigma^*$. The configurations of M will be in $Q \times (\Sigma^*)^4 \times \mathbb{Z}^4$, for some finite set of states Q. In particular, the initial configuration is $(s_0, w, \varepsilon, \varepsilon, \varepsilon, 0, 0, 0, 0)$, with $w \in \{0, 1\}^n$ encoding a quantum state of length $n \in \mathbb{N}$; the tapes $t_{call}$, $t_l$, and $t_K$ are initially empty $(\varepsilon)$. The tape heads all start on the first cells indexed by 0. For $m \in \mathbb{Z}$, let $t(m)$ denote the symbol at position $m$ on tape $t$. Given a word $w \in \Sigma^*$ and a tape $t$, $tw$ denotes that the content of $t$ ends with the word $w$.

By abuse of notation, let $[[e]]$ denote the result of evaluating the expression e with respect to the machine current configuration. Also, we will assume that deterministic computations, such as taking tape $t||[[i]]$ and appending $f([i])$, for any function $f$, are done by a reversible Turing machine [Bennett 1973], as reversible TMs are well-formed QTMs [Bernstein and Vazirani 1997, Theorem 4.2].

We now describe a QTM M simulating P inductively on the statement S.

* The **skip** statement is trivial.

* If $S = q ::= U^f(j); M$ appends $[[q]]$ to $t_K$. As the program terminates, $t_{in}([[[q]]]) \neq \#$ and the transition function is set to:

$$ \forall a \in \{0, 1\}, \delta(s_S, t_{in}([[[q]]]), s_{next(S)}, a, N) \triangleq \langle t_{in}([[[q]])|[[U^f]]([[[j]])]|a) \rangle $$

where $s_S$ is the state before executing the assignment when the head of the input tape has been moved to position $[[q]]$, and $s_{next(S)}$ is the state just after executing the assignment. Finally, the machine erases $||[[q]]$ at the end of $t_K$, leaves its head in the last non-blank cell of $t_K$, and moves the head in $t_{in}$ back to the initial cell. Program P has $\text{level}_P(n) = 0$ and the simulating machine runs in time $O(n)$.

For the remaining statements, assume by induction hypothesis the existence of two conservative QTMs $M_1$ and $M_2$ that compute functions $[[P_1]]$ and $[[P_2]]$, respectively, with $P_1 \triangleq D :: S_1$ and $P_2 \triangleq D :: S_2$. By induction hypothesis $M_1$ and $M_2$ run in time $O(n + n \times \text{level}_P(n))$. States of $M_i$ will be denoted by $s^i$, for $i \in \{1, 2\}$. By using internal clocks, we can assume without loss of generality that machines $M_i$ halt in exactly the same time for any quantum input of length $n$.

* Consider the case $S = S_1 S_2$. Machine M is defined as in [Bernstein and Vazirani 1997, Dovetailing Lemma], with the initial state $s_0 \triangleq s_0^1$, its final state $s_T \triangleq s_T^2$, and the two machines are composed by setting $s_T^1 = s_0^2$. The machine M is stationary, well-formed and it is well-behaved since the running time of $M_2$ only depends on $n$ and the output of $M_1$ contains a superposition of equally sized quantum states. M computes $[[P]]$ in time $O(n + n \times \text{level}_P(n)) + O(n + n \times \text{level}_P(n)) = O(n + n \times \text{level}_P(n))$.

* For the conditional $S = \text{if b then } S_1 \text{ else } S_2$, we build a machine M that concatenates $||[[b]]$ on the working tape $t_K$ and runs $M_1$ or $M_2$ deterministically depending on the value of $[[b]]$,
using the [Bernstein and Vazirani 1997, Branching Lemma]. Then we erase $[[b]]$ from the end of tape $t_K$. M computes $[[P]]$ in time $\max_i(O(n + n \times \text{level}_P(n))) = O(n + n \times \text{level}_P(n))$.

* For the quantum case $S = \text{qcase q of } \{0 \to S_1, 1 \to S_2\}$, the machine appends $[[q]]$ on tape $t_K$. It reads $t_{in}([[q]])$, sets it to #, and if it reads 0 runs $M_1$, if it reads 1, runs $M_2$. Finally, from state $s_1^-$, it writes 0 in $t_{in}([[q]])$, moves the head to index 0, and transitions to $s_T$; similarly, from state $s_T^-$, the machines writes 1 in $t_{in}([[q]])$ before moving the head and transitioning to $s_T$. We have that $M$ computes $[[P]]$ in time $\max_i(O(n + n \times \text{level}_P(n))) = O(n + n \times \text{level}_P(n))$.

* For the procedure call $S = \text{call proc}[i](s)$, inductively define machine $M$ as follows: update $t_{call}$ by appending $[[i]]$, and update $t_l$ by adding the qubit pointer indices excluded in $[[s]]$, separating them using the symbol &. We then run machine $M_{\text{proc}}$ that computes the function $[[P_{\text{proc}}]]$, for $P_{\text{proc}} \triangleq \text{D} \text{:: S}_{\text{proc}}\{[[i]]/x, s/\bar{q}\}$, in time $O(m + m \times \text{level}_{P_{\text{proc}}}(m))$, with $m \triangleq [[|s|]] \le n$, afterwards erasing $[[i]]$ and the new indices of $t_{in}$. As $\text{level}_{P_{\text{proc}}}(n) = O(\text{level}_P(n))$ and the complexity of $M$ is $O(n + n \times \text{level}_P(n))$. $\square$

Now we show that any PFOQ program computes a FBQPfunction.

**THEOREM 3 (SOUNDNESS).** *Given a PFOQ program P, a function $f: \{0, 1\}^* \to \{0, 1\}^*$, and a value $p \in (\frac{1}{2}, 1]$. If $f$ is computed by $[[P]]$ with probability $p$ then $f \in \text{FBQP}.$*

**PROOF.** Given a PFOQ program P, by Lemma 3, there exists a conservative QTM $M_P$ that computes $[[P]]$ in time $O(n + n \times \text{level}_P(n))$. By Lemma 2, there exists a polynomial $Q \in \mathbb{N}[X]$ such that $\forall n$, $\text{level}_P(n) \le Q(n)$. Consequently, the result holds by Definition 7. $\square$

# 4 Polytime completeness

In this section we show that any function in FBQP can be faithfully approximated by a PFOQ program. Toward this end, we show that [Yamakami 2020]'s FBQP-complete function algebra can be exactly simulated in PFOQ.

A characterization of FBQP was provided in [Yamakami 2020] using a function algebra, named $\overline{\square}_1^{\text{QP}}$. Given a quantum state $|\psi\rangle$ and a word $w \in \{0, 1\}^n$, with $n \le \ell(|\psi\rangle)$, $|\psi\rangle$ can be written as $|\psi\rangle = \sum_i \alpha_i |w_i z_i\rangle$ with $w_i \in \{0, 1\}^n$ and $z_i \in \{0, 1\}^{\ell(|\psi\rangle)-n}$. We write $\langle w|\psi\rangle$ as an abuse of notation for the quantum state defined by $\langle w|\psi\rangle \triangleq \sum_i \alpha_i \langle w|w_i\rangle |z_i\rangle$, which consists of projecting the state $|\psi\rangle$ onto the subspace where the first $n$ qubits are in state $|w\rangle$. For instance,

$$ \langle 00 | \left( \frac{1}{\sqrt{2}} |000\rangle + \frac{1}{2} |001\rangle + \frac{1}{2} |010\rangle \right) = \frac{1}{\sqrt{2}} |0\rangle + \frac{1}{2} |1\rangle. $$

**DEFINITION 8 (YAMAKAMI'S FUNCTION ALGEBRA).** $\overline{\square}_1^{\text{QP}}$ is the smallest class of functions including the following basic functions:

* $I(|\psi\rangle) \triangleq |\psi\rangle$

* $Ph_\theta(|\psi\rangle) \triangleq |0\rangle\langle 0|\psi\rangle + e^{i\theta}|1\rangle\langle 1|\psi\rangle$, with $\theta \in [0, 2\pi) \cap \tilde{\mathbb{C}}$,

* $Rot_\theta(|\psi\rangle) \triangleq \cos\theta|\psi\rangle + \sin\theta(|1\rangle\langle 0|\psi\rangle - |0\rangle\langle 1|\psi\rangle)$, with $\theta \in [0, 2\pi) \cap \tilde{\mathbb{C}}$,

* $NOT(|\psi\rangle) \triangleq |0\rangle\langle 1|\psi\rangle + |1\rangle\langle 0|\psi\rangle$

* $SWAP(|\psi\rangle) \triangleq \begin{cases} |\psi\rangle & \text{if } \ell(|\psi\rangle) \le 1 \\ \sum_{a,b \in \{0,1\}} |ba\rangle\langle ab|\psi\rangle & \text{otherwise,} \end{cases}$

and closed under schemes Comp, Branch, and kQRec$_t$, for $k, t \in \mathbb{N}$,

* $\text{Comp}[F, G](|\psi\rangle) \triangleq F(G(|\psi\rangle))$

* $\text{Branch}[F, G](|\psi\rangle) \triangleq \begin{cases} |\psi\rangle & \text{if } \ell(|\psi\rangle) \le 1 \\ |0\rangle \otimes F(\langle 0|\psi\rangle) + |1\rangle \otimes G(\langle 1|\psi\rangle) & \text{otherwise,} \end{cases}$
$$
\bullet \ kQRec_t[F, G, H](|\psi\rangle) \triangleq \begin{cases} F(|\psi\rangle) & \text{if } l(|\psi\rangle) \le t \\ G\left(\sum_{w \in \{0,1\}^k} |w\rangle \otimes F_w(w|H(|\psi\rangle))\right) & \text{otherwise,} \end{cases} \\
\text{where each } F_w \in \{kQRec_t[F, G, H], I\}.
$$

To handle general FBQP functions, [Yamakami 2020] defines the extended encoding of an input $x \in \{0, 1\}^*$ as $\phi_P(|x\rangle) \triangleq |0^{l(|x\rangle)}1\rangle|0^{P(l(|x\rangle)+6)}1\rangle|x\rangle$, for some polynomial $P \in \mathbb{N}[X]$ that is an upper bound on the output size of the desired FBQP function. $\phi_P$ simply consists in the quantum state $|x\rangle$ preceded by a polynomial number of ancilla qubits (the constants appearing in the expression are a result of the precise simulation of the QTM used in [Yamakami 2020]). These ancilla provide space for internal computations and account for the polynomial bound associated with polynomial time QTMs.

THEOREM 4 ([YAMAKAMI 2020]). Given $f: \{0,1\}^* \to \{0,1\}^*$ with polynomial bound $P \in \mathbb{N}[X]$, the following statements are equivalent.

1. The function $f$ is in FBQP.

2. There exists $F \in \widehat{\Box_1^{QP}}$ such that $F \circ \phi_P$ computes $f$ with probability $\frac{2}{3}$.

We now show that any function in $\widehat{\Box_1^{QP}}$ can be simulated by a PFOQ program.

THEOREM 5. Let $F$ be a function in $\widehat{\Box_1^{QP}}$. Then there exists a PFOQ program $P$ such that $[[P]] = F$.

PROOF. We prove this result by structural induction on a function in the $\widehat{\Box_1^{QP}}$ algebra. The basic function $I$ can be simulated by $P(\bar{q}) = \varepsilon :: \mathbf{skip}$. $F \in \{Ph_\theta, ROT_\theta, NOT\}$ can be simulated using an assignment. In these cases $P(\bar{q}) = \varepsilon :: \bar{q}[1] * = U^f(0)$; with $f$ such that $[[U^f]](0) = F$. The basic initial function SWAP can be simulated by the program $P(\bar{q}) = \varepsilon :: \text{SWAP}(\bar{q}[1], \bar{q}[2])$, with the SWAP statement defined in Section 2.2.

We now simulate the *Comp*, *Branch* and *kQRec*<sub>*t*</sub> schemes. For that purpose, assume the existence of PFOQ programs $P_F(\bar{q}) = D_F :: S_F$, $P_G(\bar{q}) = D_G :: S_G$, and $P_H(\bar{q}) = D_H :: S_H$ simulating the $\widehat{\Box_1^{QP}}$ functions *F*, *G*, and *H*, respectively. For simplicity, we assume that there are no name clashes between the procedures declared in $D_F$, $D_G$, and $D_H$.

*Comp*[F, G] can be simulated by $P(\bar{q}) = D_F, D_G :: S_G S_F$. Moreover $P \in \text{PFOQ}$ by construction.

*Branch*[F, G] can be simulated by

$$
\begin{align*}
P(\bar{q}) &= D_F, D_G, \mathbf{decl} \ proc_F(\bar{q})\{S_F\}, \mathbf{decl} \ proc_G(\bar{q})\{S_G\} :: \\
&\qquad \mathbf{qcase} \ \bar{q}[1] \ \mathbf{of} \ \{0 \to \mathbf{call} \ proc_F(\bar{q} \ominus [1]); 1 \to \mathbf{call} \ proc_G(\bar{q} \ominus [1]); \}.
\end{align*}
$$

Procedures $proc_F$ and $proc_G$ are not recursive and therefore $P \in \text{PFOQ}$.

We introduce the following syntactical sugar for an extended quantum case for $k \ge 2$, $\forall a \in \{0, 1\}$, and $\forall w \in \{0, 1\}^{k-1}$:

$$
\begin{align*}
\mathbf{qcase} \ s[i_1, \dots, i_k] \quad & \mathbf{of} \ \{aw \to S_{aw}\} \\
\triangleq \ \mathbf{qcase} \ s[i_1] \ \mathbf{of} \ \{ & 0 \to \mathbf{qcase} \ s[i_2 \dots i_k] \ \mathbf{of} \ \{w \to S_{0w}\}, \\
& 1 \to \mathbf{qcase} \ s[i_2 \dots i_k] \ \mathbf{of} \ \{w \to S_{1w}\} \}.
\end{align*}
$$
$kQRec_t[F, G, H]$ can be simulated by

$P(\bar{q}) = D_F, D_G, D_H,$

`decl proc_F(\bar{q}){S_F}, decl proc_G(\bar{q}){S_G}, decl proc_H(\bar{q}){S_H},`

`decl kQRec_t(\bar{p}){`

`if |\bar{p}| > t then`

`call proc_H(\bar{p});`

`qcase \bar{p}[1...k] of {w → S_w}`

`call proc_G(\bar{p});`

`else`

`call proc_F(\bar{p});` ::

`call kQRec_t(\bar{q});`

with $S_w \triangleq \begin{cases} \textbf{call} \ kQRec_t(\bar{p} \ominus [1 \dots k]); & \text{if } F_w = kQRec_t, \\ \textbf{skip}; & \text{if } F_w = I. \end{cases}$

The recursive calls to procedure $kQRec_t$ are of the shape **call** $kQRec_t(\bar{p} \ominus [1, \dots, k])$. Moreover, $kQRec_t \succ_P$ proc$_F$, proc$_G$, proc$_H$, and $P_F$, $P_G$, $P_H \in \text{wf}$. Consequently, $P \in \text{wf}$. Finally, the procedure $kQRec_t$ is called recursively at most once per branch of a quantum case. Consequently, $\text{width}_P(kQRec_t) \le 1$ and $P$ is a PFOQ program. $\square$

We are now ready to state the completeness result.

**THEOREM 6.** For every function $f$ in FBQP with polynomial bound $Q \in \mathbb{N}[X]$, there is a PFOQ program $P$ such that $[\![P]\!] \circ \phi_Q$ computes $f$ with probability $\frac{2}{3}$.

**PROOF.** Consider a function $f$ in FBQP with polynomial bound $Q$ and an input $|\psi\rangle \in \mathcal{H}$. By Theorem 4 there exists a function $F$ in $\widehat{\Box_1^{QP}}$ such that $F \circ \phi_Q$ computes $f$ with probability $\frac{2}{3}$. By Theorem 5, there exists a program $P_F$ such that $[\![P_F]\!] = F$. Finally, $[\![P_F]\!] \circ \phi_Q$ computes $f$ with probability $\frac{2}{3}$. $\square$

# 5 Compilation to polynomial-size quantum circuits

In this section, we provide an algorithm that compiles a PFOQ program on a given input length $n \in \mathbb{N}$ into a quantum circuit of size polynomial in $n$.

## 5.1 Quantum Circuits

Quantum circuits [Deutsch 1989] are a well-known graphical computational model for describing quantum computations. Qubits are represented by wires. Each unitary transformation $U$ acting on $n$ qubits can be represented as a gate $U$ with $n$ inputs and $n$ outputs. A circuit $C$ is an element of a PROP category ([MacLane 1965], a symmetric strict monoidal category) whose morphisms are generated by gates in $G$ and wires. Let $1$ be the identity circuit (for any length) and $\circ$ and $\otimes$ be the composition and product, respectively. By abuse of notation, given $k$ circuits $C^1, \dots, C^k, \circ^{k}_{i=1} C^i$ will denote the circuit $\tilde{C}^1 \circ \dots \circ \tilde{C}^k$, where each circuit $\tilde{C}^i$ is obtained by tensoring $C^i$ appropriately with identities so that the output of $C^i$ matches the input of $C^{i+1}$. By construction, a circuit is acyclic. Each circuit $C_n$ can be indexed by its number $n \in \mathbb{N}$ of input wires (i.e., non ancilla qubits) and computes a function $[\![C_n]\!] \in \mathcal{H}_{2^n} \to \mathcal{H}_{2^n}$. To deal with functions in $\mathcal{H} \to \mathcal{H}$, we consider families of circuits $(C_n)_{n \in \mathbb{N}}$, that are sequences of circuits such that each $C_n$ encodes computation on quantum states of length $n$. Hence each circuit has $n$ input qubits plus some extra ancilla qubits.
These ancillas can be used to perform intermediate computations but also to represent functions whose output size is strictly greater than their input size. To avoid the consideration of families encoding undecidable properties, we put a uniformity restriction.

**DEFINITION 9.** A family of circuits $(C_n)_{n \in \mathbb{N}}$ is said to be uniform if there exists a polynomial time Turing machine that takes $n$ as input and outputs a representation of $C_n$, for all $n \in \mathbb{N}$.

In quantifying the complexity of a circuit, it is necessary to specify the considered elementary gates, and define the complexity of an operation as the number of elementary gates needed to perform it. In our setting, this will be of the same order as the number of elementary instructions corresponding to a unitary operation $q^* = U^f(i)$. Notice that, as exemplified in Figure 8, the controlled version of a unitary may comprise more than a single elementary gate, and in fact the chosen amplitude may have to be approximated up to some desired value; but these can all be considered to add a constant overhead on the number of instructions. The size #C of a circuit C is equal to the number of its gates and wires.

**DEFINITION 10.** A family of circuits $(C_n)_{n \in \mathbb{N}}$ is said to be polynomial size with $\alpha \in \mathbb{N} \to \mathbb{N}$ ancilla qubits if there exists a polynomial $P \in \mathbb{N}[X]$ such that, for each $n \in \mathbb{N}$, $\#C_n \le P(n)$ and the number of ancilla qubits in $C_n$ is exactly $\alpha(n)$.

Let $\chi_m : \mathcal{H}_{2^n} \to \mathcal{H}_{2^{n+m}}$ be defined by $\chi_m(|\psi\rangle) \triangleq |\psi\rangle \otimes |0^m\rangle$, for a state $|\psi\rangle$ of size $n$. This functions pads the input with ancillas in state $|0\rangle$ to match the circuit dimension. Furthermore, we use $\| |\psi\rangle \|$ to denote the norm of state $|\psi\rangle$. Finally, let $|w\rangle$, for $w \in \{0, 1\}^*$, be the size of the word $w$.

**THEOREM 7 (ADAPTED FROM [YAO 1993] AND [NIELSEN AND CHUANG 2011]).** A function $f : \{0, 1\}^* \to \{0, 1\}^*$ is in FBQP iff there exists a uniform polynomial size family of circuits $(C_n)_{n \in \mathbb{N}}$ with $\alpha$ ancilla qubits s.t. $\forall x \in \{0, 1\}^*$,

$$ \left\| \langle f(x) | \mathcal{C}_{|x|} \rangle \circ \chi_{\alpha(|x|)} (|x\rangle) \right\| \ge \frac{2}{3}. $$

## 5.2 Compilation Algorithm

For each PFOQ program P, the existence of a polynomial size uniform family of circuits $(C_n)_{n \in \mathbb{N}}$ that computes $[P]$ is entailed by the combination of Lemma 2 and Theorem 7. However, compilation of a program into its equivalent circuit via its QTM representation is far from desirable in a practical scenario. In this section, we exhibit an algorithm that compiles any PFOQ program directly into a polynomial size circuit. The remainder of this section will be devoted to presenting an algorithm, named **compile**, which, for a given PFOQ program P and a given integer $n$, produces a circuit $C_n$ such that $\forall |\psi\rangle \in \mathcal{H}_{2^n}, [P](|\psi\rangle) = \xi_n \circ [C_n] \circ \chi_{\alpha(n)}(|\psi\rangle)$, where $\xi_m$ removes the ancilla qubits from the output state by performing the projection $\xi_m(|\psi\rangle) \triangleq \sum_{w \in \{0,1\}^m} \langle w0^{n-m}|\psi\rangle$, where $n = l(|\psi\rangle)$.

The subroutine **compr** (Algorithm 1) generates the circuit inductively on the program statement. It takes as inputs: a program P, a list of qubit pointers $l$, and a control structure `cs`. A control structure `cs` is a partial function in $\mathbb{N} \to \{0, 1\}$, mapping a qubit pointer to a control value (of a quantum case). Let $\cdot$ be the control structure of empty domain. For $n \in \mathbb{N}$ and $k \in \{0, 1\}$, `cs[n := k]` is the control structure obtained from `cs` by setting `cs(n) = k`. Given a partial function $f: A \to B$, let `dom(f)` be the domain of $f$.

For a given $x \in \{0, 1\}^*$, we say that state $|x\rangle$ satisfies `cs` if, $\forall n \in \text{dom}(cs)$, $cs(n) = k \Rightarrow |\langle k|_n|x\rangle|^2 = 1$. Put differently, $|x\rangle$ satisfies `cs` if it for every $n \in \text{dom}(cs)$, qubit $n$ in $|x\rangle$ is in state $cs(n)$. In the context of Figure 8, this can be interpreted as $|x\rangle$ being a basis state where $U$ will be applied since $|x\rangle$ satisfies $U$'s control structure.

Two control structures `cs` and `cs'` are said to be **orthogonal** if there does not exist a state $|x\rangle$ that satisfies `cs` and `cs'`. This occurs when two control structures differ on a value in both their domains.
<caption>**Algorithm 1 (compr)**</caption>

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

**if** $S$ **= skip** **then**
  $C \leftarrow 1$
  ▶ Identity circuit

**else if** $S$ = $s[i] * U^f(j)$; **and** ($s[i], l) \downarrow_{\mathbb{N}} n$ **and** ($U^f(j), l) \downarrow_{\mathbb{C}^{2 \times 2}} M$ **then**
  $C \leftarrow M cs, [n]$
  ▶ Controlled gate

**else if** $S$ = $S_1 S_2$ **then**
  $C \leftarrow compr(D :: S_1, l, cs) \circ compr(D :: S_2, l, cs)$
  ▶ Composition

**else if** $S$ **= if** $b$ **then** $S_{\text{true}}$ **else** $S_{\text{false}}$ **and** ($b, l) \downarrow_{\mathbb{B}} b$ **then**
  $C \leftarrow compr(D :: S_b, l, cs)$
  ▶ Conditional

**else if** $S$ = $\mathbf{qcase}$ $s[i]$ **of** $\{0 \to S_0, 1 \to S_1\}$ **and** ($s[i], l) \downarrow_{\mathbb{N}} n$ **then**
  $C \leftarrow compr(D :: S_0, l, cs[n := 0]) \circ compr(D :: S_1, l, cs[n := 1])$
  ▶ Quantum case

**else if** $S$ = $\mathbf{call}$ $proc[i](s)$; **and** ($s, l) \downarrow_{\mathcal{L}(\mathbb{N})}$ $[]$ **then**
  $C \leftarrow 1$
  ▶ Nil call

**else if** $S$ = $\mathbf{call}$ $proc[i](s)$ **and** ($s, l) \downarrow_{\mathcal{L}(\mathbb{N})}$ $l' \neq$ $[]$ **and** ($i, l) \downarrow_{\mathbb{Z}} n$ **then**
  **if** $\text{width}_P(\text{proc}) = 0$ **then**
    $C \leftarrow compr(D :: S^{\text{proc}}\{n/x\}, l', cs)$
    ▶ Non-recursive call
  **else if** $\text{width}_P(\text{proc}) = 1$ **then**
    $C \leftarrow optimize(D, [(cs, S^{\text{proc}}\{n/x\})], proc, l', \{\})$
    ▶ Recursive call
  **end if**
  **end if**
  **return** $C$

Intuitively, two controlled gates with orthogonal control structures will act on disjoint sets of basis states. An important consequence of this is that the two controlled gates will commute.

Given a control structure `cs` and a statement `S`, a controlled statement is a pair (`cs`, `S`) ∈ `Cst` $\triangleq$ ($\mathbb{N} \to \{0, 1\}$)×Statements. Intuitively, a controlled statement (`cs`, `S`) denotes a statement controlled by the qubits whose indices are in `dom cs`. For a unitary gate `U` ∈ $\mathcal{H}_{2^n} \to \mathcal{H}_{2^n}$, a control structure `cs`, and a list of pointers `l = [x_1, ..., x_n] ∈ L(\mathbb{N})` such that `{x_1, ..., x_n} \cap dom cs = \emptyset`, `U cs, l` denotes the circuit applying gate `U` on qubits `q[x_1], ..., q[x_n]`, whenever $\forall m \in dom cs$, `q[m]` is in state $|cs(m)\rangle$. Given a set `S`, let `card(S)` be the cardinality (i.e., number of elements) of `S`. As demonstrated in [Nielsen and Chuang 2011], this circuit can be built with `O.card dom cs)` elementary gates and ancillas, and a single controlled-U gate.

**EXAMPLE 6.** As an illustrative example, consider a binary gate `U` and a control structure `cs` such that `dom cs` = {1, 2, 3}, `cs(1) = cs(2) = 1`, and `cs(3) = 0`. Also consider a list `l = [4, 5] ∈ L(\mathbb{N})`. The circuit `U cs, l` is provided in Figure 8.

Similarly, we can define a generalized Toffoli gate as a circuit of the shape `NOT cs, n`. Since `card dom cs)` will not scale with the size of the input, such a circuit has a constant cost in gates and ancillas and can thus be considered as an elementary gate. We will also be interested in rear-ranging wires under a given control structure. For two lists of qubit pointers `l_1 = [x_1, ..., x_n]`, `l_2 =
<figure><img src="image_5.png" /><figcaption>Fig. 8. Example of circuit $U cs, l$</figcaption></figure>

$[x'_1, \dots, x'_n] \in \mathcal{L}(\mathbb{N})$, define $SWAP cs, l_1, l_2$ as the circuit that swaps the wires in $l_1$ with wires in $l_2$, controlled on $cs$. This circuit needs in the worst case one ancilla and $O(n)$ controlled $SWAP$ gates (also known as Fredkin gates).

Let $\mathcal{D} \triangleq \text{Dict}(\text{Procedures} \times \mathbb{Z} \times \mathbb{N} \to \mathbb{N} \times \mathcal{L}(\mathbb{N}))$ denote the set of dictionaries mapping keys of the shape $(\text{proc}, i, j)$ to pairs of the shape $(a, l)$, where $i$ is the value of a classical parameter, $j$ is the size of a sorted set, and $a$ is a qubit index. We will denote the empty dictionary by $\emptyset$. Let also $a \leftarrow \textbf{new ancilla}()$ be an instruction that sets $a$ to a fresh qubit index.

The subroutine **optimize** (Algorithm 2) treats the complex cases where circuit optimization (merging) is needed, that is, for recursive procedure calls. It takes as input a sequence of procedure declarations D, a list of controlled statements $l_{\text{Cst}}$, a procedure name proc, a list of qubit pointers $l$, and a dictionary Anc. The subroutine iterates on list $l_{\text{Cst}}$ of controlled statements, indicating the statements left to be treated together with their control qubits. When recursive procedure calls appear in distinct branches of a quantum case, the algorithm merges these calls together. For that purpose, it uses new ancilla qubits as control qubits. Given procedure calls of shape **call** proc[i](s), with respect to a given list $l \in \mathcal{L}(\mathbb{N})$, we evaluate $(i, l) \Downarrow_{\mathbb{Z}} i$, $(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} l'$, and $(|s\rangle, l) \Downarrow_{\mathbb{N}} j$. If the key $(\text{proc}, i, j)$ already exists in the dictionary Anc, the associated ancilla is re-used, otherwise, Anc[proc, i, j] is set to $(a, l')$. We include a few comments in the code which help identify the different compilation cases, where we use the shorthand phrase “S is recursive” to say that statement S contains a recursive procedure call.

We describe the technique of Algorithm 2 as **anchoring and merging**, highlighting the two types of operations performed to reduce the circuit complexity:

(1) **Anchoring**: each function call on a specific input size (and specific integer input) is assigned a controlled ancilla that will carry all its subsequent calls and operations;

(2) **Merging**: whenever a procedure call is repeated (same procedure, same input size, same integer input value), its realization is done simply by routing the control into the correct ancilla.

Some extra ancillas $e$ are also created for swapping wires and are not explicitly indexed since they are not revisited by the subroutine, and are just considered unique. Ancillas $a$ and $e$ are indexed and treated as input qubits, therefore they can be part of the domain of control structures.

The **compile** algorithm employs two subroutines, named **compr** and **optimize**, and is defined as **compile**(P, n) $\triangleq$ **compr**(P, [1, ..., n], ·).

**THEOREM 8.** For each $P \in \text{PFOQ}$, we have that, for all $n \in \mathbb{N}$ and $|\psi\rangle \in \mathcal{H}_{2n}$, the following hold:

1. $[[P]](|\psi\rangle) = \xi_n \circ [[\textbf{compile}(P, n)]] \circ \chi_{\alpha(n)}(|\psi\rangle)$ and

2. $\#\textbf{compile}(P, n) = O(n^{2rk(P)+1})$.
**Algorithm 2 (optimize)** Build circuit for recursive procedure proc
**Inputs:** (D, l<sub>Cst</sub>, proc, l, Anc) ∈ Decl × 𝒰(Cst) × Procedures × 𝒰(ℝ) × 𝒟

C<sub>L</sub> ← 1; C<sub>R</sub> ← 1; P ← D :: **skip**;
**while** l<sub>Cst</sub> ≠ [] **do**
    (cs, S) ← hd(l<sub>Cst</sub>); l<sub>Cst</sub> ← tl(l<sub>Cst</sub>)

**if** S = S<sub>1</sub> S<sub>2</sub> **then**
    ▶ Composition (Figure 10a)

**if** w<sub>P</sub><sup>proc</sup>(S<sub>1</sub>) = 1 **then**
        l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (cs, S<sub>1</sub>); C<sub>R</sub> ← **compr**(D :: S<sub>2</sub>, l, cs) ◦ C<sub>R</sub>

**else**
        l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (cs, S<sub>2</sub>); C<sub>L</sub> ← C<sub>L</sub> ◦ **compr**(D :: S<sub>1</sub>, l, cs)

**end if**

**end if**

**if** S = **if** b **then** S<sub>true</sub> **else** S<sub>false</sub> **and** (b, l) ⇝<sub>ℝ</sub> b **then**
    ▶ Conditional (Figure 10b)

**if** w<sub>P</sub><sup>proc</sup>(S<sub>b</sub>) = 1 **then**
        l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (cs, S<sub>b</sub>)

**else**
        C<sub>L</sub> ← C<sub>L</sub> ◦ **compr**(D :: S<sub>b</sub>, l, cs)

**end if**

**end if**

**if** S = **qcase** s[i] **of** {0 → S<sub>0</sub>, 1 → S<sub>1</sub>} **and** (s[i], l) ⇝<sub>ℝ</sub> n **then**
    ▶ Quantum case (Figure 10c)

**if** w<sub>P</sub><sup>proc</sup>(S<sub>0</sub>) = 1 and w<sub>P</sub><sup>proc</sup>(S<sub>1</sub>) = 1 **then**
        l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (cs[n := 0], S<sub>0</sub>), (cs[n := 1], S<sub>1</sub>)

**else if** w<sub>P</sub><sup>proc</sup>(S<sub>1</sub>) = 0 **then**
        l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (cs[n := 0], S<sub>0</sub>);
        C<sub>R</sub> ← **compr**(D :: S<sub>1</sub>, l, cs[n := 1]) ◦ C<sub>R</sub>

**else if** w<sub>P</sub><sup>proc</sup>(S<sub>0</sub>) = 0 **then**
        l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (cs[n := 1], S<sub>1</sub>);
        C<sub>R</sub> ← **compr**(D :: S<sub>0</sub>, l, cs[n := 0]) ◦ C<sub>R</sub>

**end if**

**end if**

**if** S = **call** proc'[i](s) **and** (s, l) ⇝<sub>ℝ</sub> l' ≠ [] **and** (i, l) ⇝<sub>ℝ</sub> n **then**
    ▶ Merging (Figure 10d)

**if** (proc', n, |l'|) ∈ Anc **then**
        Let (a, l'') = Anc[proc', n, |l'|] **in**
        e ← **new ancilla**();

C<sub>L</sub> ← C<sub>L</sub> ◦ NOT(es, e) ◦ NOT(·[e = 1], a) ◦ SWAP(·[e = 1], l', l'');

C<sub>R</sub> ← SWAP(·[e = 1], l'', l') ◦ NOT(·[e = 1], a) ◦ NOT(es, e) ◦ C<sub>R</sub>

**else**
        a ← **new ancilla**()

Anc[proc', n, |l'|] ← (a, l');

C<sub>L</sub> ← C<sub>L</sub> ◦ NOT(es, a); C<sub>R</sub> ← NOT(es, a) ◦ C<sub>R</sub>;

l<sub>Cst</sub> ← l<sub>Cst</sub>@
        (·[a = 1], S<sup>proc'</sup>{n/i})]

**end if**

**end if**

**end while**

**return** C<sub>L</sub> ◦ C<sub>R</sub>
<figure><img src="image_6.png" /><figcaption>Fig. 9. Example of merging two instances of the unitary $U$.</figcaption></figure>

Item 1 means that **compile** preserves the semantics of its input program, whereas item 2 means that the obtained circuit has a polynomial upper bound on the number of its gates and wires.

PROOF. From Corollary 1 and Theorem 10. □

EXAMPLE 7. **compile**(QFT, n) outputs the circuit provided in Figure 4 corresponding to the FOQ program QFT of Example 1. Notice that there is no extra ancilla as no procedure call appears in the branch of a quantum case.

## 5.3 Polynomial-Size Circuits

We show Theorem 8 by exhibiting that any exponential growth of the circuit can be avoided by the **compile** algorithm using an argument based on orthogonal control structures. With a linear number of gates and a constant number of extra ancillas, we can merge calls referring to the same procedure, on different branches of a quantum case, when they are applied to sorted sets of equal size. An example of the construction is given in Figure 9, where two instances of a gate $U$ are merged into one using SWAP gates and gates controlled by orthogonal control structures.

The following proposition shows that multiple uses of a gate can be merged in one provided they are applied to orthogonal control structures.

LEMMA 4. For any circuit $C_n \triangleq \circ_{i=1}^k UUNDER\{c_{s_i}, l_i\}$, with a unitary gate $U$, pairwise orthogonal $c_{s_1}, \dots, c_{s_k} \in C_{\text{st}}$, and $l_1, \dots, l_k \in \mathcal{L}(\mathbb{N})$, there exists a circuit $C$ using one controlled gate $U$, $O(kn)$ gates, and $O(k)$ ancillas, and such that $[C] = [C_n]$.

PROOF. We describe the circuit that achieves the result and then prove its correctness. Let $a_i$, for $i \in \{1, \dots, k\}$, be ancillas in the zero state. Define $C \triangleq C^1 \circ G(\cdot[a_k = 1], l_k) \circ C^2$ with

$$C^1 \triangleq \circ_{i=1}^k \mathrm{NOT}(c_{s_i}, a_i) \circ (\circ_{i=1}^{k-1} \mathrm{NOT}(\cdot[a_i = 1], a_k)) \circ (\circ_{i=1}^{k-1} \mathrm{SWAP}(\cdot[a_i = 1], l_i, l_k))$$

and $C^2$ defined from $C^1$ by reversing the order of the gates. The total number of ancillas is $k$. Circuits $C^1$ and $C^2$ contain a constant number of controlled NOT gates and, in the worst case, $O(kn)$ controlled SWAP gates (depending on the overlap between $l_k$ and each $l_i$).

Consider a computational basis state $|x\rangle$, for $x \in \{0, 1\}^n$. Since all control structures $c_{s_i}$ are pairwise orthogonal, after the two compositions of NOT circuits in $C^1$, $|x\rangle$ satisfies $\cdot[a_i := 1]$ iff it satisfies $c_{s_i}$, for $i \in \{1, \dots, k-1\}$. Moreover, $|x\rangle$ satisfies $\cdot[a_k := 1]$ iff there exists $i$ such that it satisfies $c_{s_i}$. Therefore, each SWAP sends wires in $l_i$ into $l_k$ iff $|x\rangle$ satisfies $c_{s_i}$ and then $U$ is applied on $l_k$ if it satisfies one of the control structure $c_{s_i}$. As circuit $C^2$ reverses the actions of $C^1$, afterwards, the qubits are in the right positions, all ancillas are set to zero, and the result on non-ancillary qubits is the same as in $C_n$. □

The properties of **compile** shown thus far will allow us to argue the validity of the resulting circuit, by showing an invariant property of the list of controlled statements $l_{C_{\text{st}}}$. At each step of
**optimize**, we are handling one of the controlled statements in $l_{Cst}$, say (cs, S), such that we obtain a new list $l'_{Cst}$ in the following way:

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

where $C_L$ and $C_R$ on the left and right, respectively, represent circuits not containing recursive calls. We let empty gates (either white or shaded) denote arbitrary parts of the circuit that can appear in the context of a rule. We use the vertical dashed lines to represent to separate the controlled statements in $l_{Cst}$ from the rest of the circuit. The fact that $l'_{Cst}$ will still only contain mutually orthogonal controlled statements will allow us to continually unpack each element (cs, S) in a way that preserves circuit semantics.

The case for each possible statement S for a controlled statement (cs, S) where S contains a recursive call, is given in Figure 10. To simplify notation, we represent using $\boxed{a}$ the addition of a fresh ancilla in state $|0\rangle$ with label a to the circuit. In Figure 10e (and and Figure 11), gates noted $\leftrightarrow$ represent the swapping of wires (see Figure 9).

We now show that orthogonality is an invariant property of **optimize**.

**LEMMA 5.** *Orthogonality is an invariant property of the control structures in $l_{Cst}$ of the subroutine **optimize**. In other words, for any two distinct pairs (cs, S), (cs', S') in $l_{Cst}$, cs and cs' are orthogonal.*

**PROOF.** The proof is done by induction on a procedure statement, doing a case analysis on the rules of **optimize**. The initial value of $l_{Cst}$ is of the form $[(cs, S^{proc})]$, which trivially satisfies the condition. Consider the possible cases for a pair (cs, S) in $l_{Cst}$. By induction hypothesis, assume that cs is orthogonal to all other control structures. For Composition, quantum case and classical **if**, the replacing pair is either of the shape (cs, S'), or it is two pairs with $cs[n := 0]$ and $cs[n := 1]$, therefore we conclude that the resulting $l_{Cst}$ has pairwise orthogonal controls.

For a procedure call, we consider two cases. The first case occurs when a control statement $(\cdot [a := 1], S^{proc})$ is added to the list $l_{Cst}$ and a is an ancilla controlled by cs. Since the original pair is removed, this construction also satisfies the invariant property. In the second case, there already exists an ancilla a assigned to the triple (proc, i, j). Let us argue by induction on the number of previous procedure call instances for this ancilla. Let $cs_1, \dots, cs_k$ be control structures such that a computational basis state $|x\rangle$ satisfies $\cdot [a := 1]$ iff it satisfies one of the $cs_i$, which we assume by induction hypothesis are pairwise orthogonal. By the definition of PFOQ, cs will be orthogonal to each of the $cs_i$, and so after gate NOT ($cs$, a), a state $|x\rangle$ will satisfy $\cdot [a := 1]$ iff it satisfies any of $cs, cs_1, \dots, cs_k$. Since cs was orthogonal to all other control structures appearing in $l_{Cst}$, and the original pair is removed, the result $l_{Cst}$ will have pairwise orthogonal controls. $\square$

**THEOREM 9.** *For any program P in PFOQ, compile(P, n) runs in time $O(n^{2rk(P)+1})$.*

**PROOF.** We first show that an execution of the **optimize** subroutine performs $O(n^2)$ calls to **compr**. We use a simple counting argument. The dictionary Anc ensures that ancillas related to the same (proc', i, j) $\in$ Procedures $\times$ $\mathbb{Z}$ $\times$ $\{1, \dots, n\}$ will only be created once. The classical parameter can either be updated to a new constant or by adding (or subtracting) a constant and this can be done $O(n)$ times as procedure calls also remove at least an element from the sorted set parameter. So the range of values for i is $O(n)$, therefore the space of possible values has size $O(n^2)$. Hence $O(n^2)$ ancillas can be created, which also bounds the number of calls to **compr**.
<figure><img src="image_8.png" /></figure>

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

<figure><img src="image_10.png" /><figcaption>Fig. 10. A step of the **optimize** subroutine.</figcaption></figure>

Second, consider an execution of **compr**. Subroutine **compr** calls itself directly only outside of recursive procedure calls, meaning that these cases consist of constant time circuit constructions. On the case of a call to a recursive procedure, it does a single call to **optimize** which creates $O(n^2)$ calls back to **compr**. Each of these instances of **compr** either does a non-recursive circuit construction of constant size, or does a call to **optimize** for a procedure of strictly lower rank, as defined in the proof of Lemma 2. Since there are $O(n^2)$ such calls, the maximum total number of procedure calls is $O(n^{2rk(P)})$, where $rk(P)$ is the rank of P (Definition 5). Each of these recursive procedure calls can have a constant number of merge constructions with linear complexity, therefore the total number of gates is $O(n^{2rk(P)+1})$. $\square$

The final size of the generated circuit is bounded by the number of steps of the **compile** algorithm, as each step adds at most a constant number of gates and ancillas.

**COROLLARY 1.** For any program P in PFOQ, if $C_n \triangleq \text{compile}(P, n)$ we have that $\#C_n = O(n^{2rk(P)+1})$.

We now show that the **compile** algorithm is semantics-preserving.

**THEOREM 10.** The circuit obtained in **compile**(P, n) implements the PFOQ program P applied to an input of size n.
<figure><img src="image_11.png" /></figure>

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

<figure><img src="image_13.png" /><figcaption>Fig. 11. Circuit representation illustrating the correctness of merging.</figcaption></figure>

We assume two identical procedure statements, $S^{proc'}$, for same input size and same integer input value, where one instance has already been anchored on ancilla $a$. From the orthogonality property in Lemma 5, the elements in $l_{Cst}$ commute and we may make the two repeated procedure calls adjacent.

We merge the two instances as in Lemma 4. Since $\cdot[a = 1]$ and $cs$ are orthogonal by hypothesis, we may add $cs$ to the ancilla $a$. A new ancilla $e$ is created to control the set of swap gates, represented as $\leftrightarrow$.

By orthogonality, merging is adjacent to $S^{proc'}$ and does not contain any recursive calls, and we thus obtain a new list of recursive controlled statements, $l'_{Cst}$.

**PROOF.** This can be shown by checking that each step of **compile** and **optimize** preserves the semantics of the program. This is easy to check in **compile**, so we will focus on the steps performed in **optimize**.

The **optimize** subroutine consists of simplification steps performed on the list of controlled statements, until the list is empty and the subroutine terminates. We can therefore simply show that each simplification preserves the semantics of the treated statement. This can be done by inspecting the rules in Figure 10 and checking their correctness.

For instance, in case 10a, we obtain the circuit by replacing $(cs, S)$ by $(cs, S_1) \circ (cs, S_2) \circ (cs, S_3)$, where $S_2$ is recursive. Since $cs$ is orthogonal to all other control structures in $l_{Cst}$, we have that $(cs, S_1)$ and $(cs, S_3)$ commute with all these controlled statements (but not each other) and can be moved to the left and right, respectively, into the non-recursive parts of the circuit. The cases of quantum (10c) and boolean (10b) control are trivial.

In the case where the procedure call is repeated (same procedure, same input length, and same classical input value), we obtain the circuit in Figure 10d. The validity of merging is based on the reasoning in Figure 11.

For a procedure call $S = \mathbf{call} \ proc'[i](s)$, where it is the first instance of $proc'$ for a given input size and classical input (Figure 10e), we may replace $(cs, S)$ with $(cs, S^{proc'})$ applied on the appropriate qubits. To obtain the final circuit, we simply direct the control structure $cs$ into a fresh ancilla and proceed inductively on the procedure body. $\square$
```c
    decl compex(p) {
        if |p| > 2 then
            qcase p[1] of
                { 0 → call compex(p ⊖ [1]);
                  1 → qcase p[2] of
                    { 0 → skip;
                      1 → call compex(p ⊖ [1, 2]); }
                }
            else p[1] *= U; } ::
        call compex(q);
```

<figure><img src="image_14.png" /><figcaption>Fig. 13. One step of **optimize** on the controlled statement (cs, S<sup>compex</sup>).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 14. One step of **optimize** on the controlled statement (cs, call compex[i](s)).</figcaption></figure>

## 5.4 Compilation Example

We will now consider the example of the PFOQ program provided in Figure 12 and show how the **compile** algorithm works to generate a polynomial-size circuit that simulates it for a given input size. This program has a single procedure compex with two recursive calls on inputs of different sizes and makes use of the arbitrary operator U.

In our compilation example, we will consider the simple case where the input size is large enough so that we remain in the recursive case. Therefore, each of compilation will be one step of the **optimize** subroutine (Algorithm 2). Our compilation will consist of three operations: implementing the recursive call of compex, anchoring, and merging. The circuit simulating the procedure body S<sup>compex</sup> and the circuit simulating a call “call compex” will be denoted:
<figure><img src="image_16.png" /></figure>

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

By the definition of compex, its procedure body consists of two recursive calls on two distinct branches, which we expand directly, as in Figure 13, where `cs` represents a given control structure, and the vertical dashed line represents the separation of recursive and non-recursive statements (as in Figure 10).

Notice that while we have at most one recursive call per branch, in Figure 13 the branches must appear in sequence and so the complexity is given by the sum over the branches. This is the problem identified in [Yuan and Carbin 2022] as *branch sequentialization*, which arises in problems that involve branching over quantum data: “Branch sequentialization denotes the fact that the time complexity of a conditionally branching quantum program may be larger than its classical equivalent and the developer may need to structure the program differently to avoid this slowdown.”

In [Yuan and Carbin 2022], the authors address this problem in the context of a binary tree traversal by restructuring their program to create an ancilla which controls the branching case. We will see in this example that the restrictions of PFOQ are strong enough that we can solve this problem at the compiler level, even with the added difficulty that the quantum branching occurs with procedure calls on different input sizes.

In Figure 14, we identify the two cases that arise in simplifying procedure calls: in anchoring, we direct the control structure `cs` to a fresh ancilla $a_k$, which we then use to control the procedure statement. This ancilla is indexed by $k$ as it depends on the number $k$ of qubits on which the procedure is called; in merging, since the ancilla has already been created, we simply redirect `cs`, which makes it so that we only need to expand one procedure for each size (notice that in this case the merging does not require any controlled swapping).

To graphically represent the creation of ancillas during the circuit compilation, we use an *ancilla diagram*, where each node $a_k$ represents the ancilla anchoring the body of procedure compex on input size $k$. Edges in the diagram denote Toffoli gates connecting ancillas – in this case, each node $a_k$ will have two outgoing edges, ◦ and ●●, directed to nodes $a_{k-1}$ and $a_{k-2}$, respectively. When the node represents a procedure call that has not yet been treated, it is denoted by an asterisk. The ancilla diagram serves mainly to aid the reader in visualizing the state of each ancilla, and the number of such ancillas that are created during the compilation.

Figures 15 and 16 illustrate the first steps of the compilation process, for an input $\bar{q}$ of size $n$. The dashed line separates the non-recursive (left) and recursive (right) parts of the circuit, with the right part corresponding to the list of controlled recursive statements $l_{Cst}$ changed in each step. One can verify that the semantics is conserved with each operation (anchoring, merging, and application of the procedure definition). During the compilation we have considered that $n$ is large enough that we were always in the recursive case. Since compex does not use an integer input, procedure calls will only differ on input size, and since the merging cost is $O(1)$ (wire swapping is not required) we obtain a circuit that grows linearly on the input size $n$.

# 6 Conclusion

Sound implementations of quantum programs require programming languages that allow for reasoning about desirable properties, one of which being their compilation into efficient quantum circuit families. In this work, we presented `FOQ`, a quantum programming language with a fragment `PFOQ` which represents the first programming-language-based characterization of quantum polynomial time transformations. We showed the expressivity of `PFOQ` with quite a few examples of efficient quantum programs, and we demonstrated that all `PFOQ` programs can be efficiently compiled into quantum circuits of polynomial size. In the latter objective, we addressed the problem of branch sequentialization using an anchoring-and-merging technique when building the circuit.
<table><caption>Fig. 15. Circuit construction (part 1/2).</caption><thead><tr><th></th><th>Circuit</th><th>Ancilla diagram</th><th>Next action</th></tr></thead><tbody><tr><td>(1.)</td><td>q[1]<br>q[2]<br>q &otimes; [1, 2]</td><td>...</td><td>anchoring</td></tr><tr><td>(2.)</td><td>q[1]<br>(a<sub>n-1</sub>)<br>q[2]<br>q &otimes; [1, 2]</td><td>a<sub>n-1</sub></td><td>anchoring</td></tr><tr><td>(3.)</td><td>q[1]<br>a<sub>n-1</sub><br>(a<sub>n-2</sub>)<br>q[2]<br>q &otimes; [1, 2]</td><td>...</td><td>compex definition</td></tr><tr><td>(4.)</td><td>q[1]<br>q[2]<br>q[3]<br>q &otimes; [1-3]</td><td>a<sub>n-1</sub></td><td>merging</td></tr><tr><td>(5.)</td><td>q[1]<br>q[2]<br>q[3]<br>q &otimes; [1-3]</td><td>...</td><td>compex definition</td></tr><tr><td>(6.)</td><td>q[1]<br>q[2]<br>q[3]<br>q[4]<br>q &otimes; [1-4]</td><td>...</td><td>anchoring</td></tr></tbody></table>
<table><caption>Fig. 16. Circuit construction (part 2/2).</caption><thead><tr><th></th><th>Circuit</th><th>Ancilla diagram</th><th>Next action</th></tr></thead><tbody><tr><td>(7.)</td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q &otimes; [1 &ndash; 4]</div></td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q &otimes; [1 &ndash; 4]</div><div><div>a<sub>n-1</sub></div><div>a<sub>n-2</sub></div><div>a<sub>n-3</sub></div><div>a<sub>n-4</sub></div></div></td><td>merging</td></tr><tr><td>(8.)</td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q &otimes; [1 &ndash; 4]</div></td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q &otimes; [1 &ndash; 4]</div><div><div>a<sub>n-1</sub></div><div>a<sub>n-2</sub></div><div>a<sub>n-3</sub></div><div>a<sub>n-4</sub></div></div></td><td>compex definition</td></tr><tr><td>(9.)</td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q[5]</div><div>q &otimes; [1 &ndash; 5]</div></td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q[5]</div><div>q &otimes; [1 &ndash; 5]</div><div><div>a<sub>n-1</sub></div><div>a<sub>n-2</sub></div><div>a<sub>n-3</sub></div><div>a<sub>n-4</sub></div></div></td><td>anchoring</td></tr><tr><td>(10.)</td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q[5]</div><div>q &otimes; [1 &ndash; 5]</div></td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q[5]</div><div>q &otimes; [1 &ndash; 5]</div><div><div>a<sub>n-1</sub></div><div>a<sub>n-2</sub></div><div>a<sub>n-3</sub></div><div>a<sub>n-4</sub></div></div></td><td><div>q[1]</div><div>q[2]</div><div>q[3]</div><div>q[4]</div><div>q[5]</div><div>q &otimes; [1 &ndash; 5]</div><div><div>a<sub>n-1</sub></div><div>a<sub>n-2</sub></div><div>a<sub>n-3</sub></div><div>a<sub>n-4</sub></div></div></td><td></td></tr></tbody></table>
We believe the simplicity of FOQ syntax lends itself well to the development of interesting quantum compilation strategies related to specific complexity classes. More recently, a variant of FOQ including divide-and-conquer techniques has been shown to be sound and complete for quantum poly-logarithmic time [Ferrari et al. 2025]. Furthermore, a fragment of PFOQ that is still complete for quantum polynomial time has been shown to avoid the problem of branch sequentialization altogether [Hainry et al. 2025].

Open problems in resource estimation of quantum programming languages remain, such as the investigation of techniques related to *spatial parallelization* in quantum circuits. While the characterization of quantum poly-logarithmic time in [Ferrari et al. 2025] admits a compilation strategy into uniform quantum circuits of polynomial size and poly-logarithmic depth, the complete class of such circuits, named QNC [Moore and Nilsson 2001], has not yet been implicitly characterized. This contrasts with the fact that its classical counterpart, NC, admits quite a few implicit characterizations, e.g. [Bonfante et al. 2006; Leivant 1998; Marion and Péchoux 2008].

## Acknowledgments

This work is supported by the Plan France 2030 through the PEPR integrated project EPiQ ANR-22- PETQ-0007, the HQI platform ANR-22-PNCQ-0002 and by the European projects NEASQC and HPCQS. The authors would like to thank Alexandre Guernut for his help on the compiler implementation and the anonymous reviewers for their constructive and useful comments.

## References

* Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang. 1997. Quantum computability. *SIAM J. Comput.* 26, 5 (1997), 1524–1540. doi:10.1137/S0097539795293639

* Martin Avanzini, Georg Moser, Romain Péchoux, and Simon Perdrix. 2024. On the hardness of analyzing quantum programs quantitatively. In *Programming Languages and Systems*, Stephanie Weirich (Ed.). Springer Nature Switzerland, Cham, 31–58. doi:10.1007/978-3-031-57267-8_2

* Martin Avanzini, Georg Moser, Romain Péchoux, Simon Perdrix, and Vladimir Zamdzhiev. 2022. Quantum expectation transformers for cost analysis. In *Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '22)*. ACM, 1–13. doi:10.1145/3531130.3533332

* Stephen Bellantoni and Stephen Cook. 1992. A new recursion-theoretic characterization of the polytime functions. *computational complexity* 2, 2 (01 Jun 1992), 97–110. doi:10.1007/BF01201998

* Charles H. Bennett. 1973. Logical reversibility of computation. *IBM Journal of Research and Development* 17, 6 (1973), 525–532. doi:10.1147/rd.176.0525

* Charles H. Bennett and Gilles Brassard. 2014. Quantum cryptography: public key distribution and coin tossing. *Theoretical Computer Science* 560 (dec 2014), 7–11. doi:10.1016/j.tcs.2014.05.025

* Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters. 1993. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. *Phys. Rev. Lett.* 70 (Mar 1993), 1895–1899. Issue 13. doi:10.1103/PhysRevLett.70.1895

* Ethan Bernstein and Umesh Vazirani. 1997. Quantum complexity theory. *SIAM J. Comput.* 26, 5 (1997), 1411–1473. doi:10.1137/S0097539796300921

* G. Bonfante, R. Kahle, J. Y. Marion, and I. Oitavem. 2006. Towards an implicit characterization of $NC^k$. In *Computer Science Logic, Zoltán Ésik (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 212–224*. doi:10.1007/11874683_14

* P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan. 1999. On universal and fault-tolerant quantum computing. doi:10.48550/ARXIV.QUANT-PH/9906054

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

* Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. 2003. Exponential algorithmic speedup by a quantum walk. In *Proceedings of the thirty-fifth annual ACM symposium on Theory of computing*. ACM. doi:10.1145/780542.780552

* Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. 2018. Toward the first quantum simulation with quantum speedup. *Proceedings of the National Academy of Sciences* 115, 38 (sep 2018), 9456–9461. doi:10.1073/pnas.1801723115
Andrea Colledan and Ugo Dal Lago. 2024. Circuit width estimation via effect typing and linear dependency. In *Programming Languages and Systems*, Stephanie Weirich (Ed.). Springer Nature Switzerland, Cham, 3–30. doi:10.1007/978-3-031-57267-8_1

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

Ugo Dal Lago. 2011. A short introduction to implicit computational complexity. In *ESSLLI 2010*. 89–109. doi:10.1007/978-3-642-31485-8_3

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

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

David E. Deutsch. 1989. Quantum computational networks. *Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences* 425, 1868 (1989), 73–90. doi:10.1098/rspa.1989.0099

Artur K. Ekerst. 1991. Quantum cryptography based on Bell's theorem. *Phys. Rev. Lett.* 67 (Aug 1991), 661–663. Issue 6. doi:10.1103/PhysRevLett.67.661

Florent Ferrari, Emmanuel Hainry, Romain Péchoux, and Mário Silva. 2025. Quantum programming in polylogarithmic time. (July 2025). https://hal.science/hal-05171674 working paper or preprint.

Richard P. Feynman. 1982. Simulating physics with computers. *International Journal of Theoretical Physics* 21, 6 (01 Jun 1982), 467–488. doi:10.1007/BF02650179

Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In *Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing* (Philadelphia, Pennsylvania, USA) (STOC '96). Association for Computing Machinery, New York, NY, USA, 212–219. doi:10.1145/237814.237866

Emmanuel Hainry, Romain Péchoux, and Mário Silva. 2023. A programming language characterizing quantum polynomial time. In *Foundations of Software Science and Computation Structures*, Orna Kupferman and Pawel Sobocinski (Eds.). Springer Nature Switzerland, Cham, 156–175. doi:10.1007/978-3-031-30829-1_8

Emmanuel Hainry, Romain Péchoux, and Mário Silva. 2025. Branch sequentialization in quantum polytime. In *10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)* (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 337), Maribel Fernández (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 22:1–22:22. doi:10.4230/LIPIcs.FSCD.2025.22

Thomas Häner, Torsten Hoefler, and Matthias Troyer. 2020. Assertion-based optimization of quantum programs. *Proceedings of the ACM on Programming Languages* 4, OOPSLA (Nov. 2020), 1–20. doi:10.1145/3428201

Ker-I. Ko and Harvey Friedman. 1982. Computational complexity of real functions. *Theoretical Computer Science* 20, 3 (1982), 323–352. doi:10.1016/S0304-3975(82)80003-0

D. Leivant. 1998. A characterization of $\mathbb{N}^k$ by tree recurrence. In *Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)*. 716–724. doi:10.1109/SFCS.1998.743522

Saunders MacLane. 1965. Categorical algebra. *Bull. Amer. Math. Soc.* 71, 1 (1965), 40–106. doi:10.1090/S0002-9904-1965-11234-4

Jean-Yves Marion and Romain Péchoux. 2008. A characterization of $\mathbb{N}^k$ by first order functional programs. In *Theory and Applications of Models of Computation*, Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 136–147. doi:10.1007/978-3-540-79228-4_12

Giulia Meuli, Mathias Soeken, Martin Roetteler, and Thomas Häner. 2020. Enabling accuracy-aware quantum compilers using symbolic resource estimation. *Proceedings of the ACM on Programming Languages* 4, OOPSLA (Nov. 2020), 1–26. doi:10.1145/3428198

Cristopher Moore and Martin Nilsson. 2001. Parallel quantum computation and quantum codes. *SIAM J. Comput.* 31, 3 (2001), 799–815. doi:10.1137/S0097539799355053

Michael A. Nielsen and Isaac L. Chuang. 2011. *Quantum computation and quantum information: 10th anniversary edition*. Cambridge University Press. doi:10.1017/CBO9780511976667

Masanao Ozawa and Harumichi Nishimura. 2000. Local transition functions of quantum Turing machines. *RAIRO-Theoretical Informatics and Applications* 34, 5 (2000), 379–402. doi:10.1051/ita:2000123

Romain Péchoux. 2020. Implicit computational complexity: past and future. *Mémoire d'Habilitation à Diriger des Recherches*. https://tel.archives-ouvertes.fr/tel-02978986 Université de Lorraine.

Neil J. Ross. 2015. Algebraic and logical methods in quantum computation. PhD thesis. doi:10.48550/ARXIV.1510.02198

Peter Selinger. 2004. Towards a quantum programming language. *Mathematical Structures in Computer Science* 14, 4 (2004), 527–586. doi:10.1017/S0960129504004256

Peter W. Shor. 1994. Algorithms for quantum computation: discrete logarithms and factoring. In *Proceedings 35th Annual Symposium on Foundations of Computer Science*. 124–134. doi:10.1109/SFCS.1994.365700
John van de Wetering, Richie Yeung, Tuomas Laakkonen, and Aleks Kissinger. 2025. Optimal compilation of parametrised quantum circuits. arXiv:2401.12877

Tomoyuki Yamakami. 1999. A foundation of programming a multi-tape quantum Turing machine. In *International Symposium on Mathematical Foundations of Computer Science*. Springer, 430–441. doi:10.1007/3-540-48340-3_39

Tomoyuki Yamakami. 2020. A schematic definition of quantum polynomial time computability. *J. Symb. Log.* 85, 4 (2020), 1546–1587. doi:10.1017/jsl.2020.45

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

Charles Yuan and Michael Carbin. 2022. Tower: data structures in quantum superposition. *Proceedings of the ACM on Programming Languages* 6, OOPSLA2 (Oct 2022), 259–288. doi:10.1145/3563297