Cтраница 3
В случае поиска в базе данных, вычисления, которые требуют времени Т на классическом компьютере, могут быть сделаны за время порядка fT на квантовом компьютере. Было бы очень интересно найти общий способ выделения классических алгоритмов, которые допускают такой вид fT квантового ускорения. В частности, классические компьютеры обычно решают полные NP-проблемы не вслепую, пока не встретится желательное решение, а делая перебор, который является значительно более продуманным и эффективным, и при этом остается достаточно приемлемым. До какой степени эти наиболее эффективные алгоритмы могут быть улучшены с помощью квантовых вычислений. [31]
Может оказаться, что следующий подход является более ценным. Выполнение эффективных квантовых алгоритмов, которые изучаются в настоящее время, может быть обеспечено одним или несколькими квантовыми чипами ( регистрами), управляемыми классическим компьютером. Значительная часть всей вычислительной работы, помимо управления квантовыми чипами, также возлагается на классический компьютер. Анализируя физическое устройство такой архитектуры, мы получаем прямой доступ к его классической компоненте ( электрической или нейронной сети), тогда как размещение его квантовой компоненты может составлять трудную задачу. Например, квантовые чипы в головном мозге могут быть представлены макромолекулами того типа, который рассматривается в некоторых теоретических моделях высокотемпературной сверхпроводимости. [32]
Мы осуществили самую простую возможную версию квантового алгоритма Дойча-Джозса ( Deutsch-Jozsa, D-J) [6], который определяет, является ли неизвестная функция постоянной или сбалансированной. Сбалансированная функция f ( x) О для точно половины ее аргументов, и f ( x) 1 для оставшихся. Чтобы с уверенностью определить, является ли функция постоянной или сбалансированной, на детерминированном классическом компьютере требуется до 2N - l 1 вызовов функции: даже если взять половину аргументов и найти f ( x) О для каждого, все еще нельзя с уверенностью заключить, что функция постоянна. Кливом и др. [20] и Аланом Таппом, позволяет квантовому компьютеру определять, является ли f ( x) постоянной или сбалансированной, используя только один вызов функции. [33]
Как мы знаем, возможная точность в операциях с квантовыми вычислениями, определяется не фундаментальными физическими законами, а свойствами материалов, из которых построен квантовый компьютер, и его архитектурой. В настоящее время неясно, какие типы архитектуры, если они вообще существуют, дадут высокую точность. Если точность квантового компьютера будет достаточно велика, чтобы сделать его более мощным, чем классический компьютер, то для понимания его потенциальных возможностей следует считать саму эту точность ресурсом переменной величины. Считать точность большой постоянной величиной ( хотя для любой данной машины это почти наверняка так) - это примерно то же самое, что трактовать классический компьютер как конечный автомат: поскольку память любого компьютера ограничена, эта точка зрения технически правильна, но не очень полезна. [34]
Однако, в науке о вычислениях имеется гораздо больше важных проблем, про которые не ясно, являются ли они полиномиально решаемыми по времени или NP-полными. Поэтому квантовые компьютеры, вероятно, не будут так широко использованы, пока на них не научатся решать NP-полные проблемы. Решение NP-проблемы в некотором смысле является Святым Граалем теоретической компьютерной науки, которую множество людей пытались решить на классическом компьютере. [35]
Существующие в настоящее время системы подготовки текстовых документов значительно отличаются друг от друга характеристиками, возможностями по вводу и редактированию текста, его форматированию и выводу на печать, а также по степени сложности освоения пользователем. При этом все текстовые процессоры используют различные метафоры для построения документов и различные способы представления документа для обозрения во время работы над ним. В WordPerfect, текстовом процессоре с наиболее длинной историей, до сих пор заметны черты, отражающие его первоначальную цель, - сделать пользование классическими компьютерами 1980 - х гг. столь же простым, как и пользование пишущей машинкой. Сложные документы в среде WordPerfect представлены в виде простых файлов с разметкой. [36]
То есть существует такая с, что если амплитуды в унитарной матрице, описывающей квантовый гейт, возмущаются не более, чем на c / t, то у квантового компьютера остается вполне реальный шанс дать желаемый ответ. Точно также необходимо, чтобы декогеренция была полиномиально мала по t, для того, чтобы иметь после t шагов вычислений разумную вероятность успеха. Однако, построение квантового компьютера с высоким уровнем точности и низким уровнем декогерентности, предназначенного для реализации длинных вычислений, может являть собой фундаментальную проблему для экспериментальной физики. В классических компьютерах вероятностные ошибки преодолеваются не только за счет средств оборудования, но и за счет программного обеспечения, введения избыточности и кодов, корректирующих ошибки. По всей видимости, метод избыточности для квантовых вычислений не годится в силу существования теоремы о невозможности клонирования битов [ Peres, 1993, § 9 - 4 ], но этот аргумент не отрицает возможности применения более сложных программных методов повышения точности и уменьшения декогеренции. [37]
Когда классический детерминированный компьютер Тьюринга решает задачу, он всегда делает это, вычисляя функцию. Тот множитель, который она ищет, может быть определен с помощью дополнительного условия, уменьшая работу по вычислению функции. Следовательно, при решении задач классический компьютер не может помочь в выполнении более сложной вычислительной задачи, чем та, которая была поставлена. [38]
Настоящая работа знакомит с тем, как можно использовать квантовую механику для усовершенствования вычислений. Проблема, которая здесь рассматривается - факторизация большого числа, решение которой является экспоненциально сложной для обычного компьютера. В качестве вступления мы дадим обзор стандартных инструментов вычисления, универсальных гейтов и машин. Эти идеи впервые появились в теории классических компьютеров без диссипации, а затем были применены к квантовым компьютерам. [39]
Как мы знаем, возможная точность в операциях с квантовыми вычислениями, определяется не фундаментальными физическими законами, а свойствами материалов, из которых построен квантовый компьютер, и его архитектурой. В настоящее время неясно, какие типы архитектуры, если они вообще существуют, дадут высокую точность. Если точность квантового компьютера будет достаточно велика, чтобы сделать его более мощным, чем классический компьютер, то для понимания его потенциальных возможностей следует считать саму эту точность ресурсом переменной величины. Считать точность большой постоянной величиной ( хотя для любой данной машины это почти наверняка так) - это примерно то же самое, что трактовать классический компьютер как конечный автомат: поскольку память любого компьютера ограничена, эта точка зрения технически правильна, но не очень полезна. [40]
Определение массивов квантовых гейтов требует реализации обратимых вычислений. Другими словами, зная квантовое состояние на выходных проводах гейта, можно однозначно сказать, какое состояние было на входе. Это отражение того факта, что несмотря на макроскопическую стрелу времени, законы физики оказываются полностью обратимыми. Как может показаться, все, построенное по законам физики, должно быть обратимым. Однако, классические компьютеры обходят это утверждение благодаря диссипации энергии, что делает такой компьютер термодинамически необратимым. В квантовом компьютере это оказывается невозможно, так как суперпозиция квантовых состояний должна поддерживаться в течение всего вычисления. Это требует дополнительных затрат при проведении классических вычислений на квантовом компьютере, какие иногда требуется производить в подпрограммах квантовых вычислений. [41]
Цифровой компьютер, как это общепринято считать, является эффективным универсальным вычислительным устройством. Также считается, что он способен воспроизвести работу любого физического вычислительного устройства, причем требуемое для этого время возрастет не более, чем на полиномиальный множитель. В данной статье рассматриваются разложение целых чисел на простые множители и нахождение дискретных логарифмов. Хорошо известно, что обе эти проблемы являются сложными для классического компьютера и являются основой различных предлагаемых криптографических систем. В работе предлагаются эффективные алгоритмы для решения этих двух проблем на квантовом компьютере. Эти алгоритмы являются полиномиальными по числу шагов по отношения к размеру входного слова, другими словами, по отношению к количеству цифр, содержащихся в слове, которое необходимо факторизовать. [42]
Однако, если разрешить квантовую суперпозицию состояний логических элементов, становятся возможными быстрые решения некоторых трудных задач. Один такой пример - поиск полным перебором: нужно опознать элемент, обладающий некоторым специфическим свойством, из неупорядоченного списка из 7V элементов. Как только элемент проверяется, легко сказать, обладает он или нет этим свойством. Однако список не имеет никакой известной структуры, по которой можно бы было предвидеть, какой из элементов обладает этим свойством с большей вероятностью. При таких условиях любому классическому алгоритму, как вероятностному, так и детерминистическому, потребуется проверить по крайней мере 0.57V элементов, чтобы добиться успеха с вероятностью 0.5. Квантовые компьютеры могут находиться в суперпозиции состояний и одновременно экзаменовать множество элементов; значит, имеется возможность искать быстрее, чем с классическими компьютерами. [43]
Однако, если разрешить квантовую суперпозицию состояний логических элементов, становятся возможными быстрые решения некоторых трудных задач. Один такой пример - поиск полным перебором: нужно опознать элемент, обладающий некоторым специфическим свойством, из неупорядоченного списка из N элементов. Как только элемент проверяется, легко сказать, обладает он или нет этим свойством. Однако список не имеет никакой известной структуры, по которой можно бы было предвидеть, какой из элементов обладает этим свойством с большей вероятностью. При таких условиях любому классическому алгоритму, как вероятностному, так и детерминистическому, потребуется проверить по крайней мере 0.57V элементов, чтобы добиться успеха с вероятностью 0.5. Квантовые компьютеры могут находиться в суперпозиции состояний и одновременно экзаменовать множество элементов; значит, имеется возможность искать быстрее, чем с классическими компьютерами. [44]
Еще с доевклидовых времен известно, что любое целое число п может быть однозначно представлено в виде произведения простых чисел. Этот результат чрезвычайно важен для изучения эффективности факторизационных алгоритмов. Lenstra and Lenstra, 1993 ] тратит на представление числа в виде простых множителей асимптотически exp ( c ( logn) 1 / 3 ( loglogn) 2 / 3) шагов при любой константе с. В силу того, что входные данные, число п, длиной только logn бит, этот алгоритм является экспоненциальным по времени. Конечно, такие постпроцедурные шаги можно было бы осуществить и на квантовом компьютере, но нет причин не использовать классический компьютер, если он для этой задачи более эффективен. [45]