Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

An imperative programming language characterizing FBQP

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

Published Jun 27, 2022• 0 citations
OpenAlex

Abstract

We introduce an imperative programming language called QPT (Quantum Poly-Time) with recursion rules that captures the complexity class FBQP(Functions Bounded-error Quantum Polytime), the class of functions computable in polynomial time by a quantum Turing machine with at most 1/3 probability of error, commonly accepted as the class of feasible problems for quantum computers. Our result takes advantage of a function algebra proposed by Yamakami characterizing FBQP.

Related papers

A Polytime Quantum Programming Language

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

As quantum computing emerges as a promising computational paradigm, quantum programming languages provide the tools that bridge the distance between abstract programming and its hardware implementation. In some cases, restricted programming languages may even provide an avenue for more efficient circuit compilation strategies. In this work, we introduce foq , a first-order quantum programming language which allows for quantum control and recursion, and where a syntactically restricted subset of programs ( pfoq ) is shown to be sound and complete for quantum polytime computation. This is achieved by bounding both the recursion depth and the branching width of programs, which we demonstrate to still be compatible with various interesting applications, such as quantum teleportation and the quantum Fourier transform. pfoq constitutes the first programming-language-based characterization of the quantum complexity class fbqp , and we provide a semantics-preserving compilation algorithm such that any pfoq program can be compiled into a quantum circuit that grows polynomially on its number of input qubits, using an anchoring-and-merging technique to solve the problem of branch sequentialization.

ACM Transactions on Quantum Computing•Sep 30, 2025•0 citations

A Programming Language Characterizing Quantum Polynomial Time

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

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.

Lecture notes in computer science•Jan 1, 2023•6 citations

Quantum Programming in Polylogarithmic Time

Ferrari, Florent, Emmanuel Hainry F, Romain Péchoux +1 more

Polylogarithmic time delineates a relevant notion of feasibility on several classical computational models such as Boolean circuits or parallel random access machines. As far as the quantum paradigm is concerned, this notion yields the complexity class FBQPOLYLOG of functions approximable in polylogarithmic time with a quantum random-access Turing machine. We introduce a quantum programming language with first-order recursive procedures, which provides the first programming-language-based characterization of FBQPOLYLOG. Each program computes a function in FBQPOLYLOG (soundness) and, conversely, each function of this complexity class is computed by a program (completeness). We also provide a compilation strategy from programs to uniform families of quantum circuits of polylogarithmic depth and polynomial size, whose set of computed functions is known as QNC, and recover the well-known separation result FBQPOLYLOG $\subsetneq$ QNC.

arXiv:2507.15415•Jan 1, 2025•0 citations

A programming language characterizing quantum polynomial time

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

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.

arXiv:2212.06656•Dec 13, 2022•0 citations

Elementary quantum recursion schemes that capture quantum polylogarithmic-time computability of quantum functions

Tomoyuki Yamakami

Abstract Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time computability, a new recursion-theoretic approach was taken lately by Yamakami [J. Symb. Logic 80, pp. 1546–1587, 2020] by way of recursion schematic definition, which constitutes six initial quantum functions and three construction schemes of composition, branching, and multi-qubit quantum recursion. By taking a similar approach, we look into quantum polylogarithmic-time computability and further explore the expressing power of elementary schemes designed for such quantum computation. In particular, we introduce an elementary form of the quantum recursion, called the fast quantum recursion, and formulate $EQS$ (elementary quantum schemes) of “elementary” quantum functions. This class $EQS$ captures exactly quantum polylogarithmic-time computability, which forms the complexity class BQPOLYLOGTIME. We also demonstrate the separation of BQPOLYLOGTIME from NLOGTIME and PPOLYLOGTIME. As a natural extension of $EQS$ , we further consider an algorithmic procedural scheme that implements the well-known divide-and-conquer strategy. This divide-and-conquer scheme helps compute the parity function, but the scheme cannot be realized within our system $EQS$ .

arXiv:2311.15884•Mathematical Structures in Computer Science•Aug 1, 2024•2 citations

Quantum Computability

Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang

In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani [Proc. 25th ACM Symposium on Theory of Computation, 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339]. On the other hand, if quantum Turing machines are allowed unrestricted amplitudes (i.e., arbitrary complex amplitudes), then the corresponding BQP class has uncountable cardinality and contains sets of all Turing degrees. In contrast, allowing unrestricted amplitudes does not increase the power of computation for error-free quantum polynomial time (EQP). Moreover, with unrestricted amplitudes, BQP is not equal to EQP. The relationship between quantum complexity classes and classical complexity classes is also investigated. It is shown that when quantum Turing machines are restricted to have transition amplitudes which are algebraic numbers, BQP, EQP, and nondeterministic quantum polynomial time (NQP) are all contained in PP, hence in ${\rm P}^{#{\rm P}}$ and PSPACE. A potentially practical issue of designing "machine independent" quantum programs is also addressed. A single ("almost universal") quantum algorithm based on Shor's method for factoring integers is developed which would run correctly on almost all quantum computers, even if the underlying unitary transformations are unknown to the programmer and the device builder.

SIAM Journal on Computing•Oct 1, 1997•260 citations
We introduce an imperative programming language called QPT (Quantum Poly-Time) with recursion rules that captures the complexity class FBQP(Functions Bounded-error Quantum Polytime), the class of functions computable in polynomial time by a quantum Turing machine with at most 1/3 probability of error, commonly accepted as the class of feasible problems for quantum computers. Our result takes advantage of a function algebra proposed by Yamakami characterizing FBQP.
As quantum computing emerges as a promising computational paradigm, quantum programming languages provide the tools that bridge the distance between abstract programming and its hardware implementation. In some cases, restricted programming languages may even provide an avenue for more efficient circuit compilation strategies. In this work, we introduce foq , a first-order quantum programming language which allows for quantum control and recursion, and where a syntactically restricted subset of programs ( pfoq ) is shown to be sound and complete for quantum polytime computation. This is achieved by bounding both the recursion depth and the branching width of programs, which we demonstrate to still be compatible with various interesting applications, such as quantum teleportation and the quantum Fourier transform. pfoq constitutes the first programming-language-based characterization of the quantum complexity class fbqp , and we provide a semantics-preserving compilation algorithm such that any pfoq program can be compiled into a quantum circuit that grows polynomially on its number of input qubits, using an anchoring-and-merging technique to solve the problem of branch sequentialization.
Polylogarithmic time delineates a relevant notion of feasibility on several classical computational models such as Boolean circuits or parallel random access machines. As far as the quantum paradigm is concerned, this notion yields the complexity class FBQPOLYLOG of functions approximable in polylogarithmic time with a quantum random-access Turing machine. We introduce a quantum programming language with first-order recursive procedures, which provides the first programming-language-based characterization of FBQPOLYLOG. Each program computes a function in FBQPOLYLOG (soundness) and, conversely, each function of this complexity class is computed by a program (completeness). We also provide a compilation strategy from programs to uniform families of quantum circuits of polylogarithmic depth and polynomial size, whose set of computed functions is known as QNC, and recover the well-known separation result FBQPOLYLOG ⊊\subsetneq⊊ QNC.
Abstract Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time computability, a new recursion-theoretic approach was taken lately by Yamakami [J. Symb. Logic 80, pp. 1546–1587, 2020] by way of recursion schematic definition, which constitutes six initial quantum functions and three construction schemes of composition, branching, and multi-qubit quantum recursion. By taking a similar approach, we look into quantum polylogarithmic-time computability and further explore the expressing power of elementary schemes designed for such quantum computation. In particular, we introduce an elementary form of the quantum recursion, called the fast quantum recursion, and formulate EQSEQSEQS (elementary quantum schemes) of “elementary” quantum functions. This class EQSEQSEQS captures exactly quantum polylogarithmic-time computability, which forms the complexity class BQPOLYLOGTIME. We also demonstrate the separation of BQPOLYLOGTIME from NLOGTIME and PPOLYLOGTIME. As a natural extension of EQSEQSEQS , we further consider an algorithmic procedural scheme that implements the well-known divide-and-conquer strategy. This divide-and-conquer scheme helps compute the parity function, but the scheme cannot be realized within our system EQSEQSEQS .
In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani [Proc. 25th ACM Symposium on Theory of Computation, 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339]. On the other hand, if quantum Turing machines are allowed unrestricted amplitudes (i.e., arbitrary complex amplitudes), then the corresponding BQP class has uncountable cardinality and contains sets of all Turing degrees. In contrast, allowing unrestricted amplitudes does not increase the power of computation for error-free quantum polynomial time (EQP). Moreover, with unrestricted amplitudes, BQP is not equal to EQP. The relationship between quantum complexity classes and classical complexity classes is also investigated. It is shown that when quantum Turing machines are restricted to have transition amplitudes which are algebraic numbers, BQP, EQP, and nondeterministic quantum polynomial time (NQP) are all contained in PP, hence in ${\rm P}^{#{\rm P}}$ and PSPACE. A potentially practical issue of designing "machine independent" quantum programs is also addressed. A single ("almost universal") quantum algorithm based on Shor's method for factoring integers is developed which would run correctly on almost all quantum computers, even if the underlying unitary transformations are unknown to the programmer and the device builder.