论文标题
量子多项式时间的编程语言
A programming language characterizing quantum polynomial time
论文作者
论文摘要
我们引入了一种名为FOQ的一阶量子编程语言，其终止程序是可逆的。我们将FOQ限制为一个严格且可拖动的子集，名为PFOQ，该子集终止具有有界宽度的程序，该程序提供了第一个基于编程语言的量子复杂性类FBQP的表征。最后，我们提出了一种可拖动的语义传播算法，该算法将PFOQ程序汇编为输入量值数量多项式的量子电路。
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.
