Speaker
Description
Современные квантовые вычислители представляют из себя NISQ-устройства (Noisy Intermediate-Scale Quantum devices), и поэтому на них могут быть реализованы лишь алгоритмы, устойчивые к вычислительным ошибкам, а, следовательно, и физическим шумам, наиболее интересными из которых с практической точки зрения являются алгоритмы оптимизации. Несмотря на то, что в долгосрочной перспективе более удобными для реализации универсальных масштабных FTQC (Fault-Tolerant Quantum Computers) представляются сегодня вычислители вентильного типа (GTQC - Gate-Type Quantum Computers), в кратко и среднесрочной перспективах более привлекательными для решения практических задач оптимизации выглядит другой тип квантовых компьютеров – адиабатические квантовые компьютеры, или, точнее, их текущий вариант реализации, называемый квази-адиабатическими квантовыми отжигателями, в настоящее время существенно опережающими по количеству кубитов квантовые компьютеры вентильного типа.
Дополнительным преимуществом адиабатических вычислений является и то, что помимо собственно квантовых аннилеров (например, Diraq [1]) на сегодняшний день имеются достаточно мощные гибридные (например, D-Wave [2]) и цифровые (например, Toshiba [3] и Fujitcy [4]) отжигатели – специализированные программно-аппаратные комплексы, эмулирующие квантовый отжиг и предназначенные для решения задач оптимизации, а также программные эмуляторы квантового отжига.
Данные устройства и программы предназначены для решения лишь одного класса задач – задач QUBO (Quadratic Unconstrained Binary Optimization), т.е. задачи нахождения глобального минимума квадратичной формы
Q(q(1), q(2), …, q(N)) = α(0,0)+Σ_i,j{α(i,j)q(i)q(j)},
где q(1), q(2), …, q(N) – бинарные переменные, которые могут принимать значения 0 или 1, а α(i,j) – действительные коэффициенты связи, кодирующие условие задачи. Однако к задачам QUBO могут быть сведены многие задачи оптимизации и, кроме того, существуют стандартные базовые методы, позволяющие сделать это.
В научной литературе рассматривается возможность применения квантового отжига к решению ряда задач оптимизации, которые условно можно разделить по трем основным направлениям практического и научно-практического использования:
• оптимальное управление и задачи дискретной оптимизации в экономике (логистика, маршрутизация, сценарное планирование, оптимальное управления портфелем и т.п.) [5];
• параметризация моделей сложных систем различной природы (материаловедение [6], геофизика [7], метеорология и пр.);
• обучение систем AI/ML.
Однако применение данного инструментария к задачам параметризации моделей, задаваемых сложными функциями с большим количеством переменных, сталкивается с существенными трудностями. С одной стороны, применение стандартных базовых методов сведения задач оптимизации к задачам QUBO сопровождается при масштабировании задачи нелинейным ростом количества необходимых дополнительных бинарных переменных. С другой стороны, во-первых, имеющиеся вычислительные системы имеют ограничения как по количеству бинарных переменных q(i), так и по количеству ненулевых коэффициентов связи α(i,j). Во-вторых, при масштабировании задачи качество получаемых решений достаточно быстро падает, а время расчета в гибридных и цифровых отжигателях нелинейно растет.
В свете сказанного актуальной представляется задача разработки методов сведения задач многопараметрической оптимизации сложных функций к задачам QUBO с наименьших количеством бинарных переменных. В докладе представлен как краткий обзор стандартных базовых методов сведения задач оптимизации к задачам QUBO, так и недавно разработанный в группе прикладных квантовых алгоритмов лаборатории «Квантовой инженерии света» ЮУрГУ метод, дающий существенно меньший темп роста количества бинарных переменных при масштабировании задачи. Идея метода состоит в использовании разложения сложной оптимизируемой функции в ряд Тейлора, что позволяет декомпозировать исходную задачу оптимизации на несколько последовательных подзадач, часть из которых решается методами ML, а часть достаточно просто сводится к задачам QUBO существенно меньшего размера, чем это было бы при использовании стандартных базовых методов сведения к задачам QUBO. Метод разработан на примере одной из важных задач вычислительного материаловедения – задачи параметризации потенциалов межмолекулярного взаимодействия, однако, как представляется, применим к достаточно широкому кругу задач оптимизации сложных функций от большого количества переменных.
Список литературы:
[1] https://diraq.com/
[2] https://www.dwavesys.com/
[3] https://www.global.toshiba/ww/products-solutions/ai-iot/sbm.html
[4] https://www.fujitsu.com/global/services/business-services/digital-annealer/
[5] Sheir Yarkoni, Elena Raponi, Thomas Bäck, Sebastian Schmitt, 2022, «Quantum Annealing for Industry Applications: Introduction and Review», https://doi.org/10.1088/1361-6633/ac8c54
[6] Nikolay V. Maletin et al., 2023, «On the possibility of using quantum annealers to solve problems of parametrization of intermolecular interaction potentials», Laser Physics Letters, 20 115205, DOI 10.1088/1612-202X/acfd8e
[7] Н.В. Малетин, 2023, «О возможности решения масштабных одномерных задач инверсии сейсмических данных на современных квантовых отжигателях», Геофизика № 2-2023, стр. 102, DOI 10.34926/geo.2023.59.58.012
