Cтраница 3
Действительно, выполнение N последовательных вставок - не самый эффективный способ построения сортирующего дерева, состоящего из N элементов. В следующем разделе при обсуждении реализации классического алгоритма пирамидальной сортировки этим двум вопросам уделяется особое внимание. [31]
В случае поиска в базе данных, вычисления, которые требуют времени Т на классическом компьютере, могут быть сделаны за время порядка / T на квантовом компьютере. Было бы очень интересно найти общий способ выделения классических алгоритмов, которые допускают такой вид / T квантового ускорения. В частности, классические компьютеры обычно решают полные NP-проблемы не вслепую, пока не встретится желательное решение, а делая перебор, который является значительно более продуманным и эффективным, и при этом остается достаточно приемлемым. До какой степени эти наиболее эффективные алгоритмы могут быть улучшены с помощью квантовых вычислений. [32]
В случае поиска в базе данных, вычисления, которые требуют времени Т на классическом компьютере, могут быть сделаны за время порядка fT на квантовом компьютере. Было бы очень интересно найти общий способ выделения классических алгоритмов, которые допускают такой вид fT квантового ускорения. В частности, классические компьютеры обычно решают полные NP-проблемы не вслепую, пока не встретится желательное решение, а делая перебор, который является значительно более продуманным и эффективным, и при этом остается достаточно приемлемым. До какой степени эти наиболее эффективные алгоритмы могут быть улучшены с помощью квантовых вычислений. [33]
Для решения данной задачи предлагается использовать обучающийся генетический алгоритм LGAP ( Learning Genetic Algorithm for Prognosis), наиболее подробно описанный в работе [4], который извлекает закономерности ( знания) из специфичного рода данных и использует эти знания для краткосрочного прогнозирования. Применение данного метода обусловлено тем, что большинство классических алгоритмов прогнозирования временных рядов не учитывают специфику и сложность задачи многофакторного прогнозирования развития социально-экономических объектов. В основном они рассчитаны на прогноз в одномерном случае и не учитывают взаимосвязей, которые существуют между различными показателями, а тем более между объектами и поэтому носят сугубо ограниченный, локальный характер и не позволяют давать достоверный прогноз. Те же методы, которые способны учитывать многомерный случай имеют слишком большое время работы и их работа практически невозможна без серьезного предварительного анализа данных. Поэтому они не могут применяться в силу ограниченности специалистов математиков-аналитиков и вычислительных ресурсов. [34]
Схематически описывается модель квантового компьютера, а также некоторые тонкости в его программировании. Алгоритм Шора [1, 2] эффективной факторизации чисел на квантовом компьютере представлен в двух частях: квантовая процедура внутри алгоритма и классический алгоритм, который требует квантовую процедуру. [35]
Однако указанный алгоритм допускает дальнейшие упрощения. Полуоткрытая модель ( 4.50 J - (4.53) может быть сведена к эквивалентной замкнутой модели с последующим применением для новой модели классического алгоритма двумерной балансировки. [36]
О БПФ написаны тома, и, как никакое другое изобретение, разработка этого алгоритма изменила цифровую обработку сигналов, сделав доступной всю мощь анализа Фурье. В этой главе мы покажем, почему наиболее популярные алгоритмы БПФ ( которые называют БПФ по основанию 2) имеют преимущества над классическим алгоритмом ДПФ, дадим ряд рекомендаций, позволяющих получить больше практической пользы от БПФ, и приведем ссылки на листинги исходных текстов программ на разных языках программирования. Для читателей, желающих узнать некоторые детали, мы завершаем эту главу выводом алгоритма БПФ по основанию 2 и демонстрацией нескольких способов реализации БПФ. [37]
Предложен новый полиномиальный по времени квантовый алгоритм, использующий квантовое преобразование Фурье, определяющий собственные значения и собственные функции оператора Гамильтона. Алгоритм может быть применен в тех случаях ( обычно имеющих место в физических и химических задачах ab initio), для которых все известные классические алгоритмы требуют экспоненциального времени вычисления. Рассмотрено применение алгоритма к конкретным задачам, и сделан вывод, что интересные задачи атомной физики, которые трудно решить классическими методами, могут быть разрешены с использованием от 50 до 100 квантовых битов. [38]
В качестве другой мотивации можно привлечь крайне спекулятивные, но интригующие предположения о том, что наш головной мозг на самом деле - квантовый компьютер. Например, недавний прогресс в написании эффективного программного обеспечения для игры в шахматы ( компьютер Deep Blue) показывает, что для моделирования уровня мирового чемпионата с использованием только классических алгоритмов нужно уметь проанализировать около 106 позиций в секунду, и использовать около 1010 байтов памяти. Поскольку характерное время срабатывания нейрона - около 10 - 3 сек, очень трудно объяснить с точки зрения классической физики как головной мозг мог бы выполнить эту работу и играть в шахматы столь же успешно, как Карпов. Менее впечатляющая, но не менее ресурсоемкая задача - генерация и восприятие речи, которая без труда выполняется головным мозгом любым из миллиардов людей, но пока представляет непосильную задачу для современных компьютеров, использующих классические алгоритмы. [39]
В 1879 году сэр Артур Кэли поставил задачу итерирования комплексных функций [6], которая позднее стимулировала исследования Гастона Жюлиа по проблемам теории множеств, названных теперь его именем. Проблема Кэли заключается в исследовании сходимости классического алгоритма Ньютона нахождения кубических корней, но при условии, что вещественные числа заменяются на комплексные. [40]
В статье [174] демонстрируются два основных принципа, которые используются для получения некоторых базисных алгоритмов решения так называемой координирующей задачи. Эти алгоритмы состоят в решении последовательности вспомогательных задач, чьи решения сходятся к оптимальному решению координирующей задачи. Делая частные выборы для вспомогательных задач, можно получить или классические алгоритмы ( градиентный, Ньютона, Уд завы) или двухуровневые алгоритмы декомпозиции. Дается систематический способ получения новых алгоритмов. [41]
Основной используемый конструктивный блок представляет собой массив гейтов, который берет число Ъ на входе, дает Ъ с ( mod n) на выходе. Заметим, что здесь b поступает в массив гейтов на вход, в то время как сип встроены в структуру массива квантовых гейтов. Так как сложение по ( mod n) вычислимо по классическим алгоритмам в O ( logn) шагов, такой обратимый массив квантовых гейтов может состоять только из O ( logn) гейтов и O ( logn) рабочих битов, используя методы, ранее описанные в этом разделе. [42]
Квантовая механика дает возможность ускорить процесс поиска среди неупорядоченных данных. Например, представим себе телефонную книгу, в которой содержится N фамилий, расположенных совершенно произвольным образом. Чтобы найти чей-либо телефон с вероятностью большей чем 50 %, любой классический алгоритм ( как детерминистический, так и вероятностный) потребует обращения к базе данных как минимум 0.57V раз. Квантово-механическая система может находиться в суперпозиции состояний и одновременно проверять множество имен. При надлежащем задании программы поиска вычисления искомого состояния на каждом этапе усиливают друг друга, в то время как остальные интерферируют случайным образом. В результате нужный телефонный номер может быть найден лишь за O ( v V) обращений к базе данных. [43]
Квантовая механика дает возможность ускорить процесс поиска среди неупорядоченных данных. Например, представим себе телефонную книгу, в которой содержится N фамилий, расположенных совершенно произвольным образом. Чтобы найти чей-либо телефон с вероятностью большей чем 50 %, любой классический алгоритм ( как детерминистический, так и вероятностный) потребует обращения к базе данных как минимум 0.57V раз. Квантово-механическая система может находиться в суперпозиции состояний и одновременно проверять множество имен. При надлежащем задании программы поиска вычисления искомого состояния на каждом этапе усиливают друг друга, в то время как остальные интерферируют случайным образом. В результате нужный телефонный номер может быть найден лишь за O ( / N) обращений к базе данных. [44]
В настоящее время все известные вычислительные задачи, которые могут быть выполнены более эффективно с помощью квантового параллелизма, чем с помощью любого классического метода, имеют два основных свойства. Во-первых, нет уверенности в том, что ответ будет получен за заданный промежуток времени, т.е. существует некоторая вероятность того, что программа сообщит о неудаче, уничтожая информацию о функции /, поэтому в общем случае придется все повторять несколько раз, прежде чем будет получен ответ. Во-вторых, хотя в некоторых случаях вычисления производятся быстрее, чем в любом классическом алгоритме, в среднем квантовый алгоритм не эффективнее классического. Можно показать ( Дойч, 1985), что второе свойство должно проявиться, по крайней мере, для одного выбранного входного значения при квантовом вычислении любой функции. [45]