A programming language characterizing quantum polynomial time
From MaRDI portal
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.
Cites work
- A new recursion-theoretic characterization of the polytime functions
- A new universal and fault-tolerant quantum basis
- A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
- A Short Introduction to Implicit Computational Complexity
- Categorical algebra
- scientific article; zbMATH DE number 845841 (Why is no real title available?)
- Quantum Complexity Theory
- Quantum computation and quantum information. 10th anniversary edition
- Quantum computational networks
- Quantum implicit computational complexity
- The One Way to Quantum Computation
- Towards a quantum programming language
Cited in
(9)- An algebra of pure quantum programming
- An Algebraic Language for Distributed Quantum Computing
- scientific article; zbMATH DE number 7364199 (Why is no real title available?)
- Quantum Programs as Kleisli Maps
- Invariants of quantum programs: characterisations and generation
- A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
- Elementary quantum recursion schemes that capture quantum polylogarithmic-time computability of quantum functions
- Quantum first-order logics that capture logarithmic-time/space quantum computability
- Quantum programming in polylogarithmic time
This page was built for publication: A programming language characterizing quantum polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6091186)
