Российские учёные показали, что вероятностные компьютеры решили задачи оптимизации не хуже D-Wave
Классические вероятностные компьютеры способны решать сложные задачи оптимизации не хуже крупных квантовых машин. Они работают при комнатной температуре и создаются из обычных компонентов.
Оптимизационные задачи встречаются повсюду: планирование маршрутов доставки, составление графиков на заводах, распределение электроэнергии в сетях. Число возможных решений растёт так быстро, что обычный компьютер может находить лишь посредственные варианты, а найти лучший крайне сложно.
Квантовые вычисления обещали справляться с такими задачами эффективнее. Для проверки используют модели Изинга — системы из маленьких «магнитных иголок», каждая из которых может быть направлена вверх или вниз. Иглы взаимодействуют друг с другом: одни стремятся выровняться параллельно, другие — наоборот. Поиск наименьшей энергии системы эквивалентен поиску оптимального решения задачи «да/нет» с множеством взаимозависимых факторов.
В статье Nature Communications исследователи решали особенно сложную задачу — трёхмерное спиновое стекло с случайными взаимодействиями. На этом примере квантовый компьютер D-Wave продемонстрировал масштабирование лучше некоторых классических алгоритмов.
Квантовый отжиг сравнивают с охлаждением металла: система изначально в простом состоянии постепенно переходит к низкоэнергетическому, оптимальному решению. Авторы статьи смоделировали квантовый отжиг на обычном компьютере с помощью метода дискретного смоделированного квантового отжига (DT-SQA). Вместо одной решётки магнитов создаются тысячи копий, имитирующих квантовые эффекты.
Другой подход — адаптивное параллельное закаливание (APT). Несколько копий задачи работают при разных «температурах»: одни исследуют детали, другие хаотично перебирают варианты. Копии периодически обмениваются конфигурациями. Алгоритм дополнен кластерными перемещениями: целые группы «игл» инвертируются за один шаг, что помогает быстрее находить лучшие решения.
Настоящий эффект проявляется при использовании специализированных вероятностных компьютеров (p-компьютеров). В них биты ведут себя случайно, как подброшенная монета, и естественно имитируют поведение модели Изинга. Сети p-битов автоматически стремятся к оптимальным решениям.
Такие машины создают на CPU, GPU, FPGA и комбинированных системах с наномагнитами. Все платформы позволяют параллельно обновлять множество p-битов, что ускоряет поиск решений.
Исследователи сравнили DT-SQA и APT с физическим квантовым отжигом D-Wave. DT-SQA при тысячах параллельных копий достигает сопоставимых результатов. APT с кластеризацией работает ещё эффективнее: в долгосрочной перспективе алгоритм находит решения лучше, чем DT-SQA, независимо от размера задачи.
Квантовые компьютеры работают при температурах близких к абсолютному нулю, требуют сложной криогенной техники и борьбы с декогеренцией. Вероятностные компьютеры лишены этих проблем, энергопотребление у них ниже, а масштабирование проще.
Среди авторов статьи — польский физик Марек М. Рамс из Института теоретической физики Ягеллонского университета, который отвечал за раздел по физике спиновых стекол. Это подтверждает участие польских исследователей в глобальных исследованиях квантового преимущества.
Источник: naukawpolsce.pl
Оптимизационные задачи встречаются повсюду: планирование маршрутов доставки, составление графиков на заводах, распределение электроэнергии в сетях. Число возможных решений растёт так быстро, что обычный компьютер может находить лишь посредственные варианты, а найти лучший крайне сложно.
Квантовые вычисления обещали справляться с такими задачами эффективнее. Для проверки используют модели Изинга — системы из маленьких «магнитных иголок», каждая из которых может быть направлена вверх или вниз. Иглы взаимодействуют друг с другом: одни стремятся выровняться параллельно, другие — наоборот. Поиск наименьшей энергии системы эквивалентен поиску оптимального решения задачи «да/нет» с множеством взаимозависимых факторов.
В статье Nature Communications исследователи решали особенно сложную задачу — трёхмерное спиновое стекло с случайными взаимодействиями. На этом примере квантовый компьютер D-Wave продемонстрировал масштабирование лучше некоторых классических алгоритмов.
Квантовый отжиг сравнивают с охлаждением металла: система изначально в простом состоянии постепенно переходит к низкоэнергетическому, оптимальному решению. Авторы статьи смоделировали квантовый отжиг на обычном компьютере с помощью метода дискретного смоделированного квантового отжига (DT-SQA). Вместо одной решётки магнитов создаются тысячи копий, имитирующих квантовые эффекты.
Другой подход — адаптивное параллельное закаливание (APT). Несколько копий задачи работают при разных «температурах»: одни исследуют детали, другие хаотично перебирают варианты. Копии периодически обмениваются конфигурациями. Алгоритм дополнен кластерными перемещениями: целые группы «игл» инвертируются за один шаг, что помогает быстрее находить лучшие решения.
Настоящий эффект проявляется при использовании специализированных вероятностных компьютеров (p-компьютеров). В них биты ведут себя случайно, как подброшенная монета, и естественно имитируют поведение модели Изинга. Сети p-битов автоматически стремятся к оптимальным решениям.
Такие машины создают на CPU, GPU, FPGA и комбинированных системах с наномагнитами. Все платформы позволяют параллельно обновлять множество p-битов, что ускоряет поиск решений.
Исследователи сравнили DT-SQA и APT с физическим квантовым отжигом D-Wave. DT-SQA при тысячах параллельных копий достигает сопоставимых результатов. APT с кластеризацией работает ещё эффективнее: в долгосрочной перспективе алгоритм находит решения лучше, чем DT-SQA, независимо от размера задачи.
Квантовые компьютеры работают при температурах близких к абсолютному нулю, требуют сложной криогенной техники и борьбы с декогеренцией. Вероятностные компьютеры лишены этих проблем, энергопотребление у них ниже, а масштабирование проще.
Среди авторов статьи — польский физик Марек М. Рамс из Института теоретической физики Ягеллонского университета, который отвечал за раздел по физике спиновых стекол. Это подтверждает участие польских исследователей в глобальных исследованиях квантового преимущества.
Источник: naukawpolsce.pl
