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

arXiv:2311.15884 · Mathematical Structures in Computer Science

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

Tomoyuki Yamakami

Published Aug 1, 2024• 2 citations
arXivHTMLPDF

Abstract

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

DOI
10.1017/s0960129524000264

Related papers

A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY

Tomoyuki Yamakami

Abstract In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic (inductive or constructive) definition of (primitive) recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer

arXiv:1802.02336•Journal of Symbolic Logic•Sep 8, 2020•16 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

An imperative programming language characterizing FBQP

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

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.

•Jun 27, 2022•0 citations

On the Quantum Time Complexity of Divide and Conquer

Allcock, Jonathan, Bao, Jinge, Aleksandrs Belovs +2 more

In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.

arXiv:2311.16401•Leibniz international proceedings in informatics•Nov 28, 2023•2 citations

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

•Apr 1, 2007•0 citations

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
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 .
Abstract In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic (inductive or constructive) definition of (primitive) recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer
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.
In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future
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.