- PVSM.RU - https://www.pvsm.ru -
Успехи, о которых идет речь — демонстрация условий, в которых квантовый компьютер D-Wave быстрее обычного CPU в 100 миллионов раз. Новость об этом пролетала и тут [1], и вообще [2] везде [3].
Что же это значит для простых смертных? Надо ли вовсю переключаться на программирование на квантовых компьютерах? Что там вообще за программирование?
Мне стало любопытно, и я немного почитал про детали (сама научная статья — тут [4]). Как всегда, кратко рассказываю свое понимание.
Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com [5], отсюда и стиль изложения, и наличие уточняющих вопросов.
Для начала, немного бэкграунда — что такое процессоры D-Wave.
Делать универсальный квантовый компьютер — это очень сложно и непонятно как, поэтому D-Wave делают очень узко-специализированное железо, которое решает исключительно задачу quantum annealing.
Это задача оптимизации вот такого выражения:
Есть N бинарных переменных si, они принимают значения -1 или +1. Можно задавать вещественные коэффициенты hi и Jij.
annealing — это минимизация E для всех возможных значений бинарных переменных (при фиксированных коэффициентах).
а чем управляем в итоге? hi,Jij?
Мы можем задавать их извне, да.
что инпут, а что аутпут? если мы задаем hi, Jij извне, то эта махина находит набор si при котором E минимальна или что?
Да, именно так.
Далее, надо понимать, что квантовый процесс не гарантирует нахождения глобального минимума, он с некой вероятностью находит значение, которое сколько-то близко к нему.
Пример в Гугловской статье — так называемый Number Partitioning Problem (NPP).
Классическая задача — есть набор из N положительных чисел, нужно разделить их на две кучи, чтобы суммы чисел в каждой куче были как можно ближе друг к другу.
Даже такая простая, казалось бы, задача — NP-hard и все эти дела, но ее довольно просто выразить как annealing.
Пусть бинарная переменная — это флаг принадлежности к какой-то куче.
Тогда нужно минимизировать:
Минимизация модуля — это то же самое, что минимизация квадрата.
не понимаю связку между первой формулой и задачей разделения на кучи
Вот я расписал подробней:
Один из простых и все еще часто использующихся на практике методов — simulated annealing. Википедия пишет про него достаточно прилично — https://en.wikipedia.org/wiki/Simulated_annealing [6]
Идея в том, чтобы начать с какого-то случайного состояния бинарных переменных и на каждом шаге их случайно флипать.
Если мы в результате флипа получили результат лучше — берем его. Если же нет, то берем или нет с некой вероятностью.
Вероятность зависит от разницы между новым и старым значением энергии и от так называемой "температуры" — еще одного параметра оптимизации, такого что в начале процесса температура большая, а чем дальше, тем меньше. За счет этого вероятностного процесса simulated annealing может вылезать из локальных минимумов. Разумеется, его можно проводить несколько раз, делать рестарты итд итп.
В нем нет никаких эвристик и можно управлять только "температурным режимом".
В последней версии D-Wave около тысячи кубитов (это то самое количество бинарных переменных в задаче).
Но есть некоторые детали!
Первая: вот эти Jij между двумя si и sj (они еще называются couplings) требуют связи между отдельными кубитами, т.е. чтобы между двумя параметрами был ненулевой коэффициент Jij — эти кубиты должны быть связаны.
В NPP, например, связан каждый кубит с каждым, так как все Jij ненулевые
В D-Wave каждый кубит может быть связан (барабанная дробь) с ~10 другими, причем не с любыми, а заданными заранее.
На всякий случай, русским языком — сложно придумать практическую задачу, которую можно решать на этом всем добре.
И вот мужики в Гугле стараются придумать очень теоретическую задачу, которая бы максимально хорошо ложилась на эту архитектуру.
Если у нашего пространства много больших гор и впадин между ними...
То алгоритму нужно пройти через эти впадины в процессе оптимизации, и в отличие от simulated annealing, квантовый компьютер может "туннелировать" между достаточно узкими разломами.
Т.е. simulated annealing должен увеличить энергию системы чтобы выбраться наверх холма, а квантовый копмьютер может "туннелировать" сквозь стену не увеличивая энергию системы. Отчего сойтись быстрее — "увеличивать энергию" означает более долгий случайный поиск.
Расстояние, на котором туннельный переход может произойти, определяется параметрами системы — температурой компьютера (эти все процессы становятся квантовыми при ~10K), конкретными деталями физического лейаута итд итп.
Посему, нужна задача где много вот узких переходов такой длины, чтобы она преодолевалась D-Wave.
Основной элемент из которого они такую задачу собирают:
Это 8 кубитов одного знака, и 8 кубитов другого знака. Каждый в группе из 8 кубитов соединен с остальными связью с отрицательным весом (т.е. для минимизации энергии все в группе из 8 должны быть одного знака).
Между некоторыми кубитами из первой и второй группы тоже есть связь, тоже с отрицательным знаком (но более слабая), и для нее то, что изначально группы разного знака — плохо.
В идеале, в системе все кубиты должны быть одного знака, что приводит к минимуму энергии. Но флипаньем одного или двух битов туда попасть нельзя — нужно флипнуть все биты в группе из 8, чтобы получить лучшее значение. Это и создает такие высокие (но короткие) барьеры на ландшафте.
то есть они создают вот такую "удачную" задачу с помощью этой специальной конфигурацией связи кубитов?
Ага
а какой "реальной" задаче это соответствует?
Никакой!
Это все еще задача в рамках annealing (c hi и Jij), но практической ценности у нее нет никакой и быть не может.
Потом они повторяют эту конфигурацию на всех 1000 кубитах согласно связям, прошитым в железе:
Таким образом конструируются задачи разных размеров, где надо флипать кусками по 8 кубитов.
В работе сравнивается скорость D-Wave на этой задаче с simulated annealing и еще одним алгоритмом, Quantum Monte Carlo.
Quantum Monte Carlo — это алгоритм не для квантового компьютера, который, насколько я понимаю, пытается решить интеграл, описывающий квантовое уравнение системы, методом Монте Карло.
Ну и вот они сравнивают SA и QMC на одном ядре CPU и quantum annealing на D-Wave для достижения той же точности результата (95% от оптимального, кажись). SA в их задаче для этого, например, нужно 109 запусков.
И вот теперь наконец-то мы готовы понять главный график из статьи:
Это время выполнения задачи от количества бинарных переменных.
При максимальном размере задачи D-Wave действительно быстрее simulated annelaling в 108 раз…
Но! Ассимптотически D-Wave не лучше QMC (то есть, и асимптотически лучше квантовый компьютер задачу не решает), но лучше SA.
у меня вот такой странный вопрос по этому графику, почему числа сверху такие неровные? это настоящий размер проблемы? как-то не делится на 8
Потому что в железе все несимметрично :)
Есть кубиты, у которых некоторых связей нет. На картинке полного графа видно, что есть некоторые выпадающие кластеры — где-то группа по 6, где-то 7.
Пикантности добавляет то, что у каждого экземпляра D-Wave этот граф немножко разный, потому что он зависит от yield defects.
Нет! Лучше только если сравнивать с алгоритмами без эвристик.
Алгоритмы annealing с эвристиками (которые смотрят на связность графа итд) решают ее на одном CPU быстрее, чем D-Wave. Что неудивительно: задача на высоком уровне очень простая, если увидеть что надо флипать группами по 8.
Это подводит к нас к основной критике результата и неопределенности в светлом будущем.
Оптимистично можно надеяться, что в новом железе будет большая связность и большая точность коэффициентов coupling, что даст записывать более жизненные и сложные задачи (которые эвристиками решаться не будут).
Пессимистично можно сомневаться, получится ли вообще в ближайшем будущем построить что-то с такими параметрами, будет ли там вообще квантовый эффект, и будет ли у жизненных задач такой удачный ландшафт итд итп.
(больше подробностей, ада и угара здесь — http://www.scottaaronson.com/blog/?p=2555 [7])
Подытожив — можно расслабиться, внезапного рывка нет, это следующий шажок в освоении квантовых компьютеров, практическое применение еще далеко.
Можно продолжать писать на PHP и javascript.
Автор: sim0nsays
Источник [8]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/117683
Ссылки в тексте:
[1] и тут: https://geektimes.ru/post/267324/
[2] вообще: http://blogs.wsj.com/digits/2015/12/10/googles-tough-search-a-quantum-leap-in-computing-power/
[3] везде: http://venturebeat.com/2015/12/08/google-says-its-quantum-computer-is-more-than-100-million-times-faster-than-a-regular-computer-chip/
[4] тут: http://arxiv.org/abs/1512.02206
[5] closedcircles.com: http://closedcircles.com/?invite=4d47968dbf3a2d1d7e956b0a5802b73269a80b64
[6] https://en.wikipedia.org/wiki/Simulated_annealing: https://en.wikipedia.org/wiki/Simulated_annealing
[7] http://www.scottaaronson.com/blog/?p=2555: http://www.scottaaronson.com/blog/?p=2555
[8] Источник: https://geektimes.ru/post/274160/
Нажмите здесь для печати.