Виртуальный квантовый компьютер А. Л. Восков



Дата03.05.2016
Размер88.2 Kb.
Виртуальный квантовый компьютер

А.Л. Восков 

Московский государственный университет, Россия
Аннотация

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


Введение

В последнее десятилетие наблюдается устойчивый рост интереса к квантовым вычислениям и квантовым компьютерам; имеются первые удачные попытки аппаратной реализации квантовых алгоритмов [1,2]. Квантовые компьютеры позволяют добиться беспрецендентного роста эффективности вычислений в таких областях, как поиск в базах данных, разложение простых чисел на множители, моделирование сложных молекул, фурье- и вейвлет- преобразования, а также развить принципиально новые подходы в криптографии и связи.

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

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



  • Простое и компактное ядро, эффективно использующее ресурсы ЭВМ, допускающее возможность лёгкого и быстрого расширения

  • Реализация низкоуровневого языка для управления квантовыми вычислениями

  • Наличие удобных средств разработки и отладки

  • Возможность использования существующих библиотек квантовых вычислений

  • Возможность интеграции с уже существующими языками и средами программирования без внесения изменений в ядро эмулятора

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

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


Кубиты и квантовые регистры

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



, где (1)

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

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

При этом квадраты модулей этих чисел являются вероятностями получить соответствующие значения регистра при его считывании (измерении). В связи с этим для эмуляции квантового компьютера из N кубит требуется на хранение в памяти машины по меньшей мере вещественных чисел, поэтому на персональном компьютере с 1Гб ОЗУ верхнее значение N — около 25. Затраты на вычисления растут экспоненциально. Эмуляция систем из сотен кубит на классической ЭВМ невозможна.

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

Для манипулирования вектором состояния нужны квантовые вентили — аналоги классических логических элементов. Однокубитовые вентили описываются с помощью матриц 2x2 в базисе . В качестве примера рассмотрим вентиль Адамара (H) [2,4] и результат его применения к состоянию кубита



; (3)

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

Более подробно с существующими квантовыми вентилями и схемами можно ознакомиться в работах [1-5].

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



(4)

Алгоритм перехода в N-кубитный базис

Шаг 1. Получить тензорное произведение матрицы вентиля на n кубит с единичной матрицей на N-n кубит (где N — число кубит в квантовом регистре)

Шаг 2. Получить тензорное произведение соответствующих базисов

Шаг 3. Поменять местами сначала строки, а потом и столбцы матрицы для того, чтобы отсортировать её базис.

В результате последовательного выполнения этих шагов получается матрица размером , описывающая действие квантового вентиля в базисе из N кубит на заданные 1 или 2 кубита. Рассмотрим работу этого алгоритма на примере вентиля Адамара и двухкубитного регистра.
Пусть вентиль применяется к старшему кубиту регистра.

; (5)
(6)

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


Алгоритм чтение данных из квантового регистра

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

Шаг 1.Найти вероятность того, что кубит установлен в 1 по формуле, где j — значения, в которых соответствующий бит установлен в 1.

Шаг 2. Сгенерировать случайное число x от 0 до 1; если , то считано 1, а иначе — 0

Шаг 3. Установить в ноль для тех , в которых кубит не соответствует измеренному, а для остальных умножить на . В случае, если p=0 или p=1, такая нормировка не требуется.
Результаты чтения (измерения) отдельного кубита

Начальное состояние

Конечное

состояние



Результат измерения

p






0

2/3






1

1/3


Запись данных в квантовый регистр

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


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

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



  • Ядро эмулятора

  • Квантовые вентили

  • Библиотека базовых квантовых алгоритмов

  • Интерфейсы для языков программирования и сред разработки

  • Учебная интегрированная среда разработки

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

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

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



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

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

Учебная интегрированная среда разработки создается на основе уже существующих программных продуктов. Она должна обеспечивать быструю и эффективную разработку и отладку квантовых алгоритмов. В качестве базового языка программирования возможно использование как языка высокого (Си, Паскаль, Модула-2, Оберон и т.п.), так и низкого уровня (Ассемблер для x86).

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

При применении языка низкого уровня введение квантовых вычислений целесообразно в виде специализированных команд, дополняющие возможности x86 (они могут быть реализованы как макрорасширения уже существующих ассемблеров). При этом в качестве прототипа может быть взят язык QASM для описания квантовых схем [6].
Результаты

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

Предложены и обоснованы структура эмулятора квантового компьютера и основные функции ее элементов.

Реализованы базовые функции ядра эмулятора квантового компьютера и наиболее употребительные квантовые вентили.


Литература

1. Валиев К.А., Кокин А.А. «Квантовые компьютеры: надежды и реальность». Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 352 стр.

2. Нильсен М., Чанг И. «Квантовые вычисления и квантовая информация»: Пер. с англ. - М.: Мир, 2006 г. - 824 с., ил.

3. http://www.quantiki.org/

4. Ekert A., Patrick Hayden P., Inamori H. “Basic concepts in quantum computation” arXiv:quant-ph/0011013v1 (2000)

5. Китаев А., Шень А., Вялый М. «Классические и квантовые вычисления». – М.: МЦНМО, ЧеРо, 1999. – 192 с.



6. http://www.media.mit.edu/quanta/qasm2circ/




База данных защищена авторским правом ©refedu.ru 2016
обратиться к администрации

    Главная страница