Вычислительное масштабирование квантовых и классических алгоритмов Монте-Карло

Штат$\rho$для квантово-механического гамильтониана$\hat{H}$при температуре$T = \frac{1}{k_B\beta}$является:

• $\frac{e^{-\beta \hat{H}}}{\rm{Tr}\left(e^{-\beta \hat{H}}\right)}$для канонического ансамбля ,
• $e^{-\beta \left(\hat{H}-\sum_i\mu_i\hat{N}_i-\Omega\right)}$для грандиозного канонического ансамбля с грандиозным потенциалом $\Omega$, а для частиц типа$i$: числовые операторы $\hat{N_i}$и химические потенциалы $\mu_i$.

Итак, давайте рассмотрим экспоненциальную стоимость матрицы (то, что вы называете «точной диагонализацией»). Это очень активное поле исследований даже сегодня. Алгоритм, который использует MATLAB R2016b, взят из диссертации 2010 года, а в 2016 году появилось как минимум 3 новых алгоритма ( Ruiz et al . 2016 , Grebrimedhin et al. 2016 , Guttel et al. , 2016 ). Выбор алгоритма и стоимость этого алгоритма зависят от свойств$H$и от того, насколько точно вы стремитесь получить ответ, но$15n^3$Операции с плавающей запятой (FLOP) были даны здесь как грубая оценка , где$n$- размерность матрицы, которая для гамильтониана равна$M^2$где$M$число уровней, включенных в вашу квантовую систему.

• $M=2$для двухуровневой системы, такой как спин электрона,
• $M=39$для колебательных уровней основного электронного состояния$^{6,6}$Ли$_2$,
• $M=2^Q$для$Q$кубиты или$Q$частицы со спином 1/2,
• $M$счетно бесконечно велико для квантового гармонического осциллятора,
• $M$несчетно бесконечно велико для системы с непрерывными переменными, такой как позиция$\hat{x}$.

Таким образом, грубая оценка стоимости детерминированного алгоритма равна$15M^6$FLOPs для$M$-уровневая система, в чем вы правы, является экспоненциальной по отношению к числу частиц со спином 1/2.

Что касается методов Монте-Карло, вы должны быть более конкретными в отношении того, что вам нужно. Количество макроитераций, необходимых для получения вашего ответа с точностью до$\pm\epsilon$является$\mathcal{O}\left(\sqrt{1/\epsilon}\right)$и каждая из этих макроитераций будет зависеть от$M$, но чтобы дать вам количество FLOP, вы должны быть более конкретными в своем вопросе.