Успех, о котором идет речь, — это демонстрация условий, в которых квантовый компьютер D-Wave работает в 100 миллионов раз быстрее обычного процессора.
Весть об этом полетела и здесь , И совсем повсюду .
Что это значит для простых смертных? Нужно ли переходить к программированию на квантовых компьютерах? Что это вообще за программа? Мне стало любопытно, и я почитал немного подробностей (сама научная статья здесь ).
Как всегда, я кратко объясню свое понимание.
Отказ от ответственности: сообщение было написано на основе сильно отредактированных журналов чата.
closecircles.com , отсюда и стиль изложения и наличие уточняющих вопросов.
Сначала немного предыстории — что такое процессоры D-Wave. Сделать универсальный квантовый компьютер очень сложно и непонятно как, поэтому D-Wave делает очень узкоспециализированное оборудование, решающее исключительно задачу квантового отжига.
Что вообще такое отжиг?
Это проблема оптимизации следующего выражения:
Имеется N двоичных переменных s я , они принимают значения -1 или +1. Вы можете указать реальные коэффициенты h я и Дж.
ij .
отжиг — это минимизация E для всех возможных значений двоичных переменных (с фиксированными коэффициентами).
и что у нас получается в итоге? час я ,Дж ij ? Да, мы можем установить их снаружи.
Что является входом и что является выходом? если мы установим ч я , Дж ij снаружи, то эта махина находит набор s я при котором Е минимально что ли? Да, точно.
Далее, мы должны понимать, что квантовый процесс не гарантирует нахождение глобального минимума; с определенной вероятностью он находит значение, несколько близкое к нему.
Какие практические задачи можно решить таким образом?
Примером в статье Google является так называемая проблема разделения номеров (NPP).Классическая задача: у вас есть набор из N положительных чисел, вам нужно разделить их на две кучки так, чтобы суммы чисел в каждой куче были как можно ближе друг к другу.
Даже такая, казалось бы, простая задача — NP-hard и все такое прочее, но выразить ее как отжиг довольно просто.
Пусть двоичная переменная является флагом принадлежности к некоторой куче.
Тогда вам нужно минимизировать: 
Минимизация модуля аналогична минимизации квадрата.
Не понимаю связи первой формулы с задачей разделения на кучки
Здесь я написал более подробно: 
Как такие проблемы решаются сейчас на ЦП?
Одним из простых и до сих пор часто используемых на практике методов является имитация отжига.Википедия о нем пишет вполне прилично - https://en.wikipedia.org/wiki/Simulated_annealing Идея состоит в том, чтобы начать с некоторого случайного состояния двоичных переменных и случайным образом переворачивать их на каждом этапе.
Если в результате подброса мы получим лучший результат, мы берем его.
Если нет, то с некоторой вероятностью принимаем или нет. Вероятность зависит от разницы между новым и старым значениями энергии и от так называемой «температуры» — еще одного параметра оптимизации, такого, что в начале процесса температура высокая, а по ходу процесса — тем ниже .
Благодаря этому вероятностному процессу моделируемый отжиг может выйти за пределы локальных минимумов.
Конечно, это можно проводить несколько раз, можно делать перезагрузки и т. д. В нем нет никакой эвристики и управлять можно только «температурным режимом».
Каковы ограничения D-Wave на практике?
В последней версии D-Wave около тысячи кубитов (столько же бинарных переменных в задаче).Но есть некоторые детали!
- Первое: эти J ij между двумя с я и с дж (их еще называют связями) требуют связи между отдельными кубитами, т.е.
чтобы между двумя параметрами был ненулевой коэффициент J ij — эти кубиты должны быть связаны.
В АЭС, например, каждый кубит связан друг с другом, поскольку все J ij ненулевой В D-Wave каждый кубит можно соединить (барабанная дробь) с ~10 другими, причем не любыми, а заранее заданными.
- Второе: с какой точностью можно задать эти J? ij
В D-Wave эта точность (опять дробь) составляет 4 бита.
Напомню, что на АЭС J ij =а я *а дж , то есть для я Осталось 2 бита, лол.
Итак, ребята из Google пытаются придумать очень теоретическую задачу, которая как можно лучше соответствовала бы этой архитектуре.
Почему квантовый компьютер вообще может быть более эффективным?
Если в нашем пространстве много больших гор и впадин между ними.
Затем алгоритму необходимо пройти через эти углубления в процессе оптимизации, и в отличие от моделирования отжига квантовый компьютер может «туннелировать» между довольно узкими трещинами.
Те.
Имитация отжига должна увеличить энергию системы, чтобы добраться до вершины холма, а квантовый компьютер может «пройти туннель» сквозь стену, не увеличивая энергию системы.
Зачем сходиться быстрее — «увеличение энергии» означает более длительный случайный поиск.
Расстояние, на котором может произойти туннельный переход, определяется параметрами системы — температурой компьютера (все эти процессы становятся квантовыми при ~10К), конкретными деталями физической компоновки и т. д. и т. п.
Поэтому нам нужна задача, где много узких проходов такой длины, чтобы D-Wave мог их преодолеть.
Хорошо, а как построена эта «хорошая» задача?
Основной элемент, из которого собирают такую задачу:
Это 8 кубитов одного знака и 8 кубитов другого знака.
Каждый кубит в группе из 8 связан с остальными связью с отрицательным весом (т. е.
для минимизации энергии все в группе из 8 должны быть одного знака).
Между некоторыми кубитами из первой и второй группы также существует связь, тоже с отрицательным знаком (но более слабая), и для нее плохо то, что изначально группы имеют разные знаки.
В идеале все кубиты в системе должны быть одного знака, что приводит к минимуму энергии.
Но этого невозможно добиться, перевернув один или два бита — вам нужно перевернуть все биты в группе из 8, чтобы получить наилучшее значение.
Именно это создает такие высокие (но короткие) барьеры на ландшафте.
то есть они создают такую «успешную» задачу, используя эту специальную конфигурацию связи кубита? Ага и какой «реальной» задаче это соответствует? Нет! Это все еще остается задачей при отжиге (c h я и Дж.
ij ), но практического значения не имеет и иметь не может. Затем повторяют эту конфигурацию на всех 1000 кубитах согласно связям, зашитым в железо: 
Таким образом строятся задачи разного размера, где нужно переворачивать куски по 8 кубитов.
В статье сравнивается скорость D-Wave в этой задаче с имитацией отжига и другим алгоритмом Quantum Monte Carlo. Квантовый Монте-Карло — это алгоритм Нет для квантового компьютера, который, насколько я понимаю, пытается решить интеграл, описывающий квантовое уравнение системы, методом Монте-Карло.
Ну вот они сравнивают SA и QMC на одном ядре CPU и квантовый отжиг на D-Wave, чтобы добиться одинаковой точности результата (95% от оптимального, кажется).
СА в их задаче для этого, например, нужно 10 9 запускает. И теперь мы наконец готовы понять основной график из статьи: 
Это время выполнения задачи, основанное на количестве двоичных переменных.
При максимальном размере задачи D-Wave на самом деле быстрее, чем имитация отжига, на 10 8 один раз… Но! D-Wave не асимптотически лучше QMC (то есть квантовый компьютер не решает задачу асимптотически лучше), но лучше SA. У меня такой странный вопрос по поводу этого графика, почему цифры сверху такие неровные? Это реальный размер проблемы? почему-то оно не делится на 8 Потому что в железе всё несимметрично :) Есть кубиты, которые не имеют каких-либо связей.
На картинке полного графика видно, что есть несколько кластеров-выбросов — где-то группа из 6, где-то 7. Пикантности добавляет то, что у каждого экземпляра D-Wave график немного разный, ведь он зависит от дефектов доходности.
Означает ли это, что квантовый компьютер решает, по крайней мере, эту вырожденную задачу лучше, чем обычный?
Нет! Это лучше только по сравнению с алгоритмами без эвристики.Алгоритмы отжига с эвристикой (которые смотрят на связность графа и т. д.) решают ее на одном процессоре быстрее, чем D-Wave. Что неудивительно: задание на высоком уровне очень простое, если вы видите, что нужно листать группами по 8 человек.
Это подводит нас к основной критике результата и неуверенности в светлом будущем.
Оптимистично можно надеяться, что новое оборудование будет иметь большую связность и большую точность коэффициентов связи, что позволит записывать более жизненно важные и сложные задачи (которые не будут решены эвристикой).
Пессимистически можно усомниться в том, что в ближайшем будущем можно будет построить что-то с такими параметрами, будет ли вообще квантовый эффект, будет ли у жизненных задач такой удачный ландшафт и т. д. и т. п.
(подробнее, ад и дым здесь - http://www.scottaaronson.com/blog/Эp=2555 )
Что еще можно сказать кроме этого.
- Хорошие новости — результат, кажется, доказывает, что в DWave действительно происходит какой-то квантовый процесс (это уже около десяти лет является предметом яростных холиверов).
- Больше нет необходимости бороться за количество кубитов; нам нужно бороться за связи и точность.
Вы можете продолжать писать на PHP и JavaScript. Теги: #Квантовые технологии #Процессоры #Google #Будущее здесь #d-wave #Квантовые вычисления
-
Ури, Гарольд Клейтон
19 Oct, 24 -
Китайская Философия
19 Oct, 24 -
Как Защитить Свою Облачную Инфраструктуру
19 Oct, 24 -
Стартапы: Список Всех Проектов Фрии
19 Oct, 24
