Гамильтонианское моделирование

Более широкое освещение этой темы см. в разделе «Квантовый симулятор» .

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

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

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

Техники

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

Основная статья: Прореживание блоков с развитием во времени

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

Если гамильтониан представлен в виде разреженной матрицы , алгоритм раскраски распределенных ребер можно использовать для разложения его в сумму членов; который затем можно смоделировать с помощью алгоритма Троттера – Сузуки.

Серия Тейлора

$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}}+\cdots$ разложением в ряд Тейлора . Это говорит о том, что в ходе эволюции квантового состояния гамильтониан применяется к системе снова и снова с различным числом повторений. Первый член представляет собой единичную матрицу, поэтому система не меняется при его применении, но во втором члене гамильтониан применяется один раз. Для практических реализаций ряд приходится усекать. $\left(\sum _{n\mathop {=} 0}^{N}{\frac {(-iHt)^{n}}{n!}}\right)$, где чем больше $N$, тем точнее моделирование. Это усеченное разложение затем реализуется с помощью метода линейной комбинации унитарных единиц (LCU) для гамильтонового моделирования. А именно, разлагается гамильтониан $H=\sum _{\ell =1}^{L}\alpha _{\ell }H_{\ell }$ такой, что каждый $H_{\ell }$ унитарна (например, операторы Паули всегда обеспечивают такой базис), и поэтому каждый $H^{n}=\sum _{\ell _{1},\ldots ,\ell _{n}=1}^{L}\alpha _{\ell _{1}}\cdots \alpha _{\ell _{n}}H_{\ell _{1}}\cdots H_{\ell _{n}}$ также является линейной комбинацией унитарных единиц.

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

Основная статья: Квантовая прогулка

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

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

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

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

Сложность

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

Техника	Сложность ворот	Сложность запроса
Формула продукта 1-го заказа	$O\left({\frac {t^{2}}{\epsilon }}\right)$	$O\left(d^{3}t\left({\frac {dt}{\epsilon }}\right)^{{\frac {1}{2}}k}\right)$
Серия Тейлора	$O\left({\frac {t\log ^{2}\left({\frac {t}{\epsilon }}\right)}{\log \log {\frac {t}{\epsilon }}}}\right)$	$O\left({\frac {d^{2}||H||_{\rm {max}}\log {\frac {d^{2}||H||_{max}}{\epsilon }}}{\log \log {\frac {d^{2}||H||_{\rm {max}}}{\epsilon }}}}\right)$
Квантовая прогулка	$O\left({\frac {t}{\sqrt {\epsilon }}}\right)$	$O\left(d||H||_{\rm {max}}{\frac {t}{\sqrt {\epsilon }}}\right)$
Квантовая обработка сигналов	$O\left(t+\log {\frac {1}{\epsilon }}\right)$	$O\left(td||H||_{\rm {max}}+{\frac {\log {\frac {1}{\epsilon }}}{\log \log {\frac {1}{\epsilon }}}}\right)$

Где $||H||_{\rm {max}}$ это самая крупная запись $H$.

См. также

• Столько же, сколько притворщик