Квантовые компьютеры. С точки зрения традиционного программиста-математика. Часть 2 / forpes.ru

Главная
Квантовые компьютеры. С точки зрения традиционного программиста-математика. Часть 2

Квантовые компьютеры. С точки зрения традиционного программиста-математика. Часть 2 +11

04.08.2023 08:03

java_prog 7 1700 Источник

В прошлой части мы рассмотрели базовые понятия в квантовых вычислениях: кубиты, вероятности состояний, измерения.

Квантовые гейты

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

Схема операции AND в классическом компьютере

В квантовых вычислительных системах все очень похоже, но чтобы подойти к вычислению состояния, после применения операции, надо все рассмотреть с позиции теории вероятностей. Например выше мы видим операцию AND. Она выдает в результате 1, если оба входных бита равны 1, и выдает 0 во всех остальных случаях. В квантовым мире у нас нет определенных значений кубита, кубит на входе операции находится в состоянии и 0 и 1 одновременно с какими то вероятностями получить какое-то из этих чисел в результате измерения. На выходе операции AND также будет кубит в обоих состояниях 0 и 1 с какими-то вероятностями. Если перенести определение операции AND теперь в квантовый мир, то будет следующее: операция выдает в результате кубит, который в процессе измерения даст число 1 с вероятностью равной вероятности, что на обоих входах кубиты равны 1, и в остальных случаях в результате измерения выходного кубита, будет число 0. Вот примерно такой подход и строим, чтобы перенести понятие привычных классических цепей в квантовые гейты. С какой вероятностью на входе будут данные, что дают определенный результат в классическом случае, такой и будет вероятность этого результата. Ну начнем по порядку с однокубитных операций: операций у которых на входе один кубит и на выходе один кубит.

Гейт NOT

Является квантовым аналогом однобитной операции NOT

Схема операции NOT в классическом компьютере

Попробуем построить аналог операции для квантового компьютера. Пусть кубит находится в состоянии:

$\alpha_0 |0\rangle +\alpha_1 |1\rangle$

Согласно рассуждениям выше, наш квантовый гейт должен в результирующем кубите выдавать при измерении 0 с той же вероятностью, с какой на входе будет 1. И наоборот. На выходе 1 должно быть с той же вероятностью с какой на входе 0. Напрашивается простейшее преобразование, просто поменять местами амплитуды кубита:

$\alpha_0 |0\rangle +\alpha_1 |1\rangle \xrightarrow{NOT} \alpha_1 |0\rangle +\alpha_0 |1\rangle \quad (1)$

Именно этим и занимается простейший квантовый гейт NOT.
На схемах с квантовыми алгоритмами данный гейт обозначают следующим образом

Но указание "поменяй амплитуды при состояниях кубита" математически слишком не строгое. Требуется какая-то математическая формализация. Делается это так. С каждым однокубитным гейтом ставится в соответствие матрица 2x2. Например, однокубитную операцию NOT можно представить как:

$\left( \begin{array}{cccc} 0 & 1 \\ 1 & 0 \end{array} \right)$

А чтобы получить результат операции NOT, который мы выше охарактеризовали как "переставить амплитуды у состояний кубита" мы перепишем входной и выходной кубит в векторном виде. Тогда справедливо соотношение в виде умножения матрицы с операцией на вектор:

$\left( \begin{array}{cccc} 0 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cccc} \alpha_0 \\ \alpha_1 \end{array} \right) = \left( \begin{array}{cccc} \alpha_1 \\ \alpha_0 \end{array} \right)$

А это и есть формализованное соотношение (1), где состояния записаны в виде векторов, а операция записана в виде матрицы. Рассмотрим по аналогии другие квантовые гейты.

Инверсия фазы

Этот полезный и часто используемый гейт обозначают на схемах большой буквой Z. Как видно из матрицы преобразования:

$\left( \begin{array}{cccc} 1 & 0 \\ 0 & -1 \end{array} \right) \left( \begin{array}{cccc} \alpha_0 \\ \alpha_1 \end{array} \right) = \left( \begin{array}{cccc} \alpha_0 \\ -\alpha_1 \end{array} \right)$

Данный гейт меняет знак амплитуды у состояния 1, оставляет неизменным состояние 0. Так как вероятности равняются квадратам амплитуд, то данное преобразование не изменяет вероятность 0 или 1, изменяя лишь фазу.

$\alpha_0 |0\rangle +\alpha_1 |1\rangle \xrightarrow{Z} \alpha_0 |0\rangle -\alpha_1 |1\rangle$

Гейт Адамара

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

Обозначается буквой H. Как видно из матрицы преобразования:

$\left( \begin{array}{cccc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array} \right) \left( \begin{array}{cccc} \alpha_0 \\ \alpha_1 \end{array} \right) = \left( \begin{array}{cccc} \frac{1}{\sqrt{2}} \alpha_0+\frac{1}{\sqrt{2}} \alpha_1 \\ \frac{1}{\sqrt{2}} \alpha_0-\frac{1}{\sqrt{2}} \alpha_1 \end{array} \right)\quad(2)$

На первый взгляд гейт кажется сложным, но смысл его на словах примерно следующий. Если на вход подать состояние $|0\rangle$ то на выходе получится:

$\left( \begin{array}{cccc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array} \right) \left( \begin{array}{cccc} 1 \\ 0 \end{array} \right) = \left( \begin{array}{cccc} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array} \right)$

То есть этот гейт позволяет получить равномерное распределение вероятности обоих состояний: 0 и 1. Если на вход подать состояние $|1\rangle$ то на выходе получится опять равномерное распределение по вероятности но с другой фазой.
В общем случае также можно записать преобразование гейта так:

$\alpha_0 |0\rangle +\alpha_1 |1\rangle \xrightarrow{H} (\frac{1}{\sqrt{2}} \alpha_0 + \frac{1}{\sqrt{2}} \alpha_1 ) | 0 \rangle +(\frac{1}{\sqrt{2}} \alpha_0 - \frac{1}{\sqrt{2}} \alpha_1 ) |1\rangle$

Ограничение гейтов

Нельзя взять любую матрицу 2х2 и объявить ее однокубитным квантовым гейтом. Квантовый гейт должен обладать двумя очень важными свойствами.

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

Лучше не смотрите под спойлер
Да, знатоки скажут, что я тут наврал, но, простите, я сделал это для упрощения и чтобы не отвлекаться надолго от основного повествования. Чуть позже мы выясним, что все гораздо сложнее, а пока будем понимать обратимость в таком виде.
Рассмотрим на примере гейта Адамара. Возьмем результат из (2) и к нему еще раз применим гейт Адамара.

$\left( \begin{array}{cccc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array} \right) \left( \begin{array}{cccc} \frac{1}{\sqrt{2}} \alpha_0+\frac{1}{\sqrt{2}} \alpha_1 \\ \frac{1}{\sqrt{2}} \alpha_0-\frac{1}{\sqrt{2}} \alpha_1 \end{array} \right) = \left( \begin{array}{cccc} \alpha_0 \\ \alpha_1 \end{array} \right)$

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

Нормирование. После преобразования сумма вероятностей всех состояний должна равняться единице. $|\alpha_0|^2+|\alpha_1|^2=1$ . Это логичное требование теории вероятностей. Вероятность того, что мы получим хоть какое-то любое состояние, измеряя кубит равняется единице, ведь мы не можем остаться без ответа и совсем не получить никакого состояния. Проверим, на преобразовании Адамара, что его результат дает в сумме вероятностей единицу. Итак, в результате операции Адамара у нас получилось состояние

$(\frac{1}{\sqrt{2}} \alpha_0 + \frac{1}{\sqrt{2}} \alpha_1 ) | 0 \rangle +(\frac{1}{\sqrt{2}} \alpha_0 - \frac{1}{\sqrt{2}} \alpha_1 ) | 1 \rangle$

Квадрат амплитуды при состоянии $|0\rangle$ равен:

$| \frac{1}{\sqrt{2}} \alpha_0+\frac{1}{\sqrt{2}} \alpha_1 |^2=(\frac{1}{\sqrt{2}} \alpha_0+\frac{1}{\sqrt{2}} \alpha_1)(\frac{1}{\sqrt{2}} \alpha_0+\frac{1}{\sqrt{2}} \alpha_1)^*=$ $=\frac{1}{2} | \alpha_0 |^2+\frac{1}{2} | \alpha_1 |^2+\frac{1}{\sqrt{2}} \alpha_0 \alpha_1^*+\frac{1}{\sqrt{2}} \alpha_0 \alpha_1^*$

Квадрат амплитуды при состоянии $|1\rangle$ равен:

$| \frac{1}{\sqrt{2}} \alpha_0-\frac{1}{\sqrt{2}} \alpha_1 |^2=(\frac{1}{\sqrt{2}} \alpha_0-\frac{1}{\sqrt{2}} \alpha_1)(\frac{1}{\sqrt{2}} \alpha_0-\frac{1}{\sqrt{2}} \alpha_1)^*=$ $=\frac{1}{2} | \alpha_0 |^2+\frac{1}{2} | \alpha_1 |^2-\frac{1}{\sqrt{2}} \alpha_0 \alpha_1^*-\frac{1}{\sqrt{2}} \alpha_0 \alpha_1 ^*$

Очевидно, если мы сложим эти квадраты амплитуд, то получим $|\alpha_0|^2+|\alpha_1|^2=1$
Именно для того, чтобы соответствовать этому требованию, пришлось использовать $\sqrt{2}$ в матрице оператора Адамара, что сделало ее написание несколько неудобным. Иногда проще записать матрицу операции Адамара в таком виде:

$\frac{1}{\sqrt{2}} \left( \begin{array}{cccc} 1 & 1 \\ 1 & -1 \end{array} \right)$

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

Еще немного про запутанность. Много вычислений, но вычисления простые и полезные

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

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

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

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

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

К примеру: в течение дня произведено 5 коробок линз, в каждой коробке по 7 линз. Всего линз, получается 35. Чтобы их стало четное количество надо Алисе добавить одну линзу к произведенному товару. А Боб должен ничего не добавлять. Или наоборот Боб должен добавить одну линзу, а Алиса ничего не добавлять.

Если же и Алиса, и Боб добавят каждый по линзе к произведенной партии, или оба не добавят, то одна из линз непременно пойдет в мусор, чего никто не желает.

Проблема в том, что Алиса знает, что произведено 5 коробок. Боб знает, что в каждой коробке 7 линз. Больше никакой информации у них нет, и их решение должно быть основано только на этой информации.

На следующий день произведено 6 коробок по 5 линз в каждой коробке. Алиса получает число 6, Боб получает число 5. Так как всего произведено 30 линз, то либо Алиса и Боб должны каждый добавить по одной линзе, чтобы их стало 32. Либо каждый из них должен ничего не добавлять. В остальных случаях одна из линз непременно пойдет в мусор.

Какую тактику выбрать Алисе и Бобу, чтобы принимать на основании своей доступной информации такие решения, которые минимизируют количество мусора?

Алиса и Боб, как известно по их прошлым приключениям, опытные математики. Они решили использовать тактику, что оба каждый день ничего не добавляют к произведенной партии. Тогда они будут угадывать в 75% случаях. Ведь вероятность, что количество коробок будет нечетным и одновременно количество линз в коробке будет также нечетным это $\frac{1}{2}\times\frac{1}{2}=\frac{1}{4}$ . И только в этом случае Алиса и Боб будут принимать неправильное решение и одна из линз пойдет в мусор.

Можно ли в этом мысленном эксперименте как-то снизить вероятность неблагоприятного исхода, использовать какую то другую тактику? Другую тактику использовать можно. Снизить вероятность до значения менее чем 0.25 - нельзя, поверьте. А лучше проверьте.

А теперь допустим в том же эксперименте, Алиса и Боб делят пару запутанных кубитов, что находятся в равновероятном состоянии $|00\rangle+|11\rangle$ . Нормировочный коэфициент $\frac{1}{\sqrt{2}}$ опустим, не в нем сейчас интерес.

Допустим Алиса и Боб имеют не одну а много таких пар запутанных кубитов.

Боб со своими частями запутанных кубитных, Алиса со своими частями запутанных кубитов. Кроме этих кубитов с запутанными связями, никакого другого общения у Алисы и Боба нет.

Теперь новая тактика. Сначала Алиса.

Если у Алисы информация, что произведено четное количество коробок, то она просто измеряет свой кубит. Если кубит в результате измерения показывает 1, то она добавляет одну линзу к произведенной партии. Если кубит показывает 0, то она ничего не добавляет.

Если у Алисы информация, что произведено нечетное количество коробок, то сначала Алиса преобразовывает свой кубит гейтом Адамара, а потом измеряет. Решения те же: если кубит в результате измерения показывает 1, то она добавляет одну линзу к произведенной партии. Если кубит показывает 0, то она ничего не добавляет.

Теперь новая тактика Боба.

Если у Боба информация, что произведено четное количество коробок, то Боб преобразовывает свой кубит гейтом:

$\left( \begin{array}{cccc} \cos \frac{\pi }{8} & \sin \frac{\pi }{8} \\ \sin \frac{\pi }{8} & -\cos\frac{\pi}{8} \end{array} \right)$

Если наоборот, у Боба информация, что произведено нечетное количество коробок, то Боб преобразовывает свой кубит гейтом:

$\left( \begin{array}{cccc} \cos \frac{\pi }{8} & -\sin \frac{\pi }{8} \\ -\sin \frac{\pi }{8} & -\cos \frac{\pi}{8} \end{array} \right)$

После чего Боб измеряет свой кубит и дальше все тоже самое: если кубит в результате измерения показывает 1, то Боб добавляет одну линзу к произведенной партии. Если кубит показывает 0, то Боб ничего не добавляет.

Тактику мы изложили, теперь давайте решим эту задачу и выясним, с какой вероятностью Боб и Алиса будут принимать неверное решение при применении такой тактики.

Начнем со случая, когда и количество коробок четное, и количество линз в одной коробке четное В этом случае Алиса не меняет свой кубит. Алисин кубит - зелёный. Боб преобразовывает свой кубит гейтом, согласно своей первой матрице. Кубит Боба - жёлтый.

Какова вероятность неудачи? Так как количество линз - четное, то неудачными считаются случаи $|01\rangle$ и $|10\rangle$
Какова получилась вероятность такого случая? Согласно математике теории вероятности просто сложим вероятность обоих исходов:

$P=\frac{\sin^{2}\frac{\pi}{8}+\sin^{2}\frac{\pi}{8}}{\cos^{2}\frac{\pi}{8}+\sin^{2}\frac{\pi}{8}+\cos^{2}\frac{\pi}{8}+\sin^{2}\frac{\pi}{8}} =\sin^{2}\frac{\pi}{8}$

Выражение в знаменателе добавлено для нормировки: просто сумма квадратов всех амплитуд. Не будем вычислять этот синус, просто отметим, что эта вероятность очевидно меньше, чем $\frac{1}{4}$ - тот уровень, который мы не могли никак преодолеть в любой классической тактике без использования запутанных кубитов.

Второй случай: количество коробок четное, количество линз в коробке нечетное Алиса имея информацию о четном количестве коробок ничего не делает со своим кубитом, просто измеряет. Боб преобразовывает свой кубит гейтом, который задан второй матрицей с отрицательными синусами. Результат почти такой же, только кое-где поменялись знаки.

Так как количество линз снова четное, то неудачными по прежнему считаются случаи $|01\rangle$ и $|10\rangle$ При вычислении вероятностей мы возводим амплитуду в квадрат, поэтому нам не важно с какими знаком была амплитуда. Следовательно, итоговое выражение вероятности неудачного исхода получится такое же, как и в первом случае $\sin^{2}\frac{\pi}{8}$

Третий случай: Количество коробок нечетное, количество линз в коробке четное Алиса, согласно своей тактике, применяет над своим кубитом гейт Адамара, Боб применяет гейт, заданный первой матрицей. Распишем это выражение. Как обычно, кубит Алисы зеленый, кубит Боба жёлтый.

Так как количество линз снова четное, то неудачными по прежнему считаются случаи $|01\rangle$ и $|10\rangle$ Также мы легко можем вывести следующие тригонометрические формулы:

$(\sin\frac{\pi}{8}+\cos\frac{\pi}{8})^{2}=2\cos^{2}\frac{\pi}{8}$ $(\sin\frac{\pi}{8}-\cos\frac{\pi}{8})^{2}=2\sin^{2}\frac{\pi}{8}$

А значит, вероятность неблагоприятного исхода, после возведения амплитуд в квадраты опять даст то же самое выражение:

$P=\frac{2\sin^{2}\frac{\pi}{8}+2\sin^{2}\frac{\pi}{8}}{2\cos^{2}\frac{\pi}{8}+2\sin^{2}\frac{\pi}{8}+2\cos^{2}\frac{\pi}{8}+2\sin^{2}\frac{\pi}{8}} =\sin^{2}\frac{\pi}{8}$

Последний случай. Количество коробок нечетное, и количество линз в коробке нечетное. Алиса, согласно своей тактике, применяет над своим кубитом гейт Адамара, Боб применяет гейт, заданный второй матрицей. Распишем это выражение. Как обычно, кубит Алисы зеленый, кубит Боба жёлтый.

Проблема? Никаких проблем. Ведь теперь у нас выпущено нечетное количество линз, а значит неблагоприятным исходом считаются случаи $|00\rangle,|11\rangle$ , когда и Алиса, и Боб не будут добавлять линзы к выпущенной партии, либо оба одновременно добавят по одной линзе. А значит амплитуды неблагоприятных исходов те же, что были в прошлом случае, а в итоге будет опять вероятность неблагоприятного исхода: $\sin^{2}\frac{\pi}{8}$

Вот так, в данном мысленном эксперименте, благодаря загадочной связи, возникающей между запутанными кубитами, нам удалось уменьшить вероятность неудачного исхода $\frac{1}{4}$ в классическом случае, до значения вероятности $\sin^{2}\frac{\pi}{8}$ .

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

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

Комментарии (7)

vlad1953
04.08.2023 09:46
#25823136
Хорошая статья. Мне она понравилась практическими расчетами.

freeExec
04.08.2023 09:46
#25823522
А я вот не понял про линзы. И вероятность что и коробок и линз чётное тоже 1/4, о каких шансах не выкидывать линзу в мусорку в 75% идёт речь?
1. java_prog Автор
  04.08.2023 09:46
  #25823642
  +1
  Есть 4 равновероятных исхода.
  
  а) четное число коробок, в каждой коробке четное число линз
  
  б) четное число коробок, в каждой коробке нечетное число линз
  
  в) нечетное число коробок, в каждой коробке четное число линз
  
  г) нечетное число коробок, в каждой коробке нечетное число линз
  
  В случаях а,б,в общее число линз четное.
  
  В случае г общее число линз нечетное, что неудобно и при производстве очков, одна линза пойдет в мусорку.
  1. freeExec
    04.08.2023 09:46
    #25823902
    Да, понятно.

NightShad0w
04.08.2023 09:46
#25826924
С нетерпение жду продолжения. Практические примеры с необходимой базовой теорией - бесподобны. Спасибо за проделанную работу. Прекрасное введение в квантовое программирования для нематематиков.

А можно уделить немного внимания паре упущенных моментов в формальных описаниях:
- Изменение фазы кубита - это что, куда и откуда? Если вероятность - это квадрат модуля амплитуды, то на что именно влияет знак амплитуды?
- В нескольких формулах присутствует звездочка за скобкой или у амплитуды - какой смысл этой звездочки в выражении?
- В первой части знак ⊗ использовался как векторное умножение или для выделения определенных кубитов из регистра с игнорированием остальных. Что означает ⊗ в этой части для примера с Алисой и Бобом? |0> ⊗ |1> необходимо понимать как произведение матриц амплитуд кубитов?
1. java_prog Автор
  04.08.2023 09:46
  #25828124
  Как это нематематиков? Я подчеркнул, даже в заголовке, что это для программистов-математиков. Обязательны понимание линейной алгебры и умение обращаться с комплексными числами.
  
  По вопросам:
  
  Фаза это важно, но что влияет знак амплитуды я расскажу чуть позже.
  
  Звездочка это комплексное сопряжение
  
  Это тензорное произведение. Оно похоже на обычное произведение своими линейными свойствами, но имеет другой смысл.
  1. NightShad0w
    04.08.2023 09:46
    #25828792
    Спасибо.