Принято считать, что большинство трудных аспектов, возникающих при построении реальных квантовых компьютеров, имеет отношение к проблемам неточности и декогерентности. Как показано в работе Bennett et al. [1994], квантовые гейты должны обладать точностью порядка $O(1 / t)$ для того, чтобы прийти к разумному результату после $t$ шагов квантового вычисления. То есть существует такая $c$, что если амплитуды в унитарной матрице, описывающей квантовый гейт, возмущаются не более, чем на $c / t$, то у квантового компьютера остается вполне реальный шанс дать желаемый ответ. Точно также необходимо, чтобы декогеренция была полиномиально мала по $t$, для того, чтобы иметь после $t$ шагов вычислений разумную вероятность успеха. Это утверждение имеет силу не только для простой модели декогерентности, где каждый бит имеет вероятность подвергнуться декогеренции на каждом шаге вычисления, но также для более сложных моделей декогеренции, которые происходят из фундаментальных квантовомеханических рассмотрений [Unruh, 1995, Palma et al., 1996, Chuang et al., 1995]. Однако, построение квантового компьютера с высоким уровнем точности и низким уровнем декогерентности, предназначенного для реализации длинных вычислений, может являть собой фундаментальную проблему для экспериментальной физики. В классических компьютеpax вероятностные ошибки преодолеваются не только за счет средств оборудования, но и за счет программного обеспечения, введения избыточности и кодов, корректирующих ошибки. По всей видимости, метод избыточности для квантовых вычислений не годится в силу существования теоремы о невозможности клонирования битов [Peres, 1993, $\S 9-4]$, но этот аргумент не отрицает возможности применения более сложных программных методов повышения точности и уменьшения декогеренции. В действительности, некий прогресс в направлении увеличения точности [Berthiaume et al., 1994] и уменьшения декогерентности [Shor, 1995] уже достигнут. Из работы Bennett et al. [1995] следует, что квантовые биты могут быть в точности переданы по шумным квантовым каналам, давая возможность надеяться, что в дальнейшем квантовые вычисления могут быть успешно проведены с использованием шумных квантовых битов и шумных квантовых гейтов.

Нахождение дискретных логарифмов и разложение на простые множители сами по себе не являются широко используемыми вычислительными задачами. Они стали известны потому, что на их основе построена криптографическая система открытых ключей. Таким образом, эти проблемы использовались потому, что считалось, что их трудно решить. Также это справедливо и для обобщения этих проблем, предложенных в работе Boneh, Lipton [1995]. Если использовать квантовые вычисления только для нахождения дискретного логарифма или для факторизации, вероятно, эта дисциплина станет узкоспециализированной технологией, raison d’être которой заключается в том, чтобы помешать применять криптографию открытых ключей. Однако, имеют место большое количество проблем, которые могут быть решены асимптотически быстрее на квантовом компьютере. В частности, что касается проблем, о которых не ясно, являются ли они NP-полными, проблема нахождения короткого вектора на решетке [Adleman, 1994, Adleman and McCurley, 1995] потенциально может оказаться в сфере решаемых на квантовом компьютере задач.

Однако, в науке о вычислениях имеется гораздо больше важных проблем, про которые не ясно, являются ли они полиномиально решаемыми по времени или NP-полными. Поэтому квантовые компьютеры, вероятно, не будут так широко использованы, пока на них не научатся решать NP-полные проблемы. Решение NP-проблемы в некотором смысле является Святым Граалем теоретической компьютерной науки, которую множество людей пыгались решить на классическом компьютере. Нахождение полиномиального по времени алгоритма решения таких задач на квантовом компьютере было бы величайшим открытием. Существуют слабые указания на то, что квантовые компьютеры недостаточно мощны для решения NP-полной проблемы [Bennett et al., 1997], но я не уверен, что это в перспективе все будет так, как сейчас предполагается.