Основные понятия и принципы квантовых вычислений. Квантовые вычисления Компьютер на бумаге

Сегодня я хотел бы начать публикацию серии заметок про эту животрепещущую тему, по которой недавно вышла моя новая книга , а именно введение в понимание квантовой вычислительной модели. Я благодарю моего доброго товарища и коллегу Александра за предоставленную возможность размещения в его блоге гостевых постов на эту тему.

Я постарался сделать эту кратчайшую заметку как можно более простой с точки зрения понимания неподготовленным читателем, который, однако, хотел бы понять, что такое квантовые вычисления. Тем не менее, от читателя требуется владеть базовым пониманием информатики. Ну и общее математическое образование тоже не помещало бы:). В статье нет формул, всё объясняется словами. Тем не менее, все вы можете задавать мне вопросы в комментариях, и я постараюсь объяснять, как только могу.

Что такое квантовые вычисления?

Начнём с того, что квантовые вычисления - это новая очень модная тема, которая там у них развивается семимильными шагами по нескольким направлениям (а у нас, как всякая фундаментальная наука пребывает в запустении и отдана на откуп нескольким учёным, сидящим в своих башнях из слоновой кости). И вот уже говорят о появлении первых квантовых компьютеров (D-Wave, но это не универсальный квантовый компьютер), ежегодно публикуются новые квантовые алгоритмы, создаются языки квантового программирования, сумрачный гений Международных Деловых Машин в тайных подземных лабораториях производит квантовые вычисления на десятках кубитов.

Что же это такое? Квантовые вычисления - это вычислительная модель, которая отличается от модели Тьюринга и фон Неймана, и предполагается, что для некоторых задач она является более эффективной. По крайней мере найдены задачи, для которых модель квантовых вычислений даёт полиномиальную сложность, в то время как для классической вычислительной модели неизвестно алгоритмов, которые имели бы сложность, ниже экспоненциальной (но, с другой стороны, пока ещё не доказано, что таких алгоритмов не существует).

Как такое может быть? Всё просто. Квантовая вычислительная модель основана на нескольких довольно простых правилах преобразования входной информации, которые обеспечивают массовую параллелизацию вычислительных процессов. Другими словами, можно одновременно вычислить значение функции для всех её аргументов (и это будет единственный вызов функции). Это достигается специальной подготовкой входных параметров и специальным же видом функции.

Светитель Проц учит, что всё это суть синтаксическая манипуляция с математическими символами, за которой, по сути, нет никакого смысла. Есть формальная система с правилами преобразования входа в выход, и эта система позволяет при помощи последовательного применения этих правил получать из входных данных выходные. Всё это в конечном итоге сводится к перемножению матрицы и вектора. Да, да, да. Вся модель квантовых вычислений основана на одной простой операции - умножении матрицы на вектор, в результате чего на выходе получается другой вектор.

Светитель Халикаарн в противоположность учит, что существует объективный физический процесс, который выполняет указанную операцию, и только лишь существование которого и обуславливает возможность массовой параллелизации вычислений функции. То, что мы воспринимаем это как умножение матрицы на вектор, является всего лишь способом нашего далеко не совершенного отражения объективной реальности в нашем разуме.

Мы в нашей научной лаборатории имени светителей Проца и Халикаарна объединяем эти два подхода и говорим, что модель квантовых вычислений есть математическая абстракция, которая отражает объективный процесс. В частности, числа в векторах и матрицах являются комплексными, хотя это совершенно не увеличивает вычислительную мощность модели (она бы была такой же мощной и с действительными числами), однако выбраны именно комплексные числа потому, что найден объективный физический процесс, который осуществляет такие преобразования, как описывает модель, и в котором используются именно комплексные числа. Этот процесс называется унитарной эволюцией квантовой системы.

В основе квантовой вычислительной модели лежит понятие кубита. Это практически то же самое, что и бит в классической теории информации, однако кубит может одновременно принимать несколько значений. Говорят, что кубит находится в суперпозиции своих состояний, то есть значение кубита есть линейная комбинация его базовых состояний, и коэффициенты при базовых состояниях как раз являются комплексными числами. Базовыми же состояниями являются известные по классической теории информации значения 0 и 1 (в квантовых вычислениях их принято обозначать |0> и |1>).

Пока не очень-то и понятно, в чём фишка. А фишка вот в чём. Суперпозиция одного кубита записывается как A|0> + B|1>, где A и B - некоторые комплексные числа, единственное ограничение на которые заключается в том, что сумма квадратов их модулей всегда должна равняться 1. А если рассмотреть два кубита? Два бита могут получать 4 возможных значения: 00, 01, 10 и 11. Резонно предположить, что два кубита представляют собой суперпозицию четырёх базовых значений: A|00> + B|01> + C|10> + D|11>. И так оно и есть. Три кубита представляют собой суперпозицию восьми базовых значений. Другими словами, квантовый регистр из N кубитов одновременно хранит в себе 2N комплексных чисел. Ну а с математической точки зрения это есть 2N -мерный вектор в комплекснозначном пространстве. Именно этим достигается экспоненциальная мощность модели квантовых вычислений.

Далее функция, которая применяется к входным данным. Поскольку теперь входные данные представляют собой суперпозицию всех возможных значений входного аргумента, функция должна быть преобразована в такой вид, чтобы принять такую суперпозицию и обработать её. Тут тоже всё более или менее просто. В рамках модели квантовых вычислений каждая функция представляет собой матрицу, на которую накладывается одно ограничение - она должна быть эрмитовой. Это значит, что при умножении этой матрицы на свою эрмитово-сопряжённую, должна получиться единичная матрица. Эрмитово-сопряжённая матрица получается при помощи транспонирования исходной матрицы и заменой всех её элементов на их комплексно-сопряжённые. Это ограничение следует из упомянутого ранее ограничения на квантовый регистр. Дело в том, что если такую матрицу умножить на вектор квантового регистра, то в результате получится новый квантовый регистр, сумма квадратов модулей комплекснозначных коэффициентов при квантовых состояниях которого всегда равна 1.

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

Что происходит дальше? Вот у нас есть входной вектор, который представляет собой суперпозицию различных вариантов значений входного параметра функции. Есть функция в виде эрмитовой матрицы. Квантовый алгоритм представляет собой умножение матрицы на вектор. В результате получается новый вектор. Что же это за ерунда-то такая?

Дело в том, что в модели квантовых вычислений есть ещё одна операция, которая называется измерением . Мы можем измерить вектор и получить из него конкретное значение кубита. То есть суперпозиция схлопывается в конкретное значение. И вероятность получения того или иного значения равна квадрату модуля комплекснозначного коэффициента. И теперь понятно, почему сумма квадратов должна равняться 1, поскольку при измерении всегда будет получено какое-то конкретное значение, а потому сумма вероятностей их получения равна единице.

То есть что получается? Имея N кубитов можно одновременно обработать 2N комплексных чисел. И в выходном векторе будут результаты обработки всех этих чисел одновременно. В этом мощь модели квантовых вычислений. Но получить можно только одно значение, и оно может быть каждый раз различное в зависимости от распределения вероятностей. В этом ограничение модели квантовых вычислений.

Суть квантового алгоритма заключается в следующем. Создаётся равновероятностная суперпозиция всех возможных значений входного параметра. Эта суперпозиция подаётся на вход функции. Далее по результатам её выполнения делается вывод о свойствах этой функции. Дело в том, что мы не можем получить все результаты, но вот сделать выводы о свойствах функции можем вполне. И в следующем разделе будут показаны несколько примеров.

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

Алгоритм Дойча

Это первый алгоритм, который был разработан для того, чтобы показать суть и эффективность квантовых вычислений. Задача, которую решает этот алгоритм, совсем оторвана от реальности, однако на ней как раз можно показать базовый принцип, положенный в основу модели.

Итак, пусть есть некоторая функция, которая получает на вход один бит и возвращает на выходе тоже один бит. Честно говоря, таких функций может быть всего 4. Две из них являются константными, то есть одна всегда возвращает 0, а другая всегда возвращает 1. Две другие являются сбалансированными, то есть возвращают 0 и 1 в равных количествах случаев. Вопрос: как за один вызов этой функции определить, константная она или сбалансированная?

Очевидно, что в классической вычислительной модели этого сделать нельзя. Необходимо дважды вызвать функцию и сравнить результаты. А вот в модели квантовых вычислений это сделать можно, поскольку функция будет вызвана только один раз. Посмотрим…

Как уже было написано, мы подготовим равновероятностную суперпозицию всех возможных значений входного параметра функции. Поскольку на входе у нас один кубит, то его равновероятностная суперпозиция готовится при помощи одного применения гейта Адамара (это такая специальная функция, которая и готовит равновероятностные суперпозиции:). Далее снова применяется гейт Адамара, который работает таким образом, что если ему на вход подаётся равновероятностная суперпозиция, то он преобразует её назад в состояния |0> или |1> в зависимости от того, в какой фазе находится равновероятностная суперпозиция. После этого производится измерение кубита, и если он равен |0>, то рассматриваемая функция константна, а если |1>, то сбалансирована.

Что получается? Как уже было сказано, при измерении мы не можем получить все значения функции. Но мы можем сделать определённые выводы о её свойствах. Задача Дойча как раз и спрашивает о свойстве функции. И это свойство очень простое. Ведь как выходит? Если функция константна, то сложение по модулю 2 всех её выходных значений всегда даёт 0. Если же функция сбалансирована, то сложение по модулю 2 всех её выходных значений всегда даёт 1. Именно этот результат мы и получили в результате выполнения алгоритма Дойча. Мы не знаем, какое именно значение вернула функция на равновероятностной суперпозиции всех входных значений. Мы знаем только, что это тоже суперпозиция результатов, и если теперь эту суперпозицию преобразовать специальным образом, то будут сделаны однозначные выводы о свойстве функции.

Вот как-то так.

Алгоритм Гровера

Другой алгоритм, который показывает квадратичный выигрыш по сравнению с классической вычислительной моделью, решает более приближённую к реальности задачу. Это алгоритм Гровера, или, как называет его сам Лов Гровер, алгоритм поиска иголки в стоге сена. Этот алгоритм основан на другом принципе, лежащем в основе квантовых вычислений, а именно амплификации .

Уже упоминалась некая фаза, которая может быть у квантового состояния в составе кубита. Как таковой фазы нет в классической модели, это что-то новенькое именно в рамках квантовых вычислений. Фазу можно понимать как знак у коэффициента при квантовом состоянии в суперпозиции. Алгоритм Гровера основан на том, что специально подготовленная функция меняет фазу у состояния |1>.

Алгоритм Гровера решает обратную задачу. Если есть неупорядоченый набор данных, в котором надо найти один элемент, удовлетворяющий критерию поиска, алгоритм Гровера поможет это сделать эффективнее, чем простой перебор. Если простой перебор решает задачу за O(N) обращений к функции, то алгоритм Гровера эффективно находит заданный элемент за O(√N ) обращений к функции.

Алгоритм Гровера состоит из следующих шагов:

1. Инициализация начального состояния . Опять готовится равновероятностная суперпозиция всех входных кубитов.

2. Применение итерации Гровера . Данная итерация состоит из последовательного применения функции поиска (она определяет критерий поиска элемента) и специального гейта диффузии. Гейт диффузии меняет коэффициенты при квантовых состояниях, вращая их вокруг среднего. Тем самым производится амплификация, то есть увеличение амплитуды искомого значения. Фишка в том, что осуществить применение итерации необходимо определённое количество раз (√2n ), иначе алгоритм вернёт не те результаты.

3. Измерение . После измерения входного квантового регистра с большой вероятностью будет получен искомый результат. Если необходимо увеличить достоверность ответа, то алгоритм прогоняется несколько раз и вычисляется совокупная вероятность правильного ответа.

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

Тем не менее, уже нельзя говорить о том, что учёные продолжают сидеть в своей башне из слоновой кости. Несмотря на то, что многие квантовые алгоритмы разрабатываются для каких-то странных и непонятных матаноподобных задач (например, определение порядка идеала конечного кольца), уже разработан ряд квантовых алгоритмов, которые решают очень даже прикладные задачи. В первую очередь это задачи из области криптографии (компрометация различных криптографических систем и протоколов). Далее идут типовые математические задачи на графах и матрицах, при этом такие задачи имеют очень большую область применения. Ну и есть ряд алгоритмов аппроксимации и эмуляции, которые используют аналоговую составляющую модели квантовых вычислений.

Еще пять лет назад о квантовых компьютерах знали разве что специалисты в области квантовой физики. Однако в последние годы количество публикаций в Интернете и в специализированных изданиях, посвященных квантовым вычислениям, возрастало лавинообразно. Тема квантовых вычислений стала популярной и вызвала множество различных мнений, далеко не всегда соответствующих действительности.
В настоящей статье мы постараемся как можно более доступно рассказать о том, что же такое квантовый компьютер и на какой стадии находятся современные разработки в этой области.

Ограниченные возможности современных компьютеров

О квантовых компьютерах и квантовых вычислениях часто говорят как об альтернативе кремниевым технологиям создания микропроцессоров, что, в общем-то, не совсем верно. Собственно, почему вообще приходится искать альтернативу современным компьютерным технологиям? Как показывает вся история существования компьютерной индустрии, вычислительная мощность процессоров возрастает экспоненциально. Ни одна другая индустрия не развивается столь бурными темпами. Как правило, когда говорят о темпах роста вычислительной мощности процессоров, вспоминают так называемый закон Гордона Мура, выведенный в апреле 1965 года, то есть всего через шесть лет после изобретения первой интегральной схемы (ИС).

По просьбе журнала «Электроникс» (“Electronics”) Гордон Мур написал статью, приуроченную к 35-й годовщине издания. Он сделал прогноз относительно того, как будут развиваться полупроводниковые устройства в течение ближайших десяти лет. Проанализировав темпы развития полупроводниковых устройств и экономические факторы за прошедшие шесть лет, то есть начиная с 1959 года, Гордон Мур предположил, что к 1975 году количество транзисторов в одной интегральной микросхеме составит 65 тыс.

Фактически по прогнозу Мура количество транзисторов в одной микросхеме за десять лет должно было увеличиться более чем в тысячу раз. В то же время это означало, что каждый год количество транзисторов в одной микросхеме должно удваиваться.

Впоследствии в закон Мура были внесены коррективы (дабы соотнести его с реальностью), но смысл от этого не поменялся: количество транзисторов в микросхемах увеличивается экспоненциально. Естественно, увеличение плотности размещения транзисторов на кристалле возможно лишь за счет сокращения размеров самих транзисторов. В связи с этим уместен вопрос: до какой степени можно уменьшать размеры транзисторов? Уже сейчас размеры отдельных элементов транзисторов в процессорах сопоставимы с атомарными, например ширина диоксидного слоя, отделяющего диэлектрик затвора от канала переноса заряда, составляет всего несколько десятков атомарных слоев. Понятно, что существует чисто физический предел, делающий невозможным дальнейшее уменьшение размеров транзисторов. Даже если предположить, что в будущем они будут иметь несколько иную геометрию и архитектуру, теоретически невозможно создать транзистор или подобный ему элемент с размером менее 10 -8 см (диаметр атома водорода) и рабочей частотой более 10 15 Гц (частота атомных переходов). А потому, хотим мы того или нет, неизбежен тот день, когда закон Мура придется сдать в архив (если, конечно, его в очередной раз не подкорректируют).

Ограниченные возможности по наращиванию вычислительной мощности процессоров за счет сокращения размеров транзисторов - это лишь одно из узких мест классических кремниевых процессоров.

Как мы увидим в дальнейшем, квантовые компьютеры никоим образом не представляют собой попытку решения проблемы миниатюризации базовых элементов процессоров.

Решение проблемы миниатюризации транзисторов, поиск новых материалов для создания элементной базы микроэлектроники, поиск новых физических принципов для приборов с характерными размерами, сравнимыми с длиной волны Де-Бройля, имеющей величину порядка 20 нм, - эти вопросы стоят на повестке дня уже почти два десятилетия. В результате их решения была разработана нанотехнология. Серьезной проблемой, с которой пришлось столкнуться при переходе в область наноэлектронных устройств, является уменьшение рассеиваемой энергии в процессе вычислительных операций. Мысль о возможности «логически обратимых» операций, не сопровождающихся рассеянием энергии, впервые высказал Р.Ландауер еще в 1961 году. Существенный шаг в решении данной задачи был сделан в 1982 году Ч.Беннеттом, который теоретически доказал, что универсальный цифровой компьютер может быть построен на логически и термодинамически обратимых вентилях таким образом, что энергия будет рассеиваться только за счет необратимых периферийных процессов ввода информации в машину (приготовление исходного состояния) и соответственно вывода из нее (считывание результата). К типичным обратимым универсальным вентилям относятся вентили Фредкина и Тоффоли.

Другая проблема, связанная с классическими компьютерами, кроется в самой фон-неймановской архитектуре и двоичной логике всех современных процессоров. Все компьютеры, начиная с аналитической машины Чарльза Бэббиджа и заканчивая современными суперкомпьютерами, основаны на одних и тех же принципах (фон-неймановская архитектура), которые были разработаны еще в 40-х годах прошлого столетия.

Любой компьютер на программном уровне оперирует битами (переменными, принимающими значение 0 или 1). С применением логических элементов-вентилей над битами выполняются логические операции, что позволяет получить определенное конечное состояние на выходе. Изменение состояния переменных производится с помощью программы, которая определяет последовательность операций, каждая из которых использует небольшое число бит.

Традиционные процессоры выполняют программы последовательно. Несмотря на существование многопроцессорных систем, многоядерных процессоров и различных технологий, направленных на повышение уровня параллелизма, все компьютеры, построенные на основе фон-неймановской архитектуры, являются устройствами с последовательным режимом выполнения команд. Все современные процессоры реализуют следующий алгоритм обработки команд и данных: выборка команд и данных из памяти и исполнение инструкций над выбранными данными. Этот цикл повторяется многократно и с огромной скоростью.

Однако фон-неймановская архитектура ограничивает возможность увеличения вычислительной мощности современных ПК. Типичный пример задачи, которая оказывается не по силам современным ПК, - это разложение целого числа на простые множители (простым называется множитель, который делится без остатка только на себя и на 1).

Если требуется разложить на простые множители число х , имеющее n знаков в двоичной записи, то очевидный способ решения этой задачи заключается в том, чтобы попробовать последовательно разделить его на числа от 2 до Для этого придется перебрать 2 n/2 вариантов. К примеру, если рассматривается число, у которого 100 000 знаков (в двоичной записи), то потребуется перебрать 3x10 15 051 вариантов. Если предположить, что для одного перебора требуется один процессорный такт, то при скорости в 3 ГГц для перебора всех чисел будет нужно время, превышающее возраст нашей планеты. Существует, правда, хитроумный алгоритм, решающий ту же задачу за exp(n 1/3) шагов, но даже в этом случае с задачей разложения на простые множители числа, имеющего миллион знаков, не справится ни один современный суперкомпьютер.

Задача разложения числа на простые множители относится к классу задач, которые, как говорят, не решаются за полиномиальное время (NP-полная задача - Nondeterministic polynomial-time complete). Такие задачи входят в класс невычисляемых в том смысле, что они не могут быть решены на классических компьютерах за время, полиномиально зависящее от числа битов n , представляющих задачу. Если говорить о разложении числа на простые множители, то по мере увеличения разрядности числа время, необходимое для решения задачи, возрастает экспоненциально, а не полиномиально.

Забегая вперед, отметим, что с квантовыми вычислениями связывают перспективы решения NP-полных задач за полиномиальное время.

Квантовая физика

Конечно, квантовая физика слабо связана с тем, что называют элементной базой современных компьютеров. Однако, говоря о квантовом компьютере, избежать упоминания некоторых специфических терминов квантовой физики просто невозможно. Мы понимаем, что далеко не все изучали легендарный третий том «Теоретической физики» Л.Д.Ландау и Е.М.Лифшица и для многих такие понятия, как волновая функция и уравнение Шредингера, - это что-то из потустороннего мира. Что же касается специфического математического аппарата квантовой механики, то это сплошные формулы и малопонятные слова. Поэтому мы постараемся придерживаться общедоступного уровня изложения, избегая по возможности тензорного анализа и прочей специфики квантовой механики.

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

История квантовой физики началась 14 декабря 1900 года. Именно в этот день немецкий физик и будущий нобелевский лауреат Макс Планк доложил на заседании Берлинского физического общества о фундаментальном открытии квантовых свойств теплового излучения. Так в физике появилось понятие кванта энергии, а среди других фундаментальных постоянных - постоянная Планка.

Открытие Планка и появившаяся затем, в 1905 году, теория фотоэлектрического эффекта Альберта Эйнштейна, а также создание в 1913 году Нильсом Бором первой квантовой теории атомных спектров стимулировали создание и дальнейшее бурное развитие квантовой теории и экспериментальных исследований квантовых явлений.

Уже в 1926 году Эрвин Шредингер сформулировал свое знаменитое волновое уравнение, а Энрико Ферми и Поль Дирак получили квантово-статистическое распределение для электронного газа, учитывающее заполнение отдельных квантовых состояний.

В 1928 году Феликс Блох произвел анализ квантово-механической задачи о движении электрона во внешнем периодическом поле кристаллической решетки и показал, что электронный энергетический спектр в кристаллическом твердом теле имеет зонную структуру. Фактически это стало началом нового направления в физике - теории твердого тела.

Весь XX век - это период интенсивного развития квантовой физики и всех тех разделов физики, для которых квантовая теория стала прародителем.

Появление квантовых вычислений

Идея использования квантовых вычислений впервые была высказана советским математиком Ю.И. Маниным в 1980 году в его знаменитой монографии «Вычислимое и невычислимое». Правда, интерес к его труду возник лишь два года спустя, в 1982 году, после опубликования статьи на ту же тему американского физика-теоретика нобелевского лауреата Ричарда Фейнмана. Он заметил, что определенные квантово-механические операции нельзя в точности переносить на классический компьютер. Это наблюдение привело его к мысли, что подобные вычисления могут быть более эффективными, если их осуществлять при помощи квантовых операций.

Рассмотрим, к примеру, квантово-механическую задачу об изменении состояния квантовой системы, состоящей из n спинов, за определенный промежуток времени. Не вникая в подробности математического аппарата квантовой теории, отметим, что общее состояние системы из n спинов описывается вектором в 2 n -мерном комплексном пространстве, а изменение ее состояния - унитарной матрицей размером 2 n x2 n . Если рассматриваемый промежуток времени очень мал, то матрица устроена очень просто и каждый из ее элементов легко вычислить, зная взаимодействие между спинами. Если же необходимо узнать изменение состояния системы за большой промежуток времени, то нужно перемножать такие матрицы, причем для этого требуется экспоненциально большое количество операций. Опять мы сталкиваемся с PN-полной задачей, нерешаемой за полиномиальное время на классических компьютерах. В настоящее время способа упростить данное вычисление не существует, и, скорее всего, моделирование квантовой механики является экспоненциально сложной математической задачей. Но если классические компьютеры не способны решать квантовые задачи, то, возможно, для этого целесообразно использовать саму квантовую систему? И если это действительно возможно, то подходят ли квантовые системы для решения других вычислительных задач? Подобные вопросы как раз и рассматривались Фейнманом и Маниным.

Уже в 1985 году Дэвид Дойч предложил конкретную математическую модель квантовой машины.

Однако вплоть до середины 90-х годов направление квантовых вычислений развивалось довольно вяло. Практическая реализация квантовых компьютеров оказалась весьма сложной. К тому же в научном сообществе с пессимизмом относились к тому, что квантовые операции способны ускорить решение определенных вычислительных задач. Так продолжалось вплоть до 1994 года, когда американский математик Питер Шор предложил для квантового компьютера алгоритм разложения n -значного числа на простые множители за время, полиномиально зависящее от n (квантовый алгоритм факторизации). Квантовый алгоритм факторизации Шора стал одним из основных факторов, приведших к интенсивному развитию квантовых методов вычислений и появлению алгоритмов, позволяющих решать некоторые NP-проблемы.

Естественно, возникает вопрос: почему, собственно, предложенный Шором квантовый алгоритм факторизации привел к таким последствиям? Дело в том, что задача разложения числа на простые множители имеет прямое отношение к криптографии, в частности к популярным системам шифрования RSA. Благодаря возможности разложения числа на простые множители за полиномиальное время квантовый компьютер теоретически позволяет расшифровывать сообщения, закодированные при помощи многих популярных криптографических алгоритмов, таких как RSA. До сих пор этот алгоритм считался сравнительно надежным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Шор придумал квантовый алгоритм, позволяющий разложить на простые множители n -значное число за n 3 (log n ) k шагов (k = const ). Естественно, практическая реализация такого алгоритма могла иметь скорее негативные, чем позитивные последствия, поскольку позволяла подбирать ключи к шифрам, подделывать электронные подписи и т.п. Впрочем, до практической реализации настоящего квантового компьютера еще далеко, а потому в течение ближайших десяти лет можно не опасаться, что шифры могут быть взломаны с помощью квантовых компьютеров.

Идея квантовых вычислений

Итак, после краткого описания истории квантовых вычислений можно перейти к рассмотрению самой их сути. Идея (но не ее реализация) квантовых вычислений достаточно проста и интересна. Но даже для ее поверхностного понимания необходимо ознакомиться с некоторыми специфическими понятиями квантовой физики.

Прежде чем рассматривать обобщенные квантовые понятия вектора состояния и принципа суперпозиции, разберем простой пример поляризованного фотона. Поляризованный фотон - это пример двухуровневой квантовой системы. Состояние поляризации фотона можно задать вектором состояния, определяющим направление поляризации. Поляризация фотона может быть направлена вверх или вниз, поэтому говорят о двух основных, или базисных, состояниях, которые обозначают как |1 и |0.

Данные обозначения (бра/кэт-обозначения) были введены Дираком и имеют строго математическое определение (векторы базисных состояний), которое обусловливает правила работы с ними, однако, дабы не углубляться в математические дебри, мы не станем детально рассматривать эти тонкости.

Возвращаясь к поляризованному фотону, отметим, что в качестве базисных состояний можно было бы выбрать не только горизонтальное и вертикальное, но и любые взаимно ортогональные направления поляризации. Смысл базисных состояний заключается в том, что любая произвольная поляризация может быть выражена как линейная комбинация базисных состояний, то есть a|1+b|0. Поскольку нас интересует только направление поляризации (величина поляризации не важна), то вектор состояния можно считать единичным, то есть |a| 2 +|b| 2 = 1.

Теперь обобщим пример с поляризацией фотона на любую двухуровневую квантовую систему.

Предположим, имеется произвольная двухуровневая квантовая система, которая характеризуется базисными ортогональными состояниями |1 и |0. Согласно законам (постулатам) квантовой механики (принцип суперпозиции) возможными состояниями квантовой системы будут также суперпозиции y = a|1+b|0, где a и b - комплексные числа, называемые амплитудами. Отметим, что аналога состояния суперпозиции в классической физике не существует.

Один из фундаментальных постулатов квантовой механики утверждает, что для того, чтобы измерить состояние квантовой системы, нужно ее разрушить. То есть любой процесс измерения в квантовой физике нарушает первоначальное состояние системы и переводит ее в новое состояние. Понять это утверждение не так-то просто, а потому остановимся на нем более подробное.

Вообще, понятие измерения в квантовой физике играет особую роль, и не стоит рассматривать его как измерение в классическом понимании. Измерение квантовой системы происходит всякий раз, когда она приходит во взаимодействие с «классическим» объектом, то есть с объектом, подчиняющимся законам классической физики. В результате такого взаимодействия состояние квантовой системы изменяется, причем характер и величина этого изменения зависят от состояния квантовой системы и потому могут служить его количественной характеристикой.

В связи с этим классический объект обычно называют прибором, а о его процессе взаимодействия с квантовой системой говорят как об измерении. Необходимо подчеркнуть, что при этом отнюдь не имеется в виду процесс измерения, в котором участвует наблюдатель. Под измерением в квантовой физике подразумевается всякий процесс взаимодействия между классическим и квантовым объектами, происходящий помимо и независимо от какого-либо наблюдателя. Выяснение роли измерения в квантовой физике принадлежит Нильсу Бору.

Итак, чтобы измерить квантовую систему, необходимо каким-то образом подействовать на нее классическим объектом, после чего ее первоначальное состояние будет нарушено. Кроме того, можно утверждать, что в результате измерения квантовая система будет переведена в одно из своих базисных состояний. К примеру, для измерения двухуровневой квантовой системы требуется как минимум двухуровневый классический объект, то есть классический объект, который может принимать два возможных значения: 0 и 1. В процессе измерения состояние квантовой системы будет преобразовано в один из базисных векторов, причем если при измерении классический объект принимает значение равное 0, то квантовый объект преобразуется к состоянию |0, а в случае если классический объект принимает значение равное 1, то квантовый объект преобразуется к состоянию |1.

Таким образом, хотя квантовая двухуровневая система может находиться в бесчисленном множестве состояний суперпозиции, но в результате измерения она принимает только одно из двух возможных базисных состояний. Квадрат модуля амплитуды |a| 2 определяет вероятность обнаружения (измерения) системы в базисном состоянии |1, а квадрат модуля амплитуды |b| 2 - в базисном состоянии |0.

Однако вернемся к нашему примеру с поляризованным фотоном. Для измерения состояния фотона (его поляризации) нам потребуется некоторое классическое устройство с классическим базисом {1,0}. Тогда состояние поляризации фотона a|1+b|0 будет определено как 1 (горизонтальная поляризация) с вероятностью |a| 2 и как 0 (вертикальная поляризация) с вероятностью |b| 2 .

Поскольку измерение квантовой системы приводит ее к одному из базисных состояний и, следовательно, разрушает суперпозицию (к примеру, при измерении получается значение равное |1), то это означает, что в результате измерения квантовая система переходит в новое квантовое состояние и при следующем измерении мы получим значение |1 со стопроцентной вероятностью.

Вектор состояния двухуровневой квантовой системы называется также волновой функцией квантовых состояний y двухуровневой системы, или, в интерпретации квантовых вычислений, кубитом (quantum bit, qubit). В отличие от классического бита, который может принимать только два логических значения, кубит - это квантовый объект, и число его состояний, определяемых суперпозицией, неограниченно. Однако еще раз подчеркнем, что результат измерения кубита всегда приводит нас к одному из двух возможных значений.

Теперь рассмотрим систему из двух кубитов. Измерение каждого из них может дать значение классического объекта 0 или 1. Поэтому у системы двух кубитов имеется четыре классических состояния: 00, 01, 10 и 11. Аналогичные им базисные квантовые состояния: |00, |01, |10 и |11. Соответствующий вектор квантового состояния записывается в виде a |00+ b |01+ c |10+ d |11, где |a | 2 - вероятность при измерении получить значение 00, |b | 2 - вероятность получить значение 01 и т.д.

В общем случае если квантовая система состоит из L кубитов, то у нее имеется 2 L возможных классических состояний, каждое из которых может быть измерено с некоторой вероятностью. Функция состояния такой квантовой системы запишется в виде:

где |n - базисные квантовые состояния (например, состояние |001101, а |c n | 2 - вероятность нахождения в базисном состоянии |n .

Для того чтобы изменить состояние суперпозиции квантовой системы, необходимо реализовать селективное внешнее воздействие на каждый кубит. С математической точки зрения такое преобразование представляется унитарными матрицами размера 2 L x2 L . В результате будет получено новое квантовое состояние суперпозиции.

Структура квантового компьютера

Рассмотренное нами преобразование состояния суперпозиции квантовой системы, состоящей из L кубитов, по сути, представляет собой модель квантового компьютера. Рассмотрим, к примеру, более простой пример реализации квантовых вычислений. Допустим, имеется система из L кубитов, каждый из которых идеально изолирован от внешнего мира. В каждый момент времени мы можем выбрать произвольные два кубита и подействовать на них унитарной матрицей размером 4x4. Последовательность таких воздействий - это своего рода программа для квантового компьютера.

Чтобы использовать квантовую схему для вычисления, нужно уметь вводить входные данные, проделывать вычисления и считывать результат. Поэтому принципиальная схема любого квантового компьютера (см. рисунок) должна включать следующие функциональные блоки: квантовый регистр для ввода данных, квантовый процессор для преобразования данных и устройство для считывания данных.

Квантовый регистр представляет собой совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты квантового регистра должны быть приведены в базисные состояния |0. Эта операция называется подготовкой, или инициализацией. Далее определенные кубиты (не все) подвергаются селективному внешнему воздействию (например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером), которое изменяет значение кубитов, то есть из состояния |0 они переходят в состояние |1. При этом состояние всего квантового регистра перейдет в суперпозицию базисных состояний |n с, то есть состояние квантового регистра в начальный момент времени будет определяться функцией:

Понятно, что данное состояние суперпозиции можно использовать для бинарного (двоичного) представления числа n .

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

Говоря о квантовом процессоре, нужно сделать одно важное замечание. Оказывается, для построения любого вычисления достаточно всего двух базовых логических булевых операций. С помощью базовых квантовых операций можно имитировать работу обычных логических элементов, из которых сделаны компьютеры. Поскольку законы квантовой физики на микроскопическом уровне являются линейными и обратимыми, то и соответствующие квантовые логические устройства, производящие операции с квантовыми состояниями отдельных кубитов (квантовые вентили), оказываются логически и термодинамически обратимыми. Квантовые вентили аналогичны соответствующим обратимым классическим вентилям, но, в отличие от них, способны совершать унитарные операции над суперпозициями состояний. Выполнение унитарных логических операций над кубитами предполагается осуществлять с помощью соответствующих внешних воздействий, которыми управляют классические компьютеры.

Схематическая структура квантового компьютера

После реализации преобразований в квантовом компьютере новая функция суперпозиции представляет собой результат вычислений в квантовом процессоре. Остается лишь считать полученные значения, для чего производится измерение значения квантовой системы. В итоге образуется последовательность нулей и единиц, причем, в силу вероятностного характера измерений, она может быть любой. Таким образом, квантовый компьютер может с некоторой вероятностью дать любой ответ. При этом квантовая схема вычислений считается правильной, если правильный ответ получается с вероятностью, достаточно близкой к единице. Повторив вычисления несколько раз и выбрав тот ответ, который встречается наиболее часто, можно снизить вероятность ошибки до сколь угодно малой величины.

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

Считается, что для реализации полномасштабного квантового компьютера, превосходящего по производительности любой классический компьютер, на каких бы физических принципах он ни работал, следует обеспечить выполнение следующих основных требований:

• физическая система, представляющая собой полномасштабный квантовый компьютер, должна содержать достаточно большое число L >103 хорошо различимых кубитов для выполнения соответствующих квантовых операций;
• необходимо обеспечить максимальное подавление эффектов разрушения суперпозиции квантовых состояний, обусловленных взаимодействием системы кубитов с окружающей средой, в результате чего может стать невозможным выполнение квантовых алгоритмов. Время разрушения суперпозиции квантовых состояний (время декогерентизации) должно по крайней мере в 104 раз превышать время выполнения основных квантовых операций (время такта). Для этого система кубитов должна быть довольно слабо связана с окружением;
• необходимо обеспечить измерение с достаточно высокой надежностью состояния квантовой системы на выходе. Измерение конечного квантового состояния является одной из основных проблем квантовых вычислений.

Практическое применение квантовых компьютеров

Для практического применения пока не создано ни одного квантового компьютера, который бы удовлетворял всем вышеперечисленным условиям. Однако во многих развитых странах разработке квантовых компьютеров уделяется пристальное внимание и в такие программы ежегодно вкладываются десятки миллионов долларов.

На данный момент наибольший квантовый компьютер составлен всего из семи кубитов. Этого достаточно, чтобы реализовать алгоритм Шора и разложить число 15 на простые множители 3 и 5.

Если же говорить о возможных моделях квантовых компьютеров, то их, в принципе, довольно много. Первый квантовый компьютер, который был создан на практике, - это импульсный ядерный магнитно-резонансный (ЯМР) спектрометр высокого разрешения, хотя он, конечно же, как квантовый компьютер не рассматривался. Лишь когда появилась концепция квантового компьютера, ученые поняли, что ЯМР-спектрометр представляет собой вариант квантового компьютера.

В ЯМР-спектрометре спины ядер исследуемой молекулы образуют кубиты. Каждое ядро имеет свою частоту резонанса в данном магнитном поле. При воздействии импульсом на ядро на его резонансной частоте оно начинает эволюционировать, остальные же ядра не испытывают никакого воздействия. Для того чтобы заставить эволюционировать другое ядро, нужно взять иную резонансную частоту и дать импульс на ней. Таким образом, импульсное воздействие на ядра на резонансной частоте представляет собой селективное воздействие на кубиты. При этом в молекуле есть прямая связь между спинами, поэтому она является идеальной заготовкой для квантового компьютера, а сам спектрометр представляет собой квантовый процессор.

Первые эксперименты на ядерных спинах двух атомов водорода в молекулах 2,3-дибромотиофена SCH:(CBr) 2:CH и на трех ядерных спинах - одном в атоме водорода H и двух в изотопах углерода 13 C в молекулах трихлорэтилена CCl 2:CHCl - были поставлены в 1997 году в Оксфорде (Великобритания).

В случае использования ЯМР-спектрометра важно, что для селективного воздействия на ядерные спины молекулы необходимо, чтобы они заметно различались по резонансным частотам. Позднее были осуществлены квантовые операции в ЯМР-спектрометре с числом кубитов 3, 5, 6 и 7.

Главным преимуществом ЯМР-спектрометра является то, что в нем можно использовать огромное количество одинаковых молекул. При этом каждая молекула (точнее, ядра атомов, из которых она состоит) представляет собой квантовую систему. Последовательности радиочастотных импульсов, выполняющие роль определенных квантовых логических вентилей, осуществляют унитарные преобразования состояний соответствующих ядерных спинов одновременно для всех молекул. То есть селективное воздействие на отдельный кубит заменяется одновременным обращением к соответствующим кубитам во всех молекулах большого ансамбля. Компьютер такого рода получил название ансамблевого (bulk-ensemble quantum computer) ЯМР квантового компьютера. Такие компьютеры могут работать при комнатной температуре, а время декогерентизации квантовых состояний ядерных спинов составляет несколько секунд.

В области ЯМР квантовых компьютеров на органических жидкостях к настоящему времени достигнуты наибольшие успехи. Они обусловлены в основном хорошо развитой импульсной техникой ЯМР-спектроскопии, обеспечивающей выполнение различных операций над когерентными суперпозициями состояний ядерных спинов, и возможностью использования для этого стандартных ЯМР-спектрометров, работающих при комнатной температуре.

Основным ограничением ЯМР квантовых компьютеров является сложность инициализации начального состояния в квантовом регистре. Дело в том, что в большом ансамбле молекул исходное состояние кубитов различно, что осложняет приведение системы к начальному состоянию.

Другое ограничение ЯМР квантовых компьютеров связано с тем, что измеряемый на выходе системы сигнал экспоненциально убывает с ростом числа кубитов L . Кроме того, число ядерных кубитов в отдельной молекуле с сильно различающимися резонансными частотами ограничено. Это приводит к тому, что ЯМР квантовые компьютеры не могут иметь больше десяти кубитов. Их следует рассматривать лишь как прототипы будущих квантовых компьютеров, полезные для отработки принципов квантовых вычислений и проверки квантовых алгоритмов.

Другой вариант квантового компьютера основан на использовании ионных ловушек, когда в роли кубитов выступает уровень энергии ионов, захваченных ионными ловушками, которые создаются в вакууме определенной конфигурацией электрического поля в условиях лазерного охлаждения их до сверхнизких температур. Первый прототип квантового компьютера, основанного на этом принципе, был предложен в 1995 году. Преимущество такого подхода состоит в сравнительно простом индивидуальном управлении отдельными кубитами. Основными недостатками квантовых компьютеров этого типа являются необходимость создания сверхнизких температур, обеспечение устойчивости состояния ионов в цепочке и ограниченность возможного числа кубитов - не более 40.

Возможны и другие схемы квантовых компьютеров, разработка которых ведется в настоящее время. Однако пройдет еще как минимум десять лет, прежде чем настоящие квантовые компьютеры наконец будут созданы.

Ричард Фейнман заметил, что определённые квантово - механические процессы нельзя эффективно моделировать на классическом компьютере. Это замечание привело к более общему утверждению, что для проведения вычислений квантовые процессы являются более эффективными, чем классические. Данное предположение было подтверждено Питером Шором, который разработал квантовый алгоритм разложения целых чисел на простые множители за полиномиальное время.

В квантовых системах пространство вычислений экспоненциально возрастает с размером системы, что и делает возможным экспоненциальный параллелизм. Данный параллелизм может привести к квантовым алгоритмам, которые экспоненциально быстрее классических.

Только к середине 1990-х годов теория квантовых компьютеров и квантовых вычислений утвердилась в качестве новой области науки. По-видимому, первым обратил внимание на возможность разработки квантовой логики венгерский математик И. фон Нейман. Однако в то время еще не были созданы не то что квантовые, но и обычные, классические, компьютеры. А с появлением последних основные усилия ученых оказались направлены в первую очередь на поиск и разработку для них новых элементов (транзисторов, а затем и интегральных схем), а не на создание принципиально других вычислительных устройств.

В 1960-е годы американский физик Р. Ландауэр пытался обратить внимание на то, что вычисления - это всегда некоторый физический процесс, а значит, невозможно понять пределы наших вычислительных возможностей, не уточнив, какой физической реализации они соответствуют. К сожалению, в то время среди ученых господствовал взгляд на вычисление как на некую абстрактную логическую процедуру, изучать которую следует математикам, а не физикам.

По мере распространения компьютеров ученые, занимавшиеся квантовыми объектами, пришли к выводу о практической невозможности напрямую рассчитать состояние эволюционирующей системы, состоящей всего лишь из нескольких десятков взаимодействующих частиц, например молекулы метана СН 4 . Объясняется это тем, что для полного описания сложной системы необходимо держать в памяти компьютера экспоненциально большое (по числу частиц) количество переменных, так называемых квантовых амплитуд. Возникла парадоксальная ситуация: зная уравнение эволюции, зная с достаточной точностью все потенциалы взаимодействия частиц друг с другом и начальное состояние системы, практически невозможно вычислить ее будущее, даже если система состоит лишь из 30 электронов в потенциальной яме, а в распоряжении имеется суперкомпьютер с оперативной памятью, число битов которой равно числу атомов в видимой области Вселенной. В то же время, для исследования динамики такой системы можно просто поставить эксперимент с 30 электронами, поместив их в заданные потенциал и начальное состояние. На это, в частности, обратил внимание русский математик Ю. И. Манин, указавший в 1980 году на необходимость разработки теории квантовых вычислительных устройств. В 1980-е годы эту же проблему изучали американский физик П. Бенев, явно показавший, что квантовая система может производить вычисления, а также английский ученый Д. Дойч, теоретически разработавший универсальный квантовый компьютер, превосходящий классический аналог.

Большое внимание к проблеме разработки квантовых компьютеров привлек Р. Фейнман. Благодаря его авторитетному призыву число специалистов, обративших внимание на квантовые вычисления, увеличилось во много раз.

И все же долгое время оставалось неясным, можно ли использовать гипотетическую вычислительную мощь квантового компьютера для ускорения решения практических задач. В 1994 году американский математик П. Шор предложил квантовый алгоритм, позволяющий проводить быструю факторизацию больших чисел. По сравнению с лучшим из известных на сегодня классических методов квантовый алгоритм Шора дает многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем значительней выигрыш в скорости. В случае классического алгоритма увеличение факторизуемого числа приводит к экспоненциальному росту требуемых ресурсов. Например, для разложения на множители 500-значного числа нужно в 100 млн. раз больше итераций, чем для 250-значного числа. Для алгоритма Шора объём необходимых ресурсов растёт лишь полиномиально – 500-значное число требует всего в 8 раз больше шагов, чем 250-значное.

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

В 1997 году Л. Гровер предложил квантовый алгоритм быстрого поиска в неупорядоченной базе данных. (Пример такой базы данных - телефонная книга, в которой фамилии абонентов расположены не по алфавиту, а произвольным образом.) Задача поиска, выбора оптимального элемента среди многочисленных вариантов очень часто встречается в экономических, военных, инженерных задачах, в компьютерных играх. Алгоритм Гровера позволяет не только ускорить процесс поиска, но и увеличить примерно в два раза число параметров, учитываемых при выборе оптимума.

Реальному созданию квантовых компьютеров препятствует серьезная проблема - ошибки, или помехи. Дело в том, что один и тот же уровень помех гораздо интенсивнее портит процесс квантовых вычислений, чем классических. Пути решения этой проблемы наметил в 1995 году П. Шор, разработав схему кодирования квантовых состояний и коррекции в них ошибок.

Время, которое необходимо для осуществления определённых вычислений, можно уменьшить, используя параллельные процессоры. Чтобы достичь экспоненциального уменьшения времени, требуется экспоненциально увеличить число процессоров, а, следовательно, и объём физического пространства. В квантовой системе для экспоненциального уменьшения времени, требуется лишь линейное увеличение объёма необходимого физического пространства. Это явление связано непосредственно с квантовым параллелизмом (Дойч и Джоша, 1992).

Существует ещё одна важная особенность. Пока квантовая система выполняет вычисления, доступ к результатам ограничен. Процесс доступа к результатам - это процесс измерения, который возмущает квантовое состояние, искажая его. Может показаться, что здесь ситуация ещё хуже, чем с классическими вычислениями. Получается, что мы можем только считать результат выполнения одного из параллельных процессов, а поскольку измерение является вероятностным, то мы даже не можем выбирать, результат какого процесса мы получим.

Но за прошедшие несколько лет люди обнаружили нестандартные пути искусного решения задачи измерения, чтобы использовать преимущества квантового параллелизма. Манипуляции подобного рода не имеют аналогов в классической теории и требуют применения нетрадиционных приемов программирования. Один из таких приёмов заключается в управлении квантовым состоянием таким образом, чтобы могло быть считано общее свойство всех результирующих значений, такое как симметричность или период функции. Подобная техника используется в алгоритме разложения на множители Шора. При другом подходе квантовые состояния преобразуются так, чтобы увеличить вероятность считывания интересующего нас результата вычислений. Этот приём используется в поисковом алгоритме Гровера

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

Реферат

Квантовые вычисления

Введение

Глава I. Основные понятия квантовой механики

Глава II. Основные понятия и принципы квантовых вычислений

Глава III. Алгоритм Гровера

Заключение

Список литературы

Введение

Представьте себе компьютер, память которого экспоненциально больше, чем можно было бы ожидать, оценивая его явный физический размер; компьютер, который может оперировать одновременно с экспоненциально большим набором входных данных; компьютер, который проводит вычисления в туманном для большинства из нас гильбертовом пространстве.

Тогда вы думаете о квантовом компьютере.

Идея вычислительного устройства, основанного на квантовой механике, впервые рассматривалась еще в ранних 1970-х годах и ранних 1980-х физиками и компьютерными учеными, такими, например, как Чарльз Х. Беннет из IBM Thomas J. Watson Research Center, Пол А. Бениофф из Аргоннской национальной лаборатории в Иллинойсе, Дэвидом Дойчем из Оксфордского университета, и позднее Ричардом П. Фейнманом из из Калифрнийского технологического института (Калтех). Идея возникла тогда, когда ученые заинтересовались фундаментальными ограничениями вычислений. Они поняли, что если технология будет продолжать следовать постепенному уменьшению размеров вычислительных сетей упакованных в кремниевые ЧИПы, то это приведет к тому, что индивидуальные элементы станут не больше чем несколько атомов. Тогда возникла проблема, так как на атомном уровне действуют законы квантовой физики, а не классической. А это подняло вопрос, можно ли сконструировать компьютер, основанный на принципах квантовой физики.

Фейнман одним из первых попытался дать ответ на этот вопрос. В 1982г. он предложил модель абстрактной квантовой системы, пригодной для вычислений. Он также объяснил, как такая система может быть симулятором в квантовой физике. Другими словами, физики могли бы проводить вычислительные эксперименты на таком квантовом компьютере.

Позже, в 1985 году, Дойч осознал, что утверждение Фейнмана могло бы, в конце концов, привести к квантовому компьютеру общего назначения, и опубликовал важнейшую теоретическую работу, показывающую, что любой физический процесс может в принципе быть промоделирован на квантовом компьютере.

К сожалению, все, что тогда смогли придумать, было несколько довольно надуманных математических задач, до тех пор, пока Шор выпустил в 1994 году свою работу, в которой представил алгоритм решения на квантовом компьютере одной важной задачи из теории чисел, а именно, разложения на простые множители. Он показал, как набор математических операций, сконструированных специально для квантового компьютера, может факторизовать (разложить на простые множители) огромные числа фантастически быстро, значительно быстрее, чем на обычных компьютерах. Это был прорыв, который перевел квантовые вычисления из разряда академического интереса в разряд задачи, интересной для всего мира.

Глава I . Основные понятия квантовой механики

В конце 19 века среди ученых было широко распространено мнение, что физика – наука «практически завершенная» и для полной её «завершенности» осталось совсем немного: объяснить структуру оптических спектров атомов и спектральное распределение теплового излучения . Оптические спектры атома получаются при испускании или поглощении света (электромагнитных волн) свободными или слабо связанными атомами; такими спектрами обладают, в частности, одноатомные газы и пары.

Тепловое излучение – это механизм переноса тепла между пространственно разделёнными частями тела за счет электромагнитного излучения.

Однако начало 20 века привело к пониманию того, что ни о какой «завершенности» не может быть и речи. Становилось ясным, что для объяснения этих и многих других явлений требуется кардинальным образом пересмотреть представления, лежащие в основе физической науки.

Например, исходя из волновой теории света, оказалось невозможным дать исчерпывающее объяснение всей совокупности оптических явлений.

При решении проблемы спектрального состава излучения немецким физиком Максом Планком в 1900 году было высказано предположение о том, что излучение и поглощение света веществом происходит конечными порциями, или квантами. При этом энергия фотона - кванта электромагнитного излучения (в узком смысле - света) определяется выражением

Где - частота излучаемого (или поглощаемого) света, а – универсальная постоянная, называемая теперь постоянной Планка.

Часто используется постоянная Дирака

Тогда энергия кванта выражается как , где

Круговая частота излучения.

Противоречия между рассмотрением света как потока заряженных частиц и как волны привело к понятию корпускулярно-волнового дуализма.

С одной стороны, фотон демонстрирует свойства электромагнитной волны в явлениях дифракции (огибание волнами препятствий, сравнимых с длинной волны) и интерференции (наложение волн с одинаковой частотой и с одинаковой начальной фазой) в масштабах, сравнимых с длиной волны фотона. Например, одиночные фотоны, проходящие через двойную щель, создают на экране интерференционную картину, которую можно описать уравнениями Максвелла . Тем не менее, эксперимент показывает, что фотоны излучаются и поглощаются целиком объектами, размеры которых много меньше длины волны фотона (например, атомами), или, вообще, в некотором приближении могут считаться точечными (например, электрон), то есть ведут себя как частицы - корпускулы . В окружающем нас макромире существует два фундаментальных способа передачи энергии и импульса между двумя точками пространства: непосредственное перемещение материи в одной точки в другую и волновой процесс передачи энергии без переноса вещества. Все носители энергии здесь строго разделены на корпускулярные и волновые. Напротив, в микромире такого разделения не существует. Всем частицам, а в частности и фотонам, приписываются одновременно и корпускулярные, и волновые свойства. Ситуация ненаглядна. Это объективное свойство квантовых моделей.

Почти монохроматическое излучение с частотой испускаемое источником света, можно представить себе состоящим из «пакетов излучения», которые мы называем фотонами. Монохроматическое излучение – обладающее очень малым разбросом частот, в идеале - одной длиной волны.

Распространение фотонов в пространстве правильно описывается классическими уравнениями Максвелла. При этом каждый фотон считается классическим цугом волн , определенным двумя векторными полями - напряженностью электростатического поля и индукцией магнитного поля . Цуг волн - это ряд возмущений с перерывами между ними. Излучение отдельного атома не может быть монохроматическим, потому что излучение длится конечный промежуток времени, имея периоды нарастания и угасания.

Неправильно интерпретировать сумму квадратов амплитуд и как плотность энергии в пространстве, в котором движется фотон; вместо этого каждую величину, квадратично зависящую от амплитуды волны следует интерпретировать как величину пропорциональную вероятности какого-либо процесса. Скажем, не равен энергии, вносимой фотоном в эту область, а пропорционален вероятности обнаружить фотон в этой области.

Энергия, переданная в каком-либо месте пространства фотоном, всегда равна . Тем самым где - вероятность нахождения фотона в данной области, а - число фотонов.

В 1921 году опытом Штерна-Герлаха было подтверждено наличие у атомов спина и факт пространственного квантования направления их магнитных моментов (от англ. spin - вращаться, вертеться.). Спин -собственный момент количества движения элементарных частиц, имеющий квантовую природу и не связанный с перемещением частицы как целого. При введении понятия спина предполагалось, что электрон можно рассматривать как «вращающийся волчок», а его спин - как характеристику такого вращения. Спином называют также собственный момент импульса атомного ядра или атома; в этом случае спин определяется как векторная сумма (вычисленная по правилам сложения моментов в квантовой механике) спинов элементарных частиц, образующих систему, и орбитальных моментов этих частиц, обусловленных их движением внутри системы.

Спин измеряется в единицах (приведенных постоянных Планка, или постоянных Дирака) и равен , где J - характерное для каждого сорта частиц целое (в т. ч. нулевое) или полуцелое положительное число - спиновое квантовое число , которое обычно называют просто спином (одно из квантовых чисел). В связи с этим говорят о целом или полуцелом спине частицы. Однако не следует путать понятия спин и спиновое квантовое число. Спиновое квантовое число - это квантовое число, определяющее величину спина квантовой системы (атома, иона, атомного ядра, молекулы), т. е. её собственного (внутреннего) момента импульса. Проекция спина на любое фиксированное направление z в пространстве может принимать значения J , J-1, ..., -J. Т. о., частица со спином J может находиться в 2J + 1 спиновых состояниях (при J = 1 / 2 - в двух состояниях), что эквивалентно наличию у неё дополнительной внутренней степени свободы.

Ключевым элементом квантовой механики является принцип неопределенности Гейзенберга , который говорит о том, что нельзя одновременно точно определить положение частицы в пространстве и ее импульс. Этот принцип объясняет квантование света, а также пропорциональную зависимость энергии фотона от его частоты.

Движение фотона можно описать системой уравнений Максвелла, в то время как уравнение движения любой другой элементарной частицы типа электрона описывается уравнением Шрёдингера, которое более общее.

Система уравнений Максвелла инвариантна относительно преобразования Лоренца. Преобразованиями Лоренца в специальной теории относительности называются преобразования, которым подвергаются пространственно-временные координаты (x,y,z,t) каждого события при переходе от одной инерциальной системы отсчета к другой. По сути, эти преобразования представляют собой преобразования не только в пространстве, как преобразования Галилея, но и во времени.

Глава II . Основные понятия и принципы квантовых вычислений

Хотя компьютеры стали компактными и значительно быстрее, чем раньше, справляются со своей задачей, сама задача остается прежней: манипулировать последовательностью битов и интерпретировать эту последовательность как полезный вычислительный результат. Бит - это фундаментальная единица информации, обычно представляемая как 0 или 1 в вашем цифровом компьютере. Каждый классический бит физически реализуется макроскопической физической системой, такой как намагниченность на жестком диске или заряд конденсатора. Например, текст, составленный из n символов, и сохраненный на жестком диске типичного компьютера, описывается строкой из 8n нулей и единиц. Здесь и лежит фундаментальное отличие между вашим классическим компьютером и квантовым компьютером. В то время как классический компьютер подчиняется хорошо понятным законам классической физики, квантовый компьютер это устройство, которое использует квантово-механические явления (в особенности квантовую интерференцию ), чтобы осуществлять совершенно новый способ обработки информации.

В квантовом компьютере фундаментальная единица информации (называемая квантовый бит или кубит ), не двоична, а скорее четверична по своей природе. Это свойство кубита проистекает как прямое следствие его подчиненности законам квантовой механики, которые радикально отличаются от законов классической физики. Кубит может существовать не только в состоянии, соответствующем логическим 0 или 1, как классический бит, но также в состояниях, соответствующих смесли или суперпозиции этих классических состояний. Другими словами, кубит может существовать как ноль, как единица, и как одновременно 0 и 1. При этом можно указать некоторый численный коэффициент, представляющий вероятность оказаться в каждом состоянии.

Идеи о возможности построения квантового компьютера восходят к работам Р. Фейнмана 1982- 1986 гг. Рассматривая вопрос о вычислении эволюции квантовых систем на цифровом компьютере, Фейнман обнаружил "нерешаемость" этой задачи: оказывается, что ресурсы памяти и быстродействия классических машин недостаточны для решения квантовых задач. Например, система из n квантовых частиц с двумя состояниями (спины 1/2 ) имеет 2 n базисных состояний; для ее описания необходимо задать (и записать в память ЭВМ) 2 n амплитуд этих состояний. Отталкиваясь от этого негативного результата, Фейнман высказал предположение, что, вероятно, "квантовый компьютер" будет обладать свойствами, которые позволят решать на нем квантовые задачи.

"Классические" компьютеры построены на транзисторных схемах, обладающих нелинейными зависимостями между входными и выходными напряжениями. По существу, это бистабильные элементы; например, при низком входном напряжении (логический "0") входное напряжение высокое (логическая "1"), и наоборот. Такой бистабильной транзисторной схеме в квантовом мире можно сопоставить двухуровневую квантовую частицу: состоянию припишем значения логического , состоянию , - значение логической . Переходам в бистабильной транзисторной схеме здесь будут соответствовать переходы с уровня на уровень: . Однако квантовый бистабильный элемент, получивший название кубит, обладает новым, по сравнению с классическим, свойством суперпозиции состояний: он может быть в любом суперпозиционном состоянии , где - комплексные числа, . Состояния квантовой системы из п двухуровневых частиц имеют в общем случае вид суперпозиции 2 n базовых состоянии . В конечном счете квантовый принцип суперпозиции состояний позволяет придать квантовому компьютеру принципиально новые "способности".

Доказано, что квантовая ЭВМ может быть построена всего из двух элементов (вентилей): однокубитового элемента и двухкубитового элемента контролируемое НЕ (CNOT). Матрица 2x2 элемента имеет вид:

(1)

Вентиль описывает поворот вектора состояния кубита от оси z к полярной оси, заданной углами . Если - иррациональные числа, то многократным применением вектору состояния можно придать любую наперед заданную ориентацию. Именно в этом заключается "универсальность" однокубитового вентиля в форме (1). В частном случае получаем однокубитовый логический элемент НЕ (NOT): НЕ=, НЕ=. При физической реализации элемента НЕ необходимо воздействовать на квантовую частицу (кубит) импульсом извне, переводящим кубит из одного состояния в другое. Вентиль контролируемое НЕ исполняют, воздействуя на два взаимодействующих между собой кубита: при этом посредством взаимодействия один кубит контролирует эволюцию другого. Переходы под влиянием внешних импульсов хорошо известны в импульсной магниторезонансной спектроскопии. Вентиль НЕ соответствует перевороту спина под действием импульса (вращение намагниченности вокруг оси на угол ). Вентиль CNOT выполняется на двух спинах 1/2 с гамильтонианом (спин контролирует ). CNOT выполняется в три шага: импульс + свободная прецессия в течение времени - импульс . Если (контролирующий кубит в состоянии ), то при указанных воздействиях контролируемый кубит совершает переходы (или ). Если же (контролирующий кубит в состоянии ), то результат эволюции контролируемого кубита будет другим: (). Таким образом, спин , эволюционирует по-разному при : здесь в - состояние контролирующего кубита.

При рассмотрении вопроса о реализации квантового компьютера на тех или иных квантовых системах в первую очередь исследуют реализуемость и свойства элементарных вентилей НЕ и контролируемое НЕ.

Для дальнейшего полезно также ввести однокубитовое преобразование Адамара:

В технике магнитного резонанса эти вентили осуществляются импульсами :

Схема квантового компьютера представлена на рисунке. До начала работы компьютера все кубиты (квантовые частицы) должны быть приведены в состояние , т.е. в основное состояние. Это условие само по себе не тривиально.

Оно требует или глубокого охлаждения (до температур порядка милликельвина), или применения методов поляризации. Систему п кубитов в состоянии можно считать регистром памяти, приготовленным для записи входных данных и проведения вычислений. Кроме этого регистра обычно предполагают существование дополнительных (вспомогательных) регистров, необходимых для записи промежуточных результатов вычислений. Запись данных осуществляется путем того или иного воздействия на каждый кубит компьютера. Примем, например, что над каждым кубитом регистра совершается преобразование Адамара:

В результате система перешла в состояние суперпозиции из 2 п базисных состояний с амплитудой 2 - n /2 . Каждое базисное состояние представляет собой двоичное число от до . Горизонтальные линии на рисунке обозначают оси времени.

Выполнение алгоритма совершается путем унитарного преобразования суперпозиции . представляет собой унитарную матрицу размерности 2 п. При физическом осуществлении посредством импульсных воздействий на кубиты извне матрица должна быть представлена как векторное произведение матриц размерности 2 и . Последние могут быть выполнены последовательным воздействием на единичные кубиты или пары кубитов :

Количество сомножителей в этом разложении определяет длительность (и сложность) вычислений . Все в (3) выполняются с применением операций NOT, CNOT, Н (или их разновидностей).

Замечательно, что линейный унитарный оператор действует одновременно на все члены суперпозиции

Результаты вычисления записываются в запасном регистре, который перед применением находился в состоянии . За один прогон вычислительного процесса мы получаем значения искомой функции f при всех значениях аргумента х = 0,..., 2 п - 1 . Этот феномен получил название квантового параллелизма.

Измерение результата вычислений сводится к проецированию вектора суперпозиции в (4) на вектор одного из базисных состояний :

(5)

Здесь проступает одно из слабых мест квантового компьютера: число в процессе измерения "выпадает" по закону случая. Чтобы найти при заданном , надо много раз провести вычисления и измерения, пока случайно не выпадет .

При анализе унитарной эволюции квантовой системы, совершающей вычислительный процесс, выявляется важность физических процессов типа интерференции. Унитарные преобразования совершаются в пространстве комплексных чисел, и сложение фаз этих чисел носит характер интерференции. Известна продуктивность преобразований Фурье в явлениях интерференции и спектроскопии. Оказалось, что и в квантовых алгоритмах неизменно присутствуют преобразования Фурье. Преобразование Адамара является простейшим дискретным фурье-преобразованием. Вентили типа NOT и СNOT могут быть осуществлены непосредственно на интерферометре Маха-Зендера с использованием явления интерференции фотона и вращения его вектора поляризации.

Исследуются различные пути физической реализации квантовых компьютеров. Модельные эксперименты по квантовому компьютингу выполнены на импульсном ядерном магнитно-резонансном спектрометре. В этих моделях работало два или три спина (кубита), например два спина ядер 13 С и один спин протона в молекуле трихлорэтилена

Однако в этих опытах квантовый компьютер был "ансамблевым": выходные сигналы компьютера сложены большим числом молекул в жидком растворе (~ 10 20).

К настоящему времени высказаны предложения о реализации квантовых компьютеров на ионах и молекулах в ловушках в вакууме, на ядерных спинах в жидкостях (см. выше), на ядерных спинах атомов 31 Р в кристаллическом кремнии, на спинах электронов в квантовых точках, созданных в двумерном электронном газе в гетероструктурах GaAs, на переходах Джозеф-сона. Как видим, в принципе, квантовый компьютер можно построить на атомных частицах в вакууме, жидкости, кристаллах. При этом в каждом случае предстоит преодолеть те или иные препятствия, однако среди них можно выделить несколько общих, обусловленных принципами действия кубитов в квантовом компьютере. Поставим задачу создать полномасштабный квантовый компьютер, содержащий, скажем, 10 3 кубитов (хотя и при п = 100 квантовый компьютер может стать полезным инструментом).

1. Нужно найти способы "инициализации" кубитов компьютера в состояние . Для спиновых систем в кристаллах очевидно применение сверхнизких температур и сверхсильных магнитных полей. Применение поляризации спинов накачкой может оказаться полезным при одновременном применении охлаждения и больших магнитных полей.

Для ионов в вакуумных ловушках сверхнизкое охлаждение ионов (атомов) достигается лазерными методами. Очевидна также необходимость холодного и сверхвысокого вакуума.

2. Необходимо иметь технологию избирательного воздействия импульсами на любой выбранный кубит. В области радиочастот и спинового резонанса это означает, что каждый спин должен обладать своей резонансной частотой (в терминах спектроскопического разрешения). Различия резонансных частот для спинов в молекулах обусловлены химическими сдвигами для спинов одного изотопа и одного элемента; необходимые различия частот имеются для спинов ядер различных элементов. Однако здравый смысл подсказывает, что эти дарованные природой различия резонансных частот вряд ли достаточны, чтобы работать с 10 3 спинов.

Более перспективными представляются подходы, когда можно управлять извне резонансной частотой каждого кубита. В предложении о кремниевом квантовом компьютере кубитом служит ядерный спин примесного атома 31 Р. Частота резонанса определяется константой А сверхтонкого взаимодействия ядерного и электронного спинов атома 31 Р. Электрическое поле на наноэлектроде, находящемся над атомом 31 Р, поляризует атом и изменяет константу А (соответственно резонансную частоту ядерного спина). Таким образом, наличие электрода встраивает кубит в электронную схему и настраивает его резонансную частоту.

3. Для выполнения операции CNOT (контролируемое НЕ) необходимо взаимодействие между кубитами и вида . Такое взаимодействие возникает между спинами ядер в молекуле, если ядра и разделены одной химической связью. В принципе, необходимо иметь возможность выполнять операцию для любых пар кубитов . Иметь физическое взаимодействие кубитов одного масштаба величины и по принципу "все со всеми" в природной среде вряд ли возможно. Очевидна потребность в способе настройки среды между кубитами извне путем введения электродов с управляемым потенциалом. Таким путем можно создать, например, перекрытие волновых функций электронов в соседних квантовых точках и возникновение взаимодействия вида между спинами электронов [. Перекрытие волновых функций электронов соседних атомов 31 Р обусловливает возникновение взаимодействия вида между ядерными спинами.

Чтобы обеспечить операцию , где и - отдаленные кубиты, между которыми взаимодействие вида отсутствует, необходимо применить в компьютере операцию обмена состояниями по цепочке так что обеспечивает операцию , поскольку состояние совпадает с состоянием .

4. В ходе выполнения унитарного преобразования, соответствующего избранному алгоритму, кубиты компьютера подвергаются воздействию со стороны среды; в результате амплитуды и фазы вектора состояния кубита испытывают случайные изменения - декогеренизацию . По существу, декогеренизация - это релаксация тех степеней свободы частицы, которые используются в кубите. Время декогеренизации равно времени релаксации. В ядерном магнитном резонансе в жидкостях времена и релаксации составляют 1-10 с. Для ионов в ловушках с оптическими переходами между уровнями Е 0 и Е 1 временем декогеренизации выступают время спонтанного излучения и время столкновений с остаточными атомами. Очевидно, что декогеренизация - это серьезное препятствие квантовому вычислению: начатый вычислительный процесс приобретает черты случайности по истечении времени декогеренизации. Однако можно достичь устойчивого квантового вычислительного процесса в течение сколь угодно долгого времени т > та, если систематически использовать методы квантового кодирования и коррекции ошибок (фазовых и амплитудных). Доказано, что при относительно невысоких требованиях к безошибочному выполнению элементарных операций типа NОТ и СNОТ (вероятность ошибки не более 10 -5) методы квантовой коррекции ошибок (QEC) обеспечивают устойчивую работу квантового компьютера.

Возможно и активное подавление процесса декогеренизации, если над системой кубитов проводить периодические измерения. Измерение с большой вероятностью обнаружит частицу в "правильном" состоянии, а малые случайные изменения вектора состояния при измерении коллапсируют (квантовый эффект Зенона). Однако трудно пока сказать, насколько полезным может быть такой прием, поскольку такие измерения сами по себе могут воздействовать на вычислительный процесс и нарушить его.

5. Состояния кубитов после завершения вычислительного процесса должны быть измерены, чтобы определить результат вычисления. Сегодня нет освоенной технологии таких измерений. Очевиден, однако, путь поисков такой технологии: надо использовать методы усиления в квантовом измерении. Например, состояние ядерного спина передается электронному спину ; от последнего зависит орбитальная волновая функция; зная орбитальную волновую функцию, можно организовать передачу зарядов (ионизацию); присутствие или отсутствие заряда одиночного электрона можно обнаружить классическими электрометрическими методами. Большую роль в этих измерениях будут играть, вероятно, методы зондовой силовой микроскопии.

К настоящему времени открыты квантовые алгоритмы, приводящие к экспоненциальному ускорению вычислений по сравнению с вычислениями на классическом компьютере. К ним относится алгоритм Шора определения простых множителей больших (многоразрядных) чисел. Эта чисто математическая проблема тесно связана с жизнью общества, так как на "невычислимости" таких множителей построены современные шифровальные коды. Именно это обстоятельство вызвало сенсацию, когда был открыт алгоритм Шора. Для физиков важно, что и решение квантовых задач (решение уравнения Шрёдингера для многочастичных систем) экспоненциально ускоряется, если использовать квантовый компьютер.

Наконец, очень важно, что в ходе исследований задач квантового компьютинга подвергаются новому анализу и экспериментальной проверке основные проблемы квантовой физики: проблемы локальности, реальности, дополнительности, скрытых параметров, коллапса волновой функции.

Идеи квантового компьютинга и квантовой связи возникли спустя сто лет после рождения первоначальных идей квантовой физики. Возможность построения квантовых компьютеров и систем связи показана выполненными к настоящему времени теоретическими и экспериментальными исследованиями. Квантовая физика "достаточна" для проектирования квантовых компьютеров на различной "элементной базе". Квантовые компьютеры, если их удастся построить, будут техникой XXI века. Для их изготовления потребуется создание и развитие новых технологий на нанометровом и атомном уровне размеров. Эта работа может занять, по-видимому, несколько десятилетий. Построение квантовых компьютеров было бы еще одним подтверждением принципа неисчерпаемости природы: природа имеет средства для осуществления любой корректно сформулированной человеком задачи.

В обычном компьютере информация кодируется последовательностью битов, и эти биты последовательно обрабатываются булевскими логическими элементами, чтобы получить нужный результат. Аналогично квантовый компьютер обрабатывает кубиты, выполняя последовательность операций квантовыми логическими элементами, каждый из которых представляет собой унитарное преобразование, действующее на единичный кубит или пару кубитов. Последовательно выполняя эти преобразования, квантовый компьютер может выполнить сложное унитарное преобразование над всем набором кубитов приготовленных в некотором начальном состоянии. После этого можно произвести измерение над кубитами, которое и даст конечный результат вычислений. Это сходство вычислений между квантовым и классическим компьютером позволяет считать, что, по крайней мере, в теории, классический компьютер может в точности воспроизводить работу квантового компьютера. Другими словами, классический компьютер может делать все то же самое, что и квантовый компьютер. Тогда зачем вся эта возня с квантовым компьютером? Дело в том, что, хотя теоретически классический компьютер может симулировать квантовый компьютер, это очень неэффективно, настолько неэффективно, что практически классический компьютер не в состоянии решать многие задачи, которые по плечу квантовому компьютеру. Симуляция квантового компьютера на классическом компьютере вычислительно сложная проблема, потому что корреляции между квантовыми битами качественно отличается от корреляций между классическими битами, как было впервые показано Джоном Беллом. Для примера можно взять систему только из нескольких сотен кубитов. Она существует в пространстве Гильберта размерностью ~10 90 , что потребует, при моделировании классическим компьютером, использования экспоненциально больших матриц (чтобы выполнить расчеты для каждого отдельного состояния, которое также описывается матрицей). Это означает, что классическому компьютеру понадобится экпоненциально больше времени по сравнению даже с примитивным квантовым компьютером.

Ричард Фейнман был среди первых, кто осознал потенциал, заложенный в явлении квантовой суперпозиции для решения таких задач гораздо быстрее. Например, система из 500 кубитов, которую практически невозможно промеделировать классически, представляет собой квантовую суперпозицию из 2 500 состояний. Каждое значение такой суперпозиции классически эквивалентно списку из 500 единиц и нулей. Любая квантовая операция над такой системой, например, настроенный определенным образом импульс радиоволн, который может выполнить операцию управляемое НЕ над, скажем, 100-м и 101-м кубитом, будет одновременно воздействовать на 2 500 состояний. Таким образом, за один тик компьютерных часов квантовая операция вычисляет не одно машинное состояние, как обычные компьютеры, а 2 500 состояний сразу! Однако, в конце концов, над системой кубитов производится измерение, и система коллапсирует в единственное квантовое состояние, соответствующее единственному решению задачи, единственному набору из 500 единиц и нулей, как это диктуется измерительной аксиомой квантовой механики. Это поистине волнующий результат, поскольку это решение, найденное колективным процессом квантовых параллельных вычислений, берущим свои истоки в суперпозиции, эквивалентно выполнению той же самой операции на классическом суперкомпьютере с ~10 150 отдельных процессоров (что, конечно, невозможно)!! Первые исследователи в этой области были, конечно, вдохновлены такими гигантскими возможностями, и поэтому вскоре началась настоящая охота за подходящими задачами для такой вычислительной мощи. Питер Шор, исследователь и компьютерный ученый из компании AT&T"s Bell Laboratories в Нью Джерси, предложил такую задачу, которую можно было бы решить именно на квантовом компьютере и при помощи квантового алгоритма. Алгоритм Шора использует мощь квантовой суперпозиции, чтобы раскладывать большие числа (порядка ~10 200 двоичных разрядов и больше) на множители за несколько секунд. Эта задча имеет важное практическое применение для шифрования, где общепринятый (и лучший) алгоритм шифрования, известный как RSA, основан как раз на сложности разложения больших составных чисел на простые множители. Компьютер, который с легкостью решает такую задачу, конечно, представляет большой интерес для множества правительственных организаций, использующих RSA, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.

Шифрование, однако, только одно возможное применение квантового компьютера. Шор разработал целый набор математических операций, которые могут быть выполнены исключительно на квантовом компьютере. Некоторые из этих операций используются в его алгоритие факторизации. Далее, Фейнман утверждал, что квантовый компьютер может действовать как моделирующее устройство для квантовой физики, потенциально открывая двери ко многим открытиям в этой области. В настоящее время мощь и возможности квантового компьютера, в основном, предмет теоретических рассуждений; появление первого по-настоящему функционального квантового компьютера, несомненно, принесет много новых и волнующих практических применений.

Глава III . Алгоритм Гровера

Задача поиска состоит в следующем: имеется неупорядоченная база данных, состоящая из N-элементов, из которых лишь один удовлетворяет данным условиям - именно этот элемент нужно найти. Если элемент можно осмотреть, то определение того, удовлетворяет он требуемым условиям или нет, осуществляется за один шаг. Однако база данных такова, что в ней не существует какого-либо упорядочения, которое могло бы помочь выбору элемента. Наиболее эффективный классический алгоритм для этой задачи состоит в проверке элементов из базы данных одного за другим. Если элемент удовлетворяет требуемым условиям, поиск окончен, если нет, то данный элемент откладывается так, так чтобы он вновь не подвергался проверке. Очевидно, что в этом алгоритме требуется проверить в среднем элементов прежде, чем будет найден нужный.

Реализуя данный алгоритм, можно используя то же самое оборудование, как в классическом случае, но задавая вход и выход в виде суперпозиции состояний, можно найти объект за O () квантовомеханических шагов вместо О( N )) классических шагов. Каждый квантовомеханический шаг состоит из элементарной унитарной операции, которые рассмотрим далее.

Для осуществления данного алгоритма нам необходимы следующие три элементарные операции. Первая - это приготовление состояния, в котором система находится с равной вероятностью в любом из ее N базисных состояний; вторая - это преобразование Адамара и третья - выборочный поворот фаз состояний.

Как известно основной операцией для квантовых вычислений является операция М , действующая на один бит, которая представляется следующей матрицей:

т. е. бит в состоянии 0 превращается в суперпозицию двух состояний: (1/, 1/). Аналогично, бит в состоянии 1 трансформируется в (1/, -1/,), т. е. величина амплитуды для каждого состояния равна 1/, но фаза в состоянии 1 перевернута. Фаза не имеет аналога в классических вероятностных алгоритмах. Она возникает в квантовой механике, где амплитуда вероятности комплексна. В системе, в которой состояние описывается п битами (т. е. имеется N = 2 п возможных состояний), мы можем осуществить преобразование М на каждом бите независимо, последовательно изменяя состояние системы. В случае, когда начальная конфигурация представляла собой конфигурацию с п битами в первом состоянии, полученная конфигурация будет иметь равные амплитуды для каждого из состояний. Это и есть способ создания суперпозиции с той же самой амплитудой для всех состояний.

Третье преобразование, которое нам понадобится, - это выборочное вращение фазы амплитуды в определенных состояниях. Преобразование, представленное здесь для системы из двух состояний, имеет форму:

где j = и - произвольные действительные числа. Заметим, что в отличие от преобразования Адамара и других матриц преобразования состояний, вероятность каждого состояния остается той же, т. к. квадрат абсолютной величины амплитуды в каждом состоянии остается прежним.

Рассмотрим задачу в абстрактной форме.

Пусть система имеет N = 2 п состояний, которые обозначаются как ,..., . Эти 2 п состояния представляются как n-битные строки. Пусть существует единственное состояние, скажем , которое довлетворяет условию C() = 1, тогда как для всех других состояний S, С( ,) = 0 (предполагается, что для любого состояния S условие оценивается за единицу времени). Задача состоит в распознании состояния ,

Перейдем собственно к алгоритму

Шаги (1) и (2) являются последовательностью элементарных унитарных операций описаных ранее. Шаг (3) есть завершающее измерение, осуществляемое внешней системой.

(1) Приводим систему в состояние суперпозиции:

с одинаковыми амплитудами для каждого из N состояний. Эта суперпозиция может быть получена за шагов.

(2) Повторим следующую унитарную операцию О( ) раз:

a . Пусть система будет в каком-нибудь состоянии S:

В случае С( S ) = 1, повернуть фазу на радиан;

В случае С(S) = 0, оставить систему неизмененной.

b . Применить преобразование диффузии D которое определяется матрицей D следующим образом:, если ;" и . D может быть реализована как последовательное выполнение унитарных преобразований: , где W – матрица преобразований Адамара, R – матрица фазового поворота.

(3) Произвести измерение полученного состоянии. Это состояние будет состоянием С( )„ (т. е. искомым состоянием, удовлетворяющим условию (C() = 1) с вероятностью, по крайней мере, не меньшей, чем 0.5. Заметим, что шаг (2а) - это фазовое вращение. В его реализацию должна быть включена процедура распознания состояния и последующего определения осуществлять или нет поворот фазы. Она должна проводиться таким образом, чтобы не оставлять следа на состоянии системы, так, чтобы была уверенность, что пути, приводящие к тому же самому конечному состоянию, неразличимы и могут интерферировать. Заметим, что эта процедура не включает классического измерения.

Данный квантовый алгоритм поиска, вероятно, будет проще реализовать по сравнению со многими другими известными квантово-механическими алгоритмами, так как необходимые операции - это только преобразование Уолша-Адамара и операция условного сдвига фазы, каждая из которых относительно проста по сравнению с операциями, используемыми другими квантово-механическими алгоритмами.

Заключение

Сейчас квантовые компьютеры и квантовые информационные технологии остаются в состоянии пионерских разработок. Решение трудностей, с которыми сейчас столкнулись эти технологии, обеспечит прорыв квантовых компьютеров к их законному месту самых быстрых вычислительных машин из всех физически возможных. К сегодняшнему дню исправление ошибок существенно продвинулось, приближая момент, когда мы сможем создавать достаточно надежные компьютеры, способные противостоять эффектам декогеренции. С другой стороны, создание квантового оборудования пока остается только возникающей отраслью; но работа, проделанная на сегодня, убеждает нас, что создание достаточно больших машин, способных выполнять серьезные алгоритмы, например, алгоритм Шора, всего лишь дело времени. Таким образом, квантовые компьютеры обязательно появятся. По меньшей мере, это будут самые совершенные вычислительные устройства, а современные нам компьютеры устареют. Квантовые вычисления берут свое начало в весьма специфических областях теоретической физики, но их будущее, несомненно, окажет огромное воздействие на жизнь всего человечества.

Список литературы

1. Квантовые вычисления: за и против. Под ред. В.А. Садовничего. – Ижевск: Издательский дом «Удмуртский университет», 1999. – 212 с.

2. Белонучкин В.E., Заикин Д.А., Ципенюк Ю.М., Основы физики. Курс общей физики: Учебн. В 2 т. Т. 2. Квантовая и статистическая физика. – М.: ФИЗМАТЛИТ, 2001. – 504 с.

3. Валиев К.А. «Квантовые компьютеры: можно ли их сделать «большими»?», Успехи физических наук, т. 169, № 6, 1999г.

4. Валиев К.А. «Квантовая информатика: компьютеры, связь и криптография», ВЕСТНИК РОССИЙСКОЙ АКАДЕМИИ НАУК, том 70, № 8, с. 688-695, 2000г.

5. Маслов. Д. «Квантовые вычисления и коммуникация: реальность и перспективы», Компьютерра, №46 , 2004г.

6. Халфин Л.А. «Квантовый эффект Зенона», Успехи физических наук, т. 160, № 10, 1990г.

7. Холево А. «Квантовая информатика: прошлое, настоящее, будущее»,

В МИРЕ НАУКИ, №7, 2008г.

8. Centre for Quantum Technologies, National University of Singapore www.quantumlah.org