Пусть $N$ – большое число, $F:\{0, \ldots$, $N-1\} \rightarrow\{0, \ldots, N-1\}$ – такая функция, для которой вычисление любого частного значения $F(x)$ просто, т.е. может быть сделано за время, ограниченное полиномом от $\ln x$. Мы хотим вычислить (распознать) некоторое свойство графа ( $x, F(x))$, например:
(i) Найти наименьший период $r$ функции $F$, т.е. такой наименьший вычет $r \bmod N$, что $F(x+r \bmod N)=F(x)$ для всех $x($ ключевой шаг в проблеме разложения на множители).
(ii) Найти некоторое такое $x$, что $F(x)=1$, или установить, что такое $x$ не существует (проблема поиска).

Как мы уже отмечали, попытка прямого решения такой проблемы состоит в составлении полного списка пар $(x, F(x))$ и последующем применении к нему алгоритма распознавания выясняемого свойства. Такая стратегия требует по крайней мере экспоненциального времени (как функции битового размера $N$ ), поскольку длина списка $-N$. Если оставить в стороне возможность теоретического прорыва в понимании таких задач (например, доказательство того, что $P=N P$ ), практическим решением могло бы быть использование возможности параллельного вычисления, т. е. вычисления одновременно многих или даже всех значений $F(x)$. Это занимает меньше времени, но требует (не)пропорционально много оборудования.

Замечательное предложение, высказанное Д. Дойчем (см. [DeuJ], [Deu]), состоит в использовании квантовой суперпозиции классических состояний $|x\rangle$ вместо объединения $N$ классических регистров, каждый из которых находится в одном из начальных состояний $|x\rangle$. Для большей точности далее в качестве определения формулируется математическая модель.