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

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

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

В задаче гамильтонова моделирования при заданном Гамильтониан ${\displaystyle H}$ (${\displaystyle 2^{n}\times 2^{n}}$ эрмитова матрица действующий на ${\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=\sum _{j\mathop {=} 1}^{m}H_{j}}$ и ${\displaystyle H_{j}}$ действует нетривиально на самое большее ${\displaystyle k}$ кубиты вместо ${\displaystyle n}$ кубиты. ^[3] Проблема моделирования локального гамильтониана важна, потому что большинство гамильтонианов, встречающихся в природе, k-локальны. ^[3]

Методы

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

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

Формулы произведения, также известные как формулы Троттера или разложения Троттера-Судзуки, моделируют сумму членов гамильтониана, моделируя каждое из них отдельно для небольшого временного интервала. ^[4] Если ${\displaystyle H=A+B+C}$, тогда ${\displaystyle U=e^{-i(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 _{n\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 }}}}\right)}$ [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 O\left(t+\log {\frac {1}{\epsilon }}\right)}$ [7]	${\displaystyle O\left(td||H||_{max}+{\frac {\log {\frac {1}{\epsilon }}}{\log \log {\frac {1}{\epsilon }}}}\right)}$ [8]

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

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

1. Ричард П. Фейнман (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики. 21 (6): 467–488. Bibcode:1982IJTP ... 21..467F. Дои:10.1007 / BF02650179. Получено 2019-05-04.
2. Стюарт Хэдфилд, Анаргирос Папагеоргиу (2018). «Разделяй и властвуй подход к квантовому гамильтоновому моделированию». Новый журнал физики. 20 (4): 043003. Bibcode:2018NJPh ... 20d3003H. Дои:10.1088 / 1367-2630 / aab1ef.
3. Ллойд, С. (1996). «Универсальные квантовые симуляторы». Наука. 273 (5278): 1073–8. Bibcode:1996Sci ... 273.1073L. Дои:10.1126 / science.273.5278.1073. PMID  8688088.
4. Бартел, Томас; Чжан, Икан (2019). «Оптимизированные разложения Ли-Троттера-Судзуки для двух и трех некоммутирующих членов». arXiv:1901.04974 [Quant-ph ].
5. Берри, Доминик; Чайлдс, Эндрю; Котари, Робин (2015). «Гамильтоново моделирование с почти оптимальной зависимостью от всех параметров». 56-й ежегодный симпозиум IEEE по основам компьютерных наук, 2015 г.. С. 792–809. arXiv:1501.01715. Bibcode:2015arXiv150101715B. Дои:10.1109 / FOCS.2015.54. ISBN  978-1-4673-8191-8.
6. Берри, Доминик; Чайлдс, Эндрю; Клив, Ричард; Котари, Робин; Роландо, Сомма (2015). «Моделирование гамильтоновой динамики с усеченным рядом Тейлора». Письма с физическими проверками. 114 (9): 090502. arXiv:1412.4687. Bibcode:2015ПхРвЛ.114и0502Б. Дои:10.1103 / PhysRevLett.114.090502. PMID  25793789.
7. Чайлдс, Эндрю; Маслов Дмитрий; Нам, Юнсон (2017). «К первому квантовому моделированию с квантовым ускорением». Труды Национальной академии наук. 115 (38): 9456–9461. arXiv:1711.10980. Bibcode:2017arXiv171110980C. Дои:10.1073 / pnas.1801723115. ЧВК  6156649. PMID  30190433.
8. Низкий, Гуан Хао; Чуанг, Исаак (2017). «Оптимальное гамильтоново моделирование с помощью квантовой обработки сигналов». Письма с физическими проверками. 118 (1): 010501. arXiv:1606.02685. Bibcode:2017PhRvL.118a0501L. Дои:10.1103 / PhysRevLett.118.010501. PMID  28106413.
9. Котари, Робин (8 декабря, 2017). Квантовые алгоритмы для гамильтонова моделирования: последние результаты и открытые проблемы (YouTube). США: IBM Research.