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

HAL
open science

# A programming language characterizing quantum polynomial time

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

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

## To cite this version:

Emmanuel Hainry, Romain Péchoux, Mário Silva. A programming language characterizing quantum polynomial time. 2022. [hal-03895081](https://hal.inria.fr/hal-03895081)

HAL Id: hal-03895081

https://inria.hal.science/hal-03895081

Preprint submitted on 12 Dec 2022

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.
# A programming language characterizing quantum polynomial time

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

► To cite this version:

Emmanuel Hainry, Romain Péchoux, Mário Silva. A programming language characterizing quantum polynomial time. FOSSACS 2023 - 26th International Conference on Foundations of Software Science and Computational Structures, Orna Kupferman; Pawel Sobocinski, Apr 2023, Paris, France. pp.156-175, 10.1007/978-3-031-30829-1_8. hal-03895081v3

HAL Id: hal-03895081

https://inria.hal.science/hal-03895081v3

Submitted on 18 Oct 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 programming language characterizing quantum polynomial time

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

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

**Abstract.** We introduce a first-order quantum programming language, named FOQ, whose terminating programs are reversible. We restrict FOQ to a strict and tractable subset, named PFOQ, of terminating programs with bounded width, that provides a first programming language-based characterization of the quantum complexity class FBQP. Finally, we present a tractable semantics-preserving algorithm compiling a PFOQ program to a quantum circuit of size polynomial in the number of input qubits.

# 1 Introduction

*Motivations.* Quantum computing is an emerging and promising computational model that has been in the scientific limelight for several decades. This phenomenon is mainly based on the advantage of quantum computers over their classical competitors, based on the use of purely quantum properties such as superposition and entanglement. The most notable example being Shor's algorithm for finding the prime factors of an integer [16], which is almost exponentially faster than the most efficient known classical factoring algorithm and which is expected to have spin-offs in cryptography (RSA encryption, ...).

Whether due to the fragility of quantum systems, namely the engineering problem of maintaining a large number of qubits in a coherent state, or by lack of reliable technological alternatives, quantum computing is typically described at a level close to hardware. One can think non exhaustively, to quantum circuits [9,12], to measurement-based quantum computers [5,7] or to circuit description languages [14]. This low-level machinery restricts drastically the abstraction and programming ease offered by these models and quantum programs currently suffer from the comparison with their classical competitors, which have many high-level tools and formalisms based on more than 50 years of scientific research, engineering development, and practical and industrial applications.

In order to solve these issues, a major effort is made to realize the promise of a quantum computer, which requires the development of different layers of hardware and software, together referred to as the *quantum stack*. Our paper is part of this line of research. We focus on the highest layers of the quantum stack: quantum programming languages and quantum algorithms. We seek to better understand what can be done efficiently on a quantum computer and we are particularly interested in the development of quantum programming languages where program complexity can be certified automatically by some static analysis technique.
# A programming language characterizing quantum polynomial time

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

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
[hainry,pechoux,mmachado]@loria.fr

**Abstract.** We introduce a first-order quantum programming language, named FOQ, whose terminating programs are reversible. We restrict FOQ to a strict and tractable subset, named PFOQ, of terminating programs with bounded width, that provides a first programming language-based characterization of the quantum complexity class FBQP. We finally present a tractable semantics-preserving algorithm compiling a PFOQ program to a quantum circuit of size polynomial in the number of input qubits.

## 1 Introduction

*Motivations.* Quantum computing is an emerging and promising computational model that has been in the scientific limelight for several decades. This phenomenon is mainly due to the advantage of quantum computers over their classical competitors, based on the use of purely quantum properties such as superposition and entanglement. The most notable example being Shor's algorithm for finding the prime factors of an integer [15], which is exponentially faster than the most efficient known classical factoring algorithm and which is expected to have implications in cryptography (RSA encryption, etc.).

Whether due to the fragility of quantum systems, namely the engineering problem of maintaining a large number of qubits in a coherent state, or by lack of reliable technological alternatives, quantum computing is typically described at a level close to hardware. Without any hope of being exhaustive, one can think to quantum circuits [9,11], to measurement-based quantum computers [4,7] or to circuit description languages [13]. This low-level machinery restricts drastically the abstraction and programming ease offered by these models and quantum programs currently suffer from the comparison with their classical competitors, which have many high-level tools and formalisms based on more than 50 years of scientific research, engineering development, and practical and industrial applications.

In order to solve these issues, a major effort is made to realize the promise of a quantum computer, which requires the development of different layers of hardware and software, together referred to as the *quantum stack*. Our paper is part of this line of research. We focus on the highest layers of the quantum stack: quantum programming languages and quantum algorithms. We seek to better understand what can be done efficiently on a quantum computer and we are
*Contribution.* Towards this end, we take the notion of polynomial time computation as our main object of study. Our contributions are the following.

- We introduce a quantum programming language, named FOQ, that includes first-order recursive procedures. The input of a FOQ program consist in a sorted set of qubits, a list of pairwise distinct qubit indexes. A FOQ program can apply to each of its qubits basic operators corresponding to unary unitary operators. The considered set of operators has been chosen in accordance with [17] to form a universal set of 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 a 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. FBQP is the functional extension of bounded-error quantum polynomial time, known as BQP [3], 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 the language 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 [3]. The completeness of our characterization (Theorem 6) is demonstrated by showing that PFOQ programs strictly encompass Yamakami's function algebra, known to be FBQP-complete [17].

- We also describe an algorithm, named compile (based on the subroutines described in Algorithms 1 and 2), that compiles any PFOQ program to a quantum circuit acting on $n$ qubits and of size polynomial in $n$, for all $n$. The existence of such circuits is not surprising, as a direct consequence of Yao's characterization of the class BQP in terms of uniform families of circuits of polynomial size [18]. However, a constructive generation based on Yao's algorithm is not satisfactory because of the use of quantum Turing machines which makes the circuits complex and not optimal (in size). We show that, in our setting, circuits can be effectively computed and that the compile algorithm is tractable (Theorem 7).

Our programming language FOQ and the restriction to PFOQ are illustrated throughout the paper, using the Quantum Fourier Transform QFT as a leading algorithm (Example 1).

*Related work.* This paper belongs to a long standing line of works trying to specify, understand, and analyze the semantics of quantum programming languages, starting with the cornerstone work of Selinger [15]. The motivations in restricting the considered programs to PFOQ were inspired by the works on *implicit computational complexity*, that seek to characterize complexity classes
particularly interested in the development of quantum programming languages where program complexity can be certified automatically by some static analysis technique.

*Contribution.* Towards this end, we take the notion of polynomial time computation as our main object of study. Our contributions are the following.

- We introduce a quantum programming language, named FOQ, that includes first-order recursive procedures. The input of a FOQ program consist in a sorted set of qubits, a list of pairwise distinct qubit indexes. A FOQ program can apply to each of its qubits basic operators corresponding to unary unitary operators. The considered set of operators has been chosen in accordance with [16] to form a universal set of 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 a 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. FBQP is the functional extension of *bounded-error quantum polynomial time*, known as BQP [2], 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 the language 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 [2]. The completeness of our characterization (Theorem 6) is demonstrated by showing that PFOQ programs strictly encompass Yamakami's function algebra, known to be FBQP-complete [16].

- We also describe a polynomial-time deterministic algorithm **compile** (based on the subroutines described in Algorithms 1 and 2), that takes in a PFOQ program P and an integer $n$ and outputs a quantum circuit of size polynomial in $n$ that simulates P on an input size of $n$ qubits. The existence of such circuits is not surprising, as a direct consequence of Yao's characterization of the class BQP in terms of uniform families of circuits of polynomial size [17]. However, a constructive generation based on Yao's algorithm is not satisfactory because of the use of quantum Turing machines which makes the circuits complex and not optimal (in size). We show that, in our setting, circuits can be effectively computed and that the **compile** algorithm is tractable (Theorem 9).

Our programming language FOQ and the restriction to PFOQ are illustrated throughout the paper, using the Quantum Fourier Transform QFT as a leading algorithm (Example 1).
by putting restrictions (type systems or others) on standard programming lan-
guages and paradigms [1,10,13]. These restrictions have to be implicit (i.e., not
provided by the programmer) and tractable. Among all these works, we are aware
of two results [17] and [6] studying polynomial time computations on quantum
programming languages, works from which our paper was greatly inspired. [6]
provides a characterization of BQP based on a quantum lambda-calculus. Our
work is an extension to FBQP with a restriction to first-order procedures. Last
but not least, [6] is based on Yao's simulation of quantum Turing machines [18]
while we provide an explicit algorithm for generating circuits of polynomial size.
Our work is also inspired by the function algebra of [17], that characterizes FBQP:
our completeness proof shows that any function in [17] can be simulated by a
PFOQ program (Theorem 6). However, we claim that FOQ is a more general lan-
guage for FBQP in so far that it is much less constraining (in terms of expressive
power) than the function algebra of [17]: any function of [17] can be, by design,
transformed into a PFOQ program, whereas the converse is not true.

## 2 First-order quantum programming language

*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, 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. Its syntax is provided in Figure 1.

Let $x$ denote an integer variable and $\bar{p}, \bar{q}$ denote sorted sets variables. The size of the sorted set stored in $\bar{q}$ will be denoted by $|\bar{q}|$. We can refer to the $i$-th qubit in $\bar{q}$ as $\bar{q}[i]$, with $1 \le i \le |\bar{q}|$. Hence, each non-empty sorted set variable $\bar{q}$ can be viewed as a list $[\bar{q}[1], \dots, \bar{q}[|\bar{q}|]]$. The empty sorted set, of size 0, will be denoted by nil and $\bar{q} \ominus [i]$ will denote the sorted set obtained by removing the qubit of index $i$ in $\bar{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 $\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$.

A FOQ program $P(\bar{q})$ consists of a sequence of *procedure declarations* D followed by a *program statement S*, $\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](p){S} takes a sorted set parameter p and some optional integer parameter x as inputs. S is called the *procedure*
*Related work.* This paper belongs to a long standing line of works trying to specify, understand, and analyze the semantics of quantum programming languages, starting with the cornerstone work of Selinger [14]. The motivations in restricting the considered programs to PFOQ were inspired by the works on *implicit computational complexity*, that seek to characterize complexity classes by putting restrictions (type systems or others) on standard programming languages and paradigms [1,5,12]. These restrictions have to be implicit (i.e., not provided by the programmer) and tractable. Among all these works, we are aware of two results [16] and [6] studying polynomial time computations on quantum programming languages, works from which our paper was greatly inspired. [6] provides a characterization of BQP based on a quantum lambda-calculus. Our work is an extension to FBQP with a restriction to first-order procedures. Last but not least, [6] is based on Yao's simulation of quantum Turing machines [17] while we provide an explicit algorithm for generating circuits of polynomial size. Our work is also inspired by the function algebra of [16], that characterizes FBQP: our completeness proof shows that any function in [16] can be simulated by a PFOQ program (Theorem 6). However, we claim that FOQ is a more general language for FBQP in so far that it is much less constraining (in terms of expressive power) than the function algebra of [16]: any function of [16] can be, by design, transformed into a PFOQ program, whereas the converse is not true. We can take as example the quantum Fourier transform (QFT) which, as noted in [16], cannot be exactly computed by the function algebra without an additional initial quantum function. Furthermore, the *multi-qubit recursion construction* described in [16] is more restrictive than what we allow in PFOQ, since we may only call the same recursive function in each branch.

## 2 First-order quantum programming language

*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, 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. Its syntax is provided in Figure 1.

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

statement, proc is the procedure name and belongs to a countable set Procedures. We will write S<sup>proc</sup> to refer to S and proc ∈ P holds if proc is declared in D.

Statements include a no-op instruction, applications of a unitary operator to a qubit (q *= U<sup>f</sup>(i));, sequences, (classical) conditionals, quantum cases, and procedure calls (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 q̄[i] and q̄[j], for i, j ∈ N, i ≠ 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) ⊆ {q̄} ; ∀proc ∈ P,
*var(S<sup>proc</sup>) ⊆ {x, p̄} ; procedure names declared in D pairwise are distinct; for
each procedure call, the procedure name is declared in D.

Semantics. Let $\mathcal{H}_{2^n}$ be the Hilbert space $\mathbb{C}^{2^n}$ of $n$ qubits. We use Dirac notation to denote a quantum state $|\psi\rangle \in \mathcal{H}_{2^n}$. Each $|\psi\rangle \in \mathcal{H}_{2^n}$ 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 inner product and outer product of $|\psi\rangle$ and $|\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<sup>f</sup>]] ∈ Z → $\tilde{\mathbb{C}}^{2×2}$ is associated to each U<sup>f</sup> 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 both real and imaginary parts
are in $\mathbb{R}$. One can check easily 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$.

Let $\mathbb{B}$ to 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
numbers that can be approximated by a Turing machine for any precision $2^{-k}$ in time polynomial in $k$.

<table><caption>Fig. 1: Syntax of FOQ programs</caption><tr><td>(Integers)</td><td>i</td><td>≈</td><td>n | x | i + n | i − n | |s|</td><td>with n ∈ N</td></tr><tr><td>(Booleans)</td><td>b</td><td>≈</td><td>i > i | i ≥ i | i = i | b ∧ b | b ∨ b | ¬b</td><td></td></tr><tr><td>(Sorted Sets)</td><td>s</td><td>≈</td><td>nil | ¯q | s ⊖ [i]</td><td></td></tr><tr><td>(Qubits)</td><td>q</td><td>≈</td><td>s[i]</td><td></td></tr><tr><td>(Operators)</td><td>U<sup>f</sup>(i)</td><td>≈</td><td>NOT | R<sub>Y</sub><sup>f</sup>(i) | Ph<sup>f</sup>(i)</td><td>with f ∈ Z → [0, 2π) ∩ R̄</td></tr><tr><td>(Statements)</td><td>S</td><td>≈</td><td>skip; | q * = U<sup>f</sup>(i); | S S | if b then S else S<br> | qcase q of {0 → S, 1 → S} | call proc[i](s);</td><td></td></tr><tr><td>(Procedure declarations)</td><td>D</td><td>≈</td><td>ε | <b>decl</b> proc[x](p̄){S}</td><td>D</td></tr><tr><td>(Programs)</td><td>P(p̄)</td><td>≈</td><td>D :: S</td><td></td></tr></table>

A FOQ program $P(\bar{q})$ consists of a sequence of *procedure declarations* D followed by a *program statement* $S$, $\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](p̄){S} takes a sorted set parameter 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.

Statements include a no-op instruction, applications of a unitary operator to a qubit ($q * = U^f(i)$), sequences, (classical) conditionals, *quantum cases*, and *procedure calls* (**call** proc[i](s)). A quantum case **qcase** q of {0 → $S_0$, 1 → $S_1$} provides a quantum control feature that will execute statements $S_0$ and $S_1$ in superposition. For example, the *CNOT* gate on qubits $\bar{q}[i]$ and $\bar{q}[j]$, for $i, j \in 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 \{\text{x}, \bar{p}\}$; procedure names declared in D are pairwise distinct; for each procedure call, the procedure name is declared in D.

*Semantics.* Let $\mathcal{H}_{2^n}$ be the Hilbert space $\mathbb{C}^{2^n}$ of $n$ qubits. We use Dirac notation to denote a quantum state $|\psi\rangle \in \mathcal{H}_{2^n}$. Each $|\psi\rangle \in \mathcal{H}_{2^n}$ 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 $l(|\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$.
$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 \rightarrow \tau$ fixed by the program syntax. For example, the operation $+$ has signature $\text{Integers} \times \text{Integers} \rightarrow \text{Integers}$. A total function $[[\text{op}] \in [[\tau_1]] \times \dots \times [[\tau_n]] \rightarrow [[\tau]]$ is associated to each op.

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

<figure><img src="image_3.png" /><figcaption>Fig. 2: Semantics of expressions</figcaption></figure>

Note that in rule $(Rm_{\epsilon})$, if we try to delete an undefined index then we return the empty list, and in rule $(Qu_{\epsilon})$, if we try to access an undefined qubit index then we return the value 0 (defined indexes will always be positive). The standard gates $R_Y(\pi/4)$, $P(\pi/4)$, and $CNOT$, form a universal set of gates [4], which justifies the choice of NOT, $R_Y^f(i)$, and $Ph^f(i)$ as basic operators. For instance, we can simulate the application of an Hadamard gate $H$ on $q$ by the following statement $q * = R_Y^f(0)$; $q * = \text{NOT}$; with the function $f$ defined by
$\langle \psi |$ is equal to $| \psi \rangle^\dagger$ and $| \psi \rangle \langle \phi |$ and $\langle \psi | \phi \rangle$ are respectively the inner product and outer product of $| \psi \rangle$ and $| \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 $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 both real and imaginary parts are in $\tilde{\mathbb{R}}$. One can check easily that each matrix $M \triangleq [[U^f]](n) \in \tilde{\mathbb{C}}^{2 \times 2}$ is unitary, i.e., it satisfies $M^\dagger M = M M^\dagger = I_2$.

Let $\mathbb{B}$ to 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 $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 $\text{Integers} \times \text{Integers} \to \text{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 $\downarrow_{[[\tau]]}$ is a map in $\tau \times \mathcal{L}(\mathbb{N}) \to [[\tau]]$. Intuitively, it maps an expression of type $\tau$ to its value in $[[\tau]]$ for a given list $l$ of pointers in memory. 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_\epsilon)$, if we try to delete an undefined index then we return the empty list, and in rule $(Qu_\epsilon)$, if we try to access an undefined qubit index then we return the value 0 (defined indexes will always be positive). The standard gates $R_Y(\pi/4)$, $P(\pi/4)$, and CNOT, form a universal set of gates [3], which justifies the choice of NOT, $R_Y^f(i)$, and $\text{Ph}^f(i)$ as basic operators. For instance, we can simulate the application of an Hadamard gate $H$ on $q$ by the following statement $q * = R_Y^f(0)$; $q * = \text{NOT}$; with the function $f$ defined by $\forall n, f(n) = \pi/4 \in [0, 2\pi) \cap \tilde{\mathbb{R}}$. 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 state between two qubits $\bar{q}[i]$ and $\bar{q}[j]$, with $i, j \in \mathbb{N}, i \ne 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]).$$

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

$$\text{Conf}_n \triangleq (\text{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
∀n, f(n) = π/4 ∈ [0, 2π) ∩ R̃. 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 state between two qubits ¯q[i] and ¯q[j], with i, j ∈ N, i ≠ 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]). $$

Let τ and ⊥ be two special symbols for termination and error, respectively, and let ◦ stand for a symbol in {τ, ⊥}. The set of configurations of dimension 2ⁿ, denoted Confₙ, is defined by

$$ \text{Conf}_n \triangleq (\text{Statements} \cup \{\tau, \perp\}) \times \mathcal{H}_{2^n} \times \mathcal{P}(\mathbb{N}) \times \mathcal{L}(\mathbb{N}), $$

with P(ℝ) being the powerset over ℝ. A configuration c = (S, |ψ⟩, A, l) ∈ Confₙ contains a statement S to be executed (provided that S ∈ {τ, ⊥}), a quantum state |ψ⟩ 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 ⋃ₙ∈ℝ Confₙ × Confₙ. In the rules of Figure 3, —→ is annotated by an integer, called level. For example, the level of the conclusion in the (Call[1]) 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^f(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^f(j) to the right index. Rules (Seq∘) 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∘) 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, the two statements S₀ and S₁ are intuitively evaluated in superposition, on the projected state ⟨0⟩ₙ|ψ⟩ and ⟨1⟩ₙ|ψ⟩, respectively. During these evaluations, the index n cannot be accessed anymore. The rule (Call[1]) treats the base case of a procedure call when the sorted set parameter is empty. In the non-empty case, rule (Call∘) 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^proc{n/x}, where n has been substituted to x, w.r.t. the updated qubit pointers list l'.

For a given program P = D ∶ S and a given quantum state |ψ⟩ ∈ H₂ⁿ, the initial configuration for input |ψ⟩ is c_init(|ψ⟩) ≜ (S, |ψ⟩, {1, ..., n}, [1, ..., n]) ∈ Confₙ. A program is error-free if there is no initial configuration c_init(|ψ⟩) such that c_init(|ψ⟩) —→ (⊥, |ψ'⟩, A, l). We write ⟨P⟩(|ψ⟩) = |ψ'⟩, whenever c_init(|ψ⟩) m —→ (τ, |ψ'⟩, A, l) holds for some m. (τ, |ψ'⟩, A, l) is called a terminal configuration. Let H = ⋃ₙ H₂ⁿ, a program terminates if ⟨P⟩ is a total function in H → 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
$$
\begin{array}{r@{\quad}l@{\quad}l@{\quad}l}
\begin{array}{c}
\frac{(e, l) \otimes_{\llbracket \tau_1 \rrbracket} m}{(e \text{ op } d, l) \otimes_{\llbracket \text{op} \rrbracket} (\llbracket \tau_1 \rrbracket, \llbracket \tau_2 \rrbracket)} n} & \text{(Op)} &
\frac{(i, l) \otimes_Z n}{(U^f(i), l) \otimes_{C2 \times 2} (U^f)(n)} & \text{(Unit)} \\[1.5em]
\overline{(n, l) \otimes_Z n} & \text{(Cst)} &
\frac{(s, l) \otimes_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s \ominus [i], l) \otimes_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_{k-1}, x_{k+1}, \dots, x_m]} \in [1, m]} & \text{(Rm}_e) \\[1.5em]
\frac{(s, l) \otimes_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_n]}{(s|, l) \otimes_Z n} & \text{(Size)} &
\frac{(s, l) \otimes_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s \ominus [i], l) \otimes_{\mathcal{L}(\mathbb{N})} []} \notin [1, m]} & \text{(Rm}_f) \\[1.5em]
\overline{(\text{nil}, l) \otimes_{\mathcal{L}(\mathbb{N})} []} & \text{(Nil)} &
\frac{(s, l) \otimes_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s[i], l) \otimes_N x_k} \in [1, m]} & \text{(Qu}_e) \\[1.5em]
\overline{(\bar{q}, l) \otimes_{\mathcal{L}(\mathbb{N})} l} & \text{(Var)} &
\frac{(s, l) \otimes_{\mathcal{L}(\mathbb{N})} [x_1, \dots, x_m]}{(s[i], l) \otimes_N 0} \notin [1, m]} & \text{(Qu}_f) \\[1.5em]
\end{array}
$$

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

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 $\cup_{n \in \mathbb{N}} \text{Conf}_n \times \text{Conf}_n$. In the rules of Figure 3, — is annotated by an
integer, called *level*. For example, the level of the conclusion in the $(\text{Call}_[])$ 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^f(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^f(j) to the right index. Rules (Seq◦) 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 (Casee) 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, the two statements S₀ and S₁ are intuitively evaluated in superposition, on the projected state ⟨0⟩_n|ψ⟩ and ⟨1⟩_n|ψ⟩, respectively. During these evaluations, the index n cannot be accessed anymore. The rule (Call[]) treats the base case of a procedure call when the sorted set parameter is empty. In the non-empty case, rule (Call◦) evaluates the sorted set parameter s to l' and the integer parameter
<figure><img src="image_4.png" /><figcaption>Fig. 3: Semantics of statements</figcaption></figure>

program P$_{¬}$$_{⊥}$ such that $\forall |\psi)$, if $[[P]](|\psi))$ is defined then $[[P]](|\psi)) = [[P_{¬}]](|\psi))$. For example, an assignment $s[i] * = U^f(j)$; can be transformed into the conditional statement **if** $((0 < i) \land (i \le |s|))$ **then** $s[i] * = U^f(j)$; **else** skip;.
$$ (\text{skip}, |\psi\rangle, A, l) \xrightarrow{0} (\tau, |\psi\rangle, A, l) \quad (\text{Skip}) $$

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

$$ \frac{(s[i], l) \otimes_n n \in A \quad (U^f(j), l) \otimes_{C^2 \times 2} M}{(s[i] * U^f(j);, |\psi\rangle, A, l) \xrightarrow{0} (\tau, I_{2n-1} \otimes M \otimes I_{2l(|\psi\rangle)-n} |\psi\rangle, A, l)} \quad (\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)} \quad (\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)} \quad (\text{Seq}_\perp) $$

$$ \frac{(b, l) \otimes_B b \in \mathbb{B} \quad (S_b, |\psi\rangle, A, l) \xrightarrow{m_b} (\diamond, |\psi'\rangle, A, l)}{(\text{if b then } \text{S}_{\text{true}} \text{ else } \text{S}_{\text{false}}, |\psi\rangle, A, l) \xrightarrow{m_b} (\diamond, |\psi'\rangle, A, l)} \quad (\text{If}) $$

$$ \frac{(s[i], l) \otimes_n n \in A \quad (S_k, |\psi\rangle, A \setminus \{n\}, l) \xrightarrow{m_k} (\tau, |\psi_k\rangle, A \setminus \{n\}, l)}{(\text{qcase } s[i] \text{ of } \{0 \to S_0, 1 \to S_1\}, |\psi\rangle, A, l) \xrightarrow{\max_k m_k} (\tau, \sum_k |k\rangle_n (k)_n |\psi_k\rangle, A, l)} \quad (\text{Case}_\tau) $$

$$ \frac{(s[i], l) \otimes_n n \in A \quad (S_k, |\psi\rangle, A \setminus \{n\}, l) \xrightarrow{m_k} (\diamond_k, |\psi_k\rangle, A \setminus \{n\}, l)}{(\text{qcase } s[i] \text{ of } \{0 \to S_0, 1 \to S_1\}, |\psi\rangle, A, l) \xrightarrow{\max_k m_k} (\perp, |\psi\rangle, A, l)} \quad (\text{Case}_\perp) $$

$$ \frac{(s[i], l) \otimes_N n \notin A}{(\text{qcase } s[i] \text{ of } \{0 \to S_0, 1 \to S_1\}, |\psi\rangle, A, l) \xrightarrow{0} (\perp, |\psi\rangle, A, l)} \quad (\text{Case}_\emptyset) $$

$$ \frac{(s, l) \otimes_{\mathcal{L}(N)} l' \neq [] \quad (i, l) \otimes_Z n \quad (S^{\text{proc}}\{n/x\}, |\psi\rangle, A, l') \xrightarrow{m} (\diamond, |\psi'\rangle, A, l')}{(\text{call } \text{proc}[i](s);, |\psi\rangle, A, l) \xrightarrow{m+1} (\diamond, |\psi'\rangle, A, l)} \quad (\text{Call}_\diamond) $$

$$ \frac{(s, l) \otimes_{\mathcal{L}(N)} []}{(\text{call } \text{proc}[i](s);, |\psi\rangle, A, l) \xrightarrow{1} (\tau, |\psi\rangle, A, l)} \quad (\text{Call}_\llap{1}) $$

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

x to n. It returns the result of evaluating the procedure statement $S^{\text{proc}}\{n/x\}$, where n has been substituted to x, w.r.t. the updated qubit pointers list l'.
*Example 1.* A notable example of quantum algorithm is the Quantum Fourier Transform (QFT), used as a subroutine in Shor's algorithm [16], and whose quantum circuit is provided below, with $R_n \triangleq [[\text{Ph}^{\lambda x \cdot \pi / 2^{x-1}}]](n)$, for $n \ge 2$. After applying Hadamard and controlled $R_n$ gates, the circuit performs a permutation of qubits using swap gates.

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

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

```c
decl rec(p){
    p[1] *:= H;
    call rot[2](p);
    call rec(p ⊖ [1]);
},

decl rot[x](p){
    if |p| > 1 then
        qcase p[2] of {
            0 → skip;
            1 → p[1] *:= Ph^{\lambda x \cdot \pi / 2^{x-1}} (x);
        }
    call rot[x + 1](p ⊖ [2]);
    else skip;
},

call rec(q); call inv(q);
```

*Derivation tree and level.* Given a configuration $c$ wrt a fixed program $P$, $\pi_P \succ c$ denotes the *derivation tree* of $P$, the tree of root $c$ whose children are 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$ when $P$ and $c$ are clear from the context. Note that a derivation tree $\pi$ can be infinite in the particular case of a non-terminating computation. When $\pi'$ is finite, $\pi \le \pi'$ denotes that $\pi$ is a subtree of $\pi'$.

In the case of a terminating computation $\pi \succ c$, there exists a terminal configuration $c'$ and 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 FOQ program $P$ that terminates, 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$.
For a given program $P = D :: S$ and a given quantum state $|\psi\rangle \in \mathcal{H}_{2^n}$, the initial configuration for input $|\psi\rangle$ is $c_{init}(|\psi\rangle) \triangleq (S, |\psi\rangle, \{1, \dots, n\}, [1, \dots, n]) \in \text{Conf}_n$. A program is error-free if there 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]{\text{m}} (\tau, |\psi'\rangle, A, l)$ holds for some $m$. $(\tau, |\psi'\rangle, A, l)$ is called a terminal configuration. Let $\mathcal{H} = \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 $\llbracket P \rrbracket(|\psi\rangle)$ is defined then $\llbracket P \rrbracket(|\psi\rangle) = \llbracket P_{\neg\perp} \rrbracket(|\psi\rangle)$. For example, an assignment $s[i] * = U^f(j)$; can be transformed into the conditional statement if $((0 < i) \land (i \le |s|))$ then $s[i] * = U^f(j)$; else skip;.

**Example 1.** A notable example of quantum algorithm is the Quantum Fourier Transform (QFT), used as a subroutine in Shor's algorithm [15], and whose quantum circuit is provided below, with $R_n \triangleq \llbracket \text{Ph}^{\lambda x \cdot \pi / 2^{x-1}} \rrbracket(n)$, for $n \ge 2$. After applying Hadamard and controlled $R_n$ gates, the circuit performs a permutation of qubits using swap gates.

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

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

```pascal
decl rec(p) {
  p[1] * = H;
```

```pascal
call rot[2](p);
```

```pascal
call rec(p = [1]);
```

```pascal
decl rot[x](p) {
  if |p| > 1 then
```

```pascal
  qcase p[2] of {
```

```pascal
    0 -> skip;
```

```pascal
    1 -> p[1] * = Ph^{\lambda x \cdot \pi / 2^{x-1}}(x);
```

```pascal
}
call rot[x + 1](p = [2]);
```

```pascal
else skip;
```

```pascal
decl inv(p) {
  if |p| > 1 then
```

```pascal
    SWAP(p[1], p[|p|]);
```

```pascal
call inv(p = [1, |p|]);
```

```pascal
else skip;
```

```pascal
call rec(q); call inv(q);
```

*Derivation tree and level.* Given a configuration $c$ wrt a fixed program $P$, $\pi_P \supset c$ denotes the *derivation tree* of $P$, the tree of root $c$ whose children are obtained
**Example 2.** Consider the program QFT of example 1. Assume temporarily that QFT terminates (this will be shown in Example 3). 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 rec is called recursively $n+1$ times and makes $n+1$ calls to procedure rot on sorted sets of size $n$, $n-1$, ..., 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 $[[P^{-1}]] \circ [[P]] = \text{Id}$.

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

### 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.

*Polynomial-time* FOQ. Given two statements S, S', we write $S \in S'$ to mean that S is a substatement of S' and proc $\in S$ holds if there are i and s such that **call** proc[i](s); $\in S$. Given a program P = D :: S, we define the relation $>_{P} \subseteq$ Procedures $\times$ Procedures by $proc_1 >_{P} proc_2$ if $proc_2 \in S^{proc_1}$, for any two procedures $proc_1$, $proc_2 \in S$. Let the partial order $\geq_{P}$ be the transitive and reflexive closure of $>_{P}$ and define the equivalence relation $\sim_{P}$ by $proc_1 \sim_{P} proc_2$ if $proc_1 \geq_{P} proc_2$ and $proc_2 \geq_{P} proc_1$ both hold. Define also the strict order $>_{P}$ by $proc_1 >_{P} proc_2$ if $proc_1 \geq_{P} proc_2$ and $proc_1 \not\geq_{P} proc_2$ both hold.

**Definition 1.** Let WF be the set of FOQ programs P that are error-free and satisfy the well-foundedness constraint: $\forall \text{proc} \in P, \forall \text{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 \text{WF}$, then P terminates.

**Example 3.** Consider the program QFT of Example 1. The statements of the procedure declarations define the following relation: rec $>_{\text{QFT}}$ rec, rec $>_{\text{QFT}}$ rot, rot $>_{\text{QFT}}$ rot, and inv $>_{\text{QFT}}$ inv. Consequently, rec $>_{\text{QFT}}$ rec, rot $>_{\text{QFT}}$ rot, inv $>_{\text{QFT}}$ inv, and rec $>_{\text{QFT}}$ rot hold. For each call to an equivalent procedure, we check that the argument decreases: $\bar{p} \ominus [1]$ in rec, $\bar{p} \ominus [2]$ in rot, and $\bar{p} \ominus [1, |\bar{p}|]$ in inv. Consequently, QFT $\in \text{WF}$. We deduce from Theorem 1 that QFT terminates.

We now add a further restriction on mutually recursive procedure calls for guaranteeing polynomial time using a notion of width.
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$ when *P* and *c* are clear from the context. Note that a derivation tree $\pi$ can be infinite in the particular case of a non-terminating computation. When $\pi'$ is finite, $\pi \sqsubseteq \pi'$ denotes that $\pi$ is a subtree of $\pi'$.

In the case of a terminating computation $\pi \succ c$, there exists a terminal configuration $c'$ and 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 FOQ program *P* that terminates, level<sub>*P*</sub> is a total function in $\mathbb{N} \to \mathbb{N}$ defined as level<sub>*P*</sub>(*n*) $\triangleq \max_{|\psi\rangle \in \mathcal{H}_{2^n}} \text{lv}_{\pi_P \succ c_{init}(|\psi\rangle)}$.

Intuitively, level<sub>P</sub>(*n*) corresponds to the maximal number of non-superposed procedure calls in any program execution on an input of length *n*.

**Example 2.** Consider the program QFT of example 1. Assume temporarily that QFT terminates (this will be shown in Example 3). 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 rec is called recursively *n* + 1 times and makes *n* + 1 calls to procedure rot on sorted sets of size *n*, *n* − 1, . . ., 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*<sup>-1</sup>
such that [[*P*<sup>-1</sup>]] ◦ [[*P*]] = *Id*.

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

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.

Polynomial-time FOQ. Given two statements S, S', we write S ∈ S' to mean that S is a substatement of S' and proc ∈ S holds if there are i and s such that **call** proc[i](s); ∈ S. Given a program P = D :: S, we define the relation >_P ⊆ Procedures × Procedures by proc₁ >_P proc₂ if proc₂ ∈ S<sup>proc₁</sup>, for any two procedures proc₁, proc₂ ∈ S. Let the partial order ≥_P be the transitive and reflexive closure of >_P and define the equivalence relation ~_P by proc₁ ~_P proc₂ if proc₁ ≥_P proc₂ and proc₂ ≥_P proc₁ both hold. Define also the strict order >_P by proc₁ >_P proc₂ if proc₁ ≥_P proc₂ and proc₁ ̸>ₚ proc₂ both hold.

**Definition 1.** Let WF be the set of FOQ programs *P* that are error-free and satisfy the well-foundedness constraint: $\forall \text{proc} \in P, \forall \text{call} \text{proc}'[i](s); \in S^{\text{proc}},$

$$
\mathrm{proc} \sim_{\mathrm{P}} \mathrm{proc}' \Rightarrow \exists k > 0, \exists i_1, \dots, i_k, s = \bar{p} \oplus [i_1, \dots, i_k].
$$

**Lemma 1** If *P* ∈ WF, then *P* terminates.
**Definition 2.** Given a program P and a procedure proc ∈ P, the width of proc in P, noted width<sub>P</sub>(proc), and the width of proc in P relatively to statement S, noted w<sup>proc</sup><sub>P</sub>(S), are two positive integers in N. They are defined inductively by:

$$
\begin{align*}
\text{width}_P(\text{proc}) &\triangleq w_P^{\text{proc}}(S^{\text{proc}}), \\
w_P^{\text{proc}}(\text{skip};) &\triangleq 0, \\
w_P^{\text{proc}}(q * = U^f(i);) &\triangleq 0, \\
w_P^{\text{proc}}(S_1 S_2) &\triangleq w_P^{\text{proc}}(S_1) + w_P^{\text{proc}}(S_2), \\
w_P^{\text{proc}}(\text{if } b \text{ then } S_{\text{true}} \text{ else } S_{\text{false}}) &\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 } \text{proc } \sim_P \text{proc}', \\ 0 & \text{otherwise.} \end{cases}
\end{align*}
$$

**Definition 3 (PFOQ).** Let PFOQ be the set of programs P in WF that satisfy the following constraint: ∀proc ∈ P, width<sub>P</sub>(proc) ≤ 1.

*Example 4.* In the program of Example 1, width<sub>QFT</sub>(rec) = width<sub>QFT</sub>(rot) = width<sub>QFT</sub>(inv) = 1, since rec ><sub>QFT</sub> rot holds. Since QFT ∈ WF, by Example 3, 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.

**Lemma 2** *For each* PFOQ program P, there exists a polynomial *Q* ∈ N[*X*] such
*that* ∀*n* ∈ N, level<sub>P</sub>(*n*) ≤ *Q*(*n*).

Moreover, checking whether a program is PFOQ is tractable.

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

Quantum Turing machines and FBQP. Following Bernstein and Vazirani [3], a k-tape Quantum Turing Machine (QTM), with k ≥ 1, is defined by a triplet (Σ, Q, δ) where Σ is a finite alphabet including a blank symbol #, Q is a finite set of states with an initial state s₀ and a final state s<sub>T</sub> ≠ s₀, and δ is the quantum transition function in Q × Σ<sup>k</sup> → ℧<sup>Q×Σ<sup>k</sup>×{L,N,R}<sup>k</sup></sup>; {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 Z. A QTM successfully terminates if it reaches a superposition of only the final state s<sub>T</sub>. A QTM is said to be well-formed if the transition function δ 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 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 last non-blank cell.
**Example 3.** Consider the program QFT of Example 1. The statements of the procedure declarations define the following relation: rec >QFT rec, rec >QFT rot, rot >QFT rot, and inv >QFT inv. Consequently, rec ~QFT rec, rot ~QFT rot, inv ~QFT inv, and rec >QFT rot hold. For each call to an equivalent procedure, we check that the argument decreases: p̄Θ[1] in rec, p̄Θ[2] in rot, and p̄Θ[1, |p̄|] in inv. Consequently, QFT ∈ WF. We deduce from Theorem 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 ∈ P, the width of proc in P, noted width<sub>P</sub>(proc), and the width of proc in P relatively to statement S, noted w<sup>proc</sup><sub>P</sub>(S), are two positive integers in N. They are defined inductively by:*

$$
\begin{align*}
\text{width}_P(\text{proc}) &\triangleq w_P^{\text{proc}}(S^{\text{proc}}), \\
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 } S_{\text{true}} \text{ else } S_{\text{false}}) &\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 } \text{proc } \sim_P \text{ proc'}, \\ 0 & \text{otherwise.} \end{cases}
\end{align*}
$$

**Definition 3 (PFOQ).** Let PFOQ be the set of programs P in WF that satisfy the following constraint: ∀proc ∈ P, width<sub>P</sub>(proc) ≤ 1.

*Example 4.* In the program of Example 1, width<sub>QFT</sub>(rec) = width<sub>QFT</sub>(rot) = width<sub>QFT</sub>(inv) = 1, since rec ><sub>QFT</sub> rot holds. Since QFT ∈ WF, by Example 3, 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.

**Lemma 2** *For each PFOQ program P, there exists a polynomial Q ∈ N[X] such that ∀n ∈ N, level<sub>P</sub>(n) ≤ Q(n).*

Moreover, checking whether a program is 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}$.

*Quantum Turing machines and FBQP.* Following Bernstein and Vazirani [2], a *k*-tape *Quantum Turing Machine* (QTM), with *k* ≥ 1, is defined by a triplet (*Σ*, *Q*, *δ*) where *Σ* is a finite alphabet including a blank symbol #, *Q* is a finite set of states with an initial state *s*₀ and a final state *s*<sub>T</sub> ≠ *s*₀, and *δ* is the quantum transition function in *Q* × Σ<sup>*k*</sup> → $\tilde{\mathbb{C}}^{Q \times \Sigma^k \times \{L,N,R\}^k}$; {*L*, *N*, *R*} being the
We will further refer to a QTM as being *in normal form* if the only transitions from the final state $s_τ$ 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* [17] (N.B.: our notion of stationary QTM differs but can be shown to be equivalent to the definition of stationary QTM in [17]).

A configuration $\gamma$ of a k-tape QTM is a tuple $(s, \overline{w}, \overline{n})$, where $s$ is a state in $Q$, $\overline{w}$ is a k-tuple of words in $\Sigma^*$, and $\overline{n}$ is a k-tuple of indexes (head positions) in $\mathbb{Z}$. An initial (final) configuration $\gamma_{init}$ (resp. $\gamma_{fin}$) is a configuration of the shape $(s_0, \overline{w}, \overline{0})$ (resp. $(s_τ, \overline{w}, \overline{0})$). We use $\gamma(w)$ to denote a configuration $\gamma$ where the word $w$ is written on the input/output tape. Following [3], 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 |\gamma_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 |\gamma_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) \in S$ be the quantum configuration defined by $\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$ if for any $|\psi\rangle \in \mathcal{H}$, $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 4.** 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\}^*$, $|(f(x)|F(|x|)|^2 \ge p$.

The class FBQP is the functional extension of the complexity class BQP.

**Definition 5 ([3]).** 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]$ s.t. $M$ computes $f$ in time $P$ with probability $\frac{2}{3}$.

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.

**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))$.

Now we show that any PFOQ program computes a FBQP function.

**Theorem 3.** 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.* Using Lemma 2 and Lemma 3. □
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_{\tau}$. 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 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 last non-blank cell.
We will further refer to a QTM as being *in normal form* if the only transitions
from the final state $s_{\tau}$ 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* [16]
(N.B.: our notion of stationary QTM differs but can be shown to be equivalent
to the definition of stationary QTM in [16]).

A configuration $\gamma$ of a $k$-tape QTM is a tuple $(s, \overline{w}, \overline{n})$, where $s$ is a state in $Q$, $\overline{w}$ is a $k$-tuple of words in $\Sigma^*$, and $\overline{n}$ is a $k$-tuple of indexes (head positions) in $\mathbb{Z}$. An initial (final) configuration $\gamma_{init}$ (resp. $\gamma_{fin}$) is a configuration of the shape $(s_0, \overline{w}, \overline{0})$ (resp. $(s_{\tau}, \overline{w}, \overline{0})$). We use $\gamma(w)$ to denote a configuration $\gamma$ where the word $w$ is written on the input/output tape. Following [2], 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 $\Sigma_i \alpha_i |\gamma_i\rangle$ obtained by applying a single-step transition of $M$ to a configuration $|\gamma\rangle$ (i.e., $U_M|\gamma\rangle = \Sigma_i \alpha_i |\gamma_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) \in S$ be the quantum configuration defined by $\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$ if for any $|\psi\rangle \in \mathcal{H}$, $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 4.** 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\}^*$, $|(f(x)|F(|x|)|^2 \ge p$.

The class FBQP is the functional extension of the complexity class BQP.

**Definition 5 ([2]).** 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]$ s.t. $M$ computes $f$ in time $P$ with probability $\frac{2}{3}$.

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.
## 4 FBQP 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's [17] FBQP-complete function algebra can be exactly simulated in PFOQ.

Yamakami's function algebra. A characterization of FBQP was provided in [17] using a function algebra, named $\Box_1^{\overline{QP}}$. Given a quantum state $|\psi\rangle$ and a word $w \in \{0,1\}^n$, with $n \le l(|\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\}^{l(|\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$.

**Definition 6.** $\Box_1^{\overline{QP}}$ is the smallest class of functions including the basic initial functions $\{I, Ph_\theta, Rot_\theta, NOT, SWAP\}$, with $\theta \in [0, 2\pi) \cap \tilde{\mathbb{C}}$,

$$- 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$$

$$- Rot_{\theta}(|\psi\rangle) \triangleq \cos\theta|\psi\rangle + \sin\theta(|1\rangle\langle 0|\psi\rangle - |0\rangle\langle 1|\psi\rangle)$$

$$- 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 } l(|\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}$,

$$- Comp[F, G](|\psi\rangle) \triangleq F(G(|\psi\rangle))$$

$$- Branch[F, G](|\psi\rangle) \triangleq \begin{cases} |\psi\rangle & \text{if } l(|\psi\rangle) \le 1 \\ |0\rangle \otimes F(\langle 0|\psi\rangle) + |1\rangle \otimes G(\langle 1|\psi\rangle) & \text{otherwise} \end{cases}$$

$$- kQRec_t[F, G, H](|\psi\rangle) \triangleq \begin{cases} F(|\psi\rangle) & \text{if } l(|\psi\rangle) \le t \\ G(\sum_{w \in \{0,1\}^k} |w\rangle \otimes F_w(\langle w|H(|\psi\rangle))) & \text{otherwise} \end{cases}$$

where each $F_w \in \{kQRec_t[F, G, H], I\}$.

To handle general FBQP functions, [17] defines the extended encoding of an input $x \in \{0,1\}^*$ as $\phi_P(|x\rangle) \triangleq |0^{l(|x\rangle)}1\rangle\langle 0^P(l(|x\rangle))10^{11P(l(|x\rangle))+6}\rangle\langle 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. These ancilla provide space for internal computations and account for the polynomial bound associated to polynomial time QTMs.

**Theorem 4 ([17]).** 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 \Box_1^{\overline{QP}}$ such that $F \circ \phi_P$ computes $f$ with probability $\frac{2}{3}$.

We show the following result by structural induction on a function in $\Box_1^{\overline{QP}}$.
**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))$.

Now we show that any PFOQ program computes a FBQP function.

**Theorem 3.** 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.* Using Lemma 2 and Lemma 3. □

# 4 FBQP 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's [16] FBQP-complete function algebra can be exactly simulated in PFOQ.

**Yamakami's function algebra.** A characterization of FBQP was provided in [16] using a function algebra, named $\Box_1^{\text{QP}}$. Given a quantum state $|\psi\rangle$ and a word $w \in \{0,1\}^n$, with $n \le l(|\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\}^{l(|\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$.

**Definition 6.** $\Box_1^{\text{QP}}$ is the smallest class of functions including the basic initial functions $\{I, Ph_\theta, Rot_\theta, NOT, SWAP\}$, with $\theta \in [0, 2\pi) \cap \tilde{\mathbb{C}}$,

$$- 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$$

$$- Rot_{\theta}(|\psi\rangle) \triangleq \cos\theta|\psi\rangle + \sin\theta(|1\rangle\langle 0|\psi\rangle - |0\rangle\langle 1|\psi\rangle)$$

$$- 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 } l(|\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 } l(|\psi\rangle) \le 1 \\ |0\rangle \otimes F(\langle 0|\psi\rangle) + |1\rangle \otimes G(\langle 1|\psi\rangle) & \text{otherwise} \end{cases}$$

$$- kQRec_t[F, G, H](|\psi\rangle) \triangleq \begin{cases} F(|\psi\rangle) & \text{if } l(|\psi\rangle) \le t \\ G(\sum_{w \in \{0,1\}^k} |w\rangle \otimes F_w(\langle w|H(|\psi\rangle))) & \text{otherwise} \end{cases}$$

where each $F_w \in \{kQRec_t[F, G, H], I\}$.
**Theorem 5.** Let $F$ be a function in $\widehat{\square}_1^{QP}$. Then there exists a PFOQ program $P$ such that $[P] = F$.

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.* By Theorem 4 and Theorem 5. $\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$.

*Quantum circuits* [8] 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 ([11], a symmetric strict monoidal category) whose morphisms are generated by gates $G$ and wires. Let $\mathsf{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_{i=1}^k 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 7.** 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, we consider the following set of universal elementary gates $\{R_Y(\pi/4), P(\pi/4), CNOT\}$. The size $\#C$ of a circuit $C$ is equal to the number of its gates and wires.

**Definition 8.** A family of circuits $(C_n)_{n \in \mathbb{N}}$ is said to be polynomially-sized 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)$.
To handle general FBQP functions, [16] defines the extended encoding of an input $x \in \{0,1\}^*$ as $\phi_P(|x\rangle) \triangleq |0^{|x|}1\rangle_0 P(l(|x\rangle)) 10^{11P(l(|x\rangle))+6} 1\rangle_x$, 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. These ancilla provide space for internal computations and account for the polynomial bound associated to polynomial time QTMs.

**Theorem 4 ([16]).** 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{\square}_1^{\overline{QP}}$ such that $F \circ \phi_P$ computes $f$ with probability $\frac{2}{3}$.

We show the following result by structural induction on a function in $\widehat{\square}_1^{\overline{QP}}$.

**Theorem 5.** Let $F$ be a function in $\widehat{\square}_1^{\overline{QP}}$. Then there exists a PFOQ program $P$ such that $[[P]] = F$.

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.* By Theorem 4 and Theorem 5. $\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$.

*Quantum circuits* [8] 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 ([10], a symmetric strict monoidal category) whose morphisms are generated by gates $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_{i=1}^k 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}_{2n} \to \mathcal{H}_{2n}$. 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.
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$. Let $\xi_m : \mathcal{H}_{2^n} \to \mathcal{H}_{2^m}$, with $m \le n$, be defined by $\xi_m(|\psi\rangle) \triangleq \sum_{w \in \{0,1\}^m} \sum_{z \in \{0,1\}^{n-m}} \langle wz|\psi\rangle|w\rangle$. Finally, let $|w\rangle$, for $w \in \{0,1\}^*$, be the size of the word $w$.

**Theorem 1 (Adapted from [18] and [12]).** A function $f : \{0,1\}^* \to \{0,1\}^*$ is in FBQP iff there exists a uniform polynomially-sized family of circuits $(C_n)_{n \in \mathbb{N}}$ with $\alpha$ ancilla qubits s.t. $\forall x \in \{0,1\}^*$, $|\langle f(x)|\xi_{|f(x)|} |\otimes [C_{|x|}] \circ \chi_{\alpha(|x|)}(|x>)\rangle|^2 \ge \frac{2}{3}$.

In Theorem 1, $[C_{|x|}]$ is a function in $\mathcal{H}_{2^{|x|+\alpha(|x|)}} \to \mathcal{H}_{2^{|x|+\alpha(|x|)}}$. The function $\chi_{\alpha(|x|)}$ pads the input with ancilla in state $|0\rangle$ to match the circuit dimension. The function $\xi_{|f(x)|}$ projects the output of the circuit to match the length of the function output $|f(x)|$. Hence, for $|x\rangle \in \mathcal{H}_{2^{|x|}}$, $\xi_{|f(x)|} \circ [C_{|x|}] \circ \chi_{\alpha(|x|)}(|x>) \in \mathcal{H}_{2^{|f(x)|}}$.

*Compilation to circuits.* For each PFOQ program P, the existence of a polynomially-sized uniform family of circuits $(C_n)_{n \in \mathbb{N}}$ that computes $[P]$ is entailed by the combination of Lemma 2 and Theorem 1. However, due to the complex machinery of QTM, the constructions of both proofs cannot be used in practice to generate a circuit. In this section, we exhibit an algorithm that compiles directly a PFOQ program to a polynomially-sized circuit. Note that this compilation process requires some care since recursive procedure calls in quantum cases may yield an exponential number of calls. The remainder of this section will be devoted to present 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)$.

The **compile** algorithm uses two subroutines, named **compr** and **optimize**, and is defined by **compile(P, n) ≜ compr(P, [1, ..., n], ·).**

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) \triangleq k$. For a given $x \in \{0,1\}^*$, we say that state $|x\rangle$ satisfies **cs** if, $\forall n \in dom(\mathcal{cs})$, $cs(n) = k \Rightarrow |\langle k|_n|x\rangle|^2 = 1$. Two control structures **cs** and **cs'** are **orthogonal** if there does not exist a state $|x\rangle$ that satisfies **cs** and **cs'**. Note that if $\exists i \in dom(\mathcal{cs}) \cap dom(\mathcal{cs}')$, $cs(i) + cs'(i) = 1$ then **cs** and **cs'** are **orthogonal**.

Given a control structure **cs** and a statement S, a controlled statement is a pair $(cs, S) \in \text{Cst} \triangleq (\mathbb{N} \to \{0,1\}) \times \text{Statements.}$ Intuitively, a controlled statement $(cs, S)$ denotes a statement controlled by the qubits whose indices are in $dom(\mathcal{cs})$. For a unitary gate $U \in \mathcal{H}_{2^n} \to \mathcal{H}_{2^n}$, a control structure **cs**, and a list of pointers $l = [x_1, ..., x_n] \in \mathcal{L}(\mathbb{N})$ such that $\{x_1, ..., x_n\} \cap dom(\mathcal{cs}) = \emptyset$, $U(\mathcal{cs}, l)$ denotes the circuit applying gate $U$ on qubits $\bar{q}[x_1], ..., \bar{q}[x_n]$, whenever $\forall m \in dom(\mathcal{cs})$, $\bar{q}[m]$ is in state $|\mathcal{cs}(m)\rangle$. As demonstrated in [12], this circuit can be built with $O(\text{card}(dom(\mathcal{cs})))$ elementary gates and ancillas, and a single controlled-U gate.
**Definition 7.** 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 consid-
ered elementary gates, and define the complexity of an operation as the number
of elementary gates needed to perform it. In our setting, we consider the follow-
ing set of universal elementary gates $\{R_Y(\pi/4), P(\pi/4), CNOT\}$. The size $\#C$
of a circuit $C$ is equal to the number of its gates and wires.

**Definition 8.** 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$. Let $\xi_m : \mathcal{H}_{2^n} \to \mathcal{H}_{2^m}$, with $m \le n$, be defined by $\xi_m(|\psi\rangle) \triangleq \sum_{w \in \{0,1\}^m} \sum_{z \in \{0,1\}^{n-m}} \langle wz|\psi\rangle |w\rangle$. Finally, let $|w\rangle$, for $w \in \{0,1\}^*$, be the size of the word $w$.

**Theorem 7. (Adapted from [17] and [11])** 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|\left\langle f(x) | \xi_{|f(x)|} | \mathcal{C}_{|x|} \right\rangle \circ \chi_{\alpha(|x|)}(|x>)\right|^2 \ge \frac{2}{3}$.

In Theorem 7, $\llbracket C_{|x|} \rrbracket$ is a function in $\mathcal{H}_{2|x|+\alpha(|x|)} \to \mathcal{H}_{2|x|+\alpha(|x|)}$. The function $\chi_{\alpha(|x|)}$ pads the input with ancilla in state $|0\rangle$ to match the circuit dimension. The function $\xi_{|f(x)|}$ projects the output of the circuit to match the length of the function output $|f(x)|$. Hence, for $|x\rangle \in \mathcal{H}_{2|x|}$, $\xi_{|f(x)|} \circ \llbracket C_{|x|} \rrbracket \circ \chi_{\alpha(|x|)}(|x>) \in \mathcal{H}_{2|f(x)|}$.

*Compilation to circuits.* For each PFOQ program P, the existence of a polynomial-
size uniform family of circuits $(C_n)_{n \in \mathbb{N}}$ that computes $\llbracket P \rrbracket$ is entailed by the
combination of Lemma 2 and Theorem 7. However, due to the complex ma-
chinery of QTM, the constructions of both proofs cannot be used in practice
to generate a circuit. In this section, we exhibit an algorithm that compiles
directly a PFOQ program to a polynomial-size circuit. Note that this compi-
lation process requires some care since recursive procedure calls in quantum
cases may yield an exponential number of calls. The remainder of this sec-
tion 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}, \llbracket P \rrbracket(|\psi\rangle) = \xi_n \circ \llbracket C_n \rrbracket \circ \chi_{\alpha(n)}(|\psi\rangle)$.

The compile algorithm uses two subroutines, named **compr** and **optimize**,
and is defined by **compile**(P, n) ≜ **compr**(P, [1, ..., n], ·).

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) \triangleq k$. For a given $x \in \{0,1\}^*$,
**Algorithm 1 (compr)**

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

Let $D :: S = P$ in

if $S = \text{skip}$; then

$C \leftarrow 1$ ▷ Identity circuit

else if $S = s[i] * U^f(j)$; and $(s[i], l) \Downarrow_N n$ and $(U^f(j), l) \Downarrow_{C^{2 \times 2}} M$ then

$C \leftarrow M cs, [n]$ ▷ Controlled gate

else if $S = S_1 S_2$ then

$C \leftarrow \text{compr}(D :: S_1, l, cs) \circ \text{compr}(D :: S_2, l, cs)$ ▷ Composition

else if $S = \text{if b then } S_{\text{true}}$ else $S_{\text{false}}$ and $(b, l) \Downarrow_B b$ then

$C \leftarrow \text{compr}(D :: S_b, l, cs)$ ▷ Conditional

else if $S = \text{qcase } s[i] \text{ of } \{0 \to S_0, 1 \to S_1\}$ and $(s[i], l) \Downarrow_N n$ then

$C \leftarrow \text{compr}(D :: S_0, l, cs[n := 0]) \circ \text{compr}(D :: S_1, l, cs[n := 1])$ ▷ Quantum case

else if $S = \text{call } \text{proc}[i](s)$ and $(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})}$ [] then

$C \leftarrow 1$ ▷ Nil call

else if $S = \text{call } \text{proc}[i](s)$ and $(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} l' \neq []$ and $(i, l) \Downarrow_Z n$ then

if $\text{width}_P(\text{proc}) = 0$ then

$C \leftarrow \text{compr}(D :: S^{\text{proc}}\{n/x\}, l', cs)$ ▷ Non-recursive call

else if $\text{width}_P(\text{proc}) = 1$ then

$C \leftarrow \text{optimize}(D, [(cs, S^{\text{proc}}\{n/x\})], \text{proc}, l', {})$ ▷ Recursive call

end if

end if

return $C$
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$. Two control structures $cs$ and $cs'$ are orthogonal if there does not exist a state $|x\rangle$ that satisfies $cs$ and $cs'$. Note that if $\exists i \in \text{dom}(cs) \cap \text{dom}(cs')$, $cs(i) + cs'(i) = 1$ then $cs$ and $cs'$ are orthogonal.

**Algorithm 1 (compr)**

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

Let $D :: S = P$ in

if $S = \mathbf{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 \text{compr}(D :: S_1, l, cs) \circ \text{compr}(D :: S_2, l, cs)$

▷ Composition

else if $S = \mathbf{if b}$ then $S_{\text{true}}$ else $S_{\text{false}}$ and $(b, l) \Downarrow_{\mathbb{B}}^b$ then

$C \leftarrow \text{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 \text{compr}(D :: S_0, l, cs[n := 0]) \circ \text{compr}(D :: S_1, l, cs[n := 1])$

▷ Quantum case

else if $S = \mathbf{call}$ $\text{proc}[i](s)$ and $(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})}^n$ then

$C \leftarrow 1$

▷ Nil call

else if $S = \mathbf{call}$ $\text{proc}[i](s)$ and $(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})}^n$ $l' \neq$ [] and $(i, l) \Downarrow_{\mathbb{Z}}^n$ then

if $\text{width}_P(\text{proc}) = 0$ then

$C \leftarrow \text{compr}(D :: S^{\text{proc}}\{n/x\}, l', cs)$

▷ Non-recursive call

else if $\text{width}_P(\text{proc}) = 1$ then

$C \leftarrow \text{optimize}(D, [(cs, S^{\text{proc}}\{n/x\})], \text{proc}, l', {})$

▷ Recursive call

end if

end if

return $C$

Given a control structure $cs$ and a statement $S$, a controlled statement is a pair $(cs, S) \in \text{Cst} \triangleq (\mathbb{N} \to \{0, 1\}) \times \text{Statements}$. Intuitively, a controlled statement $(cs, S)$ denotes a statement controlled by the qubits whose indices are in $\text{dom}(cs)$. For a unitary gate $U \in \mathcal{H}_{2^n} \to \mathcal{H}_{2^n}$, a control structure $cs$, and a list of pointers $l = [x_1, \dots, x_n] \in \mathcal{L}(\mathbb{N})$ such that $\{x_1, \dots, x_n\} \cap \text{dom}(cs) = \emptyset$, $U cs l$ denotes the circuit applying gate $U$ on qubits $\bar{q}[x_1], \dots, \bar{q}[x_n]$, whenever $\forall m \in \text{dom}(cs)$, $\bar{q}[m]$ is in state $|cs(m)\rangle$. As demonstrated in [11], this circuit can be built with $O(\text{card}(\text{dom}(cs)))$ elementary gates and ancillas, and a single controlled-U gate.
<figure><img src="image_6.png" /><figcaption>Fig. 4: Example of circuit $U cs l$</figcaption></figure>

**Example 5.** 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] \in \mathcal{L}(\mathbb{N})$. The circuit $U cs l$ is provided in Figure 4.

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 rearranging wires under a given control structure. For two lists of qubit pointers $l_1 = [x_1,...,x_n]$, $l_2 = [x'_1,...,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 \mathcal{D}(\text{Procedures} \times \mathbb{Z} \times \mathbb{N} \rightarrow \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 \text{new ancilla()}$ be an instruction that sets $a$ to a fresh qubit index.

The subroutine **optimize** (Algorithm 2) treats the complex cases where circuit optimizations (merging) are needed, that is for recursive procedure calls. It takes as input a sequence of procedure declarations $D$, a list of controlled statements $l_{Cst}$, a procedure name $\text{proc}$, a list of qubit pointers $l$, and a dictionary $\text{Anc}$. The subroutine iterates on list $l_{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** $\text{proc}[i](s)$, with respect to a given list $l \in \mathcal{L}(\mathbb{N})$, such that $(i,l) \Downarrow_Z i$, $(s,l) \Downarrow_{\mathcal{L}(\mathbb{N})} l'$, and $(|s|,l) \Downarrow_{\mathbb{N}} j$. If the key $(\text{proc}, i, j)$ already exists in the dictionary $\text{Anc}$, the associated ancilla is re-used, otherwise, $\text{Anc}[\text{proc}, i, j]$ is set to $(a, l')$.

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.

**Theorem 2.** $\forall P \in \text{PFOQ}, \exists Q \in \mathbb{N}[X], \forall n \in \mathbb{N}, \forall |\psi\rangle \in \mathcal{H}_{2^n}, [[P]](|\psi\rangle) = \xi_n \circ [[\text{compile}(P,n)]] \circ \chi_{\alpha(n)}(|\psi\rangle)$ and $\#\text{compile}(P, n) \le Q(n)$.
<figure><img src="image_3.png" /><figcaption>Fig. 4: Example of circuit $U cs, l$</figcaption></figure>

**Example 5.** 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] \in \mathcal{L}(\mathbb{N})$. The circuit $U cs, l$ is provided in Figure 4.

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 rearranging wires under a given control structure. For two lists of qubit pointers $l_1 = [x_1, ..., x_n]$, $l_2 = [x'_1, ..., 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 \mathcal{D}(\text{Procedures} \times \mathbb{Z} \times \mathbb{N} \to \mathbb{N} \times \mathcal{L}(\mathbb{N}))$ be 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 \text{new ancilla()}$ be an instruction that sets $a$ to a fresh qubit index.

The subroutine **optimize** (Algorithm 2) treats the complex cases where circuit optimizations (merging) are needed, that is for recursive procedure calls. It takes as input a sequence of procedure declarations $D$, a list of controlled statements $l_{Cst}$, a procedure name `proc`, a list of qubit pointers $l$, and a dictionary `Anc`. The subroutine iterates on list $l_{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})$, such that $(i, l) \Downarrow_{\mathbb{Z}} i$, $(s, l) \Downarrow_{\mathcal{L}(\mathbb{N})} l'$, and $(|s|, l) \Downarrow_{\mathbb{N}} j$. If the key `(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 can assume w.l.o.g. that the statement controlled on the ancilla can be treated only after all the re-uses of the ancilla. This can be done without increasing the total complexity of **optimize**.

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.
**Algorithm 2 (optimize)** Build circuit for recursive procedure proc
**Inputs:** (D, l<sub>Cst</sub>, proc, l, Anc) ∈ Decl × 𝒰(Cst) × Procedures × 𝒰(ℝ) × 𝒟

$C_L \leftarrow 1; C_R \leftarrow 1; P \leftarrow D \text{::} \text{skip};$

while $l_{Cst} \neq []$ do

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

if S = S<sub>1</sub> S<sub>2</sub> then

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

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

else

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

end if

end if

if S = if b then S<sub>true</sub> else S<sub>false</sub> and (b, l) ⇝<sub>B</sub> b then

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

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

else

$C_L \leftarrow C_L \circ \text{compr}(D \text{::} S_b, 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>N</sub> n then

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

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

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

$l_{Cst} \leftarrow l_{Cst}[(cs[n := 0], S_0)];$

$C_R \leftarrow \text{compr}(D \text{::} S_1, l, cs[n := 1]) \circ C_R$

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

$l_{Cst} \leftarrow l_{Cst}[(cs[n := 1], S_1)];$

$C_R \leftarrow \text{compr}(D \text{::} S_0, l, cs[n := 0]) \circ C_R$

end if

end if

if S = call proc'[i](s) and (s, l) ⇝<sub>𝒰(ℝ)</sub> l' ≠ [] and (i, l) ⇝<sub>ℝ</sub> n then

if (proc', n, |l'|) ∈ Anc then

Let $(a, l'') = \text{Anc}[\text{proc}', n, |l'|]$ in

$e \leftarrow \text{new ancilla}();$

$C_L \leftarrow C_L \circ \text{NOT}(cs, e) \circ \text{NOT}(\cdot[e = 1], a) \circ \text{SWAP}(\cdot[e = 1], l', l'');$

$C_R \leftarrow \text{SWAP}(\cdot[e = 1], l'', l') \circ \text{NOT}(\cdot[e = 1], a) \circ \text{NOT}(cs, e) \circ C_R$

else

$a \leftarrow \text{new ancilla}();$

$\text{Anc}[\text{proc}', n, |l'|] \leftarrow (a, l');$

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

$l_{Cst} \leftarrow l_{Cst}[(\cdot[a = 1], S^{\text{proc}'}\{n/x\})]$

end if

end if

end while

return $C_L \circ C_R$
**Algorithm 2 (optimize)** Build circuit for recursive procedure proc
**Inputs:** (D, l<sub>Cst</sub>, proc, l, Anc) ∈ Decl × 𝒰(Cst) × Procedures × 𝒰(ℝ) × 𝒟

$C_L \leftarrow \mathbb{1}; C_R \leftarrow \mathbb{1}; P \leftarrow D \text{ :: } \mathbf{skip};$
while $l_{Cst} \neq []$ do
    (cs, S) $\leftarrow$ hd(l<sub>Cst</sub>); $l_{Cst} \leftarrow$ tl(l<sub>Cst</sub>)

if S = S<sub>1</sub> S<sub>2</sub> then

if $w_P^{\text{proc}}(S_1) = 1$ then
$l_{Cst} \leftarrow l_{Cst}[(cs, S_1)]; C_R \leftarrow \text{compr}(D \coloneqq S_2, l, cs) \circ C_R$

else
$l_{Cst} \leftarrow l_{Cst}[(cs, S_2)]; C_L \leftarrow C_L \circ \text{compr}(D \coloneqq S_1, l, cs)$

end if

end if

if S = if b then S<sub>true</sub> else S<sub>false</sub> and (b, l) ⇝<sub>B</sub> b then

if $w_P^{\text{proc}}(S_b) = 1$ then
$l_{Cst} \leftarrow l_{Cst}[(cs, S_b)]$

else
$C_L \leftarrow C_L \circ \text{compr}(D \coloneqq S_b, 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>N</sub> n then

if $w_P^{\text{proc}}(S_0) = 1$ and $w_P^{\text{proc}}(S_1) = 1$ then
$l_{Cst} \leftarrow l_{Cst}[(cs[n := 0], S_0), (cs[n := 1], S_1)]$

else if $w_P^{\text{proc}}(S_1) = 0$ then
$l_{Cst} \leftarrow l_{Cst}[(cs[n := 0], S_0)];$
$C_R \leftarrow \text{compr}(D \coloneqq S_1, l, cs[n := 1]) \circ C_R$

else if $w_P^{\text{proc}}(S_0) = 0$ then
$l_{Cst} \leftarrow l_{Cst}[(cs[n := 1], S_1)];$
$C_R \leftarrow \text{compr}(D \coloneqq S_0, l, cs[n := 0]) \circ C_R$

end if

end if

if S = call proc'[i](s) and (s, l) ⇝<sub>𝒰(ℝ)</sub> l' ≠ [] and (i, l) ⇝<sub>ℝ</sub> n then

if (proc', n, |l'|) ∈ Anc then
    Let (a, l'') = Anc[proc', n, |l'|] in
    e ← new ancilla();
    $C_L \leftarrow C_L \circ \text{NOT}(cs, e) \circ \text{NOT}(\cdot[e = 1], a) \circ \text{SWAP}(\cdot[e = 1], l', l'');$
    $C_R \leftarrow \text{SWAP}(\cdot[e = 1], l'', l') \circ \text{NOT}(\cdot[e = 1], a) \circ \text{NOT}(cs, e) \circ C_R$

else
    a ← new ancilla()
    Anc[proc', n, |l'|] ← (a, l');
    $C_L \leftarrow C_L \circ \text{NOT}(cs, a); C_R \leftarrow \text{NOT}(cs, a) \circ C_R;$
    $l_{Cst} \leftarrow l_{Cst}[(\cdot[a = 1], S^{\text{proc}'}\{n/x\})]$

end if

end if

end while
return $C_L \circ C_R$
*Example 6. compile(QFT, n)* outputs the circuit provided in Example 1. Notice that there is no extra ancilla as no procedure call appears in the branch of a quantum case.

*Polynomial-size circuits.* We show Theorem 2 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 5 where two instances of a gate *U* are merged into one using *SWAP* gates and gates controlled by orthogonal control structures.

<figure><img src="image_7.png" /><figcaption>Fig. 5: Example of circuit optimization</figcaption></figure>

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 U cs_i l_i$, with a unitary gate $U$, pairwise orthogonal $cs_1, \dots, cs_k \in \text{Cst}$, 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]$.

Now we show that orthogonality is an invariant property of compile.

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

**Theorem 7.** For any program *P* in PFOQ, compile(*P*, *n*) runs in time *O*(*n*²|*P*|+1).

*Proof.* Using Lemma 4 and Lemma 5. □

As there is no circuit duplication in the assignments of compile, we can
deduce from Theorem 7 that the compiled circuit is of polynomial size.

**Corollary 1.** For any program *P* in PFOQ, there exists a polynomial *Q* ∈ N[*X*] such that #compile(*P*, *n*) ≤ *Q*(*n*).
**Theorem 8.** For any P in PFOQ, there is $Q \in \mathbb{N}[X]$, $\forall n \in \mathbb{N}$, $\forall |\psi\rangle \in \mathcal{H}_{2^n}$, $[[P](|\psi\rangle) = \xi_n \circ [[compile(P, n)]] \circ \chi_{\alpha(n)}(|\psi\rangle)$ and $\#compile(P, n) \le Q(n)$.

**Example 6.** compile(QFT, n) outputs the circuit provided in Example 1. Notice that there is no extra ancilla as no procedure call appears in the branch of a quantum case.

**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 5 where two instances of a gate *U* are merged into one using *SWAP* gates and gates controlled by orthogonal control structures.

<figure><img src="image_4.png" /><figcaption>Fig. 5: Example of circuit optimization.</figcaption></figure>

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 U(cs_i, l_i)$, with a unitary gate $U$, pairwise orthogonal $cs_1, \dots, cs_k \in \text{Cst}$, 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]]$.

Now we show that orthogonality is an invariant property of compile.

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

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

*Proof.* Using Lemma 4 and Lemma 5. □

As there is no circuit duplication in the assignments of compile, we can deduce from Theorem 9 that the compiled circuit is of polynomial size.

**Corollary 1.** For any P in PFOQ, there exists a polynomial $Q \in \mathbb{N}[X]$ such that $\#compile(P, n) \le Q(n)$.
References

1. Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. *computational complexity*, 2(2):97-110, Jun 1992.

2. Charles H. Bennett. Logical reversibility of computation. *IBM Journal of Research and Development*, 17(6):525-532, 1973.

3. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. *SIAM Journal on Computing*, 26(5):1411-1473, 1997.

4. P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan. On universal and fault-tolerant quantum computing, 1999.

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

6. Ugo Dal Lago, Andrea Masini, and Margherita Zorzi. Quantum implicit computational complexity. *Theoretical Computer Science*, 411(2):377-409, 2010.

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

8. David Elieser Deutsch. Quantum computational networks. *Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences*, 425(1868):73-90, 1989.

9. Richard P. Feynman. Simulating physics with computers. *International Journal of Theoretical Physics*, 21(6):467-488, Jun 1982.

10. Ugo Dal Lago. A short introduction to implicit computational complexity. In *ESSLLI 2010*, pages 89-109, 2011.

11. Saunders MacLane. Categorical algebra. *Bulletin of the American Mathematical Society*, 71(1):40-106, 1965.

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

13. Romain Péchoux. Implicit computational complexity: past and future. *Mémoire d'habilitation à diriger des recherches*, 2020. Université de Lorraine.

14. Neil J. Ross. Algebraic and logical methods in quantum computation. PhD thesis, 2015.

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

16. Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In *Proceedings 35th Annual Symposium on Foundations of Computer Science*, pages 124-134, 1994.

17. Tomoyuki Yamakami. A schematic definition of quantum polynomial time computability. *J. Symb. Log.*, 85(4):1546-1587, 2020.

18. Andrew Chi-Chih Yao. Quantum circuit complexity. In *Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science*, pages 352-361, 1993.
# 6 Acknowledgments

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

# References

1. Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the polytime functions. computational complexity 2(2), 97–110 (Jun 1992). https://doi.org/10.1007/BF01201998

2. Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM Journal on Computing 26(5), 1411–1473 (1997). https://doi.org/10.1137/S0097539796300921

3. Boykin, P.O., Mor, T., Pulver, M., Roychowdhury, V., Vatan, F.: On universal and fault-tolerant quantum computing (1999). https://doi.org/10.48550/ARXIV.QUANT-PH/9906054

4. Briegel, H.J., Browne, D.E., Dür, W., Raussendorf, R., Van den Nest, M.: Measurement-based quantum computation. Nature Physics 5(1), 19–26 (2009). https://doi.org/10.1038/nphys1157

5. Dal Lago, U.: A short introduction to implicit computational complexity. In: ESS-LLI 2010. pp. 89–109 (2011). https://doi.org/10.1007/978-3-642-31485-8_3

6. Dal Lago, U., Masini, A., Zorzi, M.: Quantum implicit computational complexity. Theoretical Computer Science 411(2), 377–409 (2010). https://doi.org/10.1016/j.tcs.2009.07.045

7. Danos, V., Kashefi, E.: Determinism in the one-way model. Physical Review A 74(5), 052310 (2006). https://doi.org/10.1103/PhysRevA.74.052310

8. Deutsch, D.E.: Quantum computational networks. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 425(1868), 73–90 (1989)

9. Feynman, R.P.: Simulating physics with computers. International Journal of Theoretical Physics 21(6), 467–488 (Jun 1982). https://doi.org/10.1007/BF02650179

10. MacLane, S.: Categorical algebra. Bulletin of the American Mathematical Society 71(1), 40–106 (1965). https://doi.org/10.1090/S0002-9904-1965-11234-4

11. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press (2011)

12. Péchoux, R.: Implicit computational complexity: past and future. Mémoire d'habilitation à diriger des recherches (2020), https://tel.archives-ouvertes.fr/tel-02978986, université de Lorraine

13. Ross, N.J.: Algebraic and logical methods in quantum computation. PhD thesis (2015). https://doi.org/10.48550/ARXIV.1510.02198

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

15. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 124–134 (1994). https://doi.org/10.1109/SFCS.1994.365700

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

17. Yao, A.C.C.: Quantum circuit complexity. In: Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. pp. 352–361 (1993). https://doi.org/10.1109/SFCS.1993.366852
A Proofs

**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 by

$$
\begin{array}{l}
(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} \\
\qquad \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{array}
$$

with NOT† ≜ NOT, $R_Y^f(i)^† ≜ R_Y^{-f}(i)$ and Ph$^f(i)^† ≜ Ph^{-f}(i)$. P$^{-1}$ terminates and is such that $\forall |\psi\rangle, [[P^{-1}]]([P](|\psi\rangle)) = |\psi\rangle$. □

**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} \ proc[i](s);, |\psi\rangle, A, l) \gg_P (\mathbf{call} \ proc'[i')(s);, |\psi'\rangle, A', l')$$

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

Given $\pi \succ (\mathbf{call} \ proc[i](s);, |\psi\rangle, A, l)$ and $\pi' \succ (\mathbf{call} \ proc'[i')(s);, |\psi'\rangle, A', l')$, we show that if $\pi' \sqsubseteq \pi$ then it holds that

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

Consider a program $P \in \mathbf{WF}$. Assume that $\pi' \sqsubseteq \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. □

**Lemma 2** For each PFOQ program $P$, there exists a polynomial $Q \in \mathbb{N}[X]$ such that $\forall n \in \mathbb{N}$, $\text{level}_P(n) \le Q(n)$.

*Proof.* Consider a PFOQ program $P = D :: S$. We define the *rank* of a procedure in P as follows:

$$
\begin{array}{ll}
rk(\mathbf{proc}) \triangleq 0 & \text{if } \mathcal{H} \mathbf{proc}', \mathbf{proc} \succ_P \mathbf{proc}', \\
rk(\mathbf{proc}) \triangleq \max\{rk(\mathbf{proc}') + 1 \mid \mathbf{proc} \succ_P \mathbf{proc}'\} & \text{otherwise.}
\end{array}
$$
The rank of program P is defined by $rk(P) \triangleq \max_{\text{proc} \in P} rk(\text{proc})$.

We show the result by induction on the rank of procedure calls in S. Take call proc[i](s); ∈ S. If rk 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 level<sub>D::call</sub> proc[i](s); (n) = O(n).

Induction hypothesis: assume that any procedure proc' such that rk proc' ≤ k satisfies level<sub>D::call</sub> proc'[i](s); (n) = O(n<sup>k+1</sup>). Consider a procedure proc such that rk 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,

$$ \text{level}_{\text{D::call proc[i](s)}}(n) = \sum_{\text{proc}'<\text{P proc}} O(n^{\text{rk}}(\text{proc}')) = O(n^{\text{rk}}(\text{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,

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

We conclude by observing that for a program P = D :: S<sub>1</sub> ... S<sub>k</sub>, it holds that level<sub>P</sub>(n) = O(∑<sub>i=1</sub><sup>k</sup> level<sub>D::S<sub>i</sub></sub>(n)) = O(n<sup>rk(P)+1</sup>). □

**Theorem 2.** For each FOQ program P, it can be decided in time O(|P|^2) whether P<sub>¬⊥</sub> ∈ PFOQ.

*Proof.* The relations ~P, ≥P, and >P can be computed in time O(|P|^2). Moreover, any FOQ program P can be transformed in time O(|P|) into an equivalent error-free program P<sub>¬⊥</sub> of size O(|P|). Consequently, it can be decided in time O(|P|^2) whether P<sub>¬⊥</sub> ∈ WF and each width can be computed in time O(|P|^2). □

**Lemma 3** For any terminating FOQ program P, there exists a conservative QTM M that computes ⌊P⌋ in time O(n + n × level<sub>P</sub>(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 Σ = {0, 1, #, ||, &}, where # is the blank symbol and where || and & are special separation symbols for encoding stacks. The input tape t<sub>in</sub> of M contains a word in {0, 1, #}<sup>n</sup> encoding the quantum state. The 3 working tapes are t<sub>call</sub>, t<sub>l</sub>, and t<sub>K</sub> for storing the integer values of a procedure call, the list of qubit pointers, and intermediate classical computations, respectively, as words in Σ<sup>*</sup>. The configurations of M will be in Q × (Σ<sup>*</sup>)<sup>4</sup> × Z<sup>4</sup>, for some finite set of states Q. In particular, the initial
configuration is $(s_0, w, \epsilon, \epsilon, \epsilon, 0, 0, 0, 0)$, with $w \in \{0, 1\}^n$ encoding a quantum state of length $n \in \mathbb{N}$; the tapes $t_{\text{call}}$, $t_l$, and $t_K$ are initially empty ($\epsilon$). 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 $\llbracket e \rrbracket$ 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 \llbracket i \rrbracket$ and appending $f(\llbracket i \rrbracket)$, for any function $f$, are done by a reversible Turing machine [2], as reversible TMs are well-formed QTMs [3, Theorem 4.2].

We now describe a QTM $M$ simulating P inductively on the statement S. The **skip**; statement is trivial. If $S = q \ast = U^f(j)$; $M$ appends $\llbracket q \rrbracket$ to $t_K$. As the program terminates, $t_{\text{in}}(\llbracket q \rrbracket) \neq \#$ and the transition function is set to:

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

where $s_S$ is the state before executing the assignment when the head of the input tape has been moved to position $\llbracket q \rrbracket$, and $s_{\text{next}(S)}$ is the state just after executing the assignment. Finally, the machine erases $\llbracket q \rrbracket$ at the end of $t_K$, leaves its head in the last non-blank cell of $t_K$, and moves the head in $t_{\text{in}}$ back to the initial cell. Program P has 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 $\llbracket P_1 \rrbracket$ and $\llbracket P_2 \rrbracket$, 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 [3, 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 $\llbracket P \rrbracket$ 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 = \textbf{if b then S}_1 \textbf{ else S}_2$, we build a machine $M$ that concatenates $\llbracket b \rrbracket$ on the working tape $t_K$ and runs $M_1$ or $M_2$ deterministically depending on the value of $\llbracket b \rrbracket$, using the [3, Branching Lemma]. Then we erase $\llbracket b \rrbracket$ from the end of tape $t_K$. $M$ computes $\llbracket P \rrbracket$ 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 = \textbf{qcase q of } \{0 \to S_1, 1 \to S_2\}$, the machine appends $\llbracket q \rrbracket$ on tape $t_K$. It reads $t_{\text{in}}(\llbracket q \rrbracket)$, sets it to $\#$, and if it reads 0 runs $M_1$, if it reads 1, runs $M_2$. Finally, from state $s_T^1$, it writes 0 in $t_{\text{in}}(\llbracket q \rrbracket)$, moves the head to index 0, and transitions to $s_T$; similarly, from state $s_T^2$, the machines writes 1 in $t_{\text{in}}(\llbracket q \rrbracket)$ before moving the head and transitioning to $s_T$. We have that $M$ computes $\llbracket P \rrbracket$ 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 = \textbf{call proc}[i](s)$; inductively define machine $M$ as follows: update $t_{\text{call}}$ by appending $\llbracket i \rrbracket$, and update $t_l$ by adding the qubit pointer
indices excluded in $\llbracket s \rrbracket$, separating them using $\&$. We then run machine $M_{\text{proc}}$ that computes the function $\llbracket P_{\text{proc}} \rrbracket$, for $P_{\text{proc}} \triangleq D :: S^{\text{proc}}(\llbracket i \rrbracket)/x, s/\bar{q}$, in time $O(m + m \times \text{level}_{P_{\text{proc}}}(m))$, with $m \triangleq \llbracket s \rrbracket \le n$, afterwards erasing $\llbracket i \rrbracket$ 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))$. This concludes the proof. $\square$

**Theorem 5.** Let $F$ be a function in $\widehat{\Box_1^{QP}}$. Then there exists a PFOQ program $P$ such that $\llbracket P \rrbracket = F$.

*Proof.* We prove this result by structural induction on a function in the $\widehat{\Box_1^{QP}}$ algebra. The basic initial function $I$ can be simulated by $P(\bar{q}) = \varepsilon :: \textbf{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 $\llbracket U^f \rrbracket(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.

We now simulate the *Comp*, *Branch* and $kQRec_t$ 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

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

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] \ \mathbf{of} \ \{aw \to S_{aw}\} \\ \triangleq \ \mathbf{qcase} \ s[i_1] \ \mathbf{of} \ \{ \begin{aligned}[t] & 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{aligned} \}. \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} \text{call } kQRec_t(\bar{p} \ominus [1 \dots k]); & \text{if } F_w = kQRec_t, \\ \text{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])$. More $kQRec_t >_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$

**Theorem 3.** *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 5. $\square$

**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 $\square_1^{\overline{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$

**Lemma 4** *For any circuit $C_n \triangleq \circ_{i=1}^k U cs_i l_i)$, with a unitary gate $U$, pairwise orthogonal $cs_1, \dots, cs_k \in \text{Cst}$, 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}(cs_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 $cs_i$ are pairwise orthogonal, after the two compositions of NOT circuits in $C^1$, $|x\rangle$ satisfies $[a_i := 1]$ iff it satisfies $cs_i$, for $i \in \{1, \dots, k-1\}$. Moreover, $|x\rangle$ satisfies $[a_k := 1]$ iff there exists $i$ such that it satisfies $cs_i$. Therefore, each SWAP sends wires in $l_i$ into $l_k$ iff $|x\rangle$ satisfies $cs_i$ and then $U$ is applied on $l_k$ if it satisfies one of the control structure $cs_i$. As circuit $C^2$ reverts 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$. $\square$

**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 $([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 $(\text{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 $[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 $\text{NOT}(cs, a)$, a state $|x\rangle$ will satisfy $[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 7.** For any program $P$ in PFOQ, compile($P, n$) runs in time $O(n^{2|P|+1})$.

*Proof.* We first show that an execution of the **optimize** subroutine performs at most $O(n^2)$ calls to **compr**. We use a simple counting argument. The dictionary Anc ensures that ancillas related to the same $(\text{proc}', i, j) \in \text{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 at most $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 at most $O(|P| \cdot n^2)$. Hence $O(n^2)$ ancillas can be created, which also bounds the number of calls to **compr**.

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 at most $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 at most $O(n^2)$ such calls, the maximum total number of procedure calls is $O(n^{2rk(P)}) \in O(n^{2|P|})$ (see proof of Lemma 2 for a definition of rank $rk$). Each of these recursive procedure calls can have at most a constant number of merge constructions with linear complexity, therefore the total number of gates is $O(n^{2|P|+1})$. $\square$

## B Example of circuit compilation with function merging

Consider the following program in PFOQ, defined for some unitary gate U:

```p
P(\bar{q}) \triangleq \textbf{decl} \ proc(\bar{p})\{
    \textbf{if} |\bar{p}| > 2\textbf{:
        \qquad \textbf{qcase} \bar{p}[1] \textbf{of} \{0 \to \textbf{call} \ proc(\bar{p} \ominus [1]);\,
        \qquad \quad 1 \to \textbf{qcase} \bar{p}[2] \textbf{of} \{0 \to \textbf{skip};\,
        \qquad \quad \quad 1 \to \textbf{call} \ proc(\bar{p} \ominus [1, 2]);
        \qquad \} \\
    \qquad \textbf{else} \bar{p}[1] *:= U;
\}
\textbf{::} \textbf{call} \ proc(\bar{q});
```

Consider first a naive approach to building a circuit representing this program. The circuit representation of P can be seen as:

<figure><img src="image_8.png" /></figure>
For a large input length, creating the circuit by applying this definition would deal the following progression.

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

It is easy to see that this construction results in $O(|\bar{q}|2^{|\bar{q}|})$ gates. Consider the following example of input length $|\bar{q}| = 7$. Each Toffoli gate carries a complexity cost of $O(|\bar{q}|)$.

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

This is the scenario that **optimize** subroutine (Algorithm 2) avoids. By making use of the fact that there are multiple calls to `proc` with same input size with orthogonal controls, calls to sorted sets of equal size can be merged onto the same ancilla.

The following is the circuit that simulates $P$ on the same input size, using 6 ancillas that, in this example, are not reset to zero for ease of reading. We have also indexed each Toffoli gate, which have $O(1)$ cost since they have constant size (at most 3).
<figure><img src="image_11.png" /></figure>

In the specific case of procedure proc, there is no need to move around qubits while merging, which simplifies the construction and allows the circuit to scale with $O(|\bar{q}|)$. We represent each ancilla created for proc on input length $i$ as $a_{proc,i}$ (note that there is no integer parameter in this case so we omit it here in the index of ancillas). Since the only non-recursive cases are for input length $i = 1, 2$, those are the only ancillas with controlled gate U.

We can graphically see how the circuit is built linearly. The directed graph below shows the creation of each ancilla $a_{proc,i}$, where each node is an ancilla and each edge indicates a (generalized) Toffoli gate, numbered exactly as in the circuit. We further add a tag $\circ$ or $\bullet\bullet$ to differentiate between the two types of Toffoli gate, which represent the two recursive branches, $\circ$ for the vertical and diagonal edges where the first qubit is in state 0, and $\bullet\bullet$ for the horizontal edges which refer to the case where the first two qubits are both in state 1.

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

Nodes have as incoming edges the branches that reach the same quantum input length and are merged in the same ancilla. If we were to represent the circuit for larger input lengths, we would obtain a continuation of this directed graph to the right, following the same pattern.
## C Example: quantum teleportation

Quantum teleportation is an interesting technique that allows for transportation of qubits between far away agents, Alice and Bob. If Alice and Bob share *n* EPR states, they can teleport any *n*-length state between their labs.

In our case, we consider an input state of length *n*, and we extend it with qubits |0⟩⊗2*n*. The following is a FOQ program where we use the 2*n* zero state qubits to create a Bell state and then perform the teleportation for each qubit, such that the *i*-th qubit of the initial state appears in position 3*n* − 2(*i* − 1) of the final state for 1 ≤ *i* ≤ *n*.

```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);
```

It can be easily shown that the program is in PFOQ. We apply the principle of deferred measurement to avoid performing any measurements until the end, and therefore use typical controlled *NOT* and *Z* gates as opposed to the same gates controlled on results of measurements. The following is an example of the circuit compilation for the teleportation of a state of length *n* = 3.
<figure><img src="image_13.png" /></figure>
D Example of derivation tree

The derivation tree $\pi$ described below corresponds to the evaluation of procedure rot of Example 1 on an input of length 2.

$$ \text{Let } |\psi'\rangle \triangleq |0\rangle\langle 0|_2 |\psi'\rangle + |1\rangle\langle 1|_2 \left( \begin{smallmatrix} 1 & 0 \\ 0 & e^{i\pi/2^{2-1}} \end{smallmatrix} \right) \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} |\psi'\rangle $$

in:

Let

$$ \pi_1 \triangleq \left\{ \begin{array}{c} \frac{(\bar{p}, [1, 2]) \Psi_{\mathcal{L}(\mathcal{N})} [1, 2]}{(\bar{p}[2], [1, 2]) \Psi_{\mathcal{N}} [2]} \quad \frac{(2, [1, 2]) \Psi_{\mathcal{Z}} [2]}{(\bar{p}[1], [1, 2]) \Psi_{\mathcal{N}} [1]} \\ \text{(skip: } |\psi'\rangle \{1\}, [1, 2]\) \xrightarrow{0} (\tau, |\psi'\rangle \{1\}, [1, 2]) \quad (\bar{p}[1] * \text{Ph}_{\lambda y, \pi/2^{y-1}}(2); |\psi'\rangle \{1\}, [1, 2]) \xrightarrow{0} (\tau, \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/2^{2-1}} \end{pmatrix}) \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} |\psi'\rangle \{1\}, [1, 2]) \end{array} \right. $$

and

$$ (\text{qcase } \bar{p}[2] \text{ of } \{0 \to \text{skip}; 1 \to \bar{p}[1] * \text{Ph}_{\lambda y, \pi/2^{y-1}}(2); \}, |\psi'\rangle \{1, 2\}, [1, 2]) \xrightarrow{0} (\tau, |\psi'\rangle \{1, 2\}, [1, 2]) $$

$$ \pi_2 \triangleq \left\{ \begin{array}{c} \frac{(\bar{p}, [1, 2]) \Psi_{\mathcal{L}(\mathcal{N})} [1, 2]}{(\bar{p} \oplus [2], [1, 2]) \Psi_{\mathcal{L}(\mathcal{N})} [1]} \quad \frac{(2, [1, 2]) \Psi_{\mathcal{Z}} [2]}{(2 + 1, [1, 2]) \Psi_{\mathcal{Z}} [3]} \\ \text{(skip: } |\psi'\rangle \{1, 2\}, [1, 2]\) \xrightarrow{0} (\tau, |\psi'\rangle \{1, 2\}, [1, 2]) \quad (\bar{p}[1] * \text{Ph}_{\lambda y, \pi/2^{y-1}}(2); |\psi'\rangle \{1, 2\}, [1, 2]) \xrightarrow{0} (\tau, \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}) \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} |\psi'\rangle \{1, 2\}, [1, 2]) \end{array} \right. $$

in:

$$ \text{Let } S \triangleq \text{ if } |\bar{p}| > 1 \text{ then qcase } \bar{p}[2] \text{ of } \{0 \to \text{skip}; 1 \to \bar{p}[1] * \text{Ph}_{\lambda y, \pi/2^{y-1}}(2); \} \text{ call rot}[2 + 1](\bar{p} \oplus [2]); \text{ else skip}; $$

$$ \text{and } S' \triangleq \text{ qcase } \bar{p}[2] \text{ of } \{0 \to \text{skip}; 1 \to \bar{p}[1] * \text{Ph}_{\lambda y, \pi/2^{y-1}}(2); \} \text{ call rot}[2 + 1](\bar{p} \oplus [2]); $$

in:

$$ \pi \triangleq \left\{ \begin{array}{c} \frac{(\bar{p}, [1, 2]) \Psi_{\mathcal{L}(\mathcal{N})} [1, 2]}{(\bar{p}|, [1, 2]) \Psi_{\mathcal{Z}} [2]} \quad \frac{(1, [1, 2]) \downarrow_{\mathcal{Z}} [1]}{(\bar{p}| > 1, [1, 2]) \Psi_{\mathcal{B}} \text{ true}} \quad \frac{\pi_1}{\pi_2} \\ \text{(call rot}[2](\bar{p}), |\psi'\rangle \{1, 2\}, [1, 2]) \xrightarrow{1+1} (\tau, |\psi'\rangle \{1, 2\}, [1, 2]) \end{array} \right. $$