qmc-loop-algorithm-report.tex

\ifx\pdfminorversion\undefined\else\pdfminorversion=4\fi
\documentclass{beamer}
\usepackage[institute=Nat]{styles/beamerthemefau}
\usefonttheme{professionalfonts}

\usepackage[UKenglish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[style=iso]{datetime2}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}
\usepackage{physics}
\usepackage{ragged2e}
\usepackage{bbm}
\usepackage{tikz}
\usepackage[separate-uncertainty=true, binary-units]{siunitx}
%\usepackage{algpseudocode}
\graphicspath{{../figures/}}

\usepackage[backend=biber,urldate=iso,date=iso]{biblatex}
\addbibresource{references.bib}

\date{2022-12-12}
\title{Path Integral Quantum Monte Carlo}
\subtitle{Quantum and Classical Algorithms for Quantum Many-Body Systems}
\author{Stefan Gehr}
\institute[FAU]{Friedrich-Alexander Universität Erlangen-Nürnberg}

\newcommand{\die}{\vcenter{\hbox{\includegraphics[width=1em]{die.png}}}}

\begin{document}
\begin{trueplainframe}
\titlepage
\end{trueplainframe}

\begin{frame}{Outline}
	\tableofcontents
\end{frame}

\section{Classical Monte Carlo}
\subsection{Classical Ising Model}
\subsection{Markov Chain}
\subsection{Detailed Balance Condition}
\subsection{Metropolis Algorithm}
\begin{frame}{Monte Carlo Basics}
\begin{minipage}{0.48\linewidth}
	%\only<2>{
	%\visible<2>{
\begin{block}{Classical Ising Model}
	\begin{align*}
		H(\vec{\sigma}) &= - \sum_{i}\left(J\sigma_i\sigma_{i+1} + \mu \sigma_i\right) \\
		\sigma_i &\in \{-1, +1\}\qquad \vec{\sigma} = (\sigma_1, \dots, \sigma_N) \\
		Z &= \sum_{\vec{\sigma}} w_{\vec{\sigma}} = \sum_{\vec{\sigma}}e^{-\beta H(\vec{\sigma})}
	\end{align*}
\end{block}
	%}
\begin{block}{Markov Chain}
	\begin{align*}
		\vec{\sigma}_1\to \vec{\sigma}_2 \to \vec{\sigma}_3 \to \cdots
	\end{align*}
	The number of occurrences of \(\vec{\sigma}\) according to Boltzmann weight
	\[N_{\vec{\sigma}} \propto e^{-\beta H(\vec{\sigma})} =: w_{\vec{\sigma}}\]
\end{block}
\end{minipage}
\hfill
\begin{minipage}{0.48\linewidth}
\begin{block}{Exponential Configuration Space}
	\begin{align*}
		C = \{\vec{\sigma} = (\sigma_1,\dots,\sigma_N) \,|\, \sigma_i \in \{-1,+1\}\}
	\end{align*}
	Most configurations \(\vec{\sigma}_i\) are highly unlikely
	\(w_{\vec{\sigma}_i}\approx 0\) \\
	\begin{minipage}{0.3\linewidth}
	\Centering
	\begin{tikzpicture}
		\node[circle,draw,fill=lightgray,minimum size=3em] (c) at (0,0){};
		\node[circle,draw,fill=red,minimum size=0.8em] (c) at (0.1,0.4){};
	\end{tikzpicture}
	\end{minipage}
	\hfill
	\begin{minipage}{0.65\linewidth}
	{\color{lightgray} All possible configurations} \\
	{\color{red} Significant configurations}
	\end{minipage}
	% TODO Tikz circle in circle
\end{block}
\begin{block}{Detailed Balance condition}
	\begin{align*}
			w_{\vec{\sigma}}\,	p(\vec{\sigma} \to \vec{\sigma}')
		=	w_{\vec{\sigma}'}\,	p(\vec{\sigma}' \to \vec{\sigma})
	\end{align*}
	Assures configuration \(\vec{\sigma}\) is sampled with weight \(w_{\vec{\sigma}}\)
\end{block}
\begin{block}{Ergodicity}
	All configurations should be reachable after finitely many steps
\end{block}
\end{minipage}
\end{frame}
\begin{frame}{Metropolis Algorithm}
\begin{minipage}{0.45\linewidth}
\begin{block}{Split the Probability}
	\begin{align*}
		p(\vec{\sigma} \to  \vec{\sigma}') = p_{\text{prop}}(\vec{\sigma} \to  \vec{\sigma}')p_{\text{acc}}(\vec{\sigma} \to  \vec{\sigma}') \\
		\Rightarrow \frac{p_{\text{acc}}(\vec{\sigma}\to \vec{\sigma}')}{p_{\text{acc}}(\vec{\sigma}'\to \vec{\sigma})}
		= \frac{p_{\text{prop}}(\vec{\sigma}'\to \vec{\sigma})w_{\vec{\sigma}'}}{p_{\text{prop}}(\vec{\sigma}\to \vec{\sigma}')w_{\vec{\sigma}}}
	\end{align*}
	Choose e.g. \(p_{\text{prop}}(\vec{\sigma}\to \vec{\sigma}') = \frac{1}{N}\) (flip one of \(N\) sites)
	Accept the new configuration \(\vec{\sigma}'\) with probability
	\begin{align*}
		\min\left(1,\frac{p_{\text{acc}}(\vec{\sigma}\to \vec{\sigma}')}{p_{\text{acc}}(\vec{\sigma}'\to \vec{\sigma})}\right)
		= \min\left(1,e^{-\beta\, [H(\vec{\sigma}') - H(\vec{\sigma})]}\right)
	\end{align*}
\end{block}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
\visible<2->{
\begin{block}{Markov Chain}
\begin{align*}
	\visible<2->{&\vec{\sigma}_1 \to \cdots \to \vec{\sigma}_A} \\
	\visible<3->{&\vec{\sigma}_A \overset{\text{change}}{\implies} \vec{\sigma}_B} \\
	\visible<4->{
	&\die{} \begin{cases}
		\visible<4->{\le \min\left(1,\frac{p_{\text{acc}}(\vec{\sigma}_A\to \vec{\sigma}_B)}{p_{\text{acc}}(\vec{\sigma}_B\to \vec{\sigma}_A)}\right) \\
					 \implies \vec{\sigma}_1 \to \cdots \to \vec{\sigma}_A \to \vec{\sigma}_B} \\
		\visible<5->{> \min\left(1,\frac{p_{\text{acc}}(\vec{\sigma}_A\to \vec{\sigma}_j)}{p_{\text{acc}}(\vec{\sigma}_j\to \vec{\sigma}_A)}\right) \\
					 \implies \vec{\sigma}_1 \to \cdots \to \vec{\sigma}_A \to \vec{\sigma}_A}
	\end{cases}}
\end{align*}
\end{block}
}
\end{minipage}
\end{frame}
\begin{frame}{Hands-On Example}
\begin{minipage}{0.48\linewidth}
\visible<1->{
	\(N = 4, J = 1, \mu = 2, \beta = \num{0.1}\) \\
	Start with random configuration \(\vec{\sigma}_1 = \uparrow \uparrow \downarrow \uparrow = (1, 1, -1, 1)\).
}
\visible<2->{
	\begin{align*}
		H(\uparrow\uparrow\downarrow\uparrow) = -4
	\end{align*}
}
\visible<3->{
	Suggest to flip first site \(\vec{\sigma}_2 \overset{?}{=} \downarrow\uparrow\downarrow\uparrow\)
	\begin{align*}
		H(\downarrow\uparrow\downarrow\uparrow) = 4
	\end{align*}
}
\visible<4->{
	Accept with probability
	\begin{align*}
		\min\left(1, e^{-\num{0.1} \times \left[4 - (-4)\right]}\right) = e^{-\num{0.8}} \approx \num{0.45} \\
		\die{} = \num{0.63} > \num{0.45} \Rightarrow \text{decline} \Rightarrow \vec{\sigma}_1 = \vec{\sigma}_0 = \uparrow\uparrow\downarrow\uparrow
	\end{align*}
}
\visible<6->{
	Suggest to flip third site \(\vec{\sigma}_3 \overset{?}{=} \uparrow\uparrow\uparrow\uparrow\)
	\begin{align*}
		H(\uparrow\uparrow\uparrow\uparrow) = -12 \\
		\min\left(1, e^{-\num{0.1}\times \left[-12 - (-4)\right]}\right) = \min(1, e^{\num{1.6}}) = 1 \\
		\die{} \le 1 \Rightarrow \text{accept} \implies \vec{\sigma}_2 = \uparrow\uparrow\uparrow\uparrow
	\end{align*}
}
\end{minipage}
\hfill
\begin{minipage}{0.48\linewidth}
\begin{block}{Markov Chain}
\begin{align*}
	\visible<1->{&\uparrow\uparrow\downarrow\uparrow} \\
	\visible<5->{&\quad\Downarrow \\
	&\uparrow\uparrow\downarrow\uparrow \to \uparrow\uparrow\downarrow\uparrow \\
	}
	\visible<7->{&\quad\Downarrow \\
	&\uparrow\uparrow\downarrow\uparrow \to \uparrow\uparrow\downarrow\uparrow
	\to \uparrow\uparrow\uparrow\uparrow
	}
\end{align*}
\end{block}
\end{minipage}
\end{frame}
\subsection{Heat-Bath Algorithm}
\begin{frame}{Heat-Bath Algorithm}
\begin{minipage}{0.45\linewidth}
\begin{block}{Idea}
\[ p(\vec{\sigma} \to \vec{\sigma}') = p(\vec{\sigma}') \]
Always accept the new configuration
\end{block}
\begin{block}{Local Energy}
	\begin{align*}
		E_i(\sigma_i) = -J \left(\sigma_{i-1}\sigma_i + \sigma_i\sigma_{i+1}\right) -\mu\sigma_i
	\end{align*}
\end{block}
\begin{block}{Probability}
	\begin{align*}
		p_i(\uparrow) = p_i(\downarrow \,\to \, \uparrow) = p_i(\uparrow \,\to  \,\uparrow)
		= \frac{e^{-\beta E_i(\uparrow)}}{e^{-\beta E_i(\uparrow)} + e^{-\beta E_i(\downarrow)}}
	\end{align*}
\end{block}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
\begin{block}{Example}
	\(N = 4, J = 1, \mu = 2, \beta = \num{0.1}\) \\
	Start with random configuration
	\[\uparrow\uparrow\downarrow\uparrow = (1,1,-1,1)\]
	Set value at site 1
	\begin{align*}
		E_1(\uparrow) = -4 \qquad
		E_1(\downarrow) = 4 \\
		p(\uparrow) = \frac{e^{-\num{0.1} \times (-4)}}{e^{-\num{0.1}\times (-4)} + e^{-\num{0.1} \times 4}} \approx \num{0.69} \\
		\die{}
		\begin{cases}
			< \num{0.69} \implies \uparrow\uparrow\downarrow\uparrow \to \uparrow\uparrow\downarrow\uparrow \\
			\ge \num{0.69} \implies \uparrow\uparrow\downarrow\uparrow \to \downarrow\uparrow\downarrow\uparrow \\
		\end{cases}
	\end{align*}
\end{block}
\end{minipage}
\end{frame}
\begin{frame}{Observables}
\begin{minipage}{0.45\linewidth}
\begin{enumerate}
	\item<1-> \(N_{\text{eq}}\) sweeps to reach equilibrium
	\item<2-> Use equilibrated MC steps for sampling
	\item<3-> Expectation values \(\expval{O} = \frac{1}{Z}\sum_{\vec{\sigma}}w_{\vec{\sigma}}O(\vec{\sigma}) \approx \frac{1}{N_{\text{samples}}}\sum_{i=1}^{N_{\text{samples}}}O(\vec{\sigma}_i)\)
	\item<4-> Blocking analysis for correlations
	\begin{align*}
		R = \frac{m\sigma_{\overline{O}_{\text{block}}}^2}{\sigma_O^2} \qquad
		\tau_O = \frac{1}{2}(R_{\text{sat}}-1)
	\end{align*}
\end{enumerate}
\visible<5->{\includegraphics[width=0.8\linewidth]{BoFoQoOo_gausshist_polarisation.pdf}}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
	\visible<5->{\includegraphics[width=\linewidth]{BoFoQoOo_rplot.pdf}}
\end{minipage}
\end{frame}
\section{Quantum Monte Carlo}
\subsection{XXZ Quantum Spin Chain}
\subsection{Trotter Decomposition}
\begin{frame}{Quantum Monte Carlo}
\begin{minipage}{0.45\linewidth}
\begin{block}{XXZ Quantum Spin Chain}
	\begin{align*}
		H &= J_x \sum_i (S_i^xS_{i+1}^x + S_i^yS_{i+1}^y) + J_z\sum_i S_i^z S_{i+1}^z \\
		&= \frac{J_x}{2}\sum_i \left(S_i^+S_{i+1}^- + S_i^-S_{i+1}^+\right) + J_z \sum_i S_i^z S_{i+1}^z
	\end{align*}
	\[S^+ = S^x + iS^y, \quad S^- = S^x - iS^y \]
\end{block}
\begin{block}{Simple Case \(N=2\)}
	\begin{align*}
		H_{2} &= \frac{J_x}{2}(S_1^+S_2^-+S_1^-S_2^+)+J_zS_1^zS_2^z \\
		H_{2} &\frac{1}{\sqrt{2}}(\ket{\uparrow\downarrow}\pm\ket{\downarrow\uparrow})
		= \left(-\frac{J_z}{4}\pm\frac{J_x}{2}\right)\frac{1}{\sqrt{2}}(\ket{\uparrow\downarrow}\pm\ket{\downarrow\uparrow}) \\
		H_{2} &\ket{\uparrow\uparrow}
		= \frac{J_z}{4}\ket{\uparrow\uparrow} \qquad
		H_{2} \ket{\downarrow\downarrow}
		= \frac{J_z}{4}\ket{\downarrow\downarrow}
	\end{align*}
\end{block}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
\begin{block}{Possible Boltzmann Weights}
	\begin{align*}
	\vcenter{\hbox{\includegraphics{square.none.pdf}}} &\equiv \bra{\downarrow\downarrow} e^{-\Delta\tau H_{2}} \ket{\downarrow\downarrow} = e^{\Delta\tau J_z / 4}\\
	\vcenter{\hbox{\includegraphics{square.left.right.pdf}}} &\equiv \bra{\uparrow\uparrow} e^{-\Delta\tau H_{2}} \ket{\uparrow\uparrow} = e^{\Delta\tau J_z / 4} \\
	\vcenter{\hbox{\includegraphics{square.left.pdf}}} &\equiv \bra{\uparrow\downarrow} e^{-\Delta\tau H_{2}} \ket{\uparrow\downarrow} = e^{\Delta\tau J_z /4}\cosh(\Delta\tau J_x /2) \\
	\vcenter{\hbox{\includegraphics{square.right.pdf}}} &\equiv \bra{\downarrow\uparrow} e^{-\Delta\tau H_{2}} \ket{\downarrow\uparrow} = e^{\Delta\tau J_z /4}\cosh(\Delta\tau J_x /2) \\
	\vcenter{\hbox{\includegraphics{square.diag.rl.pdf}}} &\equiv \bra{\uparrow\downarrow} e^{-\Delta\tau H_{2}} \ket{\downarrow\uparrow} = -e^{\Delta\tau J_z /4}\sinh(\Delta\tau J_x /2) \\
	\vcenter{\hbox{\includegraphics{square.diag.lr.pdf}}} &\equiv \bra{\downarrow\uparrow} e^{-\Delta\tau H_{2}} \ket{\uparrow\downarrow} = -e^{\Delta\tau J_z /4}\sinh(\Delta\tau J_x /2)
	\end{align*}
\end{block}
\end{minipage}
\end{frame}
\begin{frame}{Trotter Decomposition}
\begin{minipage}{0.5\linewidth}
\begin{block}{Split Hamiltonian}
	\begin{align*}
		H &= \underbrace{\frac{J_x}{2}\sum_{\text{odd } i}(S_i^+S_{i+1}^-+S_i^-S_{i+1}^+) + J_z\sum_{\text{odd } i}S_i^zS_{i+1}^z}_{H'} \\
		  &+ \underbrace{\frac{J_x}{2}\sum_{\text{even }i}(S_i^+S_{i+1}^-+S_i^-S_{i+1}^+) + J_z\sum_{\text{even }i}S_i^zS_{i+1}^z}_{H''}
	\end{align*}
\end{block}
\begin{block}{Path Integral}
	\begin{align*}
		\tr\left[e^{-\beta H}\right]
		&= \tr\left[\left(e^{-\Delta\tau H}\right)^m\right] \\
		&= \tr\left[\left(e^{-\frac{\Delta\tau}{2}H''}e^{-\Delta\tau H'}e^{-\frac{\Delta\tau}{2}H''} + \mathcal{O}(\Delta\tau^3)\right)^m\right] \\
		&= \tr\left[\left(e^{-\Delta\tau H'}e^{-\Delta\tau H''}\right)^m\right] + \mathcal{O}(\Delta\tau^2) \\
		&= \sum_{\vec{\sigma}_1\cdots\vec{\sigma}_{2m}}\bra{\vec{\sigma}_1}e^{-\Delta\tau H'}\ketbra{\vec{\sigma}_{2m}}
		e^{-\Delta\tau H''}\ket{\vec{\sigma}_{2m-1}} \\
		&\cdots\bra{\vec{\sigma}_3}e^{-\Delta\tau H'}\ketbra{\vec{\sigma}_{2}}
		e^{-\Delta\tau H''}\ket{\vec{\sigma}_{1}}
		+ \mathcal{O}(\Delta\tau^2)
	\end{align*}
\end{block}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
	\includegraphics[width=0.8\linewidth]{worldline.pdf}
\end{minipage}
\end{frame}
\begin{frame}{Updating Schemes}
\begin{minipage}{0.48\linewidth}
\begin{block}{Local Update}
	\Centering{\includegraphics[width=0.6\linewidth]{localupdate.pdf}}
\end{block}
\begin{block}{Six Vertex Model}
	\Centering{
		\includegraphics[width=0.4\linewidth]{sixvertex-map.pdf}
		\qquad
		\includegraphics[width=0.4\linewidth]{sixvertex-worldline.pdf}
	}
\end{block}
\end{minipage}
\hfill
\begin{minipage}{0.48\linewidth}
\begin{block}{Single Loop Update}
	\includegraphics[width=0.98\linewidth]{singleloopupdate.pdf}
\end{block}
\end{minipage}
\end{frame}

{
	\nocite{*}
	\printbibliography
}

\end{document}