Гамильтоново моделирование - Hamiltonian simulation

Гамильтоново моделирование (также называемый квантовое моделирование) проблема в квантовая информатика который пытается найти вычислительная сложность и квантовые алгоритмы необходимы для моделирования квантовых систем. Гамильтоново моделирование - это проблема, которая требует алгоритмов, которые эффективно реализуют эволюцию квантового состояния. Проблема гамильтонова моделирования была предложена Ричард Фейнман в 1982 году, где он предложил квантовый компьютер в качестве возможного решения, поскольку моделирование общих гамильтонианов, кажется, растет экспоненциально по отношению к размеру системы. ^[1]

Постановка задачи

В задаче гамильтонова моделирования при заданном Гамильтониан ${ displaystyle H}$ (${ Displaystyle 2 ^ {п} раз 2 ^ {п}}$ эрмитова матрица действующий на ${ displaystyle n}$ кубиты), время ${ displaystyle t}$ и максимальная ошибка моделирования ${ displaystyle epsilon}$, цель - найти алгоритм, приближающий ${ displaystyle U}$ такой, что ${ displaystyle || U-e ^ {- iHt} || leq epsilon}$, куда ${ displaystyle e ^ {- iHt}}$ это идеальная эволюция и ${ displaystyle || cdot ||}$ это спектральная норма.^[2]Частным случаем проблемы гамильтонова моделирования является проблема локального гамильтонова моделирования. Это когда ${ displaystyle H}$ является k-локальным гамильтонианом на ${ displaystyle n}$ кубиты, где ${ Displaystyle H = сумма _ {j mathop {=} 1} ^ {m} H_ {j}}$ и ${ displaystyle H_ {j}}$ действует нетривиально на самое большее ${ displaystyle k}$ кубиты вместо ${ displaystyle n}$ кубиты. ^[3] Проблема моделирования локального гамильтониана важна, потому что большинство гамильтонианов, встречающихся в природе, k-локальны. ^[3]

Методы

Формулы продукта

Формулы произведения, также известные как формулы Троттера или разложения Троттера-Судзуки, моделируют сумму членов гамильтониана, моделируя каждое из них отдельно для небольшого временного интервала. ^[4] Если ${ displaystyle H = A + B + C}$, тогда ${ Displaystyle U = е ^ {- я (A + B + C) t} = (e ^ {- iAt / r} e ^ {- iBt / r} e ^ {- iCt / r}) ^ {r} }$ для большого ${ displaystyle r}$; куда ${ displaystyle r}$ - количество временных шагов для моделирования. Большой ${ displaystyle r}$, тем точнее моделирование.

Если гамильтониан представить в виде Разреженная матрица, распределенные окраска края алгоритм можно использовать для разложения его на сумму членов; который затем можно смоделировать с помощью алгоритма Троттера-Судзуки. ^[5]

Серия Тейлор

${ displaystyle e ^ {- iHt} = sum _ {n mathop {=} 0} ^ { infty} { frac {(-iHt) ^ {n}} {n!}} = I-iHt- { frac {H ^ {2} t ^ {2}} {2}} + { frac {iH ^ {3} t ^ {3}} {6}} + ...}$ посредством Серия Тейлор расширение. ^[6] Это говорит о том, что во время эволюции квантового состояния гамильтониан снова и снова применяется к системе с различным числом повторений. Первый член - это единичная матрица, поэтому сначала система не меняется, но во втором члене гамильтониан применяется один раз. Для практических применений серию необходимо обрезать (${ displaystyle sum _ {п mathop {=} 0} ^ {N} { frac {(-iHt) ^ {n}} {n!}}}$) где чем больше ${ displaystyle N}$, тем точнее моделирование. ^[7]

Квантовая прогулка

В квантовом блуждании реализована унитарная операция, спектр которой связан с гамильтонианом in, тогда Алгоритм квантовой оценки фазы используется для настройки собственных значений. Это делает ненужным разложение гамильтониана на сумму членов, как в методах Троттера-Судзуки. ^[6]

Квантовая обработка сигналов

Алгоритм обработки квантового сигнала работает путем преобразования собственных значений гамильтониана в вспомогательный кубит, преобразования собственных значений с помощью вращения одного кубита и, наконец, проецирования вспомогательного кубита. ^[8] Было доказано, что он является оптимальным по сложности запроса, когда речь идет о гамильтоновом моделировании. ^[8]

Сложность

Таблица сложности гамильтоновых алгоритмов моделирования, упомянутых выше. Гамильтоново моделирование можно изучать двумя способами. Это зависит от того, как задан гамильтониан. Если он указан явно, то сложность шлюза имеет большее значение, чем сложность запроса. Если гамильтониан описать как оракул (черный ящик ), то количество запросов к оракулу более важно, чем количество вентилей схемы. В следующей таблице показаны ворота и сложность запросов ранее упомянутых методов.

Техника	Сложность ворот	Сложность запроса
Формула продукта 1-го порядка	${ displaystyle O left ({ frac {t ^ {2}} { epsilon}} right)}$ [7]	${ displaystyle O left (d ^ {3} t left ({ frac {dt} { epsilon}} right) ^ {{ frac {1} {2}} k} right)}$ [9]
Серия Тейлор	${ displaystyle O left ({ frac {t log ^ {2} left ({ frac {t} { epsilon}} right)} { log log { frac {t} { epsilon }}}}верно)}$ [7]	${ displaystyle O left ({ frac {d ^ {2} || H || _ {max} log { frac {d ^ {2}} || H || _ {max}} { epsilon}) }} { log log { frac {d ^ {2} || H || _ {max}} { epsilon}}}} right)}$ [6]
Квантовая прогулка	${ displaystyle O left ({ frac {t} { sqrt {e}}} right)}$ [7]	${ displaystyle O left (d || H || _ {max} { frac {t} { sqrt { epsilon}}} right)}$ [5]
Квантовая обработка сигналов	${ Displaystyle О влево (т + журнал { гидроразрыва {1} { epsilon}} вправо)}$ [7]	${ displaystyle O left (td || H || _ {max} + { frac { log { frac {1} { epsilon}}}} { log log { frac {1} { epsilon }}}}верно)}$ [8]

Где ${ displaystyle || H_ {max} ||}$ это самая большая запись ${ displaystyle H}$.

Рекомендации