Введение 2
2 Задача логистики 4
2.1 Маршрутная формулировка 4
2.2 Последовательная формулировка 6
2.3 Перевод формулировок задачи логистики к задачам класса квадратичной
бинарной оптимизации без ограничений 7
2.4 Quantum Approximate Optimization Algorithm 9
3 Расчет энергии ионизации 10
3.1 Основной формализм 10
3.2 Variational Quantum Eigensolver 12
3.3 Алгоритм расчета энергии ионизации 13
4 Параметризация состояния 15
5 Вычисление градиентов на квантовом компьютере 16
6 Результаты 18
6.1 Задача логистики с временными окнами 18
6.2 Задача логистики без временных окон 19
6.3 Результаты вычисления энергии ионизации 22
7 Выводы 24
7.1 Задача логистики буровых установок 24
7.2 Расчет энергии ионизации
Список литературы
На сегодняшний день квантовые вычисления являются быстро развивающейся обла¬стью исследований. Квантовый компьютер - это вычислительное устройство, которое использует эффекты квантовой механики (квантовая суперпозиция, квантовая запутанность) для реализации вычислений. В ряде случаев квантовые расчеты имеют экспоненциальное преимущество перед классическими [1].
Единицей информации квантового компьютера является квантовый бит (кубит), который описывается вектором в гильбертовом пространстве и может быть представлен в виде суперпозиции |ф) = а |0) + в |1), где {|0) , 11)} - это некоторый базис и |а|2+ |в|2= 1. Состояние кубита преобразуется с помощью квантовых гейтов, которые одновременно изменяют всю суперпозицию, обеспечивая ограниченный измерениями параллелизм. Алгоритмы на квантовых компьютерах реализуются с помощью квантовых цепей, которые являются последовательностью квантовых гейтов. Кубит находится в суперпозиции на протяжении всего процесса вычислений, однако после измерения переходит в состояние |0) с вероятностью |а|2или состояние |1) с вероятностью @|2. Система из nкубитов может быть представлена в виде суперпозиции 2"базисных векторов.
Манин [2] и Фейнман [3] впервые предложили использовать квантовый компьютер для расчета квантовых систем. Основная мысль заключалась в том, чтобы построить управляемую квантовую систему и использовать ее для расчета многочастичных квантовых систем. Возможности для расчета таких систем на классических компьютерах ограничены из-за экспоненциального роста сложности волновой функции с увеличением числа частиц. При этом такие расчеты необходимы для теоретического описания электронной структуры атомов и молекул. Знание электронной структуры в свою очередь необходимо для понимания свойств атомов и химических соединений.
В ходе развития квантовых вычислений были найдены новые применения возможностей квантового компьютера. Так, в 1997 году Питер Шор предложил алгоритм факторизации чисел на простые множители [4]. Также со временем все большее внимание стали привлекать задачи комбинаторной оптимизации [5], решение которых может быть эффективно улучшено с помощью квантового компьютера [6]. Целью комбинаторных задач явля¬ется поиск оптимального решения в рамках фиксированного набора ограничений. Одним из их приложений является задача логистики, которая представляет собой минимизацию расстояния при перемещении по заданной карте. В данной задаче существует множество подходов к решению (формулировок), влияющих на число переменных, вид ограничений и точность получаемых результатов.
На сегодняшний день, несмотря на значительный прогресс в разработке квантовых вычислительных устройств их возможности ограничены. Это происходит из-за того, что они подвержены шумам вследствие декогеренции и неточности выполнения гейтов. Одним из наиболее перспективных подходов к решению задач на таких устройствах являются вариационные квантовые алгоритмы (VQA), использующие классический компьютер на ряду с квантовым. Считается, что VQA устойчивы к шумам различного происхождения за счет своей гибридной природы. Однако они являются эвристическими, в силу чего не ясно, смогут ли VQA превзойти результаты решения задач на классическом компьютере.
Среди вариационных подходов можно выделить два: Variational Quantum Eigensolver (VQE) [7]и Quantum Approximate Optimization Algorithm (QAOA) [8]. Выбор алгоритма определяется задачей, а их главное отличие заключается в подготовке начального состояния (анзаца). Гибридный алгоритм VQE используется для нахождения собственных значений гамильтониана задачи. Результаты реализации Variational Quantum Eigensolver зависят от сложности квантовых цепей и классической оптимизационной процедуры. То есть, выбор оптимизатора и вариационного анзаца, используемого для параметризации начального состояния, влияет на точность результатов алгоритма VQE. Quantum Approximate Optimization Algorithm полностью наследует структуру Variational Quantum Eigensolver. Однако в отличие от VQE, анзац которого мы можем менять, параметризация состояния в QAOA фиксирована и содержится в структуре алгоритма.
В расчетах квантовой химии зачастую рассматриваются задачи не вычисления энергии основного состояния, а расчет энергии ионизации молекулярной системы. Последовательная оценка энергий Nи N — 1 частиц с помощью VQE и нахождение их разности может привести к накоплению ошибок квантового компьютера. Чтобы повысить точность расчетов, предлагается вычислять энергию ионизации сразу с помощью специально разработанного алгоритма. Он так же, как и предыдущие, является гибридным и включает в себя классическую оптимизационную процедуру, однако возвращает разность двух средних значений гамильтониана.
В данной работе задача логистики буровых установок описана в разделе 2. Теоретическим методам, используемым для расчета энергии ионизации посвящен раздел 3.3. Описание вариационных квантовых алгоритмов VQE и QAOA содержится в разделах 3.2 и 2.4 соответственно. Пункт 4 включает в себя подробное описание анзаца, используемого при реализации VQE. Метод расчета градиентов, необходимых для реализации оптимизационных процедур, представлен в разделе 5. Параграф 6 содержит результаты расчетов.
