РУКОВОДСТВО
Камень, ножницы, бумага: поворот в области квантовых вычислений
Новый способ играть с передовыми вычислениями
Развлекайтесь играми с квантовыми вычислениями
Мне нравится демонстрировать эффекты квантовых вычислений. Особенно через игры, использующие квантовую суперпозицию и запутанность.
Квантовые вычисления — невероятно захватывающая технология, которая повлияет практически на все отрасли и науки. Изучение того, как работают квантовые вычисления и, в частности, чем они отличаются от классических вычислений, может сделать вас лучшим программистом и более логически мыслить!
Итак, я подумал, что было бы забавно придумать игру, которую можно было бы реализовать на квантовом компьютере, чтобы еще больше продемонстрировать различия между квантовыми и традиционными вычислениями.
Нет недостатка в удивительных квантовых подвигах
Квантовые компьютеры обладают многими удивительно мощными (и даже сбивающими с толку!) свойствами по сравнению со своими классическими аналогами.
Повышение производительности за счет экспоненциальной вычислительной мощности, одновременной оценки нескольких сценариев и даже таких простых вещей, как генерация расширенных случайных чисел, — все это может быть достигнуто на квантовом уровне.
Мы сосредоточимся на суперпозиции — методе, который позволяет квантовому компьютеру одновременно оценивать множество различных сценариев. Чтобы было весело — воспользуемся игрой!
Идеи для квантовых игр
Я долго искал идеи игры, которая была бы достаточно простой в использовании, в которую было бы достаточно легко играть, и в которой можно было бы использовать преимущества квантовой обработки.
Также было бы полезно, если бы это никогда не делалось раньше!
Это привело меня к идее классических игр, таких как крестики-нолики, покер и другие игры.
Хотя многие исследовательские работы, сочетающие квантовые вычисления с играми, часто фокусируются на различных алгоритмических подходах и математической сложности, я хотел создать что-то более понятное.
Написание программы квантовых вычислений не должно быть сложным.
Как только вы разберетесь в различных вентилях и поведении кубитов, вы сможете создать широкий спектр квантовых приложений.
Что может быть лучше, чем продемонстрировать это с помощью игры в камень, ножницы, бумага!
Камень ножницы Бумага
«Камень, ножницы, бумага» — игра для двух игроков. В игре каждый игрок тайно выбирает камень, бумагу или ножницы. Игроки обычно считают до трех, а затем одновременно раскрывают свою руку.
Правила игры гласят, что камень побеждает ножницы, ножницы побеждают бумагу, а бумага побеждает камень.
Достаточно просто! Или это?
Математический парадокс
Основополагающий принцип «камень, ножницы, бумага» на самом деле является мерой веса и ценности.
Можно считать, что камень ценится больше, чем ножницы. Точно так же ножницы ценятся больше, чем бумага. Все идет нормально.
Камень › Ножницы › Бумага
Итак, если камень больше ножниц, а ножницы больше бумаги, то, несомненно, камень больше бумаги. Однако по правилам игры бумага ценится больше, чем камень!
Камень › Ножницы › Бумага › Камень?
Это вообще парадокс!
Подумав об этом математически на мгновение
Давайте сделаем шаг назад, чтобы рассмотреть парадокс, который делает игру «камень, ножницы, бумага» такой уникальной.
Учтите, что у нас есть три переменные: A, B и C (представляющие камень, ножницы и бумагу соответственно). Каждой переменной присваивается вес такой, что A › B и B › C. Транзитивное свойство неравенства утверждает, что в соответствии с этим расположением A › C.
Это наводит нас на мысль, что если качать › ножницы и ножницы › бумагу, то качать › бумагу. Ясно, что игра ведется не так!
На самом деле, это предпосылка парадокса Харди.
Парадокс Харди о камне, ножницах и бумаге
Парадокс Харди, разработанный Люсьеном Харди в 1992 году, исследует ситуацию, когда три переменные, которые, казалось бы, выровнены по весу, каждая из которых больше, чем следующая, все же могут создать ситуацию, когда последняя переменная оказывается больше, чем предыдущая. первое — нарушение транзитивного свойства неравенства.
На самом деле, такое нарушение вполне возможно в квантовом мире, где частицы могут запутываться и, по сути, встречаются в игре камень, ножницы, бумага!
Я думаю, мы только что нашли идеальную игру, чтобы продемонстрировать некоторые возможности квантовых вычислений.
Установление правил игры
Мы собираемся создать программу квантовых вычислений, которая сможет найти все выигрышные руки в игре «камень, ножницы, бумага».
Мы создадим как классическую, так и квантовую версию программы, чтобы продемонстрировать разницу в сложности.
Первое, что нам нужно сделать, это закодировать элементы в игре, чтобы мы могли использовать их в алгоритме. Поскольку каждый игрок может выбрать один из трех предметов (камень, ножницы или бумага) в каждом раунде игры, у нас может быть девять различных вариантов игровых комбинаций.
Давайте используем первую букву для каждого элемента, чтобы обозначить возможные варианты выбора каждого игрока в раунде игры. Поэтому возможные руки, которые можно разыграть, показаны ниже.
[RR, RP, RS, PR, PS, PP, SR, SP, SS]
В приведенном выше списке показаны все возможные комбинации, начиная с «камень против камня» (RR), «камень против бумаги» (RP), «камень против ножниц» (RS) и т. д.
Из приведенных выше девяти возможных комбинаций только три являются выигрышными: камень против ножниц (RS), ножницы против бумаги (SP) и бумага против камня (PR).
[RS, SP, PR]
Переход в цифровой мир
Теперь, когда мы определили наши игровые варианты, нам нужно преобразовать эти варианты из букв (R, S, P) в двоичные цифры нуля или единицы. Это необходимо для того, чтобы мы могли в конечном итоге представить выбор в виде кубитов.
Поскольку у нас есть три элемента, мы будем представлять их значениями от нуля до двух (00, 01, 10).
# The Items 00 = Rock 01 = Paper 10 = Scissors
Важно отметить двоичные значения, которые мы присваиваем каждому элементу, так как мы будем ссылаться на них при рассмотрении ввода и вывода наших программ.
Далее давайте определим правила игры с точки зрения первого игрока.
# Rock 00 vs 00 = Tie 00 vs 01 = Loss 00 vs 10 = Win # Paper 01 vs 00 = Win 01 vs 01 = Tie 01 vs 10 = Loss # Scissors 10 vs 00 = Loss 10 vs 01 = Win 10 vs 10 = Tie
Теперь, когда мы определили простое цифровое определение для каждой возможной игровой руки, давайте начнем писать код.
Кодирование игры битами
Теперь, когда наши игровые элементы определены как двоичные значения, мы можем хранить эти значения в кубитах. Давайте создадим объект Python, который определяет каждый элемент с соответствующим значением, как указано в предыдущем разделе выше.
# Encode the choices as qubits.
choices = {
‘rock’: [0,0],
‘paper’: [0,1],
‘scissors’: [1,0]
}
Теперь давайте посмотрим, сможем ли мы найти все возможные выигрышные ходы, которые можно сделать.
Создание логического выражения для выигрыша
Мы уже определили представление для каждого выбора (камень 00, бумага 01, ножницы 10). Поскольку у нас два игрока, на раунд приходится четыре бита.
Один раунд игры может выглядеть так, как показано ниже.
Игрок 1 выбирает камень.
Игрок 2 выбирает бумагу.
камень = 00 и бумага = 01
Введите значение 0001.
Чтобы определить, является ли этот ход выигрышным для первого игрока, нам нужно проверить некоторую логику, диктующую правила игры.
Правила игры гласят, что камень побеждает ножницы, ножницы побеждают бумагу, а бумага побеждает камень.
Мы можем закодировать эти правила, используя булеву логику.
bool isWin = (rock and scissors) or (scissors and paper) or (paper and rock)
Медленный способ найти все выигрышные руки
Давайте начнем с написания классической компьютерной программы для поиска всех выигрышных комбинаций.
Мы можем создать метод с именем check_all_games(), который перебирает список всех возможных комбинаций элементов и возвращает только те комбинации, которые являются выигрышными для первого игрока.
def check_all_games():
# Generate a list of all possible game choices for player1 and player2.
result = []
count = 0
games = list(itertools.product([0, 1], repeat=4))
for game in games:
# Example: (1, 0, 0, 1) => scissors vs paper
player1 = list(game[0:2])
player2 = list(game[2:4])
# A quick check to make sure both player moves are valid.
if player1 in list(choices.values()) and player2 in list(choices.values()):
# ...
is_win = isWin(player1, player2)
if is_win:
result += [game]
count += 1
return (result, count)
([(0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 1)], 16)
Метод возвращает список выигрышных комбинаций, включая «камень против ножниц», «бумага против камня» и «ножницы против бумаги». Он также возвращает количество итераций, которые потребовались для поиска всех комбинаций.
(0, 0, 1, 0) = камень (0, 0) против ножниц (1, 0)
(0, 1, 0, 0) = бумага (0, 1) против камня (0, 0)
(1, 0, 0, 1) = ножницы (1, 0) и бумага (0, 1)
Вы заметили, что для поиска всех выигрышных игр потребовалось 16 итераций? Не говоря уже о том, что итерации включают недопустимые комбинации битов, такие как [1, 1, 1, 1], которые даже не соответствуют действительному элементу!
Может ли квант лучше?
Давайте попробуем это снова. Однако на этот раз мы собираемся создать программу квантовых вычислений, чтобы найти все выигрышные руки.
Так же, как и в классической программе, мы определим функцию isWin(), которая кодирует правила игры.
Квантовая схема черного ящика, кодирующая определенный набор логических правил (например, правила выигрыша в нашей игре), называется оракулом.
Поскольку наш оракул будет работать с двоичными значениями 0 и 1, а не с именами переменных, давайте просто перепишем наше логическое выражение, используя эти значения.
bool isWin = (00 and 10) or (01 and 00) or (10 and 01)
Также, поскольку мы будем использовать библиотеку квантовых вычислений Qiskit, нам нужно будет представить кубиты в обратном порядке. Поэтому мы устроим нашу логику соответствующим образом, поменяв местами правый и левый биты.
[(0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 1)] [(q1 q0 q3 q2),(q1 q0 q3 q2),(q1 q0 q3 q2)]
Первая строка — это наш результат выигрышных рук, полученный из нашей классической программы. Мы просто представляем каждый бит кубитом (обозначается как q0, q1, q2, q3). Кубиты расположены в обратном порядке, так что первые два бита принадлежат первому игроку, а последние два бита — второму игроку. Кубиты каждого игрока расположены так, что младший бит справа, а старший бит слева (соответствует [q1, q0] и [q3, q2]). Мы повторяем это для всех трех выигрышных комбинаций рук.
Создание оракула
Давайте создадим оракул для нашего решения для квантовых вычислений.
Как и в случае с классической программой, мы будем кодировать правила игры с помощью булевой логики. Однако на этот раз разница заключается в том, что мы имеем в виду q0, q1, q2, q3 для обозначения камня, ножниц, бумаги.
Например, первый тип выигрышной руки, закодированный в нашем оракуле, — «камень против ножниц». Мы можем закодировать это, как показано ниже.
Камень против ножниц
(0, 0, 1, 0)
(q1 q0 q3 q2)
Условие первой выигрышной руки
(не q0, не q1, не q2 и q3)
Обратный порядок кубитов
(не q1, не q0 и не q3, а не q2)
Преобразование в двоичный формат
(00 против 10)
Преобразование в игровой раунд
(камень против ножниц)
# Define a classical logical circuit with 4 variables (qubits). isWin = 'def isWin(q0: Int1, q1: Int1, q2: Int1, q3: Int1) -> Int1:\n return (not q0 and not q1 and not q2 and q3) or (q0 and not q1 and not q2 and not q3) or (not q0 and q1 and q2 and not q3)' # Convert the logic to a quantum circuit. formula = ClassicalFunction(isWin) fc = formula.synth() # Convert the quantum circuit to a quantum program. qc = QuantumCircuit(4+1) qc.compose(fc, inplace=True)
Все выигрышные руки кодируются в оракуле одной строкой булевой логики. Это создает схему квантовых вычислений, которую можно использовать в нашей программе для поиска всех выигрышных рук!
Собрав все это вместе, мы можем создать программу квантовых вычислений, используя этот оракул.
# Get the number of qubits needed.
n = len(choices['rock']) * 2
qc = QuantumCircuit(n + 1, 1)
# Paper vs Rock.
qc = encode('paper', 'rock', qc)
# Append the rock, paper, scissors oracle.
qc.append(oracle, range(5))
# Measure the result!
qc.measure(4, 0)
В этом примере мы играем один раунд игры с бумагой против камня. Обратите внимание, что в получившейся программе квантовых вычислений первый кубит (q0) инвертируется с помощью X-Gate до значения один, а второй кубит (q1) остается со значением нуля. Это соответствует (01), который представляет бумагу. Точно так же третий и четвертый кубиты (q2 и q3) остаются равными нулю (00), что соответствует камню.
Это игра бумаги против камня.
Результат нашей программы квантовых вычислений возвращает вывод, указывающий, является ли это выигрышной рукой. Поскольку вывод кубитов идет в обратном порядке (помните, мы читаем справа налево!), ниже я выделил пример вместе с обозначениями, поясняющими каждое значение кубита.
1 00 01
^- win
^^----- rock
^^--------paper
Запуск программы квантовых вычислений
Запустим программу и посмотрим на результат. Поскольку бумага всегда побеждает камень, мы ожидаем, что наша программа выдаст значение, равное единице, по всем измерениям квантовой программы.
simulator = Aer.get_backend('aer_simulator')
job = execute(qc, simulator)
result = job.result()
counts = result.get_counts()
key = max(counts, key=counts.get)
print(counts)
plot_histogram(counts)
{‘1’: 1024}
Действительно, мы можем видеть, что все измерения дают сильное значение, равное единице. Это указывает на то, что бумага против камня — это победа первого игрока!
Точно так же мы можем запустить тот же оракул в раунде игры «бумага против ножниц». В этом раунде мы ожидаем, что результат будет нулевым, поскольку бумага всегда побеждает ножницы.
# Rock vs Scissors.
qc = encode('paper', 'scissors', qc)
{‘0’: 1024}
В очередной раз мы получили правильный ответ, указывающий на то, что это проигрыш для первого игрока.
Что ж, пока мы только определяем, является ли одиночный раунд игры выигрышным для первого игрока. Это не очень впечатляет. В конце концов, наша классическая программа нашла все выигрышные руки (хотя для этого потребовалось 16 итераций!).
Можем ли мы найти всевыигрышные комбинации?
Сила квантовой обработки
Как оказалось, поскольку мы создали квантовый оракул, который кодирует выигрышные комбинации в нашей игре, мы фактически можем вычислить все выигрышные комбинации. Более того, мы можем сделать это всего за один цикл процессора!
Вместо жесткого кодирования наших кубитов с определенным значением нуля или единицы, которое соответствовало определенному выбору камня, ножниц, бумаги для каждого игрока, мы поместим кубиты в суперпозицию. Это изменяет значение кубитов со значения 0 или 1 на значение 0 и 1 одновременно. !
Используя суперпозицию, мы можем оценить все возможные игровые комбинации за одно выполнение и вернуть только те выигрышные комбинации, которые удовлетворяют логической логике оракула.
Вот пример того, как это делается.
qc = QuantumCircuit(n + 1) qc.h(range(n)) # Append the sudoku oracle. qc.append(oracle, range(n+1)) # Measure the result! qc.measure_all() qc.draw(output='mpl')
Обратите внимание, что мы пропустили жесткое кодирование конкретного элемента для первого и второго игроков. Вместо этого мы используем ворота Адамара, чтобы поместить все четыре кубита в суперпозицию, чтобы они одновременно удерживали значения 0 и 1.
Это приводит к схеме квантовых вычислений, как показано выше. Если мы запустим эту программу, мы должны ожидать увидеть индикацию всех выигрышных рук, которые удовлетворяют булевой логике оракула.
В результатах наиболее значимый кубит (самый левый или самый нижний) имеет значение 0 (проигрыш) или 1 (выигрыш). Итак, нас интересуют 3 победы в крайнем правом углу графика.
Однако это выглядит не совсем так!
На самом деле все возможные комбинации значений кубитов кажутся совершенно случайными.
Гроувер ищет спасение
Как оказалось, при поиске в пространстве кубитов в суперпозиции с оракулом нам нужно усилить результаты измерения выигрышных комбинаций, которые удовлетворяют оракула, и минимизировать проигрышные комбинации, которые не удовлетворяют оракула.
Мы можем сделать это с помощью квантового алгоритма Поиск Гровера.
Алгоритм поиска Гровера использует процесс рассеивания и усиления, который позволяет правильным результатам плавать выше, в то время как неправильные результаты остаются низкими. Он может использоваться для поиска ключа в базе данных неупорядоченных элементов и выполняет поиск квадратично быстрее, чем любой классический алгоритм.
После запуска этой новой схемы с использованием алгоритма поиска Гровера вместе с нашим тем же оракулом для камня, ножниц, бумаги мы можем увидеть следующее изменение в выводе.
Изучив приведенные выше результаты, мы действительно получили три результата, которые намного выше, чем остальные комбинации. На самом деле, они напрямую соответствуют выигрышным ходам в игре!
Если мы декодируем каждый результат, начиная с самого левого на диаграмме, и меняя местами биты, которые Qiskit вернул в качестве вывода, мы можем определить выигрышные руки. Напомним, что самый старший бит является наименее значащим битом и соответствует первому игроку.
0001 = бумага (01) vs камень (00) = ПОБЕДА
0110 = ножницы (10) vs бумага (01) = ПОБЕДА
1000 = камень (00) против ножниц (10) = ПОБЕДА
0001 => 01 versus 00 => paper versus rock => WIN ^- q0 ^--- q1 ^---- q2 ^----- q3
Самое удивительное в этом то, что классической программе потребовалось 16 итераций, чтобы найти эти три выигрышные комбинации. Программе квантовых вычислений понадобился всего один шаг!
Еще немного веселья
Мы только что рассмотрели, как программа квантовых вычислений может находить все выигрышные ходы в игре «камень, ножницы, бумага» всего за одно выполнение на процессоре. Мы сделали это, поместив кубиты в суперпозицию.
Однако, играя с тем, какие кубиты находятся в суперпозиции, а какие нет, мы действительно можем создать различное поведение нашей программы.
Например, предположим, что мы хотим найти лучший ход для первого игрока, когда второй игрок делает конкретный выбор. Мы можем сделать это, установив кубиты первого игрока в суперпозицию и оставив кубиты второго игрока жестко запрограммированными на определенное значение.
Если мы теперь запустим квантовую программу, вместо того, чтобы увидеть три результата с высокими значениями (соответствующими всем выигрышным рукам), мы должны ожидать увидеть только одно высокое значение, которое будет соответствовать выигрышной руке, которую игрок должен выбрать, чтобы победить. игрок два.
В приведенном выше сценарии мы назначаем второму игроку выбор камня (00). Посмотрим, что квантовая программа выберет в качестве своего хода!
Результат показывает (0001). При чтении от младшего к старшему биту получается, что первый игрок выбирает бумагу (01) всякий раз, когда второй игрок выбирает камень (00). Этот ход действительно является выигрышной игрой для первого игрока!
Бумага побеждает камень!
Вы можете скачать полный пример кода программы камень, ножницы, бумага здесь.
Ваша очередь
Теперь, когда мы завершили программу квантовых вычислений для поиска всех выигрышных ходов в игре «Камень, ножницы, бумага», давайте на мгновение задумаемся о том, чего мы добились.
Классическая программа нашла все выигрышные комбинации за 16 итераций. Напротив, квантовая версия, использующая поиск Гровера, выполняется всего за одну итерацию. Это лишь одно из фантастических различий между тем, как работают классические и квантовые компьютеры.
Поиск Гровера можно применять ко многим различным проблемам поиска, включая алгоритмы, файловые системы и базы данных, и это лишь некоторые из них. Кроме того, поскольку область квантовых вычислений еще так молода, у вас есть реальная возможность оказать влияние.
Я надеюсь, что вы хотите больше узнать об этой удивительной технологии. Теперь твоя очередь!
об авторе
Если вам понравилась эта статья, рассмотрите возможность подписаться на меня в Medium, Twitter и на моем веб-сайте, чтобы получать уведомления о моих будущих публикациях и исследовательской работе.
