QM Logo Fabrizio

A Generalization of Deutsch's Example

  1. Costantini and F. Smeraldi, http://xxx.lanl.gov, quant-ph/9702020, 1997 (Submitted Feb 7th)


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.

Full paper (on arXiv)

Backlinks: Publications