Каковы перспективы квантовых вычислений? В этом разделе мы обсудим поиски других алгоритмов и опишем наибольшие трудности, возникающие при построении квантовых компьютеров.

В этой статье мы обсудили один алгоритм, приводящий к экспоненциальному ускорению по сравнению с обычными методами эффективное вычисление периода длинной последовательности. Сегодня это – единственный алгоритм, обнаруживающий такое ускорение. Этот алгоритм был применен к традиционной задаче вычислительной математики – задаче факторизации только благодаря пониманию глубокой структуры, лежащей в основе этой проблемы. Это требование оказывается общим – квантовый параллелизм приведет к экспоненциальному ускорению только в тех задачах, структура которых позволяет избежать необходимости проверки экспоненциально большого числа решений $[28,29,30,31]$. Таким образом, подход с применением грубой силы к некоторым сложнейшим вычислительным вопросам, известным как NP-полные задачи, не приведет к успеху и с использованием квантового параллелизма. Любой прогресс в решении таких задач требует обнаружения некоторой структуры, лежащей в их основе. Вместо этого, квантовые компьютеры, похоже, будут наиболее полезны для моделирования малых квантовых систем и управления ими [6].

Насколько трудно будет построить квантовый компьютер? Даже в рамках очевидно малых систем атомного размера квантовые вычисления проходят на огромном объеме гильбертова пространства. Квантовое вычисление подразумевает построение траектории от стандартного начального состояния к сложному конечному состоянию. Главная трудность состоит в том, чтобы держаться этой траектории. Покинуть ее означает исчезнуть в гильбертовом пространстве. Наибольшая проблема – это сверхчувствительность к возмущениям, сдвигающим вычислительную траекторию случайным образом с ее направления. Такие
возмущения происходят от неконгролируемых связей с внешним шумом [32]. Слишком рано предсказывать тяжесть этой проблемы. Хотя кажется, что нет фундаментальных ограничений на то, как хорошо мы можем изолировать квантовую систему. В настоящее время некоторые реализации квантовых компьютеров рассматриваются теоретиками и экспериментаторами в разных странах $[17,18,33,34,35,36,37]$. Одна многообещающая схема включает ионные ловушки $[34,35]$ – следующее поколение образцов атомных часов. В течение следующих двух десятилетий обычные компьютеры достигнут атомных размеров; возможно, квантовые компьютеры достигнут этих размеров раньше.