Расчеты модели Изинга и электронной структуры атомов и молекул с помощью квантовых алгоритмов
|
1 Введение 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 Расчет энергии ионизации 24
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 Расчет энергии ионизации 24
На сегодняшний день квантовые вычисления являются быстро развивающейся областью исследований. Квантовый компьютер - это вычислительное устройство, которое использует эффекты квантовой механики (квантовая суперпозиция, квантовая запутанность) для реализации вычислений. В ряде случаев квантовые расчеты имеют экспоненциальное преимущество перед классическими.
Единицей информации квантового компьютера является квантовый бит (кубит), который описывается вектором в гильбертовом пространстве и может быть представлен в виде суперпозиции |ф) = а |0) + в |1), где {|0) , 11)} - это некоторый базис и |а|2 + |в|2 = 1. Состояние кубита преобразуется с помощью квантовых гейтов, которые одновременно изменяют всю суперпозицию, обеспечивая ограниченный измерениями параллелизм. Алгоритмы на квантовых компьютерах реализуются с помощью квантовых цепей, которые являются последовательностью квантовых гейтов. Кубит находится в суперпозиции на протяжении всего процесса вычислений, однако после измерения переходит в состояние |0) с вероятностью |а|2 или состояние |1) с вероятностью @|2. Система из n кубитов может быть представлена в виде суперпозиции 2" базисных векторов.
Манин и Фейнман впервые предложили использовать квантовый компьютер для расчета квантовых систем. Основная мысль заключалась в том, чтобы построить управляемую квантовую систему и использовать ее для расчета многочастичных квантовых систем. Возможности для расчета таких систем на классических компьютерах ограничены из-за экспоненциального роста сложности волновой функции с увеличением числа частиц. При этом такие расчеты необходимы для теоретического описания электронной структуры атомов и молекул. Знание электронной структуры в свою очередь необходимо для понимания свойств атомов и химических соединений.
В ходе развития квантовых вычислений были найдены новые применения возможностей квантового компьютера. Так, в 1997 году Питер Шор предложил алгоритм факторизации чисел на простые множители . Также со временем все большее внимание стали привлекать задачи комбинаторной оптимизации , решение которых может быть эффективно улучшено с помощью квантового компьютера. Целью комбинаторных задач является поиск оптимального решения в рамках фиксированного набора ограничений. Одним из их приложений является задача логистики, которая представляет собой минимизацию расстояния при перемещении по заданной карте. В данной задаче существует множество подходов к решению (формулировок), влияющих на число переменных, вид ограничений и точность получаемых результатов.
На сегодняшний день, несмотря на значительный прогресс в разработке квантовых вычислительных устройств их возможности ограничены. Это происходит из-за того, что они подвержены шумам вследствие декогеренции и неточности выполнения гейтов. Одним из наиболее перспективных подходов к решению задач на таких устройствах являются вариационные квантовые алгоритмы (VQA), использующие классический компьютер на ряду с квантовым. Считается, что VQA устойчивы к шумам различного происхождения за счет своей гибридной природы. Однако они являются эвристическими, в силу чего не ясно, смогут ли VQA превзойти результаты решения задач на классическом компьютере.
Среди вариационных подходов можно выделить два: Variational Quantum Eigensolver (VQE) и Quantum Approximate Optimization Algorithm (QAOA). Выбор алгоритма определяется задачей, а их главное отличие заключается в подготовке начального состояния (анзаца). Гибридный алгоритм 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 содержит результаты расчетов.
Единицей информации квантового компьютера является квантовый бит (кубит), который описывается вектором в гильбертовом пространстве и может быть представлен в виде суперпозиции |ф) = а |0) + в |1), где {|0) , 11)} - это некоторый базис и |а|2 + |в|2 = 1. Состояние кубита преобразуется с помощью квантовых гейтов, которые одновременно изменяют всю суперпозицию, обеспечивая ограниченный измерениями параллелизм. Алгоритмы на квантовых компьютерах реализуются с помощью квантовых цепей, которые являются последовательностью квантовых гейтов. Кубит находится в суперпозиции на протяжении всего процесса вычислений, однако после измерения переходит в состояние |0) с вероятностью |а|2 или состояние |1) с вероятностью @|2. Система из n кубитов может быть представлена в виде суперпозиции 2" базисных векторов.
Манин и Фейнман впервые предложили использовать квантовый компьютер для расчета квантовых систем. Основная мысль заключалась в том, чтобы построить управляемую квантовую систему и использовать ее для расчета многочастичных квантовых систем. Возможности для расчета таких систем на классических компьютерах ограничены из-за экспоненциального роста сложности волновой функции с увеличением числа частиц. При этом такие расчеты необходимы для теоретического описания электронной структуры атомов и молекул. Знание электронной структуры в свою очередь необходимо для понимания свойств атомов и химических соединений.
В ходе развития квантовых вычислений были найдены новые применения возможностей квантового компьютера. Так, в 1997 году Питер Шор предложил алгоритм факторизации чисел на простые множители . Также со временем все большее внимание стали привлекать задачи комбинаторной оптимизации , решение которых может быть эффективно улучшено с помощью квантового компьютера. Целью комбинаторных задач является поиск оптимального решения в рамках фиксированного набора ограничений. Одним из их приложений является задача логистики, которая представляет собой минимизацию расстояния при перемещении по заданной карте. В данной задаче существует множество подходов к решению (формулировок), влияющих на число переменных, вид ограничений и точность получаемых результатов.
На сегодняшний день, несмотря на значительный прогресс в разработке квантовых вычислительных устройств их возможности ограничены. Это происходит из-за того, что они подвержены шумам вследствие декогеренции и неточности выполнения гейтов. Одним из наиболее перспективных подходов к решению задач на таких устройствах являются вариационные квантовые алгоритмы (VQA), использующие классический компьютер на ряду с квантовым. Считается, что VQA устойчивы к шумам различного происхождения за счет своей гибридной природы. Однако они являются эвристическими, в силу чего не ясно, смогут ли VQA превзойти результаты решения задач на классическом компьютере.
Среди вариационных подходов можно выделить два: Variational Quantum Eigensolver (VQE) и Quantum Approximate Optimization Algorithm (QAOA). Выбор алгоритма определяется задачей, а их главное отличие заключается в подготовке начального состояния (анзаца). Гибридный алгоритм 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 содержит результаты расчетов.
Результаты тестирования показали, что квантовые алгоритмы позволяют получать допустимые решения с удовлетворительной точностью. Эти решения обычно имеют значение целевых функций, порядка значения, полученного с помощью жадного алгоритма. Это может быть связано с низкой комбинаторной сложностью задач, либо, что более вероятно, с тем, что метод генерации данных идеально подходит для решения жадным алгоритмом. Проверка данной гипотезы подразумевает полный перебор всех решений и даже на задачах малой размерности. Ее реализация не представляется возможной за разумное время.
В отдельных случаях квантовые и квантово-вдохновленные алгоритмы показывали решение лучше классических. Например, в задаче логистики с временными окнами OR-Tools ни разу не нашел допустимое решение. В случае с OR-Tools было замечено, что он работает существенно лучше, когда ему предлагается какое-либо первоначальное решение (например, из жадного алгоритма). Также в задаче логистики без временных окон алгоритмы QAOA, симуляции отжига и симулятор когерентной машины Изинга зачастую давали решения более оптимальные, чем алгоритм Or-tools.
Стоит отметить, что решение существенно зависит используемого солвера. Например, облачные решения симуляции отжига для задач QUBO с вероятностью 100% выдавали допустимое решение, однако оно всегда было хуже жадного алгоритма. С другой стороны, реализация симуляции отжига QUBO из пакета qubovert, которая использовалась во всех локальных тестах, выдает куда более хаотические результаты, и вероятность нахождения допустимого решения порядка 2%. Также, необходимо отметить, что такую метрику как "вероятность допустимого решения” довольно сложно определить для разных солве- ров, поскольку все квантово-вдохновленные солверы имеют разные параметры и критерии остановки. Например, в симуляции отжига в качестве критериев используются
• количество отжигов,
• время одного отжига,
а в алгоритме Or-tools критериями являются
• стартовый алгоритм,
• время работы алгоритма,
что сложно сравнимо, например, с тем же жадным алгоритмом.
...
В отдельных случаях квантовые и квантово-вдохновленные алгоритмы показывали решение лучше классических. Например, в задаче логистики с временными окнами OR-Tools ни разу не нашел допустимое решение. В случае с OR-Tools было замечено, что он работает существенно лучше, когда ему предлагается какое-либо первоначальное решение (например, из жадного алгоритма). Также в задаче логистики без временных окон алгоритмы QAOA, симуляции отжига и симулятор когерентной машины Изинга зачастую давали решения более оптимальные, чем алгоритм Or-tools.
Стоит отметить, что решение существенно зависит используемого солвера. Например, облачные решения симуляции отжига для задач QUBO с вероятностью 100% выдавали допустимое решение, однако оно всегда было хуже жадного алгоритма. С другой стороны, реализация симуляции отжига QUBO из пакета qubovert, которая использовалась во всех локальных тестах, выдает куда более хаотические результаты, и вероятность нахождения допустимого решения порядка 2%. Также, необходимо отметить, что такую метрику как "вероятность допустимого решения” довольно сложно определить для разных солве- ров, поскольку все квантово-вдохновленные солверы имеют разные параметры и критерии остановки. Например, в симуляции отжига в качестве критериев используются
• количество отжигов,
• время одного отжига,
а в алгоритме Or-tools критериями являются
• стартовый алгоритм,
• время работы алгоритма,
что сложно сравнимо, например, с тем же жадным алгоритмом.
...
Подобные работы
- Расчеты модели Изинга и электронной структуры атомов и молекул с помощью квантовых алгоритмов
Магистерская диссертация, физика. Язык работы: Русский. Цена: 4875 р. Год сдачи: 2023