Завершаем серию публикаций об известном квантовом алгоритме Дойча и Йожи.
Хотите начать работу с квантовым машинным обучением? Взгляните на статью Практическое квантовое машинное обучение с помощью Python.
В предыдущем посте мы разработали вероятностную версию квантового алгоритма Дойча и Йожи.
Исходный алгоритм Дойча и Йожи сообщает вам, производит ли данная функция постоянный вывод (всегда одинаковый) или сбалансированный (равное количество нулей и единиц). Но он предполагает, что сбалансированная функция сбалансирована в определенных границах. Если, например, граница равна двум (как в первом алгоритме Дойча), то алгоритм предполагает, что один прогон дает 0, а другой результат 1.
При рассмотрении вероятностных систем реального мира, таких как подбрасывание монеты, это предположение кажется нереалистичным. Вы можете подбросить честную монету три или более раз подряд, что приведет к одинаковому результату. Конечно, вы можете усомниться в честности монеты. Вероятность получения честной монеты уменьшается с каждым броском, дающим одинаковый результат. Тем не менее, нельзя утверждать, что монета обманута с уверенностью.
Наша вероятностная версия устранила это предположение. Когда монета с уверенностью справедлива, алгоритм выдает результат 0. Если монету можно обмануть, алгоритм выдает оба выхода, 0 и 1. Вероятность выхода 1 представляет вероятность того, что монета справедлива.
Тем не менее, алгоритм не завершен. Хотя он дает разные результаты для честных и обманутых монет, эти результаты неоднозначны. Если у вас честная монета, алгоритм всегда возвращает 0. Мы измеряем 0 в 100% случаев. Таким образом, вероятность измерения 0 представляет собой вероятность получить честную монету - 100%. Но когда у вас обманутая монета, вероятность получить 1 представляет собой вероятность получить честную монету.
Это означает, что когда мы измеряем 1 из 25% случаев, шанс получить честную монету составляет 25%. Это становится проблематичным, когда шанс выпадения честной монеты равен почти 0. Тогда мы почти всегда измеряем 0. Это подразумевает обманную монету. Но если бы мы всегда измеряли 0, это означало бы честно.
Итак, нам нужно настроить нашу квантовую схему. Прежде чем мы начнем, давайте кратко рассмотрим первую версию.
На следующем рисунке изображена схема с тремя подбрасываниями хедз-ап.
В отличие от этого, следующая схема показывает схему с двумя подбрасываниями хедз-ап и одним подбрасыванием решки. Единственная разница между обеими схемами - это часть оракула, которая представляет соответствующий бросок.
Схема состоит из пяти частей. Сначала мы помещаем кубиты, представляющие броски, в суперпозицию. Во-вторых, оракул применяет вентили Адамара к кубитам, представляющим подбрасывание хвоста вверх. И он применяет вентили с контролируемым НЕ к кубитам, представляющим броски один на один.
В-третьих, мы возвращаем вспомогательный кубит в состояние | 0⟩, и вентиль с тройным управлением-НЕ вычисляет вероятность получения честной монеты, учитывая, что все кубиты представляют собой броски один на один. В-четвертых, серия вентилей Z и Адамара, за которыми следует еще один вентиль с тройным управлением-НЕ, вычисляет вероятность честной монеты, учитывая, что все кубиты представляют собой подбрасываемые решки.
В-пятых, измеряем вспомогательный кубит.
Если одни кубиты представляют собой хедз-ап, а другие - решающие, то ни один вентиль с тройным НЕ применяется, поэтому вспомогательный кубит остается в состоянии | 0⟩.
И это то, что мы стремимся изменить. Он не должен оставаться в состоянии | 0⟩. Вместо этого он должен стать | 1⟩.
Звучит не слишком сложно, правда? Проблема, однако, в том, что мы не должны вмешиваться ни в один из ворот с тройным НЕ. И это оказывается настоящей проблемой.
Начнем с простого. Если мы хотим, чтобы вспомогательный кубит находился в состоянии | 1⟩, почему бы нам не удалить вентиль НЕ, который мы применяем к вспомогательному кубиту, непосредственно перед вентилями с тройным управлением-НЕ?
Это очень хорошо работает, когда у нас есть честная монета. Тогда вспомогательный кубит находится в состоянии | 1⟩.
Но когда все три броска одинаковы, например, хедз-ап, как на следующем рисунке, тогда мы измеряем вспомогательный кубит как 1 с ошибочной вероятностью. Вместо 12,5% сейчас 87,5%.
Обратите внимание, что неточности связаны с эмпирическим характером используемого моделирования.
Очевидно, решение должно учитывать кубиты, которые представляют собой подбрасывания. Мы должны применить вентиль НЕ к вспомогательному кубиту, только если все три подбрасывания находятся в одном и том же состоянии.
Итак, когда все три кубита представляют собой подбрасывание хедз-ап, все они находятся в состоянии | −, потому что вентили управляемого НЕ, которые мы применяем в оракуле, выполняют для них фазовый откат. Мы могли бы применить вентили Адамара к каждому из них, чтобы привести их в состояние | 1⟩. Затем мы применяем еще один вентиль с тройным НЕ. Следующие ворота Адамара возвращают их в | −.
Это работает очень хорошо, когда все три кубита представляют собой бросок один на один (что указывает на обманную монету). Теперь вероятность измерения 1 представляет собой вероятность получения честной монеты.
Но он терпит неудачу, когда происходит бросок решки. Тогда мы не измеряем кубит как 1 только примерно в 50% случаев.
Это связано с тем, что наш недавно добавленный гейт с тройным управлением-НЕ применяется и в этом случае. Когда вы посмотрите на схему, вы увидите, что мы применили три логических элемента Адамара к кубиту, представляющему собой бросок решкой вверх. Поскольку вентиль Адамара возвращается в исходное состояние, первые два компенсируют друг друга. Но третий вентиль Адамара переводит кубит в состояние | +⟩. Мы также знаем это состояние как:
Это состояние представляет собой комбинацию базовых состояний | 0⟩ и | 1⟩. Таким образом, вентиль с тройным управлением НЕ применяется к части | 1⟩.
Хорошо, может нам нужно применить другую последовательность ворот? Мы можем попробовать. Но успеха не будет. Проблема в нашем оракуле. Пока мы переводим кубиты, представляющие хвосты, в состояние | −⟩, мы переводим кубиты, представляющие хвосты, в состояние | 1⟩.
Эти два состояния ортогональны друг другу. Здесь помогает взгляд на сферу Блоха.
Мы специально поместили кубиты, представляющие подбрасывание хедз-ап и хвост-ап, ортогональными друг другу. Это позволяет нам упорядочить состояния кубита так, чтобы вентили с тройным управлением НЕ работали так, как мы хотим. Мы используем одно тройное НЕ для учета бросков один на один, а другое - для учета бросков решкой.
Хитрость заключается в том, чтобы поместить кубиты, представляющие правильную сторону (орел или решку), в состояние, при котором вероятность его измерения составляет 1 из 50%. В результате каждый вентиль с тройным управлением НЕ переводит вспомогательный кубит только в 1 / 2³ в состояние | 1⟩. Это общая вероятность получения честной монеты с учетом трех подбрасываний с одинаковым результатом. Но как только один кубит представляет другую сторону, тройное контролируемое НЕ больше не применяется, потому что мы перевели соответствующий кубит в состояние | 0⟩.
Мы помещаем кубиты, представляющие две стороны, ортогональными друг другу, потому что состояние | 0⟩ ортогонально состояниям кубита, которые с вероятностью 50% измерить кубит как 1 (например, состояние | +⟩).
Таким образом, хотя ортогональность помогает нам преуспеть в одном вычислении, она не дает нам сделать другого. Мы не можем легко переставить кубиты, чтобы они указывали в противоположных направлениях. Это потребовало бы от нас рассмотрения каждой конкретной комбинации бросков хедз-ап и решка. Это было бы очень обременительно.
Вместо этого мы добавляем еще один кубит для представления каждого броска. А внутри нашего оракула мы применяем вентили, которые направляют кубиты в противоположных направлениях. Например, мы оставляем кубиты, представляющие хедз-ап, в состоянии | 0⟩, а кубиты, представляющие хвосты, в состоянии | 1⟩.
Затем мы применяем другое тройное контролируемое НЕ, если все три кубита представляют собой хедз-ап или решку. Поэтому мы измеряем вспомогательный кубит как 1 с вероятностью получения честной монеты.
На следующем рисунке изображена последняя схема, представляющая (предположительно обманутую) монету, которая выпадает трижды подряд один на один.
Результаты показывают, что вероятность получения честной монеты составляет около 0,125, представленная измерением кубита как 1.
На следующем рисунке показана схема, представляющая два броска один-на-один и один бросок решка.
Мы всегда измеряем эту схему как 1, что указывает на уверенность в наличии честной монеты.
Вывод
В этом посте мы завершили нашу улучшенную версию квантового алгоритма Дойча и Йозса.
Эта последняя схема дает правдоподобные результаты, измеряя вспомогательный кубит как 1, представляющий честную монету.
Кроме того, в этом посте подробно описаны различные подходы к решению данной проблемы, в том числе и не решающие ее. Обычно мы сосредотачиваемся на том, что работает. Но я считаю, что видеть то, что не работает, тоже имеет некоторую ценность. Он иллюстрирует общий процесс решения проблемы, который обычно не так прост, как нам хотелось бы. Видя, что подходы, которые не работают, вы можете уберечь вас от тех же «ошибок» и потери времени, пытаясь заставить что-то работать, что не работает.
Хотите начать работу с квантовым машинным обучением? Взгляните на статью Практическое квантовое машинное обучение с помощью Python.
Первые три главы получите бесплатно здесь.
