Characterizing classes of functions computable by quantum parallelism

Abstract Computation by quantum parallelism involves associating a quantum state v(f) to each function f: Zm → Zn. v(f) is formed from superpositions of states labelled by the values of f, the standard choice being an equally weighted superposition of all the values of f. A joint property G(f) of the values f(0),..., f(m–1) is called computable by quantum parallelism (QPC) if there is an observable g which will reveal the value G(f), with non-zero probability, when applied to v(f), and will never show a false value. It is shown that the problem of deciding which Gs are QPC can be formulated entirely in terms of the linear relations which exist among the v(f)s. In the case of f:Zm→Z2, G:(Z2)m → Z2 we explicitly describe all properties which are QPC and show that this includes only m2 + m + 2 of the 22m such properties. By using a suitable nonstandard definition for v(f) this number can be increased to 22m — 2m+1 (for m 1).