Дойч продемонстрировал, что учет квантовой интерференции приводит к существенному уменьшению числа вычислений, которые необходимо проделать при решении задач на компьютере. Приведем пример сокращения вычислений за счет интерференции [42], принадлежащий Дойчу. Рассмотрим отображения вида / : {0,1} -> {0,1}. Существует ровно четыре различных отображений данного вида. Два из них назовем постоянными: для одного /(0) = /(1) = 0, для второго -/(0) = /(1) - 1. Предположим, что дается возможность произвести только одно вычисление для того, чтобы убедиться, является ли данная функция / постоянной. С точки зрения классических вычислений, одного вычисления мало! Нужно сделать два вычисления: вычислить /(0) и /(1).

Два различаемых уровня входных и выходных сигналов, проходящих по цепям ЭВМ, и которые мы обозначали выше как 0 и 1, - это некоторые простейшие состояния, наблюдаемые на входе и выходе любого логического элемента, или схемы, собранной из логических элементов. Для них выше мы использовали обозначения - i,j. Введем более изощренные обозначения и будем писать вместо г и j -\i) и |г). Это все однобитовые состояния. Два различаемых уровня входных и выходных сигналов, проходящих по цепям ЭВМ, и которые мы обозначали выше как 0 и 1, - это некоторые простейшие состояния, наблюдаемые на входе и выходе любого логического элемента, или схемы, собранной из логических элементов. Для них выше мы использовали обозначения - i,j. Введем более изощренные обозначения и будем писать вместо г и j -\i) и |г). Это все однобитовые состояния.

Способность квантового компьютера обрабатывать информацию параллельно колоссально ускоряет вычисления. "Например, квантовый компьютер, оперирующий с 200 q-битами, может достичь такого же эффекта при разложении 400-разрядного числа на простые множители (это важная задача криптографии), как 2200 одновременных вычислений с классическими битами. Невозможно представить себе обычный компьютер с таким количеством процессоров. Специалисты говорят по этому поводу, что квантовый компьютер может производить подобные вычисления экспоненциально быстрее, чем лучшие из известных в настоящее время классических алгоритмов". "Квантовый компьютер заменил последовательный перебор вариантов на единовременное измерение, которое даст результат, недостижимый в принципе дедуктивными методами" [8].