# 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.