Действительно ли квантовый процессор D Wave в 100 миллионов раз быстрее обычного?

На протяжении нескольких лет наш сайт освещал заявления компании D‑Wave касательно её квантовых устройств. За это время моё к ним отношение колебалось в диапазоне от скептицизма, и даже сильного скептицизма, до умеренного энтузиазма.



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

Конечно, лучший способ оценить достижения D‑Wave это не пресс релизы компании и не характеристики и параметры, написанные на упаковке процессоров, — к этому всему стоит относиться с огромным подозрением. Лучше посмотреть, что пишут в своих публикациях исследователи, которые имели возможность непосредственно попробовать продукты D‑Wave. И не смотря на мои сомнения, работа, опубликованная на сайте arXiV одновременно с пресс‑релизом — так же, как и пара работ, вышедших ранее, — весьма интересна. Если сложить всё вместе, то выходит, нам в конце концов стоит отнестись к прогрессу компании с осторожным оптимизмом.

Краткая история компании D‑Wave

Если вы не знакомы с историей и деятельностью компании D‑Wave, вы можете легко найти несколько статей об этом, прежде чем продолжать. Здесь мы лишь вкратце напомним: давным‑давно, в далёкой‑далёкой стране (Канаде) маленькая стартап‑компания объявила о планах создать 16‑битный квантовый компьютер. Для всех это было большой неожиданностью, учитывая, что до этого многие исследователи с гордостью сообщали о создании одно- или двухбитных устройствах. Компания намутила воды ещё больше, объявив, что обещаемый компьютер будет основан на совсем ином подходе по сравнению с любыми прежними разработками. Подход назвали адиабатическими квантовыми вычислениями.

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

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

Здесь‑то компания D‑Wave и выходит на сцену. Вместо того, чтобы начинать с нужного множества состояний (со сложной формой диаграммы), компания начинает с множества, которое можно представить в виде чаши, и формирует основное состояние всех частиц («располагая» их на дне чаши). Далее медленно и осторожно деформирует чашу до более сложной формы, которая нам необходима (это называется адиабатический процесс, отсюда и пошло название адиабатический квантовый компьютер). Если всё сделать аккуратно, то частицы останутся в основном состоянии, а в конце процесса трансформации мы получим решение.

Затем, чтобы получить ответ, мы просто считываем состояние всех частиц. Задание выполнено.

В чём же здесь квантовость?

Всё описанное выше полностью относится к классическим явлениям. Биты могут быть квантовыми сущностями, но их можно также представить и в виде крошечных магнитов, прыгающих вверх и вниз, и здесь не требуется никакой квантовости. Но оборудование D‑Wave называют квантовым, так как оно использует квантовое туннелирование. При сложных множествах состояний (со сложной диаграммой) квантовые биты (кубиты) могут быть захвачены в состоянии с наименьшей энергией, которое не является решением (так как это локальный минимум, но не абсолютный для всего множества). В классической механике кубиту пришлось бы повышать свою энергию и выбираться из текущей впадины, чтобы попасть в более глубокую. Однако квантовые частицы в состоянии просачиваться через барьер между минимумами.

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

(Для высоких, но тонких барьеров туннелирование хорошо подходит. Но оно становится менее применимым по мере увеличения толщины барьера. Компания D‑Wave должна удерживать барьеры тонкими.)

Разумеется, здесь есть свои сложности. Если один и тот же процесс должен произойти между кубитами, которые очень слабо связаны между собой (например, посредством других кубитов), то квантовое туннелирование крайне маловероятно, и от него в данном случае мало или же и вовсе нет никакой пользы для выхода из локального минимума.

В компьютерах D‑Wave процесс туннелирования происходит физически. Но те, кто хочет повозиться с технологией у себя дома, могут на самом деле воспроизвести всё это на обычном компьютере. Этот процесс называется имитацией нормализации (отжига) (в противовес реальной физической нормализации, которую проводит D‑Wave) и использует математическую модель физической системы. Вы даже можете симулировать квантовую нормализацию, что будет виртуальным аналогом процесса, наличие в своих устройствах которого компания D‑Wave пытается продемонстрировать.

Как у нас дела с нормализацией?

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

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

Однако почти не обсуждается вопрос увеличения количества кубитов до каких-либо существенных и полезных значений. А интеграция квантового вычислителя с обычным компьютером просто оставлена читателям в качестве упражнения для ума.

Компания D‑Wave, наоборот, занялась «разумной инженерией, рискованной физикой». В первую очередь они выбрали технологию, которая пригодна для масштабирования. Их кубиты основаны на сверхпроводящих квантовых интерферометрах (СКВИДах). СКВИДы могут быть нанесены на печатную плату методом фотолитографии; эксперименты других исследователей показали, что они когерентны и могут быть сцеплены. Хотя эти свойства и не появляются автоматически, так что вам, быть может, придётся потратить определённое время, чтобы убедиться, что сцепленность действительно имеет место в вашем устройстве.

Однако вместо того, чтобы стремиться подтвердить квантовость, компания D‑Wave сфокусировалась на инженерии: увеличении количества кубитов, обеспечении интеграции с доступными в продаже обычными ЭВМ и оптимизации процесса нормализации, чтобы вычисления производились с максимальной возможной скоростью. Это разумная инженерия, и компания доказала приверженность ей. D‑Wave выпустили сопроцессор, который физически производит нормализацию с необыкновенно большим количеством битов, быстро и просто. Нам всем следовало бы впасть в трепет от таких достижений.

Но риск таится в физике. Компания D‑Wave не знает, СКВИДы ведут себя как классические биты или как кубиты. Справедливости ради надо сказать, что это не так-то просто выяснить, — я даже не знаю, как можно непосредственно подтвердить сцепленность между десятью или больше кубитами, к примеру.

Вместо того, чтобы выяснять это, D‑Wave пошла несколько непрямым путём, который можно назвать подтверждением с помощью производительности. Компания рассуждает следующим образом: если известно, что определённая задача масштабируется на классическом компьютере одним образом, а на квантовом компьютере — другим, то можно сравнить масштабируемость, решая вычислительные задачи разных объёмов и наблюдая за результатом.

Приведём простой (и выдуманный) пример: трудоёмкость задачи подсчёта количества яиц в одной корзине на квантовом компьютере возрастает линейно вместе с количеством яиц; на классическом компьютере — экспоненциально. В случае с количеством яиц равным нулю оба компьютера выполняют вычисления одинаково. В случае с одним яйцом квантовый компьютер производит вычисления в два раза быстрее. В случае с десятью — квантовый компьютер уже в 2 000 раз быстрее. Таким образом, вычислительная задача с 10‑ю яйцами позволяет получить надёжное подтверждение.

Говоря в терминах нашего примера, устройство D‑Wave способно решать задачи подсчёта количества только для максимум трёх яиц, при этом в оптимальном варианте получается семикратный выигрыш в производительности. При таком выигрыше, на результат существенно влияет реализация вычислительного процесса на обоих компьютерах — каким именно образом производится работа алгоритма. Даже если удалось подтвердить семикратный выигрыш в производительности, нельзя с уверенностью сказать, что на самом деле это означает.

Тем не менее данный результат доказал эффективность и целесообразность подхода компании D‑Wave. Полученные показатели масштабируемости скорее говорят о квантовой природе компьютера, чем о классической. К сожалению, до сих пор во всех случаях, продемонстрированных компанией, можно найти такую реализацию классической ЭВМ, которая превзойдёт процессор D‑Wave.

«подпись к изображению»

Квантовость обнаружена

Однако в конце 2014 г. компании Google и D‑Wave, НАСА и учёные Университета штата Мичиган установили, что в процессоре D-Wave на самом деле происходит туннелирование.

По крайней мере локально. Но что это означает — локально? Это связано со структурой процессора D‑Wave. В идеале, при имитации нормализации (отжига) для преодоления всех трудностей каждый кубит должен быть соединён с каждым другим кубитом. Для схемы с 1 000 кубитами это становится существенным вызовом. Чтобы избежать его, кубиты собраны в группы по восемь. Внутри группы каждый кубит соединён с четырьмя другими. В двух соседних группах четыре кубита из каждой этой группы соединены попарно друг с другом. Фактически, каждая группа сильно связана с каждой, а кубиты из разных групп слабо связаны.

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

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

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

Это именно то, что отметили учёные. Позднее более тщательные проверки только подтвердили данные наблюдения. Чтобы обобщить достижение, скажем, что подтверждено использование туннелирования в тесно связанных регионах в процессоре D‑Wave. И это здорово, но до сих пор нет доказательств туннелирования между слабо связанными регионами.

Достаточно ли коротких туннелей?

Туннелирование внутри локальной группы работает и эффективно, в то время как все вопросы, связанные с туннелированием между группами, остаются открытыми. Вот главный вопрос из упомянутого чуть выше исследования: важно ли данное ограничение? Приносит ли локальное туннелирование ускорение, пусть это и не максимальное ускорение, которое можно было бы ожидать от полностью квантового компьютера? Другими словами, компания D‑Wave пыталась понять, сведёт ли на нет данная ограниченная связанность предполагаемый выигрыш при вычислениях.

Простите за небольшой спойлер, но ответ довольно сложен: хотя в работе и присутствуют намёки, в ней на самом деле не даётся определённого ответа на поставленный вопрос.

Подход, применённый командой исследователей, во многом всё тот же, как и в предыдущих работах, посвящённых производительности: поставить определённую вычислительную задачу, и сравнить её масштабируемость при различных методах имитации нормализации (отжига) на обычном компьютере и при физической нормализации на микросхеме D‑Wave. В данном случае в качестве вычислительной задачи была выбрана… симуляция архитектуры D‑Wave. Другими словами, учитывая связанность кубитов, поиск энергетического минимума. Естественно, аппаратура D‑Wave довольно хорошо оптимизирована под эту задачу. По факту она выполняет локальное туннелирование с максимальным эффектом, так как одновременный прыжок всех битов (туннелирование) намного более вероятен, чем классический процесс перепрыгивания каждого кубита по отдельности.

Для этой вычислительной задачи в ходе исследования делается два важных вывода. Во‑первых, процессор D‑Wave намного быстрее двух классических алгоритмов, которые использовались для сравнения. Во‑вторых, получаемая производительность выше в 10⁸ раз — весьма впечатляющий результат.

Но… здесь есть пару «но». Во‑первых, масштабируемость нисколько не выше, чем у лучшего из алгоритмов (квантовый метод Монте‑Карло). Поэтому выигрыш в производительности остаётся постоянным, и нет даже намёка на лучшую масштабируемость. Во‑вторых, процессор D‑Wave может быть даже быстрее при выполнении меньших задач, так как физический процесс нормализации имеет настраиваемое минимальное время (устанавливается в управляющей программе), которое вполне может быть продолжительнее реально необходимого.

Такие хорошие новости могут на самом деле запросто обернуться плохими. Почему? Смотрим, если производительность аппаратуры D‑Wave для небольших вычислительных задач на самом деле выше, чем проявляется, то вместо того чтобы разница в производительности относительно классического алгоритма оставалась постоянной (масштабируемость у них одинаковая, но быстродействие D-Wave всегда выше), эта разница по мере увеличения объёма задачи уменьшается, вместо того чтобы расти, как надеялись обнаружить в компании D‑Wave. В таком случае, масштабируемость больше соответствует худшему классическому алгоритму (алгоритму имитации нормализации (отжига)), чем лучшему. Вырисовывается не радостная картина.

Есть ещё одно дополнение к результатам исследования. Основная подпрограмма, выполняющая имитацию нормализации, может быть подстроена под конкретную задачу, если вам известны её тонкости. Например, можно сперва провести поиск для кластеров сильно связанных кубитов, которые слабо связаны с соседними кластерами. Затем эти кластеры заменяются единичными псевдобитами. В таком случае автоматически обходятся локальный минимум кластера при условии неправильной ориентации.

Тонко настроенный классический алгоритм обходит процессор D‑Wave.

Всё настолько плохо?

Имея такие противоречивые результаты, можем ли мы делать какие-либо выводы? Первый вывод: процессор D‑Wave симулирует работу процессора D‑Wave очень эффективно. И эта новость лучше, чем может показаться на первый взгляд. В конце концов, если бы устройство не могло бы делать и этого, то нельзя было бы и ожидать, что оно вообще ещё что-то сможет сделать на хорошем уровне. Второй вывод: процессор D‑Wave начинает подавать некоторые надежды — в устройстве явно присутствуют некоторые квантовые явления.

Тем не менее здесь есть одно важное условие. Форматирование вычислительной задачи под архитектуру D‑Wave не должно быть слишком трудоёмким, это касается как затрат на само форматирование, так и затрат на извлечение и анализ полученных результатов. Иначе выигрыш в производительности будет нивелирован эксплуатационными расходами.

Есть ещё один менее приятный вывод касательно перспектив технологии D‑Wave. Хотя наличие локального квантового туннелирования и подтверждено, похоже, что польза от него довольно ограничена. Пока что туннелирование приносит постоянный выигрыш в производительности по сравнению с традиционным компьютером, но не лучшую масштабируемость.

Хотя есть одно замечание к данному факту. Нельзя сказать, что масштабируемость, обнаруженная на некоем наборе небольших задач, исключает возможность лучшей масштабируемости на другом наборе более крупных задач, так как масштабируемость, полученная в ходе данных экспериментов, может оказаться больше зависима от тонкостей реализации, чем от процесса физической нормализации. Проще говоря, мы до сих пор не можем спрогнозировать, как процессор D‑Wave поведёт себя в случае действительно больших задач.

В заключении можно сказать, что архитектура процессора сама по себе начинает ограничивать его полезность. Это понимают и инженеры D‑Wave, поскольку они, вместо того чтобы увеличивать количество кубитов, уже планируют разработку следующего поколения процессоров, основанных на иной архитектуре. Разработчики надеются создать новый, усовершенствованный процессор, в котором связь между элементами построена в виде десятимерной изометрической решётки. Детали не раскрываются, но, похоже, в планах инженеров создание внутренне сильно связанных кластеров при несколько меньшей связанности между кластерами. В результате повышенная плотность связей внутри кластера — как и повышенная связность между кластерами — должна способствовать более эффективному выполнению больших вычислительных задач. Это довольно многообещающе.

Учитывая насколько я был пессимистично настроен по поводу D‑Wave ещё в 2007 г., я вынужден признать, компания продвинулась намного дальше, чем кто-либо в здравом уме ожидал от них. D‑Wave нашла изящные инженерные решения, и я на самом деле надеюсь, что им удастся воплотить ещё более смелые задумки касательно новой архитектуры. Суммируя всё это, может статься, что они в конце концов реализуют некоторые из своих ранних ошеломляющих заявлений.

http://gearmix.ru/