7. Теория игр: с квантовой механикой преимущество всегда на вашей стороне
В этой главе исследуются две игровые загадки, которые демонстрируют впечатляющее превосходство квантовых алгоритмов в сравнении с их классическими аналогами.
• Загадка про фальшивую монету. Это классическая задача на взвешивание, предложенная математиком Е.Д. Шеллом в 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)).
Примечание
Было доказано, что для обнаружения одной фальшивой монеты при помощи лабораторных весов на классическом компьютере нужны минимум две попытки.
Рис. 7.1. Решение загадки про фальшивую монету для восьми монет
Квантовый способ решения
Хотите верьте, хотите нет, но существует квантовый алгоритм, который может найти фальшивую монету за одно квантовое взвешивание вне зависимости от количества монет N! Вообще говоря, для любого количества фальшивых монет k независимо от N временная сложность такого алгоритма составляет O(k1/4).
Примечание
Квантовый алгоритм определения фальшивой монеты является примером ускорения четвертой степени по сравнению с его классическим аналогом.
Так, на рис. 7.2 показано превосходство квантового алгоритма над классическим аналогом при решении загадки про фальшивую монету. Рассмотрим его подробнее. Квантовый алгоритм поиска одной фальшивой монеты (k = 1) можно разделить на три этапа: запрос к квантовым весам, создание квантовых весов и определение фальшивой монеты.
Рис. 7.2. Сравнение временной сложности квантового и классического алгоритмов для загадки про фальшивую монету
Шаг 1. Запрос к квантовым весам
Квантовый алгоритм будет выполнять запрос к квантовым весам в суперпозиции. Чтобы сделать это, используем бинарную строку запроса для кодирования монет на чашах весов. Например, строка запроса 11101111 означает, что на весах лежат все монеты, кроме монеты с индексом 3. Весы уравновешены, если нет ни одной фальшивой монеты, и наклонены в ином случае. Это проиллюстрировано в следующей таблице.
| Количество монет N | Индекс фальшивой монеты F | Строка запроса | Результат |
| 8 | 3 | 11101111 | Весы уравновешены (0) |
| 8 | 3 | 11111111 | Весы наклонены (1) |
Алгоритм действий следующий.
1. Использовать два квантовых регистра для запроса к квантовым весам, где первый регистр предназначен для строки запроса, а второй — для результата.
2. Подготовить суперпозицию всех бинарных строк запроса с четным количеством единиц.
3. Для получения суперпозиции состояний с четным количеством единиц выполнить преобразование Адамара в базисном состоянии 
и проверить, является ли вес Хэмминга для |x| четным. Может быть показано, что вес Хэмминга для |x| является четным тогда и только тогда, когда x1 ⊕x2 ⊕ … ⊕xN = 0.
Примечание
Вес Хэмминга (hw) строки — это количество символов, отличных от нулевого символа используемого алфавита. Например, hw(11101) = 4, hw(11101000) = 4, hw(000000) = 0.
4. Наконец, измерить второй регистр. Если наблюдается состояние 
, то первый регистр является суперпозицией всех желаемых бинарных строк запроса. Если получено 
, то нужно повторять процедуру, пока не будет наблюдаться состояние 
.
Обратите внимание, что при каждом повторе вероятность успеха составляет точно 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. Второй этап алгоритма — создание весов.
Рис. 7.3. Квантовая схема для загадки про фальшивую монету с N = 8, k = 1 и фальшивой монетой с индексом 6 (этот граф в полную величину можно найти на странице загрузки исходного кода)
Шаг 2. Создание квантовых весов
В предыдущем разделе мы создали суперпозицию всех бинарных строк запроса, у которых вес Хэмминга четный. На данном шаге создаем квантовый балансир, устанавливая позицию фальшивой монеты. Таким образом, если k — позиция фальшивой монеты относительно бинарной строки 
, то квантовые весы вернут:
.
Это реализовано с помощью вентиля 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). В их реализации используется модель «Б-оракул» («балансный оракул»), при этом:
• на вход поступает N бит x = x1x2…xn ∈ {0, 1}N;
• создается строка запроса, состоящая из N троек таких битов, что q = q1q2…qn Є {0, 1, −1}N, с одинаковым количеством 1 и –1;
• ответом является один такой бит, что
Примечание
Оракул является частью алгоритма, рассматриваемой как черный ящик. Он используется для упрощения схем и сравнения сложности квантовых и классических алгоритмов. Хороший оракул должен быть быстрым, универсальным и легко реализуемым.
Пример применения Б-оракула для двух фальшивых монет с k = 2 и N = 6 приведен на рис. 7.4.
Рис. 7.4. Модель Б-оракула для k = 2 и N = 6
В общем, загадка о фальшивой монете — типичный пример ускорения квантового алгоритма по сравнению с классическим аналогом. В следующем разделе рассмотрим еще одну своеобразную псевдомагическую головоломку под названием «магический квадрат Мермина — Переса».
Магический квадрат Мермина — Переса
Это еще одна классическая загадка, впервые предложенная физиками Д. Мермином и А. Пересом в качестве примера квантовой псевдотелепатии, или способности двух игроков общаться сверхъестественным образом незаметно для наблюдателей. Это возможно благодаря волшебству запутывания. Рассмотрим ее подробнее.
Два игрока, Алиса и Боб, ведут игру против арбитра. Магический квадрат — это матрица размерностью 3 × 3 со следующими правилами (рис. 7.5).
• Все элементы представлены либо 0, либо 1, так что сумма элементов в каждой строке четная, а в каждом столбце — нечетная. Игра называется магическим квадратом, потому что подобный квадрат невозможен. Как показано на рис. 7.5, не существует верной комбинации, где сумма строк четная, а столбцов — нечетная (возьмите бумагу и ручку и проверьте сами). Это обусловлено нечетным количеством элементов в матрице.
Арбитр отправляет целое число a∈ {1, 2, 3} Алисе, а b∈ {1, 2, 3} — Бобу. Ответом Алисы должна быть a-я строка квадрата, ответом Боба — b-й столбец.
• Алиса и Боб выигрывают, если сумма элементов Алисы четная, а Боба — нечетная и в пересечении их ответов находятся одинаковые значения. В противном случае побеждает арбитр.
• Перед стартом Алиса и Боб могут разработать стратегию и обменяться информацией. Например, могут решить давать ответы при помощи матрицы, приведенной на рис. 7.5. Однако им не разрешается общаться во время игры.
Рис. 7.5. Магический квадрат Мермина — Переса
К примеру, в приведенной ранее матрице, если бы арбитр отправил a = 1 Алисе и b = 2 — Бобу, ответом Алисы было бы 110 (первая строка), а Боба — 100 (второй столбец). Элементы, находящиеся на пересечении ответов (первой строки и второго столбца), одни и те же (1), поэтому Алиса и Боб выигрывают. Можно показать, что в классическом варианте максимальная вероятность победы для Алисы и Боба составляет 8/9. То есть в данном квадрате восемь из девяти перестановок являются выигрышными. Поэтому максимальная вероятность победы Алисы и Боба — 88,8 %.
Протестируем это утверждение на простом примере, чтобы доказать, что максимальная вероятность выигрыша для классической версии магического квадрата действительно составляет 8/9 (88,88 %).
Упражнение для магического квадрата Мермина — Переса
1. Создайте магический квадрат, аналогичный приведенному на рис. 7.5, используя бинарный код (1, –1) вместо (1, 0), где произведение элементов строки 1 (четное), а произведение элементов столбца — –1 (нечетное). Подтвердите, что это фактически невозможно.
2. Создайте таблицу перестановок для значений a и b арбитра при помощи квадрата из первого шага, включающую:
• номер перестановки;
• значения для a и b;
• ответы Алисы и Боба;
• значения на пересечении ответов Алисы и Боба (помните, они должны быть одинаковыми, чтобы Алиса и Боб победили);
• результат итерации игры: Win = W (победа), Loose = L (поражение).
3. Наконец, рассчитайте вероятность победы и докажите, что максимально она составляет 8/9. (Примечание: ответ приведен в конце главы.)
Квантовая стратегия победы
Благодаря мощи квантовой механики и магии запутывания результаты Алисы и Боба можно значительно улучшить. Фактически они могут выигрывать в 100 % случаев, как если бы общались телепатически (отсюда и термин «псевдотелепатия»). Квантовая стратегия победы впервые была предложена Брассардом и его коллегами, она подразделяется на три этапа.
1. Общее запутанное состояние. Это ключ к победам Алисы и Боба в 100 % случаев.
2. Унитарные преобразования входных данных Алисы и Боба. Так создаются ответы, которые отправляются арбитру.
3. Измерения в вычислительном базисе. Конечный этап создания окончательного ответа.
Общее запутанное состояние
В квантовой стратегии победы у Алисы и Боба общее запутанное состояние:
.
Для реализации схемы требуются два кубита для Алисы и два кубита для Боба (рис. 7.6).
Рис. 7.6. Запутанное состояние для магического квадрата
• Известно, что преобразование Адамара сопоставляет базисному состоянию:
.
• Применение данного преобразования к первым двум кубитам дает:
.
• Затем к первым двум кубитам применяется вентиль Z. Помните, что он оставляет нулевое состояние неизменным и переводит 1 в –1, меняя на противоположный знак при третьем члене в приведенном ранее выражении. На данном этапе состояние принимает вид:
.
• Затем для запутывания кубитов 0–2 и 1–3 применяется вентиль CNOT:
.
• Наконец, состояния двух последних кубитов меняются на противоположные:
.
Скрипт Python для создания запутанного состояния приведен в листинге 7.5.
Листинг 7.5. Квантовая стратегия победы, запутанное состояние
# Создание запутанного состояния
Q_program = QuantumProgram()
Q_program.set_api(Qconfig.APItoken, Qconfig.config["url"])
# Четыре кубита (Alice = 2, Bob = 2)
N = 4
# Создание регистров
qr = Q_program.create_quantum_register("qr", N)
# для запоминания результата измерения на qr
cr = Q_program.create_classical_register("cr", N)
circuitName = "sharedEntangled"
sharedEntangled = Q_program.create_circuit(circuitName, [qr], [cr])
# Создание равновзвешенной суперпозиции всех строк длиной 2
for i in range(2):
sharedEntangled.h(qr[i])
# Амплитуда отрицательная, если количество единиц нечетное
for i in range(2):
sharedEntangled.z(qr[i])
# Копирование содержимого первых двух кубитов в последние два кубита
for i in range(2):
sharedEntangled.cx(qr[i], qr[i+2])
# Изменение состояния последних двух кубитов на противоположное
for i in range(2,4):
sharedEntangled.x(qr[i])
Теперь, когда у Алисы и Боба есть общее запутанное состояние, они могут начать игру и получить входные данные от арбитра.
Унитарные преобразования
Получив свои входные данные a ∈ {1, 2, 3} и b ∈ {1, 2, 3}, Алиса и Боб применяют к общим запутанным состояниям следующие унитарные преобразования: A1, A2, A3 для Алисы и B1, B2, B3 — для Боба.
Примечание
Обратите внимание, что, применив приведенные ранее преобразования к своим запутанным состояниям, Алиса и Боб смогут создать первые два бита соответствующих ответов арбитру.
В листинге 7.6 показаны унитарные преобразования для Алисы и Боба, а соответствующие им графические схемы приведены в табл. 7.1.
Листинг 7.6. Унитарные преобразования для Алисы и Боба
#------ Схемы для операций, производимых Алисой и Бобом.
# Сначала определяем управляемые U-вентили, необходимые
# для назначения фаз
from math import pi
def ch(qProg, a, b):
""" Controlled-Hadamard gate """
qProg.h(b)
qProg.sdg(b)
qProg.cx(a, b)
qProg.h(b)
qProg.t(b)
qProg.cx(a, b)
qProg.t(b)
qProg.h(b)
qProg.s(b)
qProg.x(b)
qProg.s(a)
return qProg
def cu1pi2(qProg, c, t):
""" Controlled-u1(phi/2) gate """
qProg.u1(pi/4.0, c)
qProg.cx(c, t)
qProg.u1(-pi/4.0, t)
qProg.cx(c, t)
qProg.u1(pi/4.0, t)
return qProg
def cu3pi2(qProg, c, t):
""" Controlled-u3(pi/2, -pi/2, pi/2) gate """
qProg.u1(pi/2.0, t)
qProg.cx(c, t)
qProg.u3(-pi/4.0, 0, 0, t)
qProg.cx(c, t)
qProg.u3(pi/4.0, -pi/2.0, 0, t)
return qProg
#----------------------------------------------------------------------
# Определение схем, которые Алиса и Боб используют
# для всех своих входных данных: 1, 2, 3
# Словарь для операций и схем Алисы
aliceCircuits = {}
# Квантовые схемы для входных данных Алисы 1, 2, 3
for idx in range(1, 4):
circuitName = "Alice"+str(idx)
aliceCircuits[circuitName]
= Q_program.create_circuit(circuitName, [qr], [cr])
theCircuit = aliceCircuits[circuitName]
if idx == 1:
# Схема для A_1
theCircuit.x(qr[1])
theCircuit.cx(qr[1], qr[0])
theCircuit = cu1pi2(theCircuit, qr[1], qr[0])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit = cu3pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit = ch(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0]) theCircuit.x(qr[1])
theCircuit.cx(qr[1], qr[0])
theCircuit.x(qr[1])
elif idx == 2:
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.h(qr[0])
theCircuit.h(qr[1])
elif idx == 3:
theCircuit.cz(qr[0], qr[1])
theCircuit.swap(qr[0], qr[1]) # Не поддерживается в composer
theCircuit.h(qr[0])
theCircuit.h(qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit.cz(qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
# Измерение первых двух кубитов в вычислительном базисе
theCircuit.measure(qr[0], cr[0])
theCircuit.measure(qr[1], cr[1])
# Словарь для операций и схем Боба
bobCircuits = {}
# Квантовые схемы для Боба при получении входных данных 1, 2, 3
for idx in range(1,4):
circuitName = "Bob"+str(idx)
bobCircuits[circuitName]
= Q_program.create_circuit(circuitName, [qr], [cr])
theCircuit = bobCircuits[circuitName]
if idx == 1:
theCircuit.x(qr[2])
theCircuit.x(qr[3])
theCircuit.cz(qr[2], qr[3])
theCircuit.x(qr[3])
theCircuit.u1(pi/2.0, qr[2])
theCircuit.x(qr[2])
theCircuit.z(qr[2])
theCircuit.cx(qr[2], qr[3])
theCircuit.cx(qr[3], qr[2])
theCircuit.h(qr[2])
theCircuit.h(qr[3])
theCircuit.x(qr[3])
theCircuit = cu1pi2(theCircuit, qr[2], qr[3])
theCircuit.x(qr[2])
theCircuit.cz(qr[2], qr[3])
theCircuit.x(qr[2])
theCircuit.x(qr[3])
elif idx == 2:
theCircuit.x(qr[2])
theCircuit.x(qr[3])
theCircuit.cz(qr[2], qr[3])
theCircuit.x(qr[3])
theCircuit.u1(pi/2.0, qr[3])
theCircuit.cx(qr[2], qr[3])
theCircuit.h(qr[2])
theCircuit.h(qr[3])
elif idx == 3:
theCircuit.cx(qr[3], qr[2])
theCircuit.x(qr[3])
theCircuit.h(qr[3])
# Измерение 3-го и 4-го кубитов в вычислительном базисе
theCircuit.measure(qr[2], cr[2])
theCircuit.measure(qr[3], cr[3])
В табл. 7.1 показаны квантовые схемы для унитарных преобразований A1–2 и B1–3 для IBM Q Experience Composer.
Таблица 7.1. Квантовые схемы для унитарных преобразований из листинга 7.6
| Преобразование | Схема |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Обратите внимание, что в табл. 7.1 не включено преобразование A3 ввиду того, что Composer не поддерживает вентиль SWAP, который необходим для кода из листинга 7.6. Тем не менее это не значит, что квантовую программу нельзя запустить на моделирующем или реальном устройстве. Это просто означает, что схема не будет создана в Composer. Поэтому на последнем шаге Алиса и Боб измеряют свои кубиты в вычислительном базисе.
Измерение в вычислительном базисе
После измерения у Алисы и Боба есть по два бита, которые представляют результаты измерений. Чтобы получить последний бит и, таким образом, окончательный ответ, они применяют свои правила проверки четности. То есть у Алисы сумма должна быть четной, а у Боба — нечетной, например для a = 2, для b = 3 (табл. 7.2):
Таблица 7.2. Перестановки ответов для магического квадрата при a = 2, b = 3
| ψ | Ответ Алисы | Ответ Боба | Квадрат |
|
| 000 | 001 |
|
|
| 000 | 100 |
|
|
| 011 | 010 |
|
|
| 011 | 111 |
|
|
| 101 | 010 |
|
|
| 101 | 111 |
|
|
| 110 | 001 |
|
|
| 110 | 101 |
|
В листинге 7.7 показан фрагмент скрипта для прохода в цикле по всем раундам магического квадрата.
• Проход в цикле по a[1, 3] и b[1, 3] включительно.
• Для каждых (a, b) схемы Алисы (Alice-a) и Боба (Bob-b) возвращаются в исходное состояние из листинга 7.6.
• Общее запутанное состояние ψ и схемы Алисы и Боба загружаются для запуска на моделирующее или реальное квантовое устройство.
• Для Алисы и Боба из ответа извлекается по два бита, например {'0011': 1}.
• Применение правил проверки четности: у Алисы сумма должна быть четной, а у Боба — нечетной.
• В конце ответ проверяется на корректность и отображается вероятность победы.
Листинг 7.7. Скрипт для всех раундов магического квадрата
def all_rounds(backend, real_dev, shots=10):
nWins = 0
nLost = 0
for a in range(1,4):
for b in range(1,4):
print("Asking Alice and Bob with a and b are: ", a,b)
rWins = 0
rLost = 0
aliceCircuit = aliceCircuits["Alice" + str(a)]
bobCircuit = bobCircuits["Bob" + str(b)]
circuitName = "Alice" + str(a) + "Bob"+str(b)
Q_program.add_circuit(circuitName,
sharedEntangled+aliceCircuit+
bobCircuit)
if real_dev:
ibmqx2_backend = Q_program.get_backend_
configuration(backend)
ibmqx2_coupling = ibmqx2_backend['coupling_map']
results = Q_program.execute([circuitName],
backend=backend, shots=shots
, coupling_map=ibmqx2_coupling, max_credits=3,
wait=10, timeout=240)
else:
results = Q_program.execute([circuitName],
backend=backend, shots=shots)
answer = results.get_counts(circuitName)
for key in answer.keys():
kfreq = answer[key]
# Частоты появления ключей, полученные при измерениях
aliceAnswer = [int(key[-1]), int(key[-2])]
bobAnswer = [int(key[-3]), int(key[-4])]
if sum(aliceAnswer) % 2 == 0:
aliceAnswer.append(0)
else:
aliceAnswer.append(1)
if sum(bobAnswer) % 2 == 1:
bobAnswer.append(0)
else:
bobAnswer.append(1)
if(aliceAnswer[b-1] != bobAnswer[a-1]):
#print(a, b, "Alice and Bob lost")
nLost += kfreq
rLost += kfreq
else:
#print(a, b, "Alice and Bob won")
nWins += kfreq
rWins += kfreq
print("\t#wins = ", rWins, "out of ", shots, "shots")
print("Number of Games = ", nWins+nLost)
print("Number of Wins = ", nWins)
print("Winning probabilities = ", (nWins*100.0)/(nWins+nLost))
#################################################
# main
################################################# if __name__ == '__main__':
backend = "ibmq_qasm_simulator"
#backend = "ibmqx2"
real_dev = False
all_rounds(backend, real_dev)
Запуск листинга 7.7 на удаленном моделирующем устройстве IBM Q Experience показан в листинге 7.8.
Листинг 7.8. Упрощенный стандартный вывод для запуска всех раундов магического квадрата
c:\python36-64\python.exe p_magicsq.py
For a = 1, b = 1
ibmq_qasm_simulator answer: 1000 Alice: [0, 0, 0] Bob:[0, 1, 0]
ibmq_qasm_simulator answer: 1010 Alice: [0, 1, 1] Bob:[0, 1, 0]
ibmq_qasm_simulator answer: 1111 Alice: [1, 1, 0] Bob:[1, 1, 1]
ibmq_qasm_simulator answer: 0111 Alice: [1, 1, 0] Bob:[1, 0, 0]
ibmq_qasm_simulator answer: 0000 Alice: [0, 0, 0] Bob:[0, 0, 1]
ibmq_qasm_simulator answer: 0101 Alice: [1, 0, 1] Bob:[1, 0, 0]
# 10 побед при 10 запусках
For a = 1, b = 2
ibmq_qasm_simulator answer: 1000 Alice: [0, 0, 0] Bob:[0, 1, 0]
ibmq_qasm_simulator answer: 1001 Alice: [1, 0, 1] Bob:[0, 1, 0]
ibmq_qasm_simulator answer: 1111 Alice: [1, 1, 0] Bob:[1, 1, 1]
ibmq_qasm_simulator answer: 0110 Alice: [0, 1, 1] Bob:[1, 0, 0]
ibmq_qasm_simulator answer: 0000 Alice: [0, 0, 0] Bob:[0, 0, 1]
ibmq_qasm_simulator answer: 0001 Alice: [1, 0, 1] Bob:[0, 0, 1]
# 10 побед при 10 запусках
...
For a = 3, b = 3
ibmq_qasm_simulator answer: 1000 Alice: [0, 0, 0] Bob:[0, 1, 0]
ibmq_qasm_simulator answer: 1011 Alice: [1, 1, 0] Bob:[0, 1, 0]
ibmq_qasm_simulator answer: 1101 Alice: [1, 0, 1] Bob:[1, 1, 1]
ibmq_qasm_simulator answer: 1110 Alice: [0, 1, 1] Bob:[1, 1, 1]
ibmq_qasm_simulator answer: 0111 Alice: [1, 1, 0] Bob:[1, 0, 0]
ibmq_qasm_simulator answer: 0010 Alice: [0, 1, 1] Bob:[0, 0, 1]
# 10 побед при 10 запусках
Number of Games = 90
Number of Wins = 90
Winning probability = 100.0
Примечание
При запуске на реальном устройстве вероятность выигрыша не будет 100%-ной из-за шумов окружающей среды и ошибок вентилей.
Ответы для упражнения с магическим квадратом
1. Магический квадрат, в котором произведение строки четное, а произведение столбца — нечетное, приведен далее. На самом деле такого квадрата не бывает ввиду нечетного числа клеток.
2. Таблица перестановок для квадрата из первого ответа.
| N | a | b | Алиса | Боб | Пересечение | Победа/поражение (W/L) |
| 1 | 1 | 1 | –1, –1, 1 | –1, –1, –1 | –1/–1 | W |
| 2 | 1 | 2 | –1, –1, 1 | –1, 1, 1 | –1/–1 | W |
| 3 | 1 | 3 | –1, –1, 1 | 1, –1, ? (1) | 1/1 | W |
| 4 | 2 | 1 | –1, 1, –1 | –1, –1, –1 | –1/–1 | W |
| 5 | 2 | 2 | –1, 1, –1 | –1, 1, 1 | 1/1 | W |
| 6 | 2 | 3 | –1, 1, –1 | 1, –1, ? (1) | –1/–1 | W |
| 7 | 3 | 1 | –1, 1, ? (–1) | –1, –1, –1 | –1/–1 | W |
| 8 | 3 | 2 | –1, 1, ? (–1) | –1, 1, 1 | 1/1 | W |
| 9 | 3 | 3 | –1, 1, ? (–1) | 1, –1, ? (1) | –1/1 | L |
3. Обратите внимание, что на предыдущем шаге в строках 7–9 ответ Алисы должен быть –1, поэтому произведение может быть четным (1). К тому же в столбцах 3, 6 и 9 ответ Боба должен быть 1, в связи с чем произведение может быть нечетным (−1). Наконец, вероятность рассчитывается делением общего числа побед на общее количество перестановок. Таким образом:
.
Из этой главы вы узнали, как квантовая запутанность может обеспечить значительное ускорение по сравнению с классическими вычислениями. Для квантовых весов можно добиться ускорения четвертой степени при решении классических головоломок, таких как загадка про фальшивую монету. В других, таких как магический квадрат, запутывание наделяет игроков псевдомагической телепатией. Если бы Брассард и его коллеги смогли придумать квантовую стратегию выигрыша в блек-джек или покер, мы бы точно сорвали большой куш в Вегасе. В целом эта глава показала, что квантовая механика столь же запутанная, причудливая и увлекательная, как и всегда. Она никогда не разочаровывает.
В следующей, последней главе рассказывается о самом, пожалуй, известном квантовом алгоритме — пресловутой факторизации целых чисел Шора. Это алгоритм, который может нанести сокрушительный удар по асимметричному шифрованию!
Применяют только одно из них соответственно полученному от арбитра номеру. — Примеч. науч. ред.
