A Schematic Definition of Quantum Polynomial Time Computability. (arXiv:1802.02336v1 [cs.CC])

In the past four decades, the notion of quantum polynomial-time computability
has been realized by the theoretical models of quantum Turing machines and
quantum circuits. Here, we seek a 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 quantum functions. 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 other
functions and to the theory of higher-type quantum functionals.

Article web page: