Cтраница 2
Даже если никакого пригодного для реальных вычислений квантового компьютера никогда не будет построено, данное исследование может иллюстрировать проблему моделирования квантовой механики на классическом компьютере. Любые методы, позволяющие это сделать для произвольного гамильтониана, окажутся необходимыми при моделировании квантового компьютера. Поэтому всякий метод моделирования квантовой механики как максимум с полиномиальным замедлением может привести к полиномиальному по времени фактори-зационному алгоритму. [16]
В этих работах показано, что существуют задачи, которые быстро и точно решаются на квантовом компьютере, в то время как лишь на классическом компьютере они могут быть быстро решены с высокой вероятностью с помощью генератора случайных чисел. Однако в этих статьях не показано, как решать какую-либо задачу на квантовом компьютере за полиномиальное время, про которую неизвестно, решаема ли она за полиномиальное время с помощью генератора случайных чисел с малой вероятностью ошибки; это характеристика класса сложности ВРР, который широко используется как класс эффективно решаемых задач. [17]
С более широкой точки зрения, поскольку не существует квантовых систем, которые хорошо защищены от некогерентности и поэтому не могут эффективно моделироваться на классическом компьютере, любая такая система может решать трудные вычислительные задачи. [18]
С более широкой точки зрения, поскольку не существует квантовых систем, которые хорошо защищены от некогерентности и поэтому не могут эффективно моделироваться на классическом компьютере, любая такая система может решать трудные вычислительные задачи. [19]
Хотя он не задавался вопросом, являются ли квантовомехани-ческие вычисления более мощными, ему удалось показать, что обратимая унитарная эволюция в состоянии реализовать вычислительный потенциал машины Тьюринга, и таким образом показать, что вычислительная мощность квантовой механики не меньше, чем у классического компьютера. [20]
Одним из результатов, содержащихся в этой работе, является задача с оракулом ( то есть проблема введения некой подпрограммы черный ящик, которую компьютер может использовать, но машинный код ее неизвестен), которая может быть решена за полиномиальное время на квантовой машине Тьюринга, а на классическом компьютере ее решение требует сверхполиномиальное время. Он предложил более простую конструкцию задачи с оракулом, которая решается за полиномиальное время на квантовом компьютере, но требует экспоненциального времени на обычном компьютере. Действительно, в то время как задача Бернштейна и Вазирани кажется несколько надуманной, задача Саймона выглядит вполне естественной. [21]
Классический компьютер обрабатывает каждую команду или оператор программы последовательно по очереди, в результате чего машина способна исполнять только по одной команде или оператору на каждом шаге вычисления. В параллельных компьютерах на одном шаге вычисления привлекаются несколько независимых друг от друга команд или операторов, которые исполняются параллельно на многопроцессорном вычислительном устройстве. [22]
Если мы желаем более реалистично смоделировать размер оракула и время вычисления, тогда мы могли бы принять размер оракула равным O ( N) для общего вида функции /, что будет равняться размеру оракула, который просто содержит список ROM значений функции. Из этих оценок и из () следует, что любой классический компьютер требует, по крайней мере, полиномиальное время, в то время как квантовый компьютер требует только логарифмическое время, что снова демонстрирует экспоненциальное ускорение. [23]
Два электронных состояния каждого иона обозначаются 0) и 1) и представляют кубит. Лазерные импульсы, передаваемые в резонатор по оптическим волокнам и управляемые классическим компьютером, используются для реализации гейтов и чтения выхода. Кулоновское отталкивание удерживает ионы на удалении ( пространственная избирательность), что позволяет готовить каждый ион отдельно в любой суперпозиции 0) и 1), при помощи лазерного импульса подходящей длительности и с тщательно подготовленной фазой. Это же кулоновское отталкивание позволяет производить коллективные возбуждения целого кластера, кванты которых называются фотонами. Такие возбуждения также производятся лазерными импульсами при соответствующих условиях резонанса. Получаемая резонансная избирательность в сочетании с пространственной избирательностью позволяют реализовать контроллируемое скрещенное состояние ионов, которое может быть использовано для моделирования двух - и трехбитовых гейтов. [24]
Фейнман [1982, 1986], по-видимому, первым предположил, что квантовая механика может привести к более мощным вычислительным средствам, чем машина Тьюринга. Он привел аргументы о том, почему квантовая механика находится за пределами вычислений, моделируемых на классическом компьютере. [25]
Мы опишем только массивы квантовых гейтов, или квантовые ациклические схемы, которые являются аналогом ациклических схем в теории классических компьютеров. Возможно то же самое будет справедливо и для различных моделей квантовых клеточных автоматов, но это пока не доказано. Это вселяет уверенность в том, что принадлежность к классу функций, вычислимых квантовым способом за полиномиальное время с малой вероятностью ошибки, не зависит от конкретной структуры квантового компьютера. [26]
Может оказаться, что следующий подход является более ценным. Выполнение эффективных квантовых алгоритмов, которые изучаются в настоящее время, может быть обеспечено одним или несколькими квантовыми чипами ( регистрами), управляемыми классическим компьютером. Значительная часть всей вычислительной работы, помимо управления квантовыми чипами, также возлагается на классический компьютер. Анализируя физическое устройство такой архитектуры, мы получаем прямой доступ к его классической компоненте ( электрической или нейронной сети), тогда как размещение его квантовой компоненты может составлять трудную задачу. Например, квантовые чипы в головном мозге могут быть представлены макромолекулами того типа, который рассматривается в некоторых теоретических моделях высокотемпературной сверхпроводимости. [27]
Мне кажется, что этот вопрос решен не окончательно и заслуживает дальнейшего исследования. В частности, хорошим кандидатом на роль контрпримера к количественному тезису Черча может быть турбулентность, поскольку нетривиальную динамику на многих масштабах длины трудно смоделировать на классическом компьютере. [28]
Эти изменения, конечно, не могут быть совершенно точными, они необходимо должны содержать небольшую неустранимую неточность. Если эта неточность постоянна ( то есть, не зависит от величины входных данных), тогда неизвестно, как на квантовом компьютере вычислить за полиномиальное время функцию, которая не может быть вычислена за полиномиальное время на классическом компьютере с генератором случайных чисел. Однако, если мы положим, что точность полиномиально растет с увеличением величины входных данных ( то есть, если число битов точности будет логарифмически расти по отношению к величине входных данных), то получим более мощный тип компьютера. [29]
В случае поиска в базе данных, вычисления, которые требуют времени Т на классическом компьютере, могут быть сделаны за время порядка / T на квантовом компьютере. Было бы очень интересно найти общий способ выделения классических алгоритмов, которые допускают такой вид / T квантового ускорения. В частности, классические компьютеры обычно решают полные NP-проблемы не вслепую, пока не встретится желательное решение, а делая перебор, который является значительно более продуманным и эффективным, и при этом остается достаточно приемлемым. До какой степени эти наиболее эффективные алгоритмы могут быть улучшены с помощью квантовых вычислений. [30]