12.02.2020 11:12
ph_piter 5 2000 Источник
imageПривет, Хаброжители! Квантовые вычисления не просто меняют реальность! Совершенно новая отрасль рождается на наших глазах, чтобы создать немыслимое ранее и обесценить некоторые достижения прошлого. В этой книге рассмотрены наиболее важные компоненты квантового компьютера: кубиты, логические вентили и квантовые схемы, а также объясняется отличие квантовой архитектуры от традиционной. Вы сможете бесплатно экспериментировать с ними как в симуляторе, так и на реальном квантовом устройстве с применением IBM Q Experience.

Вы узнаете, как выполняются квантовые вычисления с помощью QISKit (программный инструментарий для обработки квантовой информации), Python SDK и других API, в частности QASM.

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

Вы научитесь: • Удаленно запускать программы, пользуясь Q Experience REST API. • Писать алгоритмы, обеспечивающие высочайшую производительность по сравнению с аналогами для традиционных компьютеров. • Создавать REST-клиент на Node.js для аутентификации, прослушивания удаленных устройств, запроса информации о квантовых процессорах, удаленного контроля и запуска экспериментов в облаке. • Использовать квантовую телепортацию. Воспользовавшись классическими вычислениями и квантовой запутанностью между отправителем и получателем, передавать точное состояние кубита (квантовой информации). • Программировать и играть в квантовый вариант «Морского боя». • Использовать Q Experience Composer для создания визуальных программ/экспериментов.

Отрывок. Теория игр: с квантовой механикой преимущество всегда на вашей стороне


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

  • Загадка про фальшивую монету. Это классическая задача на взвешивание, предложенная математиком Е. Д. Шеллом в 1945 году. В ней нужно при помощи лабораторных весов за ограниченное число взвешиваний определить монету, вес которой отличается от веса других (фальшивую).
  • Магический квадрат Мермина — Переса. Это пример квантовой псевдотелепатии, или способности игроков достигать результатов, которые возможны, только если они во время игры читают мысли друг друга.

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

Загадка про фальшивую монету


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

1. Положите монеты 1–3 на левую чашу весов, а 4–6 — на правую. Отложите на время монеты 7 и 8.

2. Если перевесила правая чаша весов, то фальшивая — среди монет 1–3 (слева). Помните, что поддельная монета легче. Затем уберите монету 3 и положите на левую чашу весов монету 1, а на правую — монету 2.

  • Если перевешивает правая чаша, то фальшивая — монета 1.
  • Если перевешивает левая чаша, то фальшивая — монета 2.
  • Если весы уравновесились, то фальшивая — монета 3.

3. Если перевесила левая чаша весов, то фальшивая — среди монет 4–6. Уберите монету 6 и положите на левую чашу весов монету 4, а на правую — монету 5.

  • Если перевешивает правая чаша, то фальшивая — монета 4.
  • Если перевешивает левая чаша, то фальшивая — монета 5.
  • Если весы уравновесились, то фальшивая — монета 6.

4. Если весы уравновесились, то фальшивая монета либо 7, либо 8. Положите на левую чашу весов монету 7, а на правую — монету 8 и взвесьте.

  • Если перевешивает правая чаша, то фальшивая — монета 7.
  • Если перевешивает левая чаша, то фальшивая — монета 8.

Классический алгоритм можно реализовать вне зависимости от общего числа монет N и количества фальшивых монет k. В целом временная сложность для обобщенной задачи о поддельной монете составляет O(k log(N/k)).

ПРИМЕЧАНИЕ
Было доказано, что для обнаружения одной фальшивой монеты при помощи лабораторных весов на классическом компьютере нужны минимум две попытки.


image

Квантовый способ решения


Хотите верьте, хотите нет, но существует квантовый алгоритм, который может найти фальшивую монету за одно квантовое взвешивание вне зависимости от количества монет N! Вообще говоря, для любого количества фальшивых монет k независимо от N временная сложность такого алгоритма составляет image

ПРИМЕЧАНИЕ
Квантовый алгоритм определения фальшивой монеты является примером ускорения четвертой степени по сравнению с его классическим аналогом.

Так, на рис. 7.2 показано превосходство квантового алгоритма над классическим аналогом при решении загадки про фальшивую монету. Рассмотрим его подробнее. Квантовый алгоритм поиска одной фальшивой монеты image можно разделить на три этапа: запрос к квантовым весам, создание квантовых весов и определение фальшивой монеты.

image

Шаг 1. Запрос к квантовым весам


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

image

Алгоритм действий следующий.

1. Использовать два квантовых регистра для запроса к квантовым весам, где первый регистр предназначен для строки запроса, а второй — для результата.

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

3. Для получения суперпозиции состояний с четным количеством единиц выполнить преобразование Адамара в базисном состоянии и проверить, является ли вес Хэмминга для |x| четным. Может быть показано, что вес Хэмминга для |x| является четным тогда и только тогда, когда x1 ? x2 ? … ? xN = 0.

ПРИМЕЧАНИЕ
Вес Хэмминга (hw) строки — это количество символов, отличных от нулевого символа используемого алфавита. Например, hw(11101) = 4, hw(11101000) = 4, hw(000000) = 0.

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

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

ПРИМЕЧАНИЕ
Для упрощения восприятия программа определения фальшивой монеты разбита на листинги 7.1–7.3. Хотя я рассчитываю, что вы сможете объединить эти листинги для запуска программы, полный код есть в исходниках в файле Workspace\Ch07\p_counterfeitcoin.py.

Листинг 7.1. Скрипт запроса к квантовым весам

# ------- Запрос к квантовым весам
Q_program = QuantumProgram()
Q_program.set_api(Qconfig.APItoken, Qconfig.config["url"])

# Создание numberOfCoins +1 квантовых/классических регистров
# Один дополнительный кубит для запоминания результата
# квантовых весов
qr = Q_program.create_quantum_register("qr", numberOfCoins + 1)

# для запоминания измерения на qr
cr = Q_program.create_classical_register("cr", numberOfCoins + 1)

circuitName = "QueryStateCircuit"
circuit = Q_program.create_circuit(circuitName, [qr], [cr])

N = numberOfCoins

# Создание равновзвешенной суперпозиции всех строк длиной N
for i in range(N):
     circuit.h(qr[i])

# Выполнение XOR(x) с последовательным применением вентилей CNOT с qr[0]
# по qr[N–1] и сохранением результата в qr[N]
for i in range(N):
     circuit.cx(qr[i], qr[N])

# Измерение qr[N] и сохранение результата в cr[N]. продолжить,
# если cr[N] равен нулю, в противном случае повторить измерение
circuit.measure(qr[N], cr[N])

# Сделать запрос к квантовым весам, если значение нулевое для всех
# cr[0]...cr[N], подготовив состояние вентиля Адамара |1>,
# то есть |0> - |1> в qr[N]
circuit.x(qr[N]).c_if(cr, 0)
circuit.h(qr[N]).c_if(cr, 0)

# повторить заново вычисление при ненулевом cr[N]
for i in range(N):
     circuit.h(qr[i]).c_if(cr, 2**N)

На рис. 7.3 приведена полная схема для загадки о фальшивой монете с восемью монетами и одной фальшивой с индексом 6. На ней показаны все описанные здесь этапы для платформы IBM Q Experience. Второй этап алгоритма — создание весов.

image

Шаг 2. Создание квантовых весов


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

image

Это реализовано с помощью вентиля CNOT с xk в качестве управляющего кубита и второго регистра в качестве целевого (см. листинг 7.2).

Листинг 7.2. Создание квантовых весов

#----- Создать квантовые весы
k = indexOfFalseCoin

# Применить квантовые весы к желаемой суперпозиции состояний
# (помеченной как cr, равное нулю)
circuit.cx(qr[k], qr[N]).c_if(cr, 0)

Шаг 3. Определение фальшивой монеты


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

Листинг 7.3. Определение фальшивой монеты

# --- Определение фальшивой монеты
# Применение преобразования Адамара к qr[0] ... qr[N-1]
for i in range(N):
     circuit.h(qr[i]).c_if(cr, 0)

# Измерение qr[0] ... qr[N–1]
for i in range(N):
     circuit.measure(qr[i], cr[i])

results = Q_program.execute([circuitName], backend=backend, shots=shots)
answer = results.get_counts(circuitName)

print("Device " + backend + " counts " + str(answer))

# Получение наиболее часто встречающейся метки
for key in answer.keys():
     normalFlag, _ = Counter(key[1:]).most_common(1)[0]

for i in range(2,len(key)):
     if key[i] != normalFlag:
          print("False coin index is: ", len(key) - i - 1)

Когда крайний слева бит равен 0, индекс фальшивой монеты можно определить, если найти ту, чей вес отличается от веса остальных. Например, при N = 8 и индексе фальшивой монеты 6 результат должен быть 010111111 или 001000000. Обратите внимание на то, что, поскольку мы используем cr[N] для управления операцией до начала и после запроса к весам:

  • если крайний слева бит равен 0, то мы успешно определили фальшивую монету;
  • если крайний слева бит равен 1, то мы не получили желаемой суперпозиции и должны повторить процесс сначала.

При запуске программы на удаленном моделирующем устройстве IBM Q Experience будет получен результат, приведенный в исходниках книги Workspace\Ch07\p_counterfeitcoin.py. Обратите внимание, что я использую Windows:

c:\python36-64\python.exe p_counterfeitcoin.py
Device ibmq_qasm_simulator counts {'001000000': 1}
False coin index is: 6

Если у вас нет доступа к исходникам книги, но вы все равно хотите поэкспериментировать с этим скриптом, то поместите отрывки кода из предыдущих разделов в скрипт-контейнер из листинга 7.4 (проверьте отступы, эта особенность синтаксиса Python просто сводит с ума).

Листинг 7.4. Основной скрипт-контейнер для загадки про фальшивую монету

import sys
import matplotlib.pyplot as plt
import numpy as np
from math import pi, cos, acos, sqrt
from collections import Counter
from qiskit import QuantumProgram
sys.path.append('../Config/')
import Qconfig

# Импорт основных средств для вывода графики
import basic plot tools
from qiskit.tools.visualization import plot_histogram

def main(M = 16, numberOfCoins = 8 , indexOfFalseCoin = 6
      , backend = "local_qasm_simulator" , shots = 1 ):

      if numberOfCoins < 4 or numberOfCoins >= M:
           raise Exception("Please use numberOfCoins between 4 and ", M-1)
      if indexOfFalseCoin < 0 or indexOfFalseCoin >= numberOfCoins:
           raise Exception("indexOfFalseCoin must be between 0 and ",
           numberOfCoins-1)

      // Вставьте листинги 7.1–7.3 сюда

#################################################
# main
#################################################
if __name__ == '__main__':
     M = 8                      # Максимальное количество доступных кубитов
     numberOfCoins = 4          # До M-1, где M — количество доступных кубитов
     indexOfFalseCoin = 2             # Должен быть 0, 1... numberOfCoins — 1

     backend = "ibmq_qasm_simulator"
     #backend = "ibmqx3"
     shots = 1                         # Мы проводим эксперимент с одним запуском

     main(M, numberOfCoins, indexOfFalseCoin, backend, shots)

Обобщенный алгоритм для любого количества фальшивых монет


Для загадки про фальшивую монету математики Терхал и Смолин в 1998 году создали обобщенный алгоритм для любого количества фальшивых монет (k > 1). В их реализации используется модель «Б-оракул» («балансный оракул»), при этом:

  • на вход поступает image
  • создается строка запроса, состоящая из N троек таких битов, что imageс одинаковым количеством 1 и –1;
  • ответом является один такой бит, что
    image

ПРИМЕЧАНИЕ
Оракул является частью алгоритма, рассматриваемой как черный ящик. Он используется для упрощения схем и сравнения сложности квантовых и классических алгоритмов. Хороший оракул должен быть быстрым, универсальным и легко реализуемым.

Пример применения Б-оракула для двух фальшивых монет с k = 2 и N = 6 приведен на рис. 7.4.

image

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

Об авторе


Владимир Сильва окончил Государственный университет Мидл Теннесси (Middle TN State University), получив диплом магистра в области Computer Science. На протяжении пяти лет он работал в IBM инженером-исследователем (Research Engineer), где приобрел богатый опыт в распределенных и GRID-вычислениях.

У Владимира есть множество сертификатов, в том числе OCP (Oracle Certified Professional), MCSD (Microsoft Certified Solutions Developer) и MCP (Microsoft Certified Professional). Кроме того, он является автором большого количества технических статей для сайта IBM developerWorks. Он написал следующие книги: Grid Computing for Developers (Charles River Media), Practical Eclipse Rich Client Platform (Apress), Pro Android Games (Apress) и Advanced Android 4 Games (Apress).

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

О научных редакторах


Оригинальное издание

Джейсон Уайтхорн — опытный предприниматель и разработчик программного обеспечения. Он помог многим нефтегазовым компаниям автоматизировать и усовершенствовать их технологии с помощью сбора эксплуатационных данных, SCADA (Supervisory Control and Data Acquisition — диспетчерское управление и сбор данных) и машинного обучения. Джейсон окончил Арканзасский государственный университет (Arkansas State University), получив диплом бакалавра в области Computer Science.

Свободное время Джейсон любит проводить со своей женой и четырьмя детьми. Живет в Талсе, штат Оклахома. Больше информации о Джейсоне можно найти на его сайте jason.whitehorn.us.

Русскоязычное издание

Михаил Коробко — физик, занимается теорией и экспериментами по применению методов квантовой оптики, оптомеханики и квантовых измерений для улучшения чувствительности гравитационно-волновых детекторов. С 2012 года состоит в международной коллаборации ученых гравитационно-волнового детектора LIGO.

Михаил закончил физический факультет МГУ им. Ломоносова, в настоящий момент является аспирантом Института лазерной физики в университете Гамбурга. Свободное время он проводит с семьей, пишет научно-популярные статьи о квантовой физике и публикует посты в «Твиттере» (@hbar_universe).

» Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок

Для Хаброжителей скидка 25% по купону — Силва

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.