SpaceOdyssey 4 фев 2017 в 01:31

Не все так просто с квантовым компьютером

18 мин

45K

Компьютер компании D-Wave, который она называет квантовым

Усилия в направлении квантового компьютера предпринимаются с начала 80-х прошлого века — столетия великих научных достижений, среди которых КМ стоит на первом месте (хотя без СТО она бы не развилась). В основе квантового компьютинга лежит понятие запутанности (quantum entanglement). Однако, сложившиеся и широко популяризованные взгляды на сей предмет, на мой взгляд, слишком далеко ушли от того, что на самом деле строго вытекает из КМ. Парадигме запутанности посвящена статья, а здесь рассмотрена проблема квантовых вычислений. Главным содержанием настоящей статьи являются критические замечания в отношении научных основ мечты о Святом Граале эпохи интернета.

О кубитах для тех, кто не в теме

Исходным понятием является кубит (quantum bit) — элементарный носитель информации. В качестве физической реализации в принципе может выступать любой квантовый объект, имеющий два базовых состояния, которые обозначаются $|0\rangle$ и $|1\rangle$ . На роль кубита, например, годится фотон с одной из двух перпендикулярных поляризаций или электрон с одним из двух противоположных направлений спина. С математической точки зрения состояния являются векторами, которые можно умножать на комплексные числа, а также складывать между собой. Таким образом, помимо базовых состояний $|0\rangle$ и $|1\rangle$ , которые аналогичны 0 и 1 в обычном бите, кубит может пребывать в квантовом состоянии

$|x\rangle= c_0\cdot|0\rangle+c_1\cdot|1\rangle\qquad\qquad(1)$

где $inline$ — любые комплексные числа (в частности действительные). При этом физическое состояние кубита не изменится, если коэффициенты $inline$ умножить на одно и то же число $a\neq 0$ . Поэтому вектор $|x\rangle$ можно нормировать, т.е., выбрать множитель $a\in{\mathbb C}$ так, чтобы новые коэффициенты $inline$ удовлетворяли условию $inline$ . Тогда вектор $|x'\rangle= c_0'\cdot|0\rangle+c_1'\cdot|1\rangle$ называется нормированным или единичным.

Физический смысл состояния (1), которое называется суперпозицией базовых состояний, заключается в следующем. Если вектор $|x\rangle$ суть единичный, то числа $inline$ и $inline$ дают вероятности того, что при измерении состояния кубита будет получено $|0\rangle$ и $|1\rangle$ соответственно. После измерения кубит останется в том базовом состоянии, которое оказалось измеренным. Вывести из него может только внешнее воздействие. Таким образом можно сказать, что кубит в нормированном состоянии (1) с вероятностью $inline$ равен 0 и с вероятностью $inline$ равен 1. Ничего подобного с обычным (классическим) битом происходить не может. Суперпозиция — существенно квантовый эффект! Термин «базовые» применительно к состояниям $|0\rangle$ и $|1\rangle$ означает, что любое другое состояние кубита может быть выражено их суперпозицией в смысле (1) для некоторых чисел $inline$ (определенных с точностью до пропорциональности).

Рабочий регистр квантового компьютера мыслится набором из $inline$ кубитов, которые каким-то образом взаимосвязаны между собой — запутаны. Для того, чтобы реализовать его грандиозные возможности, число $inline$ должно быть достаточно большим, скажем $inline$ . Пусть каждый кубит номер $inline$ в регистре находится в своем состоянии $|x_j\rangle$ , где $x_{j}\in\{0,1\}$ . Если рассматривать набор из $inline$ кубитов, как квантовый объект, то его состояние можно описать набором векторов $|x_1\rangle|x_2\rangle...|x_n\rangle$ , который кратко обозначается $|x_1x_2 ... x_n\rangle$ . Часто используется термин «тензорное произведение» и обозначения вроде $|x_1\rangle\otimes...\otimes|x_n\rangle$ , способные смутить многих читателей статей о квантовых компьютерах. Им можно посоветовать просто игнорировать значок $\otimes$ , полагая

$|x_1\rangle\otimes|x_2\rangle\otimes...\otimes|x_n\rangle=|x_1x_2...x_n\rangle\qquad\qquad(2)$

Пока нет никакой запутанности — просто набор независимых кубитов, хотя и считающихся единым объектом. Запутанность появится, если мы введем в рассмотрение суперпозиции состояний (2), т.е., векторы (точнее тензоры) состояний регистра, имеющие вид

$\sum_{j=1}^n c_j\cdot |x_{1j}x_{2j}, ..., x_{nj}\rangle\qquad\qquad(3)$

где $inline$ — комплексные числа, $|x_{kj}\rangle$ — вектор состояния $inline$ — го кубита, $x_{kj}\in\{0,1\}$ . Множество всевозможных векторов вида (3) называется тензорным произведением $inline$ пространств состояний одиночных кубитов, хотя без слова «тензор» вполне можно обходиться (в фундаментальной книге Дирака «Принципы квантовой механики» оно ни разу не встречается).

Для начального, но точного и не научно-популярного знакомства с этой темой рекомендуется хорошая статья, причем достаточно параграфов 2, 3, 4, 5 и 7.1. Параграф 6 можно пропустить без ущерба для понимания основных идей. После того, как вы прочитали это введение, вам будет легче разобраться с ней, а изложение основ квантовой механики можно будет вовсе пропустить.

Квантовая запутанность

По определению состояние (3) является запутанным, если этот вектор нельзя разложить в произведение $|A_1\rangle|A_2\rangle...|A_n\rangle$ векторов состояний одиночных кубитов. В этом случае воздействие на любой из кубитов может отражаться на состояниях каких-то других кубитов регистра. Заметим, что каждый вектор $|A_j\rangle$ , вообще говоря, является суперпозицией базовых, так что $|A_j\rangle=c_{j0}|0\rangle+c_{j1}|1\rangle$ для некоторых чисел $c_{j0}, c_{j1}$ .

Для иллюстрации рассмотрим случай двух кубитов. Их общее состояние $|01\rangle$ не является запутанным, т.к. $|01\rangle=|0\rangle|1\rangle$ . Измерив, скажем, второй кубит мы найдем его в состоянии $|1\rangle$ . При этом первый останется в то же состоянии $|0\rangle$ , т.е., измерение второго на него не повлияло. Пусть теперь пара кубитов находится в состоянии $|01\rangle+|10\rangle$ . Оно является запутанным, т.к. этот вектор нельзя представить в виде произведения $|A_1\rangle|A_2\rangle$ (легко проверить).

При измерении второго кубита мы с равной вероятностью $inline$ найдем его в состоянии $|0\rangle$ или $|1\rangle$ . Если второй кубит обнаружен в состоянии $|0\rangle$ , то это означает, что запутанная пара оказалась в $|10\rangle$ . Соответственно, первый кубит автоматически попал в состояние $|1\rangle$ . Если же второй кубит измерен в состоянии $|1\rangle$ , то пара оказалась в $|01\rangle$ . Следовательно, первый кубит оказался в состоянии $|0\rangle$ в тот момент, как мы измерили второй. Таким образом, измерение состояния одного из двух запутанных кубитов мгновенно влияет на состояние второго. При этом исходное, общее состояние пары кубитов разрушается, что драматически называют коллапсом волновой функции (термин «волновая функция» можно считать синонимом для «вектор состояния», хотя между ними все же есть формальное различие).

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

Рисунок иллюстрирует измерение одного кубита в квантовом регистре из 6-ти кубитов

О бабочке, сотрясающей галактику

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

Предположим, что кубитами являются фотоны в состояниях поляризации. Очевидно, что, как единая квантовая система, они должны быть частью единого, связного поля, которое остается таковым в процессе своего распространения. Если же каждый из фотонов находится в отдельном волновом пакете и они разобщены между собой в пространстве (к примеру между пакетами ~1 м при размерах пакетов ~1 мм), то о реальной их запутанности вряд ли есть смысл говорить.

Можно формально рассматривать векторы общих состояний вида (3), но от этого наши фотоны не запутаются. Физической реальности a' priori соответствуют только векторы вида (2), которые выражают факт пребывания каждого фотона в своем «личном» состоянии поляризации, без какой-либо связи с другими. Из квантовой механики отнюдь не вытекает, что суперпозиции (3) таких «общих состояний» имеют отношение к физической реальности. Это — вопрос о применимости математической модели, на который она сама не ответит.

Однако, энтузиасты квантовой магии по существу верят в то, что любой набор однородных квантовых объектов, формально объединенных в нечто целое, автоматически образует квантовую систему с пространством состояний, состоящим из векторов вида (3). Поскольку среди таких состояний есть запутанные, эти объекты можно запутать. Нужно лишь придумать как… или откуда получить уже запутанными. Догматизации этой идеи, по-видимому, в значительной мере способствовали математики с их склонностью к формальным построениям. Квантовые вычисления — это огромное поле для приложения математических усилий, на котором растут красивые результаты вроде алгоритма Шора! При этом все ссылаются на КМ, как якобы надежную основу своей веры.

Вернемся к примеру с парой кубитов в запутанном состоянии $|01\rangle+|10\rangle$ . Допустим, что они удаляются друг от друга на такое расстояние, которое исключает физическое взаимодействие (прямо и через посредство других тел). Сторонники квантовой магии считают, что если разлет происходит по инерции без внешнего влияния, то данное, запутанное состояние останется таковым независимо от расстояния между кубитами. Формально ничто не мешает так считать, но что фактически произойдет после того, как мы измерим 1-й кубит и найдем его в состоянии $|1\rangle$ , к примеру? Согласно магической парадигме, пара кубитов окажется в состоянии $|10\rangle$ . Но это означало бы, что измеряя 1-й кубит мы автоматически влияем на 2-й. Даже если он находится на другом конце галактики! Абсурдность такого вывода не смущает научное сообщество, которое принимает ЭПР — чудеса, как якобы формально вытекающие из квантовой механики.

Более разумно предположить, что измерение 1-го кубита никак не повлияет на 2-й, а лишь уничтожит их совместное состояние без каких-либо последствий для 2-го кубита. Он так и останется в индивидуальном состоянии $|0\rangle+|1\rangle$ , в котором был первоначально. Принимая эту точку зрения мы должны просто уточнить понятие измерения составной системы. А именно: ее измерением (которое способно вызвать скачок в собственное состояние измеряемой величины) является лишь такое взаимодействие с макроскопическим объектом, которое затрагивает все подсистемы, объединением которых данная система получается.

Таким образом, абсурдные выводы из псевдопарадокса ЭПР, составляющие квантовую магию, вынуждают нас уточнить понятие возмущения. Но вместо этого ему придают абсолютный смысл, как если бы взмах крыла бабочки считался возмущением Вселенной, … хотя с философской точки зрения так оно и есть. Разумеется, эти соображения не опровергают ЭПР — парадигму. Мерилом истины является только эксперимент. В статье основополагающие эксперименты Алана Аспэ подвергнуты критике с точки зрения квантовой механики. Есть серьезные основания полагать, что они были неверно интерпретированы.

Магическая запутанность необходима для управления кубитами. Очевидно, что человек сможет взаимодействовать с отдельными кубитами в регистре через попарно запутанные с ними, пространственно разделенные между собой объекты или разводя кубиты на макроскопические расстояния при сохранении запутанности между ними. Иначе считывать/записывать данные в квантовые регистры вряд ли возможно. Безотносительно к вопросу о физической реальности запутанности в смысле ЭПР, теория квантовых компьютеров имеет собственные трудности. Рассмотрим специфическую проблему квантовых вычислений, которая известна многим специалистам, но в целом не привлекает к себе должного внимания. Она связана с симметрией/антисимметрией совместных состояний тождественных частиц.

Продукт неудачной телепортации человека (скриншот из фильма «Муха»)

Квантовая телепортация

На ЭПР основана идея телепортации, т.е., способа передачи состояния кубитов другим кубитам, расположенным на любом удалении. Об этой технологии можно прочитать в пункте 4.2.2 статьи, на которую я буду ссылаться, указывая только пункты. Описание алгоритма точно следует п. 4.1.

Небольшое отступление. Теория квантовых вычислений исходит из гипотезы о том, что любое унитарное преобразование пространства состояний квантового регистра может быть физически реализовано через воздействие на его кубиты (все вместе или по отдельности). Определение унитарного преобразования дано в п. 4 (Квантовые вентили). Условие унитарности лежит в основе квантовой механики. В квантовых вычислениях такие преобразования называются квантовыми вентилями (gate), что указывает на связь со схемотехникой. В сущности это — обратимые логические схемы, преобразующие данные в регистрах, только они действуют на кубиты, а не биты. Но некоторые квантовые вентили не имеют классических аналогов, например 1-кубитное преобразование Адамара $inline$ (п. 4.1.1).

Например вентиль $C_{not}$ он же CONTROLLED-NOT действует на пару кубитов, как классическое $C_{not}$ на пару битов. Кроме того, квантовый $C_{not}$ сохраняет суперпозиции состояний, т.е.:

$C_{not}\bigl(c_{00}|00\rangle+c_{01}|01\rangle+c_{10}|10\rangle+c_{11}|11\rangle\bigr)=c_{00}|00\rangle+c_{01}|01\rangle+c_{10}|11\rangle+c_{11}|10\rangle)$

Вернемся к телепортации. Пусть у Алисы и удаленного Боба есть по одному кубиту из запутанной пары в общем состоянии $|\psi_0\rangle=|00\rangle+|11\rangle$ . Алиса хочет телепортировать Бобу другой кубит, который находится в состоянии $|\varphi\rangle=a|0\rangle+b|1\rangle$ . Состояние набора этих кубитов можно задать вектором

Первый кубит в тройке $|xyz\rangle$ подлежит телепортации, второй и третий — это запутанная пара кубитов Алисы и Боба соответственно. Алиса применяет к вектору (4) вентиль $C_{not}\otimes I$ , а затем $H\otimes I\otimes I$ , где $inline$ — тождественное преобразование. Фактически она воздействует $C_{not}$ на первые два кубита, которые ей доступны, а третий остается неизменным. Затем применяет к первому кубиту вентиль $inline$ , при этом два других не трогает.

Потом Алиса измеряет первые два кубита, которые оказываются в одном из состояний $|xy\rangle$ , где $x,y\in\{0,1\}$ . Соответственно, запутанный с ними кубит Боба переходит в одно из четырех состояний, указанных в таблице в конце п. 4.2.2. Полученную при измерении пару битов Алиса пересылает Бобу по обычной связи через интернет. В зависимости от полученных значений он применяет к своему кубиту один из вентилей $inline$ , согласно таблице в конце п. 4.2.2. Действие $inline$ описано в начале п. 4.1.

В результате всех этих манипуляций кубит Боба переходит в состояние $a|0\rangle+b|1\rangle$ того кубита, который Алиса хотела телепортировать. При этом состояние последнего разрушилось, т.к. клонирование состояний невозможно (доказано). Таким образом, имела место передача состояния кубита, а необходимая для этого информация передана обычным образом.

Можно ли назвать это телепортацией? Даже если бы удалось передать квантовое состояние макроскопического объекта, то для его воспроизведения в другом месте потребуется физически тождественный объект. Сначала эту «заготовку» нужно разместить по месту прибытия. Поэтому фантазии о телепортациях, как способе преодоления чудовищных, межзвездных расстояний не имеют под собой основания. Кроме того для человека, который подвергся такой «нуль-транспортировке», она бы просто означала смерть. Копия исходного лица, возникшая по месту прибытия, была бы другим человеком, хотя и с тем же набором воспоминаний (см. фильм «Луна 2112» и статью). В любом случае ограничение перемещений скоростью света остается в силе, т.к. метод квантовой телепортации предполагает передачу информации посредством сигналов.

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

Согласно квантовой механике частицы делятся на два класса: бозоны и фермионы. К первым относятся фотоны, а к вторым электроны. Если набор из $inline$ бозонов образует единый квантовый объект, то допустимые для него векторы состояний (3) должны быть симметричными относительно любых перестановок частиц. Это означает, что если в каждом слагаемом $|x_{1j}x_{2j}...x_{nj}\rangle$ одинаково переставить сомножители, то вектор (3) не должен измениться. Для набора из $inline$ фермионов допустимые состояния (3) должны быть антисимметричными относительно любых перестановок. Это означает, что если в каждом слагаемом одинаково переставить сомножители, то для четной перестановки вектор (3) не изменится, а для нечетной поменяет знак. Именно различие в поведении при перестановках наборов тождественных частиц делит их на бозоны и фермионы.

Таким образом пара запутанных кубитов, являющихся бозонами, может быть в состояниях $|00\rangle$ , $|11\rangle$ , $|01\rangle+|10\rangle$ , но не может находиться в состоянии $|10\rangle$ , т.к. при транспозиции оно переходит в $|01\rangle$ . Пара кубитов, являющихся фермионами, не может быть в состояниях $|00\rangle$ и $|11\rangle$ , т.к. при транспозиции (нечетная перестановка) они не меняются. Пара фермионов может находиться в (запутанном) состоянии $|01\rangle-|10\rangle$ , т.к. при транспозиции оно переходит в $|10\rangle-|01\rangle=-(|01\rangle-|10\rangle)$ (т.е. меняет знак).

Преобразование CONTROLLED-NOT не сохраняет симметрию и антисимметрию состояний:

$C_{not}(|11\rangle)=|10\rangle$ — образ симметричного вектора не симметричен и не антисимметричен;

$C_{not}(|10\rangle-|01\rangle)=|11\rangle-|01\rangle$ — образ антисимметричного вектора не симметричен и не антисимметричен.

Таким образом, применяя преобразование $C_{not}$ к паре запутанных бозонов получим состояние, в котором эта пара не может оказаться. Аналогично, применяя $C_{not}$ к паре запутанных фермионов получим состояние, в котором они вместе быть не могут. Поэтому любая попытка физической реализации $C_{not}$ приведет к тому, что состояние двух кубитов Алисы перестанет быть запутанным, и единая квантовая система выродится в пару независимых кубитов с общим состоянием $|x\rangle|y\rangle$ .

Вектор (4), который служит исходным состоянием тройки кубитов, не является симметричным и не является антисимметричным. Это также относится к результату манипуляций над ним (см. п. 4.2.2). Таким образом, данная тройка кубитов не может находиться в запутанном состоянии, т.к. она не может образовывать единую квантовую систему из трех бозонов или трех фермионов. Однако алгоритм предполагает, что первая пара кубитов запутана с третьим. Поскольку второй и третий кубиты являются запутанными, первые два кубита должны быть запутаны между собой (вплоть до измерения Алисой состояния своих кубитов). Но, как показано выше, преобразование $C_{not}$ разрушит эту связь.

Итак, данный алгоритм телепортации нельзя осуществить с помощью физически тождественных, т.е., неразличимых кубитов. А в случае различных квантовых частиц механизм запутывания не работает. В самом деле, состояние $|x\rangle|y\rangle+|y\rangle|x\rangle$ не имеет смысла, т.к. если $|x\rangle$ есть вектор состояния 1-й частицы, то он не может быть состоянием 2-й, аналогично $|y\rangle$ . Менять местами эти сомножители нельзя! Кроме того, для различных частиц телепортация в общем теряет смысл (нельзя копировать состояние протона на нейтроне)

По-видимому, соображения симметрии/антисимметрии могут быть использованы для доказательства невозможности телепортации состояния кубита посредством других алгоритмов.

Но как быть с успешными экспериментами по телепортации одного кубита, о которых идет речь в п. 4.2.2 ?! Первый из этих опытов описан в статье. Из аннотации видно, что данный эксперимент не был телепортацией в том смысле, который обсуждался выше. Утверждается, что имело место измерение поляризации одного из пары запутанных и удаленных друг от друга фотонов. При этом оказалось, что (как и предсказывает ЭПР) второй фотон имел такую же поляризацию. Данный результат авторы назвали телепортацией. Такая свобода манипулирования научно-фантастическими терминами вносит изрядную сумятицу в умы!

Но был ли такого рода опытами подтвержден феномен запутанности взаимно удаленных частиц, являющийся основой квантовой магии? Позволю себе утверждать, что нет! Опыты с запутанными фотонами были интерпретированы ошибочно. Во всех таких экспериментах, на самом деле, фиксировались факты «запутанности» фотонов с самими собой. Этот вопрос подробно рассмотрен в статье.

Квантовые вычисления

Если в качестве кубитов использовать фермионы, например электроны в спиновых состояниях, то при числе кубитов $n\geq 3$ любой вектор состояния регистра является нулевым. Это следует из общего утверждения: любой поливектор равен нулю в пространстве, размерность которого меньше его ранга. Его легко проверить непосредственно, попытавшись составить антисимметричное состояние из векторов вида $|000\rangle, |001\rangle, \ldots, |111\rangle$ . Ничего не выйдет! Не следует путать нулевой вектор состояния регистра, не отвечающий никакому физическому состоянию, с вектором состояния, в котором все кубиты имеют значение 0.

Таким образом, фермионы не годятся для квантовых регистров из более, чем двух кубитов. Практически это означает, что квантовые компьютеры можно создавать только на «элементной базе» из бозонов. Например фотонов или альфа-частиц, хотя для последних не ясно, что считать состояниями $|0\rangle$ и $|1\rangle$ .

Однако в том виде, как принято описывать квантовые компьютеры, они не осуществимы и с кубитами-бозонами!

Известно, что любое преобразование двоичного кода может быть выполнено через композицию вентилей Фредкина $inline$ и Тоффоли $inline$ (п. 5.1). Легко проверить, что квантовый вентиль $inline$ разрушает симметрию состояний: $T(|111\rangle)=|110\rangle$ . Вентиль $inline$ действует на симметричные векторы, как тождественное преобразование. В самом деле:

$F(|101\rangle+|110\rangle+|011\rangle)=|110\rangle+|101\rangle+|011\rangle$

$F(|100\rangle+|010\rangle+|001\rangle)=|100\rangle+|010\rangle+|001\rangle$

$F(|111\rangle)=|111\rangle$ $\quad F(|000\rangle)=|000\rangle$

Легко понять, что любой симметричный, трехкубитный вектор состояния является линейной комбинацией векторов в левых частях этих уравнений. Следовательно, вентиль Фредкина не меняет симметрические состояния. Поэтому любая последовательность преобразований $inline$ и $inline$ , применяемых к тройкам кубитов в соответствующих разрядах регистров с данными, разрушит запутанные состояния таких троек или оставит их без изменений. Поэтому квантовая вычисление, реализованное последовательностью вентилей $inline$ и $inline$ , физически неосуществимо. Из аналогичных соображений (нарушение симметрии общего состояния кубитов) следует, что почти все квантовые вычисления осуществить невозможно.

Компьютер Бога

Допустим, что необходимо вычислить какую-то функцию $inline$ , которая для целого аргумента с $inline$ двоичными разрядами принимает целое значение с $inline$ двоичными разрядами. Для этого нужен регистр из $inline$ кубитов для записи значений аргумента и регистр из $inline$ кубитов для записи значений функции. Переменная $inline$ может быть равна $0, 1, \ldots, 2^n-1$ . Каждому из этих значений соответствует вектор состояния первого регистра, отвечающий состояниям кубитов $|0\rangle$ или $|1\rangle$ , которые определяются двоичными цифрами числа $inline$ . Такие состояния регистра будем обозначать $|x\rangle$ , например $|x\rangle=|01\ldots 01\rangle=|0\rangle|1\rangle\ldots |0\rangle|1\rangle$ при $x=01\ldots 01$ .

Перед началом вычислений инициируется следующее (нормированное) состояние первого регистра:

$\frac{1}{\sqrt{2^n}}\cdot\sum_{x=0}^{2^n-1}|x\rangle\qquad\qquad(5)$

Для этого к состоянию $|00\ldots 0\rangle$ применяется преобразование Уолша-Адамара (п. 4.1.1). При измерении значений кубитов в состоянии (5) с вероятностью $P=2^{-n}$ может получиться любое целое число от $inline$ до $inline$ . Затем второй регистр устанавливается в $|0\ldots 0\rangle$ , после чего система из двух регистров оказывается в состоянии $2^{-n/2}\cdot\sum_{x=0}^{2^n-1}|x,0\rangle$ . В целом оно не является запутанным. Считается, что это состояние станет запутанным после применения к паре регистров унитарного преобразования $inline$ , определяемого функцией $inline$ (см. последний абзац на стр. 27 статьи extremal-mechanics.org/wp-content/uploads/2015/07/RIFFEL.pdf, на которую я постоянно ссылаюсь). Получается следующее состояние этой пары:

$\frac{1}{\sqrt{2^n}}\cdot\sum_{x=0}^{2^n-1}|x, f(x)\rangle\qquad\qquad(6)$

Как видно, одного применения вентиля $inline$ оказалось достаточно, чтобы были вычислены значения $inline$ для всех значений $x=0, 1, \ldots, 2^n-1$ одновременно.

В этом и заключается естественный параллелизм квантовых вычислений. При рабочем количестве кубитов первого регистра в несколько сотен, число $inline$ будет гигантским, поэтому такой параллелизм принципиально не доступен на обычных суперкомпьютерах. Компьютер Бога — вполне адекватное сравнение! Однако, при считывании результатов из второго регистра с вероятностью $P=2^{-n}$ может получиться любое из значений $inline$ . Для решения этой проблемы предлагается алгоритм Гровера, который также страдает нарушением симметрии (см. ниже).

Физическая реализуемость таких параллельных вычислений выглядит сомнительной, если исходить из соображений симметрии. Как было показано выше, в роли кубитов могут выступать только бозоны. Поэтому векторы их запутанных состояний должны быть симметричными, т.е., не меняющимися при любых перестановках. Однако ясно, что вектор (6) не является симметричным — транспозиция кубитов из первого и второго регистров может изменить его.

Таким образом, после применения преобразования $inline$ общее состояние пары регистров не является запутанным. Следовательно, при измерении второго регистра с целью получения результата вычислений мы получим некоторое число $inline$ , но не сможем выяснить, какому именно значению $inline$ оно соответствует. Дело в том, что состояние (6) физически невозможно из-за нарушения симметрии, поэтому вектор $|x_0, f(x_0)\rangle$ — одно из слагаемых вектора (6) не может быть получен при измерении регистров.

Суперкомпьютер не идет ни в какое сравнение с квантовым, вот только вряд ли последний можно сделать в принципе.

Алгоритм Гровера

Итак, квантовый параллелизм при вычислении произвольных функций нельзя осуществить физически. Но предположим, что для некоторой функции $inline$ это удалось сделать и мы получили пару регистров в общем состоянии (6). Как получить доступ к результатам вычислений, если все состояния в суперпозиции (6) равновероятны? Просто измеряя состояние регистров получим некоторую, случайную пару двоичных чисел $inline$ . При этом регистры окажутся в состоянии $|x\rangle|f(x)\rangle$ , а все остальные результаты вычислений будут безвозвратно потеряны (вот он — коллапс волновой функции!). Для решения этой проблемы Гровер придумал красивый алгоритм (п. 7.1).

Допустим, что мы хотим узнать значение $inline$ для вполне определенного $inline$ . Нужно добавить к регистрам еще один кубит для записи значений логической функции $inline$ , которая по определению равна 1 при $inline$ и равна 0 при $f(x)\neq f(x_0)$ . Затем к вектору

$\frac{1}{\sqrt{2^n}}\cdot\sum_{x=0}^{2^n-1}|x, f(x), P(x)\rangle\qquad\qquad(7)$

применяется вентиль, обращающий знаки коэффициентов $inline$ при всех векторах $|x, f(x), P(x)\rangle$ в сумме (7), для которых $inline$ (п. 7.1.2). Первоначально все $a_x=1/\sqrt{2^n}$ .

К измененному таким образом вектору (7) применяется преобразование инверсии всех коэффициентов $inline$ относительно их среднего значения $inline$ . Оно описано в п. 7.1.1, при этом суммирование следует вести до $inline$ , где $inline$ — число кубитов в первом регистре. Инверсия чисел $inline$ относительно среднего означает симметричное отражение соответствующих точек относительно точки $inline$ на комплексной плоскости. В результате этих остроумных действий коэффициенты перед векторами вида $|x, f(x), 1\rangle$ в сумме (7) увеличатся по модулю в сравнении с коэффициентами перед векторами вида $|x, f(x), 0\rangle$ .

После того, как описанные шаги алгоритма Гровера будут повторены $\pi\sqrt{2^n}/4$ раз (больше нельзя!), амплитуды вероятностей (т.е. коэффициенты $inline$ ) для состояний $|x, f(x), 1\rangle$ станут существенно большими, чем для состояний $|x, f(x), 0\rangle$ . Это означает, что измерение второго регистра с наибольшей вероятностью даст число $inline$ , а двоичный код в первом регистре окажется равным некоторому числу $x=\widetilde x$ , так что $f(x_0)=f(\widetilde x)$ (возможно $\widetilde x=x_0$ ). Тем самым будет получено искомое значение функции $inline$ при $inline$ .

Если измерение все же не даст числа $inline$ , то весь процесс, включая квантовые вычисления следует повторять до тех пор, пока не получится искомый результат. Поскольку заранее он не известен, в любом случае придется повторить несколько раз, после чего выбрать из полученных чисел $inline$ то число, которое встречается чаще всего. Из-за большой вероятности события $inline$ таких повторов будет не слишком много. Так можно получить значение $inline$ для любого $x_0=0, 1, \ldots, 2^n-1$ .

Описанный метод увеличения амплитуд вероятностей $inline$ в состояниях вида

$\sum_{x=0}^{2^n-1}a(x)\cdot |x, f(x), P(x)\rangle\qquad\qquad(8)$

также страдает нарушением симметрии состояний запутанных кубитов. В самом деле, если какое-то слагаемое $|x_0, f(x_0),1\rangle$ входит в (8) с коэффициентом $a_{x_0}$ , значительно превышающим по модулю коэффициенты при векторах вида $|x, f(x),0\rangle$ , то такой вектор (8) не будет симметричным (антисимметричным).

Следовательно, алгоритм Гровера не может быть физически реализован на регистрах, кубиты которых являются неразличимыми бозонами (фермионами). Он также не может быть использован для неупорядоченного поиска записи в файле, за исключением каких-то частных случаев.

Эмуляция с помощью пространств Фока

Проблема с симметрией состояний известна, но большинство специалистов над ней явно не задумываются. В качестве решения предлагается эмуляция квантовых регистров с помощью цепочек фермионов (fermionic lattices) или, другими словами, пространств Фока. Эта идея заключается в следующем.

Пусть даны $inline$ состояний $|\psi_1\rangle,\ldots,|\psi_n\rangle$ какого-нибудь фермиона, и других состояний он принимать не может. Тогда состояние $|x_1x_2\ldots x_n\rangle$ виртуального, квантового регистра предлагается эмулировать набором из $inline$ таких фермионов, где $inline$ — число единиц в двоичном коде $x_1x_2\ldots x_n$ . При этом фермионы находятся в общем антисимметричном состоянии, отвечающем занятым состояниям $|\psi_{j_1}\rangle,\ldots,|\psi_{j_k}\rangle$ , где $j_1,\ldots,j_k$ — номера разрядов регистра, в которых стоят единицы. Соответственно, линейные комбинации вида (3) состояний виртуального регистра эмулируются такими же линейными комбинациями оответствующих им состояний цепочек фермионов.

Выбор фермионов, а не бозонов обусловлен тем, что никакие два фермиона в этой системе не могут находиться в одном состоянии $|\psi_j\rangle$ . В противном случае такая эмуляция была бы невозможной. Таким образом, всевозможным состояниям квантового регистра соответствует пространство Фока фермионных состояний, в которых число частиц варьируется от $inline$ до $inline$ .

Считается, что такая эмуляция решает проблему нарушения симметрии состояний в процессе квантовых вычислений. Однако, она катастрофически усложняет физическую реализацию квантовых алгоритмов! Дело в том, что придется различать и контролировать не 2 состояния каждого кубита в регистре из $inline$ кубитов, а $inline$ состояний фермионов в системе, где число этих частиц меняется в процессе вычислений. При этом $inline$ достигает сотен или тысяч, если нужен квантовый компьютер со всеми его фантастическими возможностями. Проблема декогеренции физических кубитов на этом фоне выглядит детской забавой, а усилия, направленные на ее решение, были затрачены во многом понапрасну.

Есть также теоретические трудности, связанные с эмуляцией запутанных состояний виртуального регистра. Для определения запутанности по состояниям фермионных цепочек прибегают к ухищрениям, которые не дают полного решения проблемы. Следствием этого стал например тот факт, что фермионному состоянию $|10\rangle-|01\rangle$ отказали в праве быть запутанным на том основании, что это состояние якобы нефизическое!

Таким образом, вопреки всеобщему энтузиазму, реальные перспективы квантовых компьютеров выглядят весьма туманно. Даже безотносительно к вопросу о физической реальности квантовой магии, принципиальная осуществимость квантовых вычислений вызывает глубокие сомнения. О них ученые предпочитают не рассказывать обществу, если судить по научно-популярным восторгам вокруг проверок нарушений неравенства Белла. Огромный массив научных работ и диссертаций по квантовым компьютерам отнюдь не служит доказательство осуществимости того, чем занимаются их авторы. Однако, научное сообщество уже не способно критически оценивать парадигму ЭПР — запутанности, которая стала догмой. На мой, возможно ложный взгляд, все это — грандиозный миф, а пропасть между микро и макромиром является непреодолимой. Просто людям хочется верить в чудеса!

Теги:

Хабы:

Квантовые технологии