Оказывается, используя законы квантовой механики, можно построить такие компьютеры, для которых задача факторизации (и многие другие!) не составит большого труда. Согласно оценкам, квантовый компьютер с памятью объемом всего лишь около 10 тысяч квантовых битов способен разложить 1000-значное число на простые множители в течение всего нескольких часов!

Задачи поиска.

Большой класс задач можно определять как задачи поиска вроде «найти x из множества возможных решений, такое, что утверждение Р(х) — истинно». Диа­пазон подобных задач широк: от поиска информации в базе данных до закраски графа. Например, задачу закраски графа можно рассматривать как поиск тако­го обозначения цветов вершин, что утверждение «все примыкающие вершины имеют разные цвета» является верным. Аналогично задача сортировки может быть рассмотрена, как поиск перестановки, для которой утверждение «переста­новка х переводит первоначальное состояние сортировки в желаемое» являлось бы верным.

В задаче неупорядоченного поиска ничего не известно о структуре простран­ства решений и об утверждении Р. Например, определение Р(х0) не дает никакой информации о возможном значении Р(х1) для х0 ¹ х1. В задаче упорядоченного поиска можно использовать информацию о пространстве поиска и об утвержде­нии Р.

Например, поиск по алфавитному списку является задачей упорядоченного поиска, и алфавитный порядок используется для построения алгоритма. В других случаях, скажем, в задачах, где нужно найти хотя бы одно решение (3 - SAT или закраска графа) структуру задачи можно использовать для построения эврис­тических алгоритмов, которые быстро дают решения для некоторых отдельных случаев. Но в общем случае, когда мы имеем задачу неупорядоченного поиска, лучшее, что можно сделать классическим путём — это последовательно про­верять истинность каждого утверждения P(x1) Для поискового пространства из N элементов обычная задача неупорядоченного поиска требует Q(N) прове­рок Р. На квантовом же компьютере, как показал Гровер, задачу неупорядо­ченного поиска можно решить с большой вероятностью производя около Q(ÖN) проверок Р. Таким образом, квантовый алгоритм Гровера [Гровер 1996] явля­ется заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска, выполняемый на классическом компьютере.

Оказывается, для неупорядоченного поиска алгоритм Гровера является оп­тимальным [Беннетт и др. 1997; Бауер и др. 1996; Залка 1997]. Однако для боль­шинства поисковых задач требуется упорядоченный поиск. Поскольку сущест­вуют классические эвристические алгоритмы, использующие упорядоченность, то можно ожидать, что существуют также и эффективные квантовые алгоритмы для упорядоченного поиска. Серф и др. [Серф и др. 1998] используют алгоритм Гровера вместо классического поиска внутри эвристического алгоритма, чтобы показать, что возможно квадратичное ускорение, когда речь идёт о решении тур-сложных задач.

Брассард и др. [Брассард и др. 1998], опираясь на алгоритм Гровера, пока­зали, что общий классический эвристический поиск имеет квантовый аналог с квадратичным ускорением.

Есть некоторая надежда на то, что для некоторых упорядоченных задач су­ществует ускорение большее, чем квадратичное. Возможно, подобные алгоритмы потребуют новых подходов, которые заключаются не просто в квантовом испол­нении классических алгоритмов. Если алгоритм Шора рассматривать в качест­ве поиска множителей, то он может послужить примером алгоритма, который достигает экспоненциального ускорения, используя структуру задачи (теорию чисел) нестандартным способом, уникальным для квантовых вычислений.

Тед Хогг также разработал несколько эвристических квантовых алгоритмов упорядоченного поиска. Его подход является совершенно неклассическим, в нём используются весьма нетривиальные свойства квантовых вычислений. Единст­венный минус его подхода заключается в том, что, как и во многих эвристи­ческих алгоритмах, использование упорядоченности является усложнённым, и при этом очень трудно определить вероятность получения верного ответа при одной итерации алгоритма. Следовательно, пока ещё не понятно, насколько эф­фективны алгоритмы Хогга. В классической теории эффективность эвристичес­ких алгоритмов оценивается с помощью эмпирического тестирования. Но, по­скольку, при моделировании квантовых операций на классическом компьютере наблюдается экспоненциальное замедление, то эмпирическое тестирование кван­товых алгоритмов сегодня невозможно, разве что за небольшими исключением. Алгоритм Хогга в применении к некоторым задачам упорядоченного поиска, яв­ляется более эффективным, чем алгоритм Гровера, но ускорение при этом явля­ется полиномиальным. С теоретической точки зрения — это менее интересно, но с практической — даже малое полиномиальное ускорение этих вычислитель­ных задач имеет огромное значение. До тех пор, пока не будет создано больших квантовых компьютеров или лучших приёмов для анализа таких алгоритмов, эффективность нельзя будет определить точно.

Современные разработки.

Август 2001 года.

Компании Hewlett-Packard и Массачусетский технологический институт (Massachusetts Institute of Technology) совместно инвестируют $2,5 млн. в создание компьютерного устройства, основанного на специфических кванто-механических свойствах.

Над созданием квантовых компьютеров уже долгое время работают ученые из IBM и других компаний и научных институтов, однако их широкое применение еще в далеком будущем. На сегодняшний день основным принципом работы квантового компьютера является вращение электронов или атомных ядер и их способность синхронного вращения в разных направлениях. Когда частица вращается "вверх", ее значение принимается за 1, "вниз" - 0. Уникальность квантовых компьютеров состоит в том, что частицы могут находиться в состоянии "наложения" - вращаться вверх и вниз.

Почти год назад, 15 августа 2000 года, корпорация IBM заявила об успешной разработке в этой области. Созданный учеными из IBM компьютер использует пять атомов в качестве процессора и памяти. По словам Айзека Ченга (Isaac Chuang), руководителя научной группы компании, новое устройство демонстрирует намного большие скорости при решении задач, нежели обычный компьютер. Специалисты утверждают, что компьютер, построенный на принципах квантовой механики исключает возможность ошибки.

Ныне используемый метод создания процессоров встретит на своем пути барьер в следующем десятилетии - способ литографии не позволит создавать чипы размером с молекулу. Технология микропроцессоров уже приближается к фундаментальным ограничениям и, следуя закону соучредителя Intel Гордона Мура, к 2010 - 2020 годам размеры транзистора должны уменьшиться до четырех-пяти атомов. Этот закон гласит, что плотность транзисторов в микросхеме удваивается каждые полтора года, и все последние 20 лет он неуклонно выполнялся. Поэтому основой уже недалекого будущего станет квантовая технология.

Нынешнии инвестиции HP и MIT - лишь часть их совместной исследовательской программы, в которую планируется вложить $25 млн. HP также сотрудничает с исследователями из Калифорнийского университета (University of California), занимающимися проблемой молекулярных компьютеров, которые, на взгляд специалистов, должны появится ранее квантовых.