Treffer: A programming language characterizing quantum polynomial time

Title:
A programming language characterizing quantum polynomial time
Authors:
Hainry, Emmanuel, Péchoux, Romain, Silva, Mário
Contributors:
Designing the Future of Computational Models (MOCQUA), Centre Inria de l'Université de Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Orna Kupferman, Pawel Sobocinski, ANR-22-PETQ-0007,EPiQ,Etude de la pile quantique : Algorithmes, modèles de calcul et simulation pour l'informatique quantique(2022), ANR-22-PNCQ-0002,HQI – R&D et Support,Initiative Nationale Hybride HPC Quantique – R&D et Support des communautés(2022), European Project: 951821,H2020-FETFLAG-2018-2020,H2020-FETFLAG-2020-01,NEASQC(2020), European Project: 101018180,H2020-JTI-EuroHPC-2020-01,H2020-JTI-EuroHPC-2020-2,HPCQS(2021)
Source:
International Conference on Foundations of Software Science and Computation Structures. :156-175
Publisher Information:
CCSD; Springer Nature Switzerland, 2023.
Publication Year:
2023
Collection:
collection:CNRS
collection:INRIA
collection:INRIA_TEST
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:CENTRALESUPELEC
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:LORIA-FM
collection:ANR
collection:PEPR_QUANTIQUE
collection:AM2I-UL
collection:ANR_QUANTIQUE
collection:ANR_QUANTIQUE_1
Subject Terms:
quantum programming language, polynomial time, quantum circuit, complexity, [INFO.INFO-PL]Computer Science [cs], Programming Languages [cs.PL], [INFO.INFO-LO]Computer Science [cs], Logic in Computer Science [cs.LO]
Subject Geographic:
Paris, France
Original Identifier:
ARXIV: 2212.06656
HAL: hal-03895081
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
ISBN:
978-3-031-30829-1
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/2212.06656; info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-031-30829-1_8; info:eu-repo/grantAgreement//951821/EU/NExt ApplicationS of Quantum Computing/NEASQC; info:eu-repo/grantAgreement//101018180/EU/High Performance Computer and Quantum Simulator hybrid/HPCQS
DOI:
10.1007/978-3-031-30829-1_8
Access URL:
https://inria.hal.science/hal-03895081
https://inria.hal.science/hal-03895081v2/document
https://inria.hal.science/hal-03895081v2/file/FBQP_Implicit.pdf
Rights:
info:eu-repo/semantics/OpenAccess
URL: http://creativecommons.org/licenses/by/
Accession Number:
edshal.hal.03895081v2
Database:
HAL

Weitere Informationen

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.