317 citations · 321 across the 11 of their papers we have counts for
13 papers
Quantum Term Rewrite Systems: Applications to Complexity Analysis
Kostia Chardonnet, Emmanuel Hainry, Romain Péchoux +1
Term Rewrite Systems (TRS) is a computational model offering a level of abstraction well-suited towards static analysis, e.g., termination or complexity analyses. In this paper, we…
Resource-Aware Quantum Programming with General Recursion and Quantum Control
Kostia Chardonnet, Emmanuel Hainry, Romain Péchoux +1
This paper introduces the hybrid quantum language with general recursion , driven towards resource-analysis. By design, does not require the specif…
Quantum Programming in Polylogarithmic Time
Florent Ferrari, Emmanuel Hainry, Romain Péchoux +1
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 th…
Expectation-based Analysis of Higher-Order Quantum Programs
Martin Avanzini, Alejandro Díaz-Caro, Emmanuel Hainry +1
The paper extends the expectation transformer based analysis of higher-order probabilistic programs to the quantum higher-order setting. The quantum language we are considering can…
Branch Sequentialization in Quantum Polytime
Emmanuel Hainry, Romain Péchoux, Mário Alberto Machado da Silva
Quantum algorithms leverage the use of quantumly-controlled data in order to achieve computational advantage. This implies that the programs use constructs depending on quantum dat…
Declassification Policy for Program Complexity Analysis
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
In automated complexity analysis, noninterference-based type systems statically guarantee, via soundness, the property that well-typed programs compute functions of a given complex…
A feasible and unitary quantum programming language
Alejandro Díaz-Caro, Emmanuel Hainry, Romain Péchoux +1
We introduce a novel quantum programming language featuring higher-order programs and quantum controlflow which ensures that all qubit transformations are unitary. Our language boa…
A programming language characterizing quantum polynomial time
Emmanuel Hainry, 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 term…
Complete and tractable machine-independent characterizations of second-order polytime
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
The class of Basic Feasible Functionals BFF is the second-order counterpart of the class of first-order functions computable in polynomial time. We present several implicit charact…
A tier-based typed programming language characterizing Feasible Functionals
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
The class of Basic Feasible Functionals BFF is the type-2 counterpart of the class FP of type-1 functions computable in polynomial time. Several characterizations have been sug…
A Type-Based Complexity Analysis of Object Oriented Programs
Emmanuel Hainry, Romain Péchoux
A type system is introduced for a generic Object Oriented programming language in order to infer resource upper bounds. A sound andcomplete characterization of the set of polynomia…
Theory of higher order interpretations and application to Basic Feasible Functions
Emmanuel Hainry, Romain Péchoux
Interpretation methods and their restrictions to polynomials have been deeply used to control the termination and complexity of first-order term rewrite systems. This paper extends…
A Framework for Algebraic Characterizations in Recursive Analysis
Olivier Bournez, Walid Gomaa, Emmanuel Hainry
Algebraic characterizations of the computational aspects of functions defined over the real numbers provide very effective tool to understand what computability and complexity over…