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

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

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