Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
July 2, 2018
Mick Bremner and I have just uploaded to arXiv our paper "Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs". In this paper, we study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs.
The Ising model partition function is defined as follows.
Definition 1 (Ising model partition function)
Let \(G=(V,E)\) be a graph with the weights \(\Omega=\{\omega_e\}_{e \in E}\) assigned to its edges and the weights \(\Upsilon=\{\upsilon_v\}_{v \in V}\) assigned to its vertices. Then the Ising model partition function is defined by $$\mathrm{Z}_\mathrm{Ising}(G;\Omega,\Upsilon) := \sum_{\sigma\in\{-1,+1\}^V}w_G(\sigma),$$ where $$w_G(\sigma) = \exp\left(\sum_{\{u,v\}\in E}\omega_{\{u,v\}}\sigma_u\sigma_v+\sum_{v\in V}\upsilon_v\sigma_v\right).$$
We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial inside a zero-free disc centred around easy to evaluate point.
We shall begin with the Ising model with all interactions and external fields equal to zero. Let us make the following definitions that will define a zero-free polyregion centred at this point.
Definition 2 (\(\delta_\Delta\))
For \(\Delta\in\mathbb{Z}^+\), we define the absolute constant \(\delta_\Delta\) by $$\delta_\Delta := \max_{0<\alpha<\frac{2\pi}{3\Delta}}\left[\sin\left(\frac{\alpha}{2}\right)\cos\left(\frac{\alpha\Delta}{2}\right)\right].$$
This constant comes from Barvinok's monograph and will define the size of the zero-free polyregion. We now define the following polyregion.
Definition 3 (\(\mathcal{R}_G(\delta)\))
For a graph \(G=(V,E)\) and \(\delta>0\), we define \(\mathcal{R}_G(\delta)\) to be the closed polyregion consisting of all sets of weights \(\Omega=\{\omega_e\}_{e \in E}\) and \(\Upsilon=\{\upsilon_v\}_{v \in V}\), such that \(|1-e^{\pm\omega_e}|\leq\delta\) for all \(e \in E\) and \(|1-e^{\pm\upsilon_v}|\leq\delta\) for all \(v \in V\).
We prove that the Ising model partition function does not vanish for graphs \(G\) of maximum degree at most \(\Delta\) in the polyregion \(\mathcal{R}_G\left(\delta_{\Delta+1}\right)\).
Theorem 1
Fix \(\Delta\in\mathbb{Z}^+\). For any graph \(G=(V,E)\) of degree at most \(\Delta\) and any \(\Omega=\{\omega_e\}_{e \in E}\) and \(\Upsilon=\{\upsilon_v\}_{v \in V}\) in the closed polyregion \(\mathcal{R}_G\left(\delta_{\Delta+1}\right)\), the Ising model partition function does not vanish, i.e., \(\mathrm{Z}_\mathrm{Ising}(G;\Omega,\Upsilon)\neq0\).
This may be of independent interest in statistical physics as the possible points of physical phase transitions are exactly the real limit points of such complex zeros.
We can now state our main theorem, which gives an efficient algorithm for approximating the partition function for any interactions and external fields inside this region.
Theorem 2
Fix \(\Delta\in\mathbb{Z}^+\) and \(0<\delta<\delta_{\Delta+1}\). There is a deterministic polynomial-time approximation scheme for the Ising model partition function \(\mathrm{Z}_\mathrm{Ising}(G;\Omega,\Upsilon)\) for all graphs \(G=(V,E)\) of maximum degree at most \(\Delta\) and all \(\Omega=\{\omega_e\}_{e \in E}\) and all \(\Upsilon=\{\upsilon_v\}_{v \in V}\) in the closed polyregion \(\mathcal{R}_G\left(\delta\right)\).
We shall now discuss how Theorem 2 allows us to approximate certain output probability amplitudes of quantum circuits.
We begin with the observation that complex-valued Ising model partition functions arise naturally in the output probability amplitudes of quantum circuits. In particular, for the class of commuting quantum circuits, known as Instantaneous Quantum Polynomial-time (IQP) circuits. IQP circuits comprise only gates that are diagonal in the Pauli-X basis. An IQP circuit is described by an X-program.
Definition 4 (X-program)
An X-program is a pair \((P,\theta)\), where \(P=(p_{ij})_{m \times n}\) is a binary matrix and \(\theta\in[-\pi,\pi]\) is a real angle. The matrix \(P\) is used to construct a Hamiltonian of \(m\) commuting terms acting on \(n\) qubits, where each term in the Hamiltonian is a product of Pauli-X operators, $$\mathrm{H}_{(P,\theta)} := -\theta\sum_{i=1}^m\bigotimes_{j=1}^nX_j^{p_{ij}}.$$ Thus, the columns of \(P\) correspond to qubits and the rows of \(P\) correspond to interactions in the Hamiltonian.
We shall consider X-programs that are induced by a graph.
Definition 5 (Graph-induced X-program)
For a graph \(G=(V,E)\) with the weights \(\left\{\omega_e\in[-\pi,\pi]\right\}_{e \in E}\) assigned to its edges and the weights \(\left\{\upsilon_v\in[-\pi,\pi]\right\}_{v \in V}\) assigned to its vertices, we define the X-program induced by \(G\) to be an X-program \(\mathcal{X}_G\) such that $$\mathrm{H}_{\mathcal{X}_G} = -\sum_{\{u,v\} \in E}\omega_{\{u,v\}}X_uX_v-\sum_{v \in V}\upsilon_vX_v.$$
Let us define a specific output probability amplitude arising from a graph-induced X-program.
Definition 6 (\(\psi_{G}\))
For a graph \(G=(V,E)\) with the weights \(\left\{\omega_e\in[-\pi,\pi]\right\}_{e \in E}\) assigned to its edges and the weights \(\left\{\upsilon_v\in[-\pi,\pi]\right\}_{v \in V}\) assigned to its vertices, we define \(\psi_{G}\) to be the probability amplitude given by $$\psi_{G} := \left\langle0^{|V|}\right|\exp\left(-i\mathrm{H}_{\mathcal{X}_G}\right)\left|0^{|V|}\right\rangle.$$
We note that any X-program can be efficiently represented by a graph-induced X-program. Moreover, X-programs are known to become universal for quantum computation under postselection. Therefore, any quantum amplitude can be expressed in the form of \(\psi_{G}\). The output probability amplitudes of such a graph-induced X-program are proportional to Ising model partition functions with imaginary weights.
Theorem 3
Let \(G=(V,E)\) be a graph with the weights \(\Omega=\left\{\omega_e\in[-\pi,\pi]\right\}_{e \in E}\) assigned to its edges and the weights \(\Upsilon=\left\{\upsilon_v\in[-\pi,\pi]\right\}_{v \in V}\) assigned to its vertices, then, $$\psi_{G} = \frac{1}{2^{|V|}}\mathrm{Z}_\mathrm{Ising}(G;i\Omega,i\Upsilon).$$
As a consequence, we obtain the following theorem, which states that we can efficiently approximate certain output probability amplitudes of quantum circuits.
Theorem 4
Fix \(\Delta\in\mathbb{Z}^+\) and \(0<\delta<\delta_{\Delta+1}\). There is a deterministic polynomial-time approximation scheme for the probability amplitude \(\psi_{G}\) for all graphs \(G=(V,E)\) of maximum degree at most \(\Delta\) with the edge weights \(\left\{\omega_e\in[-\pi,\pi]\right\}_{e \in E}\) satisfying \(|\omega_e|\leq2\arcsin(\delta/2)\) for all \(e \in E\) and the vertex weights \(\left\{\upsilon_v\in[-\pi,\pi]\right\}_{v \in V}\) satisfying \(|\upsilon_v|\leq2\arcsin(\delta/2)\) for all \(v \in V\).