A Generalization of Deutsch's Example
Giovanni Costantini, Fabrizio Smeraldi · arXiv (Cornell University) · 1997
Quantum parallelism is the main feature of quantum computation. In 1985 D. Deutsch showed that a single quantum computation may be sufficient to state whether a two-valued function of a two-valued variable is constant or not. Though the generalized problem with unconstrained domain and range size admits no deterministic quantum solution, a fully probabilistic quantum algorithm is presented in which quantum parallelism is harnessed to achieve a quicker exploration of the domain with respect to the classical ``sampling'' strategy.