# Constructive proof of Herschfeld’s Convergence Theorem

Ran Gutin
Department of Computer Science;
Imperial College London; South Kensington, London SW7 2BU;
<EMAIL_ADDRESS>
###### Abstract

We give a constructive proof of Herschfeld’s Convergence Theorem. The proof is
based on simple and generalisable insights about concave/convex functions.
Explicit convergence bounds are derived. A new special function is defined to
enable one of these bounds to be expressed. We also generalise Herschfeld’s
result to infinite radicals that nest transfinitely many times.

Keywords: constructive proof; continued powers; numerical analysis; concave
functions; reduction to lpo

MSC codes: 03F60, 26E40, 40A30, 65D15, 65D99

##  1 Introduction

In this paper, we present a constructive proof of Herschfeld’s Convergence
Theorem. Our formulation differs from Herschfeld’s in a few ways: We consider
radicals that nest _more than_ infinitely many times, as these are essential
to the proof; additionally, we formulate the conditions for convergence in
such a way that a constructive proof is possible.

Though the result is stated only for square-roots, it is easy to generalise it
to all powers in the interval $(0,1)$. We also show how to apply the
techniques presented here to some other continued functions, like continued
$\arctan$.

###  1.1 Motivation

The motivation for writing this paper was to better understand how to
“constructivise” arguments that appeal to the Monotone Convergence Theorem. An
example of that being Herschfeld’s original proof of his eponymous theorem.

Our results can also be applied to show convergence of other continued
functions, like continued $\arctan$. By continued functions, we mean the limit
(should it exist) of $f(A+f(B+f(C+\dotsc)))$. If the function $f$ is
monotonically increasing and concave then our methods are applicable, at least
to some degree.

It’s worth noting that Herschfeld’s proof can be expressed in one page, while
the argument here is longer and more sophisticated. However, unlike
Herschfeld’s non-constructive proof, the argument here states precisely when
it is possible to estimate the limit of an infinite radical, and also how to
measure the error of such an estimate. Herschfeld’s proof only provides
knowledge of when the limit exists, but not how to find it.

###  1.2 Related work

A very thorough chronology of results on problems related to infinite radicals
and continued $f$-functions is provided by [9].

One of the first complete proofs of the necessary and sufficient condition for
convergence of an infinite radical was given by [5], but an earlier proof was
given by Paul Wiernsberger in 1904. Some interesting closed-form solutions of
special cases were found by Ramanujan among others [12] (see [9] for others).
Jones studied various generalisations of Herschfeld’s convergence result.
These generalisations allow for the powers to be arbitrary positive numbers
[6] in the range $(1,\infty)$ or arbitrary negative numbers [7] .

Continued radicals continue to be an object of study. See for instance [1],
[11] and [3].

##  2 Overview and strategy

A note on notation: All numbers are taken to be non-negative real numbers. The
symbol $\phi$ denotes the golden ratio, equal to both $\frac{1+\sqrt{5}}{2}$
and the infinite radical $\sqrt{1+\sqrt{1+\dots}}$. Also, $\mathbb{R}^{+}$
denotes the set of non-negative real numbers.

The main theorem of this paper is the combination of Theorem 1 and Theorem 2.
A simplified version of this theorem states:

> Simplified Constructive HCT: An infinite radical
> $\sqrt{a_{1}+\sqrt{a_{2}+\dots}}$ where $a_{k}\geq 0$ converges if and only
> if for all $n$ there exists $\lim_{k\geq
> n}\sup_{k=n}^{\infty}a_{k}^{2^{-k}}$.

This theorem is simplified because in our actual theorem statement, the
“infinite radicals” can nest transfinitely many times.

###  2.1 Strategy for proving “if”

Let $M_{n}=\lim_{k\geq n}\sup_{k=n}^{\infty}a_{k}^{2^{-k}}$. A lower bound for
the infinite radical is now $M_{1}$, and an upper bound is $M_{1}\phi$. We can
improve these upper and lower bounds by substituting them deeper inside the
radical. In other words, an improved lower bound is $\sqrt{a_{1}+M_{2}^{2}}$,
and an improved upper bound is $\sqrt{a_{2}+M_{2}^{2}\phi}$. Again, by
substituting even deeper inside the radical, we can get a better lower bound
in the form $\sqrt{a_{1}+\sqrt{a_{2}+M^{4}}}$, and a better upper bound in the
form $\sqrt{a_{1}+\sqrt{a_{2}+\phi M^{4}}}$. And so on.

Now we need to estimate the difference between upper and lower bounds. The key
observation is the following: Let’s say our upper bound is in the form
$\sqrt{7+\sqrt{3+u}}$ for some $u$, and our lower bound is in the form
$\sqrt{7+\sqrt{3+l}}$ for some $l$. Let $\epsilon$ be the difference. It so
happens that:

$\displaystyle\epsilon$
$\displaystyle=\sqrt{7+\sqrt{3+u}}-\sqrt{7+\sqrt{3+l}}$
$\displaystyle\leq\sqrt{0+\sqrt{0+u}}-\sqrt{0+\sqrt{0+l}}$ $\displaystyle\leq
u^{1/4}-l^{1/4}$

In other words, by lowering the numbers $7$ and $3$ down to zero, we amplify
the difference. But in doing so, we also simplify the estimate for the
difference. This is ultimately how we prove “if”.

###  2.2 Strategy for proving “only if”

This is essentially in an inverse strategy to proving “if”. In doing so, we
confront transfinite radicals.

Before we describe transfinite radicals, observe that an inverse to the error
overstimate given above, i.e.

$\displaystyle\epsilon$
$\displaystyle=\sqrt{7+\sqrt{3+u}}-\sqrt{7+\sqrt{3+l}}$
$\displaystyle\leq\sqrt{0+\sqrt{0+u}}-\sqrt{0+\sqrt{0+l}}$ $\displaystyle\leq
u^{1/4}-l^{1/4}$

could be

$\displaystyle\epsilon$
$\displaystyle=\sqrt{7+\sqrt{3+u}}-\sqrt{7+\sqrt{3+l}}$
$\displaystyle\geq\sqrt{100+\sqrt{100+u}}-\sqrt{100+\sqrt{100+l}}$

In other words, we can drive the $3$ and $7$ to _larger numbers_ to
_understimate_ the error.

###  2.3 Transfinite radicals

We consider a more general class of nested radicals than Herschfeld and
others. These radicals can nest _more than_ infinitely many times. All our
results are true for this more general class of nested radicals.

We are led to do this because of a particular family of transfinite radicals
that occur naturally in our argument. This family is called the $U$ function,
and is roughly equal to $\sqrt{1+\sqrt{1+\dotsb\sqrt{x^{2^{\omega}}}}}$ where
$\omega$ denotes the first transfinite ordinal. More precisely, $U(x)$ is the
limit of the sequence $(x,\sqrt{1+x^{2}},\sqrt{1+\sqrt{1+x^{4}}},\dotsc)$
which can be interpreted as a transfinite radical for any fixed $x$.

###  2.4 Absence of differentiation

The error estimation technique used in this paper contrasts with the one
proposed by Herschfeld, in that it doesn’t use any differentiation. This is
useful because the derivative of any expression that involves nested radicals
is quite complicated. For instance,

$\frac{d}{dx}\sqrt{A+\sqrt{B+\sqrt{C+x}}}=\frac{1}{8\sqrt{C+x}\sqrt{B+\sqrt{C+x}}\sqrt{A+\sqrt{B+\sqrt{C+x}}}}.$

A similar problem afflicts all “continued functions”, not just continued
square-roots. We adopt an error estimation strategy which we have already
partially described, and is given in full generality by Lemma 3.

We demonstrate a simple example of using Lemma 3 to show constructively that
the continued function $\arctan(A+\arctan(B+\arctan(C+\dotsc)))$ converges
whenever $A,B,C$ etc. are non-negative. We even give a worst-case error bound.

##  3 Concave functions

Proofs of Lemmas 1 and 2 can be found elsewhere in the literature, but we give
proofs for the sake of completeness.

######  Lemma 1.

For any concave function $h$, real number $x$, and $\Delta
x\in\mathbb{R}^{+}$, it holds that $h(x+\Delta x)-h(x)\leq h(\Delta x)-h(0)$.

###### Proof.

The definition of concavity implies $h(\Delta x)\geq\frac{x}{x+\Delta
x}h(0)+\frac{\Delta x}{x+\Delta x}h(x+\Delta x).$ Subtracting $h(0)$ from both
sides gives

$\displaystyle h(\Delta x)-h(0)\geq\frac{\Delta x}{x+\Delta x}(h(x+\Delta
x)-h(0)).\qquad{(1)}$

Similarly, the definition of concavity implies $h(x)\geq\frac{\Delta
x}{x+\Delta x}h(0)+\frac{x}{x+\Delta x}h(x+\Delta x).$ Subtracting $h(x+\Delta
x)$ from both sides, and then negating, gives

$\displaystyle h(x+\Delta x)-h(x)\leq\frac{\Delta x}{x+\Delta x}(h(x+\Delta
x)-h(0)).\qquad{(2)}$

Combining $(1)$ with $(2)$ gives

$h(\Delta x)-h(0)\geq\frac{\Delta x}{x+\Delta x}(h(x+\Delta x)-h(0))\geq
h(x+\Delta x)-h(x)$

∎

######  Corollary 1.1.

Given $u>l$, $b>s$ and a concave function $h$, it holds that
$h(b+u)-h(b+l)<h(s+u)-h(s+l)$.

######  Remark.

$b$, $s$, $u$ and $l$ can be remembered using the mnemonics “bigger”,
“smaller”, “upper” and “lower”, which indicate through opposite meanings which
is greater than which. There is no implied ordering between bigger and lower,
or smaller and upper, because bigger isn’t opposite to lower.

###### Proof.

Apply Lemma 1 to $H(X)=h(s+l+X)$, $x=b-s$, $\Delta x=u-l$ to get $H(\Delta
x)-H(0)\geq H(x+\Delta x)-H(x)$ which is equivalent to $h(s+u)-h(s+l)\geq
h(b+u)-h(b+l)$.

∎

######  Lemma 2.

If $f$ and $g$ are concave functions, and $f$ is non-decreasing, then $f\circ
g$ is also concave and non-decreasing.

###### Proof.

$f\circ g$ is clearly non-decreasing. We hence show that it’s concave: Given
any $x,y\in\mathbb{R}$ and $\lambda\in[0,1]$, we have that

$\displaystyle g(\lambda x+(1-\lambda)y)$ $\displaystyle\geq$
$\displaystyle\lambda g(x)+(1-\lambda)g(y)$ $\displaystyle\therefore$
$\displaystyle f(g(\lambda x+(1-\lambda)y))$ $\displaystyle\geq$
$\displaystyle f(\lambda g(x)+(1-\lambda)g(y))\qquad{\text{because f is non-
decreasing}}$ $\displaystyle\geq$ $\displaystyle\lambda
f(g(x))+(1-\lambda)f(g(y))\qquad{\text{because f is concave}}$

∎

######  Lemma 3.

For any concave and non-decreasing function $h$, pair of real numbers $u>l$,
and two sequences $(a_{k})_{k=1}^{n}$ and $(b_{k})_{k=1}^{n}$ of equal length
where each $a_{k}\leq b_{k}$, it holds that

$\displaystyle h(a_{1}+h(a_{2}+\dots h(a_{n}+u)))-h(a_{1}+h(a_{2}+\dots
h(a_{n}+l)))\geq$ $\displaystyle h(b_{1}+h(b_{2}+\dots
h(b_{n}+u)))-h(b_{1}+h(b_{2}+\dots h(b_{n}+l))).$

###### Proof.

Repeated applications of Lemma 2 and Corollary 1.1 give:

$\displaystyle h(a_{1}+\dots h(a_{n}+u))-h(a_{1}+\dots h(a_{n}+l))$
$\displaystyle\geq h(b_{1}+h(a_{2}+\dots h(a_{n}+u)))-h(b_{1}+h(a_{2}+\dots
h(a_{n}+l)))$ $\displaystyle\geq h(b_{1}+h(b_{2}+\dots
h(a_{n}+u)))-h(b_{1}+h(b_{2}+\dots h(a_{n}+l)))$ $\displaystyle\dots$
$\displaystyle\geq h(b_{1}+h(b_{2}+\dots h(b_{n}+u)))-h(b_{1}+h(b_{2}+\dots
h(b_{n}+l)))$

∎

##  4 Example of using Lemma 3

We consider the easier problem of showing that
$\arctan(A+\arctan(B+\arctan(C+\dotsc)))$ converges whenever $A,B,C$ etc. are
positive. Non-constructively, we can immediately see that this converges
because of the Monotone Convergence Theorem. On the other hand, proving it
constructively is somewhat of a challenge.

Assume we’ve only observed $A$ and $B$, but not $C$, or any term after $C$.
Then the maximum value of the expression is
$\arctan(A+\arctan(B+\arctan(\infty)))$, and the minimum value is
$\arctan(A+\arctan(B+\arctan(0)))$. We’ll use the latter expression as an
estimate. An upper bound for the resulting error $\epsilon$ is thus

$\epsilon\leq\arctan(A+\arctan(B+\arctan(\infty)))-\arctan(A+\arctan(B+\arctan(0))).$

We now use Lemma 3 to derive an upper bound on the error by driving $A$ and
$B$ to zero:

$\displaystyle\epsilon$
$\displaystyle\leq\arctan(0+\arctan(0+\arctan(\infty)))-\arctan(0+\arctan(0+\arctan(0)))$
$\displaystyle=\arctan(\arctan(\arctan(\infty))).$

So as we observe $n$ terms (the $A$, $B$, $C$, $D$s etc.) our upper bound for
the error is $\arctan^{n}(\infty)$ where the superscript $n$ denotes $n$-fold
iteration. We are done using Lemma 3.

It remains to show that $\arctan^{n}(\infty)$ converges to $0$. To do so,
first observe that $\arctan^{n}(\infty)=\arctan^{n-1}(\pi/2)$.

We can proceed either by attempting to show that
$\arctan^{n-1}(\pi/2)\sim\sqrt{\frac{3}{2n}}$; or by using a sledgehammer,
which we do below:

We apply the following lemma: For any function $f$ such that for all $x\neq
0$, we have $|f(x)|<|x|$, it follows that iterates of $f$ always converge to
$0$. This claim is equivalent to the Fan Principle (sometimes confusingly
called the Fan Theorem), which is a constructively acceptable postulate.
Equivalence to the Fan Principle is demonstrated by Proposition 3.3.4 of [4].

##  5 Kappa notation

We define an operator $\operatorname*{\text{\Large{$\mathcal{K}$}}}$ which
takes as input an ordinal-indexed sequence, and outputs a number.

The value of

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$

is defined to be the limit of the sequence

$\alpha_{\omega},\sqrt{\alpha_{1}^{2^{1}}+\alpha_{\omega}^{2^{1}}},\sqrt{\alpha_{1}^{2^{1}}+\sqrt{\alpha_{2}^{2^{2}}+\alpha_{\omega}^{2^{2}}}},\sqrt{\alpha_{1}^{2^{1}}+\sqrt{\alpha_{2}^{2^{2}}+\sqrt{\alpha_{3}^{2^{3}}+\alpha_{\omega}^{2^{3}}}}},\dotsc$

By definition, these approximants are equal to

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}(1-[0<i<\omega])),\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}(1-[1<i<\omega])),\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}(1-[2<i<\omega])),\dotsc$

where we use Iverson Bracket notation.

The infinite radicals that can be expressed using this notation are more
general than the nested radicals considered by Herschfeld and many others.
Namely, the sequence $\alpha_{i}$ can be continued “past infinity”. For this
reason, we will refer to this more general class of infinite radicals as
_transfinite radicals_.

The definition assumes that the sequence is indexed up to and including the
ordinal $\omega$. It _is_ possible to generalise the definition further to
allow for arbitrarily large ordinals, but we won’t do this for the following
reasons:

  * •

The results we prove won’t change.

  * •

The definitions may become more confusing.

  * •

We may be asked to provide a constructive theory of the ordinal numbers, which
is not the goal of this paper.

Some examples of transfinite radicals expressible using this notation include:

  * •

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(2)=\sqrt{2^{2^{1}}+\sqrt{2^{2^{2}}+\sqrt{2^{2^{3}}+\dotsb}}}$.

  * •

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(x^{[i=\omega]})$ where $x$
is arbitrary. Here, we raise $x$ to the power of an Iverson Bracket. By
definition, this transfinite radical is the limit of the sequence
$x,\sqrt{1+x^{2}},\sqrt{1+\sqrt{1+x^{4}}},\sqrt{1+\sqrt{1+\sqrt{1+x^{8}}}},\dotsc$
We will make two points about this example:

    * –

There is no way of viewing this transfinite radical as an ordinary infinite
radical.

    * –

At some point, we will call this function of $x$ the $U$ function.

Our operator differs from the one used by [8] and [10]: Their notation is

$\mathop{\mathrm{\text{\Large{$K$}}}}_{i}\sqrt{\alpha_{i}},$

which stands for
$\sqrt{\alpha_{1}+\sqrt{\alpha_{2}+\sqrt{\alpha_{3}+\dotsc}}}$. However, their
notation is not appropriate for expressing transfinite radicals.

##  6 Radical capped implies radical converges

######  Lemma 4.

The function $x\mapsto x^{1/n}$, $\mathbb{R}^{+}\to\mathbb{R}^{+}$ with $n>1$
is a concave function.

###### Proof.

The second derivative is negative which implies concavity.

∎

######  Lemma 5.

Given a sequence $(\alpha_{k})_{k=1}^{n}$ of non-negative numbers, a pair of
numbers $l<u$, and a natural number $I$, we have that
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<I]\alpha_{i}+[i=I]u)-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<I]\alpha_{i}+[i=I]l)\leq
u-l$.

###### Proof.

This follows from Lemma 3, where $h(x)=\sqrt{x}$, $a_{k}=0$ and
$b_{k}=\alpha_{k}^{2^{k}}$.

We get that

$\displaystyle\sqrt{\alpha_{1}^{2^{1}}+\dots\sqrt{\alpha_{n}^{2^{n}}+u^{2^{n}}}}-\sqrt{\alpha_{1}^{2^{1}}+\dots\sqrt{\alpha_{n}^{2^{n}}+l^{2^{n}}}}$
$\displaystyle\leq\sqrt{0+\dots\sqrt{0+u^{2^{n}}}}-\sqrt{0+\dots\sqrt{0+l^{2^{n}}}}$
$\displaystyle=u-l$

∎

######  Lemma 6.

The $\operatorname*{\text{\Large{$\mathcal{K}$}}}$ operator has the following
properties:

  1. 1.

$\alpha_{i}\leq\beta_{i}\implies\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\leq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\beta_{i})$

  2. 2.

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(C\alpha_{i})=C\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$
where $C$ is any nonnegative constant.

  3. 3.

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq\alpha_{n}$
for any particular element of the sequence $\alpha_{n}$.

  4. 4.

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(1)=\phi$ where $\phi$
denotes the Golden Ratio.

  5. 5.

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+\beta_{i-n+1}[i\geq
n])=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+[i=n](\operatorname*{\text{\Large{$\mathcal{K}$}}}_{j}(\beta_{j}^{2^{n}}))^{2^{-n}})$.
This rule allows us to use recursion.

  6. 6.

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+x[i=n])=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+x[i=\omega])$.
We will call this the _shift rule_. It allows us to shift the last term to
infinity.

###### Proof.

Obvious. ∎

######  Lemma 7.

If $\sup_{k}({\alpha_{k}})=M$ then
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq M$.

###### Proof.

Let $\epsilon>0$.

From the fact that $\sup_{k}({\alpha_{k}})=M$, there is some $\alpha_{N}$ such
that $\alpha_{N}>M-\epsilon$. It follows that
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq\alpha_{N}>M-\epsilon$.
Since $\epsilon$ is arbitrary, we have that
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq M$.

∎

######  Corollary 7.1.

If we have a sequence $(M_{n})_{n}$ where each $M_{n}=\sup_{k\geq
n}\alpha_{k}$, then for each $n$ we have a lower bound
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}[i=n])$.

###### Proof.

Let $\beta_{j}=\alpha_{j+n-1}$. We have that $\sup_{j}\beta_{j}\leq M_{n}$. It
therefore follows that $\sup_{j}\beta_{j}^{2^{n}}\leq M_{n}^{2^{n}}$.
Therefore by Lemma 7, we have
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{j}(\beta_{j}^{2^{n}})\geq
M_{n}^{2^{n}}$. We finally have that

$\displaystyle\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$
$\displaystyle=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+\beta_{i-n+1}[i\geq
n])$
$\displaystyle=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+[i=n](\operatorname*{\text{\Large{$\mathcal{K}$}}}_{j}(\beta_{j}^{2^{n}}))^{2^{-n}})$
$\displaystyle\geq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+[i=n]M_{n})$

∎

######  Lemma 8.

If we have a sequence $(M_{n})_{n}$ where each $M_{n}=\sup_{k\geq
n}\alpha_{k}$, then for each $n$ we have an upper bound
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}\phi^{2^{-n}}[i=n])$.

###### Proof.

$\displaystyle\alpha_{i}$ $\displaystyle\leq\alpha_{i}[i<n]+M_{n}[i\geq n]$
$\displaystyle\therefore\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$
$\displaystyle\leq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}[i\geq
n])$
$\displaystyle=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+(\operatorname*{\text{\Large{$\mathcal{K}$}}}_{j}(M_{n}^{2^{n}}))^{2^{-n}}[i=n])$
$\displaystyle=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}(\operatorname*{\text{\Large{$\mathcal{K}$}}}_{j}(1))^{2^{-n}}[i=n])$
$\displaystyle=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}\phi^{2^{-n}}[i=n])$

∎

######  Theorem 1.

Given the infinite sequence $(\alpha_{k})_{k=1}^{\infty}$ where each
$\alpha_{k}$ is a non-negative real number, if there exists an infinite
sequence $(M_{k})_{k=1}^{\infty}$ such that
$M_{n}=\sup_{k=n}^{\infty}\alpha_{k}$, then
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$ converges.

###### Proof.

By Corollary 7.1, we have
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}[i=n])$.

By Lemma 8, we have
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\leq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}\phi^{2^{-n}}[i=n])$.

The difference between upper bound and lower bound is by definition
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}\phi^{2^{-n}}[i=n])-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i}[i<n]+M_{n}[i=n])$,
which by Lemma 5 is at most $M_{n}(\phi^{2^{-n}}-1)$, which clearly goes to
zero.

∎

##  7 The function $U(r)$

In this section, we define an interesting function called $U(r)$, and
investigate some of its properties. We will use it to prove Theorem 2. It is
defined as

$U(r)=\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<\omega]+r[i=\omega])$

It follows from Theorem 1 that the function is well-defined for all $r\geq 0$.

######  Lemma 9.

For $s\in\mathbb{R}$ and $r\in\mathbb{R}$, if $s>r\geq 1$, then $U(s)>U(r)$.

###### Proof.

If $r\geq 1$, then Corollary 7.1 gives us that
$U(r)\leq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+r\phi^{2^{-n}}[i=n])$

If $s\geq 1$, then Lemma 8 gives us that
$U(s)\geq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+s[i=n])$

Clearly for large enough $n$, we have that $s>r\phi^{2^{-n}}$. It follows that
for this value of $n$, we get:

$\displaystyle U(s)$
$\displaystyle\geq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+s[i=n])$
$\displaystyle>\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+r\phi^{2^{-n}}[i=n])$
$\displaystyle\geq U(r).$

∎

######  Corollary 9.1.

$U:[1,\infty)\to[U(1),\infty)$ is continuous, unbounded, and admits an inverse
function.

###### Proof.

We shall prove Lipschitz continuity: Lipschitz continuity follows from the
fact that for every $n\in\mathbb{N}$

$\displaystyle U(s)-U(r)$
$\displaystyle\leq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+\phi^{2^{-n}}s[i=n])-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+r[i=n])$
$\displaystyle\leq\phi^{2^{-n}}s-r\qquad{\text{by Lemma \ref{lemma-5}}}$

which implies that $|U(s)-U(r)|\leq|s-r|$.

The function is unbounded because $U(r)>r$ (Lemma 8).

The existence of an inverse follows from the fact that the function is one-to-
one, unbounded, and by the Intermediate Value Theorem. ∎

##  8 Radical converges implies radical capped

######  Lemma 10.

If we let $(\beta_{i})$ denote the result of rearranging from smaller to
larger two adjacent elements of $(\alpha_{i})$, then
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\beta_{i})$.

###### Proof.

This follows from the fact that the square-root is a convex, increasing
function that maps nonnegative numbers to nonnegative numbers.

Let $f(x)=\sqrt{x}$.

It suffices to consider only swapping the first two elements of the sequence
$(\alpha_{i})$. In other words, we define the sequence $(\beta_{i})$ by
$\beta_{i}=\min(\alpha_{1},\alpha_{2})[i=1]+\max(\alpha_{1},\alpha_{2})[i=2]+\alpha_{i}[i>2]$,
and claim that
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})\geq\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\beta_{i})$.

Finally our claim is that given $A\leq B$ and arbitrary nonnegative $x$, that

$f(f^{-1}(A)+f(f^{-2}(B)+x))\leq f(f^{-1}(B)+f(f^{-2}(A)+x)).$

We now prove it:

$\displaystyle A$ $\displaystyle\leq B$ $\displaystyle f^{-2}(A)$
$\displaystyle\leq f^{-2}(B)\qquad{\text{because $f$ is an increasing
function}}$ $\displaystyle f^{-2}(A)+x$ $\displaystyle\leq f^{-2}(B)+x$
$\displaystyle f^{\prime}(f^{-2}(A)+x)$ $\displaystyle\geq
f^{\prime}(f^{-2}(B)+x)\qquad{\text{because $f^{\prime}$ is a decreasing
function}}$ $\displaystyle f(f^{-2}(A)+x)-f^{-1}(A)$ $\displaystyle\geq
f(f^{-2}(B)+x)-f^{-1}(B)\qquad{\text{by integrating from $0$ to $x$}}$
$\displaystyle f^{-1}(B)+f(f^{-2}(A)+x)$ $\displaystyle\geq
f^{-1}(A)+f(f^{-2}(B)+x)\qquad{\text{by rearranging both sides}}$
$\displaystyle f(f^{-1}(B)+f(f^{-2}(A)+x))$ $\displaystyle\geq
f(f^{-1}(A)+f(f^{-2}(B)+x))\qquad{\text{because $f$ is an increasing
function}}$

∎

Here, we are about to generalise the definition of a transfinite radical.
We’ve avoided doing this up until now in order to keep things simple. All the
results we’ve proved previously carry through.

######  Definition.

For each finite set of ordinals
$\Omega=\\{\iota_{1},\iota_{2},\dotsc,\iota_{n}\\}$ where
$\iota_{1}<\iota_{2}<\dotsc<\iota_{n}$, let
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in\Omega}(\alpha_{i})$ denote
$\sqrt{\alpha_{\iota_{1}}^{2^{1}}+\sqrt{\alpha_{\iota_{2}}^{2^{2}}+\dotsc\sqrt{\alpha_{\iota_{n}}^{2^{n}}}}}$.

Clearly, $\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$ is
convergent iff
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in\Omega}(\alpha_{i})$ is
_Cauchy_ in $\Omega$. What this means is that for any $\epsilon>0$ there
exists a finite set of ordinals $H$ such that for all finite sets of ordinals
$K\supset H$, $\lvert\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
K}(\alpha_{i})-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(\alpha_{i})\rvert<\epsilon$.

######  Definition.

For each finite set of ordinals $\Omega$, let
$M_{\Omega}=\max_{k\in\Omega}\alpha_{k}$.

######  Lemma 11.

Given the infinite sequence $(\alpha_{k})_{k=1}^{\infty}$, if the radical
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$ is convergent,
then there exists an $M\in\mathbb{R}$ such that
$M=\sup_{k=1}^{\infty}\alpha_{k}$.

###### Proof.

The following argument will be somewhat informal. This is so as to not confuse
the reader.

Let $\epsilon>0$. Convergence means that we have a finite set of ordinals $H$
such that for any finite set of ordinals $K\supset H$,
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
K}(\alpha_{i})-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(\alpha_{i})<\epsilon$.

Consider an $H$ for which the above is true. Consider any $k\in\mathbb{N}$
such that $\alpha_{k}>M_{H}$, and let $K=H\cup\\{\alpha_{k}\\}$.

$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in K}(\alpha_{i})$ can be
written explicitly as
$\sqrt{\alpha_{1}^{2^{1}}+\sqrt{\alpha_{2}^{2^{2}}+\dotsc\sqrt{\alpha_{n}^{2^{n}}}}}$.
We’re assuming that $H=\\{1,\dotsc,n\\}\setminus\\{k\\}$ and $k\leq n$, but
this is without any loss of generality. Hence we have:

$\epsilon>\sqrt{\alpha_{1}^{2^{1}}+\sqrt{\alpha_{2}^{2^{2}}+\dotsc\sqrt{\alpha_{n}^{2^{n}}}}}-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(\alpha_{i})$

Let’s say, for instance, that $k=2$. We will write $\alpha_{k}$ as $M_{K}$ to
distinguish it. We thus have:

$\epsilon>\sqrt{\alpha_{1}^{2^{1}}+\sqrt{M_{K}^{2^{2}}+\dotsc\sqrt{\alpha_{n}^{2^{n}}}}}-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(\alpha_{i})$

We now shift $M_{K}$ to the last index. By Lemma 10, this shrinks the lower
bound:

$\epsilon>\sqrt{\alpha_{1}^{2^{1}}+\sqrt{\alpha_{3}^{2^{2}}+\dotsc\sqrt{\alpha_{n}^{2^{n}}+M_{K}^{2^{n}}}}}-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(\alpha_{i})$

We then drive all the other $\alpha_{i}$ to $M_{H}$, which they are all at
most equal to. This reduces the lower bound further.

$\epsilon>\sqrt{M_{H}^{2^{1}}+\sqrt{M_{H}^{2^{2}}+\dotsc\sqrt{M_{H}^{2^{n}}+M_{K}^{2^{n}}}}}-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(M_{H})$

We factorise out $M_{H}$:

$\epsilon>M_{H}\left(\sqrt{1+\sqrt{1+\dotsc\sqrt{1+(M_{K}/M_{H})^{2^{n}}}}}-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i\in
H}(1)\right)$

We now switch to using notation:

$\displaystyle\epsilon$
$\displaystyle>M_{H}\left(\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+(M_{K}/M_{H})[i=n])-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n])\right)$
$\displaystyle=M_{H}\left(\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n]+(M_{K}/M_{H})[i=\omega])-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<n])\right)\qquad{\text{shift
rule from Lemma \ref{lemma-6}}}$ $\displaystyle\geq
M_{H}\left(\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<\omega]+(M_{K}/M_{H})[i=\omega])-\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}([i<\omega])\right)\qquad{\text{using
Lemma \ref{lemma-3} to drive $0$ terms to $1$}}$
$\displaystyle=M_{H}(U(M_{K}/M_{H})-U(1))$

We extract out the inequality $\epsilon>M_{H}(U(M_{K}/M_{H})-U(1))$, and
rearrange it to:

$\alpha_{K}<M_{H}\cdot U^{-1}\left(\frac{\epsilon}{M_{H}}+U(1)\right)$

We thus conclude that the maximum value $M$ exists, and can be bounded as:

$M\in\left[M_{H},M_{H}\cdot
U^{-1}\left(\frac{\epsilon}{M_{H}}+U(1)\right)\right].$

∎

######  Theorem 2.

Given the infinite sequence $(\alpha_{k})_{k=1}^{\infty}$ where each
$\alpha_{k}$ is a non-negative real number, if the transfinite radical
$\operatorname*{\text{\Large{$\mathcal{K}$}}}_{i}(\alpha_{i})$ converges, then
there exists an infinite sequence $(s_{k})_{k=1}^{\infty}$ such that
$s_{n}=\sup_{k=n}^{\infty}a_{k}^{2^{-k}}$.

###### Proof.

We construct $s_{n}$ by applying Lemma 11 (which comes with a constructive
formula!) to the sequence $\beta_{i}=\alpha_{i}[i\geq n]$.

∎

##  9 Constructivity of reformulations of Herschfeld’s Theorem

My constructive statement of Herschfeld’s Theorem is given by Theorem 1 and
Theorem 2, which combined say:

> Constructive HCT: An infinite radical $\sqrt{a_{1}+\sqrt{a_{2}+\dots}}$
> where each $a_{k}$ is a non-negative real number converges if and only if
> there is a sequence $s_{n}$ such that
> $s_{n}=\sup_{k=n}^{\infty}a_{k}^{2^{-k}}$.

Herschfeld’s original statement of his theorem is somewhat simpler:

> Strong HCT: An infinite radical $\sqrt{a_{1}+\sqrt{a_{2}+\dots}}$ where each
> $a_{k}$ is a non-negative real number converges if and only if there is a
> constant $M$ such that $M=\limsup_{k=1}^{\infty}a_{k}^{2^{-k}}$.

We shall break Strong HCT into a conjuction of two statements, both converses
of each other.

> Strong HCT a: Given a sequence $(a_{k})$ where each $a_{k}$ is a non-
> negative real number, if there is a constant $M$ such that
> $M=\limsup_{k=1}^{\infty}a_{k}^{2^{-k}}$, then
> $\sqrt{a_{1}+\sqrt{a_{2}+\dots}}$ converges.

> Strong HCT b: Given a sequence $(a_{k})$ where each $a_{k}$ is a non-
> negative real number, if $\sqrt{a_{1}+\sqrt{a_{2}+\dots}}$ converges, then
> there is a constant $M$ such that $M=\limsup_{k=1}^{\infty}a_{k}^{2^{-k}}$.

We will now show the “issues” with Strong HCT b, by quoting the statement WLPO
[2].

> WLPO (_Weak Limited Principle of Omniscience_): For any infinite binary
> sequence $(b_{n})$, either all elements of the sequence are $1$ or not all
> elements are $1$.

The statement WLPO is universally accepted to be non-constructive. It turns
out that Strong HCT b actually implies it.

######  Theorem 3.

Strong HCT b implies WLPO.

###### Proof.

Consider an infinite binary sequence $(b_{n})_{n\in\mathbb{N}}$. We define a
new sequence $(c_{n})$ of real numbers, such that

$c_{n}=\begin{cases}1,&b_{n}=1,\\\ \phi,&b_{n-1}=1\text{ and }b_{n}=0\\\
0,&\text{otherwise}\end{cases}$

The infinite radical given by $\sqrt{c_{1}+\sqrt{c_{2}+\dots}}$ clearly
converges to $\phi$. This means that _we do know_ what the radical converges
to. We can even bound the rate of convergence. But according to Strong HCT b,
this means that we can determine the value of $M=\limsup_{k}c_{k}^{2^{-k}}$.

Either $M<1$ or $M>0$.

If $M<1$ then it can’t be that all terms of $b_{n}$ are $1$.

If $M>0$ then all terms of $b_{n}$ are $1$.

We have WLPO.

∎

This shows that our formulation of Constructive HCT, though strange, is
necessary to be in the form it is.111Originally, it was intended for this
section to discuss different interpretations of the statement
“$M=\limsup_{k=1}^{\infty}a_{k}^{2^{-k}}$”. The intention was to show that for
an overly strong definition of the $\limsup$ operator, _Strong HCT b_ would be
equivalent to LPO; and for an overly weak definition of $\limsup$, _Strong HCT
a_ would be equivalent to Markov’s Principle. Markov’s Principle is a
statement considered mildly acceptable to constructivists, but which cannot be
derived from the rules of constructive logic alone. This discussion was
eventually omitted because I wasn’t sure how to write it in a clear way.

Acknowledgements: The original version of this paper was very different to
this one. The change is largely because of e-mail conversations between me and
Fred Richman. These conversations challenged me to reformulate the theorem in
a way that I could convincingly call it the “Constructive Herschfeld Theorem”.
The result of this was a completely new formulation of the theorem, and a much
better strategy for proving it. I’d like to extend my thanks to Fred for his
patience.

## References

  * [1] Noboru AOKI and Shota KOJIMA.  Nested square roots and poincaré functions.  Tokyo J. Math., 39(1):241–269, 06 2016.
  * [2] Errett Bishop.  Foundations of Constructive Analysis.  Mcgraw-Hill, 1967.
  * [3] Xi Bo-Yan and Qi Feng.  Convergence, monotonicity, and inequalities of sequences involving continued powers.  Analysis, 33(3):235 – 242, 2013.
  * [4] Hannes Diener.  Constructive reverse mathematics, 2018.
  * [5] Aaron Herschfeld.  On infinite radicals.  The American Mathematical Monthly, 42(7):419–429, 1935.
  * [6] Dixon J. Jones.  Continued powers and a sufficient condition for their convergence.  Mathematics Magazine, 68(5):387–392, 1995.
  * [7] Dixon J. Jones.  Continued reciprocal roots.  The Ramanujan Journal, 38(2):435–454, Nov 2015.
  * [8] Dixon J Jones.  Continued reciprocal roots.  The Ramanujan Journal, 38:435–454, 11 2015.
  * [9] Dixon J. Jones.  A chronology of continued square roots and other continued compositions, through the year 2016.  arXiv e-prints, page arXiv:1707.06139, Jul 2017.
  * [10] A. Kersten, L.W. Schönefuss, M. Lüneburg, and T. Stoeber.  Entwicklungssätze für eine Klasse indefiniter Eigenwertprobleme mit stückweise stetiger Gewichtsfunktion.  Number nos. 206-209 in Entwicklungssätze für eine Klasse indefiniter Eigenwertprobleme mit stückweise stetiger Gewichtsfunktion. Selbstverlag des Mathematischen Instituts, 1992.
  * [11] Chris D. Lynd.  Using difference equations to generalize results for periodic nested radicals.  The American Mathematical Monthly, 121(1):45–59, 2014.
  * [12] Srinivasa Ramanujan.  Question 289. solution by the proposer.  Journal of the Indian Mathematical Society, 1911.


# Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree
Graphs

Ryan L. Mann<EMAIL_ADDRESS>http://www.ryanmann.org Centre for Quantum
Computation and Communication Technology,
Centre for Quantum Software and Information,
Faculty of Engineering & Information Technology, University of Technology
Sydney, NSW 2007, Australia  Michael J. Bremner  Centre for Quantum
Computation and Communication Technology,
Centre for Quantum Software and Information,
Faculty of Engineering & Information Technology, University of Technology
Sydney, NSW 2007, Australia

###### Abstract

We study the problem of approximating the Ising model partition function with
complex parameters on bounded degree graphs. We establish a deterministic
polynomial-time approximation scheme for the partition function when the
interactions and external fields are absolutely bounded close to zero.
Furthermore, we prove that for this class of Ising models the partition
function does not vanish. Our algorithm is based on an approach due to
Barvinok for approximating evaluations of a polynomial based on the location
of the complex zeros and a technique due to Patel and Regts for efficiently
computing the leading coefficients of graph polynomials on bounded degree
graphs. Finally, we show how our algorithm can be extended to approximate
certain output probability amplitudes of quantum circuits.

##  I Introduction

The Ising model partition function plays an important role in combinatorics
and statistical physics. In this paper we study the problem of approximating
the Ising model partition function in the complex parameter regime on bounded
degree graphs. This work is motivated by the close relationship to quantum
computation, where it can be shown that approximate evaluations of these
partition functions can encode arbitrary quantum computations De las Cuevas
_et al._ (2011). A classic result of Jaeger, Vertigan, and Welsh Jaeger  _et
al._ (1990) showed that exactly evaluating these partition functions is
#P-hard. This was shown to remain true in the approximate case Goldberg and
Guo (2017) and when restricted to graphs of bounded degree Fujii and Morimae
(2017). Therefore, it seems unlikely that an efficient algorithm exists for
approximating the partition function for general parameters on bounded degree
graphs. Furthermore, it has been conjectured that this problem remains hard on
average over certain classes of interactions and external fields Gao  _et al._
(2017); Boixo  _et al._ (2018); Bermejo-Vega  _et al._ (2018). Resolving these
conjectures is important for understanding the complexity of quantum
computing.

We establish a deterministic polynomial-time approximation scheme for the
Ising model partition function on bounded degree graphs when the interactions
and external fields are absolutely bounded close to zero (Corollary 6). This
provides a lower bound on when the interactions and external fields cause
approximations of the Ising model partition function to transition from being
contained in P to being #P-hard. Our algorithm is based on an approach due to
Barvinok Barvinok (2015, 2016a, 2016b) for approximating evaluations of a
polynomial based on the location of the complex zeros and a technique due to
Patel and Regts Patel and Regts (2017) for efficiently computing the leading
coefficients of graph polynomials on bounded degree graphs.

Barvinok’s approach considers the Taylor expansion of the logarithm of a
polynomial about an easy to evaluate point. Suppose that we can show that the
complex zeros of the polynomial lie in the exterior of a closed disc centred
at this point, then it follows that a truncated Taylor expansion provides an
additive approximation to the logarithm of the polynomial at any point in the
interior of this closed disc. Now observe that an additive approximation of
the logarithm of a polynomial corresponds to a multiplicative approximation of
the polynomial.

To construct an algorithm from this approach we need to be able to compute the
coefficients of the truncated Taylor expansion. Barvinok showed that computing
these coefficients can be reduced to computing the leading coefficients of the
polynomial itself. However, to achieve the accuracy required for an
approximation scheme, we require a number of leading coefficients that is
logarithmic in the degree of the polynomial. For many combinatorial
structures, directly computing these coefficients requires quasi-polynomial
time.

Patel and Regts Patel and Regts (2017) showed that, for several classes of
graph polynomials on bounded degree graphs, the leading coefficients can be
computed in polynomial time. Their approach is based on expressing the
coefficients as linear combinations of connected induced subgraph counts of
size logarithmic in the size of the graph. It then follows from a result due
to Borgs et al. Borgs  _et al._ (2013), which states that, for bounded degree
graphs, we can efficiently enumerate all connected induced subgraphs of
logarithmic size.

Barvinok and Soberón Barvinok and Soberón (2017) established a deterministic
quasi-polynomial time algorithm for approximating the multivariate graph
homomorphism partition function on bounded degree graphs when the matrix
entries are absolutely bounded close to one. In the case that all matrix
entries are exactly equal to one, the partition function is easy to evaluate.
Barvinok and Soberón proved that for bounded degree graphs when the matrix
entries are absolutely bounded close to one, the partition function does not
vanish. Finally, they proved that the leading coefficients can be computed in
quasi-polynomial time. Patel and Regts Patel and Regts (2017) improved this to
a deterministic polynomial-time algorithm by showing that the coefficients can
be expressed as linear combinations of connected induced subgraph counts.

In order to establish a polynomial-time approximation scheme for the Ising
model partition function, we provide an approximation-preserving polynomial-
time reduction to a restricted version of the multivariate graph homomorphism
partition function (Proposition 5). We extend the results of Barvinok and
Soberón Barvinok and Soberón (2017) and Patel and Regts Patel and Regts (2017)
to give an algorithm for approximating this restricted version of the
multivariate graph homomorphism partition function on bounded degree graphs
when the matrix entries are absolutely bounded close to one (Theorem 1). As a
consequence, we obtain a deterministic polynomial-time approximation scheme
for the Ising model partition function on bounded degree graphs when the
interactions and external fields are absolutely bounded sufficiently close to
zero. Furthermore, we prove that in this case the Ising model partition
function does not vanish (Corollary 7). This may be of independent interest in
statistical physics as the possible points of physical phase transitions are
exactly the real limit points of complex zeros Sokal  _et al._ (2005).

Previous work by Liu, Sinclair, and Srivastava Liu  _et al._ (2019) studied
the problem of approximating the ferromagnetic Ising model partition function
based on the location of complex zeros. They gave a deterministic polynomial-
time approximation scheme for the Ising model partition function in the
ferromagnetic regime for all complex external fields that are not purely
imaginary. This can be seen as an algorithmic consequence of the classic Lee-
Yang Theorem Lee and Yang (1952), which states that the ferromagnetic Ising
model partition function does not vanish except when the external fields are
purely imaginary. Peters and Regts Peters and Regts (2018) generalised this
result by determining the exact location of zeros in the ferromagnetic and
anti-ferromagnetic regime as a function of the inverse temperature and the
maximum degree.

Further work has considered the problem of approximating the Ising model
partition function on bounded degree graphs based on the decay of correlations
property. Sinclair, Srivastava, and Thurley Sinclair  _et al._ (2014)
established a deterministic polynomial-time approximation scheme for the anti-
ferromagnetic Ising model partition function on graphs of maximum degree at
most $\Delta$ when the interactions and external fields lie in the uniqueness
region of the Gibbs measure on the infinite $\Delta$-regular tree, which is
exactly the region that the decay of correlation property holds. Sly and Sun
Sly and Sun (2012) showed that for interactions outside of this region, unless
RP=NP, there is no fully polynomial-time randomised approximation scheme for
the anti-ferromagnetic Ising model partition function on graphs of maximum
degree at most $\Delta\geq 3$. Independent work by Galanis, Štefankovič, and
Vigoda Galanis  _et al._ (2016) established a similar result in the case of no
external field. Liu, Sinclair, and Srivastava Liu  _et al._ (2018) showed
that, in the case of no external field, the Ising model partition function has
no zeros in a complex neighbourhood of the decay of correlation regime. This
establishes a formal relationship between these two approaches.

Our final result is a polynomial-time algorithm for approximating certain
output probability amplitudes of quantum circuits (Corollary 9). This
algorithm is based on the observation that complex-valued Ising model
partition functions arise in the output probability amplitudes of quantum
circuits De las Cuevas  _et al._ (2011); Iblisdir  _et al._ (2014). We focus
on a class of commuting quantum circuits, known as Instantaneous Quantum
Polynomial-time (IQP) circuits Shepherd and Bremner (2009), where the mapping
to the Ising model partition function is the most straightforward Shepherd and
Bremner (2009); Shepherd (2010); Fujii and Morimae (2017). Bremner, Montanaro,
and Shepherd Bremner  _et al._ (2016) showed that general IQP circuits cannot
be efficiently classically simulated under the assumption that the Polynomial
Hierarchy does not collapse and the Ising model partition function is #P-hard
on average over certain classes of interactions and external fields.
Furthermore, IQP circuits are known to become universal for quantum
computation under postselection Bremner  _et al._ (2010), therefore,
approximating output probability amplitudes of IQP circuits is equivalent to
approximating output probability amplitudes of universal quantum circuits. Our
algorithm allows us to approximate a certain output probability amplitude of a
quantum circuit when the corresponding graph has bounded degree and the
interactions and external fields are absolutely bounded close to zero. Eldar
and Mehraban Eldar and Mehraban (2018) used a similar approach to derive a
quasi-polynomial time algorithm for approximating the permanent of a random
matrix with unit variance and vanishing mean in the context of linear optical
quantum computing.

This paper is structured as follows. In Section II, we introduce the
multivariate graph homomorphism partition function and establish a
deterministic polynomial-time algorithm for approximating a restricted version
of this partition function on bounded degree graphs when the matrix entries
are absolutely bounded close to one. In Section III, we provide an
approximation-preserving polynomial-time reduction from the Ising model
partition function to this restricted version of the multivariate graph
homomorphism partition function. We then use this reduction to establish a
deterministic polynomial-time approximation scheme for the Ising model
partition function on bounded degree graphs when the interactions and external
fields are absolutely bounded sufficiently close to zero. In this regime, we
prove that the partition function does not vanish. In Section IV, we show how
our algorithm can be extended to approximate certain output probability
amplitudes of quantum circuits. Finally, we conclude in Section V with some
remarks and open problems.

##  II Graph Homomorphism Partition Functions

A _graph homomorphism_ between two graphs $G$ and $H$ is an adjacency-
preserving map between the vertex sets, i.e., a map $h:V(G)\to V(H)$ such that
$\\{u,v\\}\in E(G)$ implies $\\{h(u),h(v)\\}\in E(H)$. Graph homomorphisms
generalise the notion of graph colouring Hell and Nešetřil (2004); for
example, a graph homomorphism from a graph $G$ to the complete graph $K_{q}$
is equivalent to a proper $q$-colouring of $G$.

Hell and Nešetřil Hell and Nešetřil (1990) proved that the problem of deciding
if a homomorphism between two graphs $G$ and $H$ exists is NP-complete. Dyer
and Greenhill Dyer and Greenhill (2000) showed that the corresponding counting
problem is #P-hard, unless the graph has some special structure; otherwise it
is in P. Furthermore, they showed that this problem remains #P-hard when
restricted to graphs of bounded degree. The _graph homomorphism partition
function_ is defined as follows.

######  Definition 1 (Graph homomorphism partition function).

Let $G=(V,E)$ be a graph and let $A=(a_{ij})_{m\times m}$ be a $m\times m$
symmetric matrix. Then the graph homomorphism partition function is defined by

$\displaystyle\mathrm{Hom}(G;A):=\sum_{\phi:V\to[m]}\prod_{\\{u,v\\}\in
E}a_{\phi(u)\phi(v)}.$

The graph homomorphism partition function evaluates to many important
combinatorial quantities, including counting the number of graph
homomorphisms, proper colourings, and independent sets Barvinok (2016b).

The complexity of computing graph homomorphism partition functions has been
widely studied. Dyer and Greenhill Dyer and Greenhill (2000) showed that
computing $\mathrm{Hom}(G;A)$ when $A$ is a fixed symmetric binary matrix is
either in P or #P-hard. Moreover, they showed that these hardness results hold
even for graphs of maximum degree three. These results were later generalised
to non-negative symmetric matrices Bulatov and Grohe (2005), real symmetric
matrices Goldberg  _et al._ (2010), and complex symmetric matrices Cai  _et
al._ (2010). Furthermore, the tractability criterion for the matrix is
decidable in polynomial time.

The graph homomorphism partition function can be generalised by assigning a
$m\times m$ symmetric matrix to each edge. The _multivariate graph
homomorphism partition function_ is defined as follows.

######  Definition 2 (Multivariate graph homomorphism partition function).

Let $G=(V,E)$ be a graph with the $m\times m$ symmetric matrices
$\mathcal{A}=\\{(a_{ij}^{e})_{m\times m}\\}_{e\in E}$ assigned to its edges.
Then the multivariate graph homomorphism partition function is defined by

$\displaystyle\mathrm{Hom}_{\mathrm{M}}(G;\mathcal{A}):=\sum_{\phi:V\to[m]}\prod_{\\{u,v\\}\in
E}a_{\phi(u)\phi(v)}^{\\{u,v\\}}.$

When the matrices are all equal, it is clear that the multivariate and
standard graph homomorphism partition functions are equivalent.

For convenience, let us define the polydisc consisting of all sets of $m\times
m$ symmetric matrices with matrix entries absolutely bounded close to one.

######  Definition 3 ($\mathcal{D}_{G,m}(\delta)$).

For a graph $G=(V,E)$, $m\in\mathbb{Z}^{+}$, and $\delta>0$, we define
$\mathcal{D}_{G,m}(\delta)$ to be the closed polydisc consisting of all sets
of $m\times m$ symmetric matrices $\mathcal{A}=\\{(a_{ij}^{e})_{m\times
m}\\}_{e\in E}$, such that $\left|1-a_{ij}^{e}\right|\leq\delta$ for all $e\in
E$ and all $i,j\in[m]$.

Barvinok and Soberón Barvinok and Soberón (2017) gave a quasi-polynomial time
algorithm for approximating $\mathrm{Hom}_{\mathrm{M}}(G;\mathcal{A})$ when
$G$ is a graph of maximum degree at most $\Delta$ and $\mathcal{A}$ lies in
the interior of the closed polydisc
$\mathcal{D}_{G,m}\left(\delta_{\Delta}\right)$. Here, $\delta_{\Delta}>0$ is
an absolute constant. The absolute constants come from Barvinok’s monograph
Barvinok (2016b), where a simpler proof was presented with better constants.
Patel and Regts Patel and Regts (2017) improved this algorithm to run in
polynomial time.

######  Definition 4 ($\delta_{\Delta}$).

For $\Delta\in\mathbb{Z}^{+}$, we define the absolute constant
$\delta_{\Delta}$ by

$\displaystyle\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].$

######  Remark.

A simple numerical search gives $\delta_{3}=0.18$, $\delta_{4}=0.13$,
$\delta_{5}=0.11$, and $\delta_{6}=0.09$. In general, we have
$\delta_{\Delta}=\Omega(1/\Delta)$.

We shall consider a restricted version of the multivariate graph homomorphism
partition function, in which the sum is restricted to map a subset of vertices
to a fixed index.

######  Definition 5 (Restricted multivariate graph homomorphism partition
function).

Let $G=(V,E)$ be a graph with the $m\times m$ symmetric matrices
$\mathcal{A}=\\{(a_{ij}^{e})_{m\times m}\\}_{e\in E}$ assigned to its edges.
Further let $S\subseteq V$ be a subset of $V$ and let $k\in[m]$ be an integer.
Then the restricted multivariate graph homomorphism partition function is
defined by

$\displaystyle\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A}):=\sum_{\begin{subarray}{c}\phi:V\to[m]\\\
\phi(s)=k,\forall s\in S\end{subarray}}\prod_{\\{u,v\\}\in
E}a_{\phi(u)\phi(v)}^{\\{u,v\\}}.$

The advantage of considering the restricted multivariate graph homomorphism
partition function is that, when reduced from the Ising partition function, it
will allows us to implement an external magnetic field. This reduction is
described in detail in Appendix D.

We extend the results of Barvinok and Soberón Barvinok and Soberón (2017) and
Patel and Regts Patel and Regts (2017) to give a deterministic polynomial-time
approximation scheme for the restricted multivariate graph homomorphism
partition function. We have the following theorem.

######  Theorem 1
(restate=[name=restatement]GraphHomomorphismPartitionFunctionBoundedDegreeGraphs).

Fix $\Delta\in\mathbb{Z}^{+}$ and $0<\delta<\delta_{\Delta}$. There is a
deterministic polynomial-time approximation scheme for the restricted
multivariate graph homomorphism partition function
$\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A})$ for all graphs $G=(V,E)$ of
maximum degree at most $\Delta$ and all $\mathcal{A}=\\{(a_{ij}^{e})_{m\times
m}\\}_{e\in E}$ in the closed polydisc $\mathcal{D}_{G,m}\left(\delta\right)$.

We prove Theorem 1 in Appendix A. Our proof requires a result of Barvinok
(Barvinok, 2016b, Theorem 7.1.4), which states that
$\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A})$ does not vanish on graphs of
maximum degree at most $\Delta$ when $\mathcal{A}$ lies in the interior of the
closed polydisc $\mathcal{D}_{G,m}\left(\delta_{\Delta}\right)$.

######  Lemma 2 (Barvinok Barvinok (2016b)).

Fix $\Delta\in\mathbb{Z}^{+}$. For any graph $G=(V,E)$ of degree at most
$\Delta$ and any $\mathcal{A}=\\{(a_{ij}^{e})_{m\times m}\\}_{e\in E}$ in the
closed polydisc $\mathcal{D}_{G,m}\left(\delta_{\Delta}\right)$, the
restricted multivariate graph homomorphism partition function does not vanish,
i.e., $\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A})\neq 0$ for all $S\subseteq
V$ and all $k\in[m]$.

Our proof also requires the following lemma, which states that we can
efficiently compute the constant term and inverse power sums of the roots of
$\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A}(z))$.

######  Lemma 3
(restate=[name=restatement]GraphHomomorphismPartitionFunctionComputeConstantTermAndInversePowerSums).

Fix $\Delta\in\mathbb{Z}^{+}$, $0<\epsilon<1$, and $C>0$. Let $G=(V,E)$ be a
graph of maximum degree at most $\Delta$ with the $m\times m$ symmetric
matrices $\mathcal{A}(z)=\\{(1+z(a_{ij}^{e}-1))_{m\times m}\\}_{e\in E}$
assigned to its edges. Further let $\\{r_{i}\\}_{i=1}^{\left|E\right|}$ be the
roots of the polynomial
$P(G,S,k;z):=\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A}(z))$. Then there is a
deterministic $(\left|V\right|/\epsilon)^{O(1)}$-time algorithm for computing
$P(G,S,k,0)$ and the inverse power sums
$\left\\{\sum_{i=1}^{\left|E\right|}r_{i}^{-j}\right\\}_{j=1}^{m}$ for
$m=C\log(\left|V\right|/\epsilon)$.

We prove Lemma 3 in Appendix B. For convenience, let us define the closed disc
$D$ of radius $\delta$ centred at the origin.

######  Definition 6 ($D(\delta)$).

For $\delta>0$, we define $D(\delta)$ to be the closed disc consisting of all
complex numbers $z$, such that $\left|z\right|\leq\delta$.

Finally, we require the following lemma, which arises from the error analysis
of Barvinok’s interpolation method Barvinok (2015, 2016a) (see Barvinok
(Barvinok, 2016b, Lemma 2.2.1)). The lemma states that, in order to get a
multiplicative approximation to a polynomial inside its zero-free disc, it is
sufficient to compute the constant term and inverse power sums of its roots.

######  Lemma 4 (name=Barvinok Barvinok (2015, 2016a, 2016b),
restate=[name=restatement]ApproximatePolynomialZeroFreeRegionInversePowerSums).

Fix $0<\epsilon<1$. Let $\\{r_{i}\\}_{i=1}^{n}$ be the roots of the polynomial
$p(z):=\sum_{k=0}^{n}a_{k}z^{k}$. Suppose that, for some $\delta>0$, the roots
of $p$ lie in the exterior of the closed disc $D(\delta)$. Suppose further
that we can compute $a_{0}$ and the inverse power sums
$\left\\{\sum_{i=1}^{n}r_{i}^{-j}\right\\}_{j=1}^{m}$ in time $\tau(m)$. Then,
for any $t$ in the interior of the closed disc $D(\delta)$, we can compute a
multiplicative $\epsilon$-approximation to $p(t)$ in time
$O\left[\tau\left(\frac{\log(n/\epsilon)}{1-\left|t\right|/\delta}\right)\right]$.

We prove Lemma 4 in Appendix C.

##  III Ising Model Partition Functions

The Ising model is described by a graph $G=(V,E)$, with the vertices
representing spins and the edges representing interactions between them. A set
of edge weights $\\{\omega_{e}\\}_{e\in E}$ characterise the interactions and
a set of vertex weights $\\{\upsilon_{v}\\}_{v\in V}$ characterise the
external fields at each spin. A configuration of the model is an assignment
$\sigma$ of each spin to one of two possible states $\\{-1,+1\\}$. The _Ising
model partition function_ is defined as follows.

######  Definition 7 (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

$\displaystyle\mathrm{Z}_{\mathrm{Ising}}(G;\Omega,\Upsilon):=\sum_{\sigma\in\\{-1,+1\\}^{V}}w_{G}(\sigma),$

where

$\displaystyle 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).$

The model is called _ferromagnetic_ if $\omega_{e}>0$ for all $e\in E$ and
_anti-ferromagnetic_ if $\omega_{e}<0$ for all $e\in E$. Otherwise, the model
is called _non-ferromagnetic_.

A classic result of Jerrum and Sinclair Jerrum and Sinclair (1993) establishes
a fully polynomial-time randomised approximation scheme for the Ising model
partition function for all graphs in the ferromagnetic regime with real vertex
weights. In contrast, they showed that no such scheme could exists in the
anti-ferromagnetic regime unless RP=NP. Furthermore, they showed that exactly
computing the Ising model partition function is #P-hard.

We shall extend the result of Theorem 1 to the Ising model partition function.
This is achieved by an approximation-preserving polynomial-time reduction from
the Ising model partition function to the restricted multivariate graph
homomorphism partition function.

######  Proposition 5
(restate=[name=restatement]IsingModelGraphHomomorphismPartitionFunctionReduction).

There is an approximation-preserving polynomial-time reduction from the Ising
model partition function to the restricted multivariate graph homomorphism
partition function.

We prove Proposition 5 in Appendix D. Let us define the following closed
polyregion, which arises naturally from applying Proposition 5 to Theorem 1.

######  Definition 8 ($\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 $\left|1-e^{\pm\omega_{e}}\right|\leq\delta$ for all $e\in E$ and
$\left|1-e^{\pm\upsilon_{v}}\right|\leq\delta$ for all $v\in V$.

We have the following corollary of Theorem 1 and Proposition 5.

######  Corollary 6.

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)$.

###### Proof.

The proof follows directly from Theorem 1 and Proposition 5, while noting that
the reduction from the Ising model partition to the restricted multivariate
graph homomorphism partition function increases the maximum vertex degree by
one. ∎

######  Remark.

It is possible to marginally increase the size of the polyregion by applying
the _$k$ -thickening_ technique of Jaeger, Vertigan, and Welsh Jaeger  _et
al._ (1990).

It is important to mention that the bounds of Corollary 6 are not sharp in
general. To see this, let us compare the results in the anti-ferromagnetic
regime with no external field, to those of Sinclair, Srivastava, and Thurley
Sinclair  _et al._ (2014). In this case, Corollary 6 tells us that there is a
deterministic polynomial-time approximation scheme for the Ising model
partition function on graphs of maximum degree at most $\Delta$ when
$\omega_{e}>-\log(\delta_{\Delta}+1)$ for all $e\in E$ (noting that in the
case of no external field the reduction preserves maximum degree). The results
of Sinclair, Srivastava, and Thurley Sinclair  _et al._ (2014) give a
deterministic polynomial-time approximation scheme when $\Delta\geq 3$ and
$\omega_{e}>-\frac{1}{2}\log\left(\frac{\Delta}{\Delta-2}\right)$ for all
$e\in E$. Hence, the bound of Corollary 6 is not sharp. It is an open problem
to prove a sharp bound in the complex case.

We also have the following corollary concerning the location of the complex
zeros of the Ising model partition function on bounded degree graphs.

######  Corollary 7.

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)\neq 0$.

###### Proof.

The proof follows directly from Lemma 2 and Proposition 5. ∎

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 Sokal  _et al._ (2005).

##  IV Quantum Simulation

Complex-valued Ising model partition functions arise naturally in the output
probability amplitudes of quantum circuits De las Cuevas  _et al._ (2011);
Iblisdir  _et al._ (2014). In particular, for the class of commuting quantum
circuits, known as _Instantaneous Quantum Polynomial-time_ (IQP) circuits
Shepherd and Bremner (2009); Shepherd (2010); Fujii and Morimae (2017). In
this section we shall show how the results of Corollary 6 allow us to
approximate output probability amplitudes of IQP circuits and, more generally,
universal quantum circuits. First introduced by Shepherd and Bremner Shepherd
and Bremner (2009), IQP circuits comprise only gates that are diagonal in the
Pauli-X basis. An IQP circuit is described by an _X-program_.

######  Definition 9 (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,

$\displaystyle\mathrm{H}_{(P,\theta)}:=-\theta\sum_{i=1}^{m}\bigotimes_{j=1}^{n}X_{j}^{p_{ij}}.$

Thus, the columns of $P$ correspond to qubits and the rows of $P$ correspond
to interactions in the Hamiltonian.

An X-program induces a probability distribution $\mathcal{P}_{(P,\theta)}$
known as an _IQP distribution_.

######  Definition 10 ($\mathcal{P}_{(P,\theta)}$).

For an X-program $(P,\theta)$ with $P=(p_{ij})_{m\times n}$, we define
$\mathcal{P}_{(P,\theta)}$ to be the probability distribution over binary
strings $x\in\\{0,1\\}^{n}$, given by

$\displaystyle\textbf{Pr}[x]:=\left|\left<x\right|\exp\left(-i\mathrm{H}_{(P,\theta)}\right)\left|0^{n}\right>\right|^{2}.$

We shall consider X-programs that are induced by a weighted graph.

######  Definition 11 (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

$\displaystyle\mathrm{H}_{\mathcal{X}_{G}}=-\sum_{\\{u,v\\}\in
E}\omega_{\\{u,v\\}}X_{u}X_{v}-\sum_{v\in V}\upsilon_{v}X_{v}.$

It will be convenient for us to define $\psi_{G}$ as a specific probability
amplitude induced by a weighted graph $G$.

######  Definition 12 ($\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

$\displaystyle\psi_{G}:=\left<0^{\left|V\right|}\right|\exp\left(-i\mathrm{H}_{\mathcal{X}_{G}}\right)\left|0^{\left|V\right|}\right>.$

We note that any X-program can be efficiently represented by a graph-induced
X-program Shepherd and Bremner (2009). Moreover, X-programs are known to
become universal for quantum computation under postselection Bremner  _et al._
(2010). 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.

######  Proposition 8
(restate=[name=restatement]IQPIsingModelPartitionFunctionRelation).

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,

$\displaystyle\psi_{G}=\frac{1}{2^{\left|V\right|}}\mathrm{Z}_{\mathrm{Ising}}(G;i\Omega,i\Upsilon).$

We prove Proposition 8 in Appendix E. We now apply Corollary 6 to Proposition
8 to achieve a deterministic polynomial-time approximation scheme for
computing $\psi_{G}$ for all graphs of bounded maximum degree with weights
absolutely bounded sufficiently close to zero.

######  Corollary 9.

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 $\left|\omega_{e}\right|\leq 2\arcsin(\delta/2)$ for all $e\in
E$ and the vertex weights $\left\\{\upsilon_{v}\in[-\pi,\pi]\right\\}_{v\in
V}$ satisfying $\left|\upsilon_{v}\right|\leq 2\arcsin(\delta/2)$ for all
$v\in V$.

###### Proof.

It follows from Corollary 6 and Proposition 8 that we have a deterministic
polynomial-time approximation scheme for computing $\psi_{G}$ for all graphs
of maximum degree at most $\Delta$ with $\Omega=\\{i\omega_{e}\\}_{e\in E}$
and $\Upsilon=\\{i\upsilon_{v}\\}_{v\in V}$ in the closed polyregion
$\mathcal{R}_{G}\left(\delta\right)$. For weights in the range $[-\pi,\pi]$,
this is achieved when $\left|\omega_{e}\right|\leq 2\arcsin(\delta/2)$ for all
$e\in E$ and $\left|\upsilon_{v}\right|\leq 2\arcsin(\delta/2)$ for all $v\in
V$. This completes the proof. ∎

It is known that approximating $\psi_{G}$ up to a multiplicative factor for
bounded degree graphs with arbitrary weights in $[-\pi,\pi]$ is #P-hard Fujii
and Morimae (2017), and so it seems unlikely that Corollary 9 can be extended
to hold in this case. We note that Corollary 9 applies to graph-induced
X-programs with weights absolutely bounded by a constant that depends only on
the maximum degree of the underlying graph. This corresponds to Hamiltonians
that have been evolved for up to a constant time and Hamiltonians that exhibit
limited interference. Furthermore, Corollary 9 applies to classes of graphs
with treewidth growing as the square root of the number of vertices; for
example, square lattices. For classes of graphs with logarithmic treewidth a
deterministic polynomial-time algorithm is known Markov and Shi (2008).

##  V Conclusion & Outlook

We have established a deterministic polynomial-time approximation scheme for
the Ising model partition function with complex parameters on bounded degree
graphs when the interactions and external fields are absolutely bounded by a
constant depending on the maximum degree of the graph. Furthermore, we have
proven that the partition function does not vanish for this class of Ising
models. Finally, we have shown how our algorithm can be extended to
approximate certain output probability amplitudes of quantum circuits.

There are a number of interesting problems that remain to be solved, the most
obvious of which is to sharpen the bounds of Corollary 6. One approach would
be to improve Lemma 2, i.e., prove that the restricted multivariate graph
homomorphism partition function does not vanish on a polydisc of a greater
radius. It may also be possible to prove sharper bounds for specific graphs of
interest. An alternative approach would be to use decay of correlation based
arguments Weitz (2006); Sly (2010); Sinclair  _et al._ (2014). It is an
important open problem to understand the relationship between the location of
complex zeros, decay of correlations, and the computational complexity of a
function. The work of Liu, Sinclair, and Srivastava Liu  _et al._ (2018) makes
significant progress towards resolving this problem.

## Acknowledgements

We thank Gavin Brennen, Jacob Bridgeman, Christopher Chubb, David Gosset,
Richard Jozsa, and Hakop Pashayan for helpful discussions. This research was
conducted by the ARC Centre of Excellence for Quantum Computation and
Communication Technology (CQC2T), project number CE170100012.

##  Appendix A Proof of Theorem 1

We shall now prove Theorem 1.

*

###### Proof.

Define $P(G,S,k;z):=\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A}(z))$, with
$\mathcal{A}(z)=\\{(1+z(a_{ij}^{e}-1))_{m\times m}\\}_{e\in E}$ and note that
$\mathcal{A}=\mathcal{A}(1)$. By Lemma 2, we have that $P(G,S,k;z)$ does not
vanish whenever $\mathcal{A}(z)$ lies in the closed polydisc
$\mathcal{D}_{G,m}(\delta_{\Delta})$. Since $\mathcal{A}(1)$ lies in the
closed polydisc $\mathcal{D}_{G,m}(\delta)$, $P(G,S,k;z)$ does not vanish for
all $\left|z\right|\leq\delta_{\Delta}/\delta$. Let
$\\{r_{i}\\}_{i=1}^{\left|E\right|}$ be the roots of $P(G,S,k;z)$. Then, by
setting $C=(1-\delta/\delta_{\Delta})^{-1}$ in Lemma 3, we have that, for any
$0<\epsilon<1$, there is a deterministic
$(\left|V\right|/\epsilon)^{O(1)}$-time algorithm for computing $P(G,S,k;0)$
and the inverse power sums
$\left\\{\sum_{i=1}^{\left|E\right|}r_{i}^{-j}\right\\}_{j=1}^{m}$ for
$m=(1-\delta/\delta_{\Delta})^{-1}\log(\left|V\right|/\epsilon)$. Then, it
follows from Lemma 4 that there is a deterministic
$(\left|V\right|/\epsilon)^{O(1)}$-time algorithm for computing a
multiplicative $\epsilon$-approximation to $P(G,S,k;z)$ for all
$\left|z\right|<\delta_{\Delta}/\delta$. Since $\delta<\delta_{\Delta}$, we
can take $z=1$. Hence, we have a deterministic polynomial-time algorithm for
computing a multiplicative $\epsilon$-approximation to
$\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A})$. This completes the proof. ∎

##  Appendix B Proof of Lemma 3

We shall now prove Lemma 3. Our proof follows from a generalisation of a
result due to Patel and Regts Patel and Regts (2017) (Lemma 11) and an
additional lemma (Lemma 12), which we prove in the remainder of the section. *

###### Proof.

The proof follows from combining Lemma 11 and Lemma 12. ∎

We shall begin with the following definitions.

######  Definition 13 ($\mathcal{G}_{n}$).

For $n\in\mathbb{Z}^{+}$, define $\mathcal{G}_{n}$ to be the collection of all
edge-coloured graphs on at most $n$ vertices.

######  Definition 14 ($G[U]$).

For a graph $G$ and a subset of vertices $U\subseteq V(G)$, define $G[U]$ to
be the subgraph induced by $U$.

######  Definition 15 ($\mathrm{Ind}_{\mathrm{C}}(G,H)$).

For two edge-coloured graphs $G$ and $H$, define
$\mathrm{Ind}_{\mathrm{C}}(G,H)$ to be the number of induced subgraphs of $G$
that are edge-colour isomorphic to $H$.

######  Definition 16 (Multiplicative graph polynomial).

A graph polynomial $P(G;z)$ is said to be multiplicative if
$P(\varnothing;z)=1$ and $P(G\cup H;z)=P(G;z)P(H;z)$ for any two graphs $G$
and $H$.

######  Definition 17 (Edge-coloured bounded induced graph counting polynomial
Patel and Regts (2017)).

Let $P(G;z)$ be a multiplicative graph polynomial defined by
$P(G;z):=\sum_{n=0}^{d(G)}\alpha_{G,n}z^{n}$ with $P(G;0)=1$. We say that
$P(G;z)$ is an edge-coloured bounded induced graph counting polynomial if
there exists constants $\mu,\nu\in\mathbb{Z}^{+}$, such that (1) the
coefficients $\alpha_{G,n}$ satisfy $\alpha_{G,n}=\sum_{H\in\mathcal{G}_{\mu
n}}\beta_{H,n}\mathrm{Ind}(H,G)$, for certain $\beta_{H,n}$ and (2) the
coefficients $\beta_{H,n}$ can be computed in time
$O\left(\nu^{\left|V(H)\right|}\right)$.

Patel and Regts (Patel and Regts, 2017, Theorem 3.10) proved that, for any
edge-coloured bounded induced graph counting polynomial, there is an efficient
algorithm for computing the constant term and inverse power sums of its roots.

######  Lemma 10 (Patel and Regts Patel and Regts (2017)).

Fix $\Delta\in\mathbb{Z}^{+}$, $0<\epsilon<1$, and $C>0$. Let $G=(V,E)$ be an
edge-coloured graph of maximum degree at most $\Delta$. Further let $P(G;z)$
be an edge-coloured bounded induced graph counting polynomial with roots
$\\{r_{i}\\}_{i=1}^{\deg(P)}$. Then there is a deterministic
$(\left|V\right|/\epsilon)^{O(1)}$-time algorithm for computing $P(G,0)$ and
the inverse power sums
$\left\\{\sum_{i=1}^{\deg(P)}r_{i}^{-j}\right\\}_{j=1}^{m}$ for
$m=C\log(\left|V\right|/\epsilon)$.

We shall now generalise the result of Patel and Regts Patel and Regts (2017)
to the restricted case, that is, where the graph polynomial is restricted to
map a subset of vertices to a fixed index. We begin by extending the previous
definitions.

######  Definition 18 (Restricted graph).

A restricted graph is a pair $(G,S)$, where $G=(V,E)$ is a graph and
$S\subseteq V$ is a subset of $V$.

######  Definition 19 ($\mathcal{R}_{n}$).

For $n\in\mathbb{Z}^{+}$, define $\mathcal{R}_{n}$ to be the collection of all
edge-coloured restricted graphs on at most $n$ vertices.

######  Definition 20 (Induced restricted subgraph).

For a restricted graph $(G,S)$ and a subset of vertices $U\subseteq V(G)$, the
restricted subgraph induced by $U$ is given by $(G[U],S\cap U)$.

######  Definition 21 (Isomorphic restricted graphs).

Two restricted graphs $(G,S)$ and $(H,T)$ are said to be isomorphic if and
only if there is an isomorphism $\varphi$ from $G$ to $H$ and $T$ is the image
of $S$ under $\varphi$.

######  Definition 22 ($\mathrm{Ind}_{\mathrm{C}}\left[(G,S),(H,T)\right]$).

For two edge-coloured restricted graphs $(G,S)$ and $(H,T)$, define
$\mathrm{Ind}_{\mathrm{C}}\left[(G,S),(H,T)\right]$ to be the number of
induced restricted subgraphs of $(G,S)$ that are edge-colour isomorphic to
$(H,T)$.

######  Definition 23 (Multiplicative restricted graph polynomial).

A restricted graph polynomial $P(G,S,k;z)$ is said to be multiplicative if
$P(\varnothing,\varnothing,k;z)=1$ and $P(G\cup H,S\cup
T,k;z)=P(G,S,k;z)P(H,T,k;z)$ for any two restricted graphs $(G,S)$ and $(H,T)$
and integer $k\in\mathbb{Z}^{+}$.

######  Definition 24 (Edge-coloured bounded induced restricted graph counting
polynomial).

Let $P(G,S,k;z)$ be a multiplicative restricted graph polynomial defined by
$P(G,S,k;z):=\sum_{n=0}^{d(G)}\alpha_{G,S,k,n}z^{n}$ with $P(G,S,k;0)=1$. We
say that $P(G,S,k;z)$ is an edge-coloured bounded induced restricted graph
counting polynomial if there exists constants $\mu,\nu\in\mathbb{Z}^{+}$, such
that (1) the coefficients $\alpha_{G,S,k,n}$ satisfy
$\alpha_{G,S,k,n}=\sum_{(H,T)\in\mathcal{R}_{\mu
n}}\beta_{H,T,k,n}\mathrm{Ind}_{\mathrm{C}}\left[(G,S),(H,T)\right]$, for
certain $\beta_{H,T,k,n}$ and (2) the coefficients $\beta_{H,T,k,n}$ can be
computed in time $O\left(\nu^{\left|V(H)\right|}\right)$.

The restricted version of Lemma 10 is then obtained by following the proof of
Patel and Regts Patel and Regts (2017) with the definitions extended in the
natural way. We omit the proof for the sake of brevity.

######  Lemma 11.

Fix $\Delta\in\mathbb{Z}^{+}$, $0<\epsilon<1$, and $C>0$. Let $G=(V,E)$ be an
edge-coloured graph of maximum degree at most $\Delta$. Further let
$P(G,S,k;z)$ be an edge-coloured bounded induced restricted graph counting
polynomial with roots $\\{r_{i}\\}_{i=1}^{\deg(P)}$. Then there is a
deterministic $(\left|V\right|/\epsilon)^{O(1)}$-time algorithm for computing
$P(G,S,k,0)$ and the inverse power sums
$\left\\{\sum_{i=1}^{\deg(P)}r_{i}^{-j}\right\\}_{j=1}^{m}$ for
$m=C\log(\left|V\right|/\epsilon)$.

######  Lemma 12.

Let $G=(V,E)$ be a graph with the $m\times m$ symmetric matrices
$\mathcal{A}(z)=\\{(1+z(a_{ij}^{e}-1))_{m\times m}\\}_{e\in E}$ assigned to
its edges and let each edge $e\in E$ be assigned a distinct colour. Further
let $S\subseteq V$ be a subset of $V$ and let $k\in[m]$ be an integer. Then,
up to an efficiently computable factor, the restricted multivariate graph
homomorphism partition function
$\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A}(z))$ is an edge-coloured bounded
induced graph counting polynomial.

###### Proof.

Define $P(G,S,k;z)$ by

$\displaystyle P(G,S,k;z):=m^{-\left|V\setminus
S\right|}\mathrm{Hom}_{\mathrm{M}}(G,S,k;\mathcal{A}(z)).$

Then,

$\displaystyle P(G,S,k;z)$ $\displaystyle=m^{-\left|V\setminus
S\right|}\sum_{\begin{subarray}{c}\phi:V\to[m]\\\ \phi(s)=k,\forall s\in
S\end{subarray}}\prod_{\\{u,v\\}\in
E}\left[1+z\left(a_{\phi(u)\phi(v)}^{\\{u,v\\}}-1\right)\right]$
$\displaystyle=m^{-\left|V\setminus
S\right|}\sum_{n=0}^{\left|E\right|}z^{n}\sum_{\begin{subarray}{c}F\subseteq
E\\\
\left|F\right|=n\end{subarray}}\left[\sum_{\begin{subarray}{c}\phi:V\to[m]\\\
\phi(s)=k,\forall s\in S\end{subarray}}\prod_{\\{u,v\\}\in
F}\left(a_{\phi(u)\phi(v)}^{\\{u,v\\}}-1\right)\right]$
$\displaystyle=\sum_{n=0}^{\left|E\right|}z^{n}\sum_{\begin{subarray}{c}F\subseteq
E\\\ \left|F\right|=n\end{subarray}}\left[m^{-\left|V(G[F])\setminus
S\right|}\sum_{\begin{subarray}{c}\phi:V(G[F])\to[m]\\\ \phi(s)=k,\forall
s\in(S\cap V(G[F]))\end{subarray}}\prod_{\\{u,v\\}\in
F}\left(a_{\phi(u)\phi(v)}^{\\{u,v\\}}-1\right)\right],$

where $G[F]$ is the subgraph of $G$ induced by $F$. Since the number of
vertices in $G[F]$ is at most $2\left|F\right|$, we can write

$\displaystyle
P(G,S,k;z)=\sum_{n=0}^{\left|E\right|}z^{n}\sum_{\begin{subarray}{c}(H,T)\in\mathcal{R}_{2n}\\\
\left|E(H)\right|=n\end{subarray}}\left[m^{-\left|V(H)\setminus
T\right|}\sum_{\begin{subarray}{c}\phi:V(H)\to[m]\\\ \phi(t)=k,\forall t\in
T\end{subarray}}\prod_{\\{u,v\\}\in
E(H)}\left(a_{\phi(u)\phi(v)}^{\\{u,v\\}}-1\right)\right]\mathrm{Ind}_{\mathrm{C}}\left[(G,S),(H,T)\right].$

Therefore, we have

$\displaystyle P(G,S,k;z)=\sum_{n=0}^{\left|E\right|}\alpha_{G,S,k,n}z^{n},$

with

$\displaystyle\alpha_{G,S,k,n}=\sum_{\begin{subarray}{c}(H,T)\in\mathcal{R}_{2n}\\\
\left|E(H)\right|=n\end{subarray}}\beta_{H,T,k,n}\mathrm{Ind}_{\mathrm{C}}\left[(G,S),(H,T)\right]$

and

$\displaystyle\beta_{H,T,k,n}=m^{-\left|V(H)\setminus
T\right|}\sum_{\begin{subarray}{c}\phi:V(H)\to[m]\\\ \phi(t)=k,\forall t\in
T\end{subarray}}\prod_{\\{u,v\\}\in
E(H)}\left(a_{\phi(u)\phi(v)}^{\\{u,v\\}}-1\right).$

It is clear that $P(G,S,k;z)$ is a multiplicative restricted graph polynomial
with $P(G,S,k;0)=1$. Furthermore, for any restricted graph
$(H,T)\in\mathcal{R}_{2n}$, the coefficients $\beta_{H,T,k,n}$ can be computed
in time $O\left(m^{\left|V(H)\setminus S\right|}\right)$. Hence, $P(G,S,k;z)$
is an edge-coloured bounded induced restricted graph counting polynomial with
constants $\mu=2$ and $\nu=m$. This completes the proof. ∎

##  Appendix C Proof of Lemma 4

We shall now prove Lemma 4. The lemma is due to Barvinok Barvinok (2015,
2016a, 2016b), however, our proof closely follows that of Patel and Regts
Patel and Regts (2017). *

###### Proof.

Define the function $f(z)$ on the closed disc $D(\delta)$ by

$\displaystyle f(z):=\log(p(z)),$

where the branch of the logarithm is chosen by taking the principal value at
$p(0)$. By Taylor’s Theorem about the point $t=0$, for each $t$ in the
interior of the closed disc $D(\delta)$,

$\displaystyle f(t)=\sum_{j=0}^{\infty}\frac{t^{j}}{j!}f^{(j)}(0).$

Define the Taylor expansion truncated at order $m$ by

$\displaystyle T_{m}(f)(t):=f(0)+\sum_{j=1}^{m}\frac{t^{j}}{j!}f^{(j)}(0).$

Now, let us write $p(z)$ in terms of its roots. By the Factor Theorem,

$\displaystyle p(z)=a_{n}\prod_{i=1}^{n}(z-r_{i}).$

Then,

$\displaystyle f(z)=\log(a_{n})+\sum_{i=1}^{n}\log(z-r_{i}).$

Therefore,

$\displaystyle f^{(j)}(0)=-(j-1)!\sum_{i=1}^{n}r_{i}^{-j}.$

Let $s_{j}$ be the $j^{\mathrm{th}}$ inverse power sum given by

$\displaystyle s_{j}:=\sum_{i=1}^{n}r_{i}^{-j}.$

Then, by noting that $f(0)=\log(a_{0})$,

$\displaystyle T_{m}(f)(t)=\log(a_{0})-\sum_{j=1}^{m}\frac{s_{j}t^{j}}{j}.$

We shall now show that, for any $0<\epsilon<1$, the Taylor expansion truncated
at order $m=O(\log(n/\epsilon))$ gives an additive $\epsilon$-approximation to
$f(t)$.

$\displaystyle\left|f(t)-T_{m}(f)(t)\right|$
$\displaystyle\leq\left|\sum_{j=m+1}^{\infty}\frac{s_{j}t^{j}}{j}\right|$
$\displaystyle\leq\frac{1}{m+1}\sum_{j=m+1}^{\infty}\left|s_{j}t^{j}\right|.$

Since the roots $\\{r_{i}\\}_{i=1}^{n}$ lie in the exterior of the closed disc
$D(\delta)$, we have $\left|s_{j}\right|<n/\delta^{j}$. Therefore,

$\displaystyle\left|f(t)-T_{m}(f)(t)\right|\leq\frac{n}{m+1}\sum_{j=m+1}^{\infty}\left(\frac{\left|t\right|}{\delta}\right)^{j}.$

Since $\left|t\right|<\delta$, by the geometric series formula,

$\displaystyle\left|f(t)-T_{m}(f)(t)\right|\leq\frac{n(\left|t\right|/\delta)^{m+1}}{(m+1)(1-\left|t\right|/\delta)}.$

Taking $m=(1-\left|t\right|/\delta)^{-1}\log(n/\epsilon)$, it follows that

$\displaystyle\left|f(t)-T_{m}(f)(t)\right|\leq\epsilon.$

We shall now show that the truncated Taylor expansion is a multiplicative
$\epsilon$-approximation to $p(t)$. For the norm, we have

$\displaystyle\left|e^{T_{m}(f)(t)-f(t)}\right|$ $\displaystyle\leq
e^{\left|T_{m}(f)(t)-f(t)\right|}$ $\displaystyle\leq e^{\epsilon},$

and

$\displaystyle\left|e^{f(t)-T_{m}(f)(t)}\right|\leq e^{\epsilon}.$

Now, for the argument,

$\displaystyle\left|\operatorname{Arg}\left(e^{T_{m}(f)(t)-f(t)}\right)\right|$
$\displaystyle=\left|\operatorname{Im}\left[\log\left(e^{f(t)-T_{m}(f)(t)}\right)\right]\right|$
$\displaystyle\leq\left|\log\left(e^{f(t)-T_{m}(f)(t)}\right)\right|$
$\displaystyle\leq\epsilon.$

This completes the proof. ∎

##  Appendix D Proof of Proposition 5

We shall now prove Proposition 5. *

###### Proof.

Let $G=(V,E)$ be a graph with the $2\times 2$ symmetric matrices
$\mathcal{A}=\\{(a_{ij}^{e})_{2\times 2}\\}_{e\in E}$ assigned to its edges.
Let us construct a new graph $G^{\prime}$ from $G$ by the following vertex
gadget. For every vertex $v\in V$, add a new vertex $s_{v}$ and an edge
$e_{v}=\\{v,s_{v}\\}$ with a $2\times 2$ symmetric matrix
$(b_{ij}^{e_{v}})_{2\times 2}$ assigned to it. Let $S=\\{s_{v}\\}_{v\in V}$,
and let $\mathcal{B}=\\{(b_{ij}^{e_{v}})_{2\times 2}\\}_{v\in V}$. Then,

$\displaystyle\mathrm{Hom}_{\mathrm{M}}(G^{\prime},S,2;\mathcal{A}\cup\mathcal{B})$
$\displaystyle=\sum_{\begin{subarray}{c}\phi:V(G^{\prime})\to[2]\\\
\phi(s)=2,\forall s\in S\end{subarray}}\prod_{\\{u,v\\}\in
E(G)}a_{\phi(u)\phi(v)}^{\\{u,v\\}}\prod_{v\in
V(G)}b_{\phi(v)\phi(s_{v})}^{e_{v}}$
$\displaystyle=\sum_{\phi:V(G)\to[2]}\prod_{\\{u,v\\}\in
E(G)}a_{\phi(u)\phi(v)}^{\\{u,v\\}}\prod_{v\in V(G)}b_{\phi(v)(2)}^{e_{v}}.$

Taking $a_{ij}^{e}=\exp\left[\omega_{e}(2i-3)(2j-3)\right]$ and
$b_{ij}^{e_{v}}=\exp\left[\upsilon_{v}(2i-3)(2j-3)\right]$,

$\displaystyle\mathrm{Hom}_{\mathrm{M}}(G^{\prime},S,2;\mathcal{A}\cup\mathcal{B})$
$\displaystyle=\sum_{\phi:V(G)\to\\{-1,+1\\}}\exp\left(\sum_{\\{u,v\\}\in
E(G)}\omega_{\\{u,v\\}}\phi(u)\phi(v)+\sum_{v\in
V(G)}\upsilon_{v}\phi(v)\right)$
$\displaystyle=\sum_{\sigma\in\\{-1,+1\\}^{V}}\exp\left(\sum_{\\{u,v\\}\in
E(G)}\omega_{\\{u,v\\}}\sigma_{u}\sigma_{v}+\sum_{v\in
V(G)}\upsilon_{v}\sigma_{v}\right)$
$\displaystyle=\mathrm{Z}_{\mathrm{Ising}}(G;\Omega,\Upsilon),$

where $\Omega=\\{\omega_{e}\\}_{e\in E}$ and
$\Upsilon=\\{\upsilon_{v}\\}_{v\in V}$. Hence, we have an approximation-
preserving polynomial-time reduction from the Ising model partition function
to the restricted multivariate graph homomorphism partition function. This
completes the proof. ∎

##  Appendix E Proof of Proposition 8

We shall now prove Proposition 8. *

###### Proof.

By definition,

$\displaystyle\psi_{G}$
$\displaystyle=\left<0^{\left|V\right|}\right|\exp\left(i\sum_{\\{u,v\\}\in
E}\omega_{\\{u,v\\}}X_{u}X_{v}+i\sum_{v\in
V}\upsilon_{v}X_{v}\right)\left|0^{\left|V\right|}\right>$
$\displaystyle=\left<+^{\left|V\right|}\right|\exp\left(i\sum_{\\{u,v\\}\in
E}\omega_{\\{u,v\\}}Z_{u}Z_{v}+i\sum_{v\in
V}\upsilon_{v}Z_{v}\right)\left|+^{\left|V\right|}\right>$
$\displaystyle=\frac{1}{2^{\left|V\right|}}\sum_{x,y\in\\{0,1\\}^{V}}\left<y\right|\exp\left(i\sum_{\\{u,v\\}\in
E}\omega_{\\{u,v\\}}Z_{u}Z_{v}+i\sum_{v\in
V}\upsilon_{v}Z_{v}\right)\left|x\right>$
$\displaystyle=\frac{1}{2^{\left|V\right|}}\sum_{x\in\\{0,1\\}^{V}}\exp\left(i\sum_{\\{u,v\\}\in
E}\omega_{\\{u,v\\}}(-1)^{x_{u}\oplus x_{v}}+i\sum_{v\in
V}\upsilon_{v}(-1)^{x_{v}}\right)$
$\displaystyle=\frac{1}{2^{\left|V\right|}}\sum_{z\in\\{-1,+1\\}^{V}}\exp\left(i\sum_{\\{u,v\\}\in
E}\omega_{\\{u,v\\}}z_{u}z_{v}+i\sum_{v\in V}\upsilon_{v}z_{v}\right)$
$\displaystyle=\frac{1}{2^{\left|V\right|}}\mathrm{Z}_{\mathrm{Ising}}(G;i\Omega,i\Upsilon).$

This completes the proof. ∎

## References

  * De las Cuevas  _et al._ (2011) G. De las Cuevas, W. Dür, M. Van den Nest, and M. A. Martin-Delgado, New Journal of Physics 13, 093021 (2011), arXiv:1104.2517 .
  * Jaeger  _et al._ (1990) F. Jaeger, D. L. Vertigan, and D. J. Welsh, in  _Mathematical Proceedings of the Cambridge Philosophical Society_, Vol. 108 (Cambridge Univ Press, 1990) pp. 35–53.
  * Goldberg and Guo (2017) L. A. Goldberg and H. Guo, Computational Complexity 26, 765 (2017), arXiv:1409.5627 .
  * Fujii and Morimae (2017) K. Fujii and T. Morimae, New Journal of Physics 19, 033003 (2017), arXiv:1311.2128 .
  * Gao  _et al._ (2017) X. Gao, S.-T. Wang, and L.-M. Duan, Physical Review Letters 118, 040502 (2017), arXiv:1607.04947 .
  * Boixo  _et al._ (2018) S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14, 595 (2018), arXiv:1608.00263 .
  * Bermejo-Vega  _et al._ (2018) J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Physical Review X 8, 021010 (2018), arXiv:1703.00466 .
  * Barvinok (2015) A. Barvinok, Theory of Computing 11, 339 (2015), arXiv:1405.1974 .
  * Barvinok (2016a) A. Barvinok, Foundations of Computational Mathematics 16, 329 (2016a), arXiv:1405.1303 .
  * Barvinok (2016b) A. Barvinok,  _Combinatorics and complexity of partition functions_, Vol. 274 (Springer, 2016).
  * Patel and Regts (2017) V. Patel and G. Regts, SIAM Journal on Computing 46, 1893 (2017), arXiv:1607.01167 .
  * Borgs  _et al._ (2013) C. Borgs, J. Chayes, J. Kahn, and L. Lovász, Random Structures & Algorithms 42, 1 (2013), arXiv:1002.0115 .
  * Barvinok and Soberón (2017) A. Barvinok and P. Soberón, Combinatorica 37, 633 (2017), arXiv:1406.1771 .
  * Sokal  _et al._ (2005) A. D. Sokal _et al._ , Surveys in Combinatorics 327, 173 (2005), arXiv:math/0503607 .
  * Liu  _et al._ (2019) J. Liu, A. Sinclair, and P. Srivastava, Journal of Statistical Physics 174, 287 (2019), arXiv:1704.06493 .
  * Lee and Yang (1952) T.-D. Lee and C.-N. Yang, Physical Review 87, 410 (1952).
  * Peters and Regts (2018) H. Peters and G. Regts, arXiv e-prints (2018), arXiv:1810.01699 .
  * Sinclair  _et al._ (2014) A. Sinclair, P. Srivastava, and M. Thurley, Journal of Statistical Physics 155, 666 (2014), arXiv:1107.2368 .
  * Sly and Sun (2012) A. Sly and N. Sun, in  _53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2012) pp. 361–369, arXiv:1203.2602 .
  * Galanis  _et al._ (2016) A. Galanis, D. Štefankovič, and E. Vigoda, Combinatorics, Probability and Computing 25, 500 (2016), arXiv:1203.2226 .
  * Liu  _et al._ (2018) J. Liu, A. Sinclair, and P. Srivastava, arXiv e-prints (2018), arXiv:1807.06577 .
  * Iblisdir  _et al._ (2014) S. Iblisdir, M. Cirio, O. Boada, and G. Brennen, Annals of Physics 340, 205 (2014), arXiv:1208.3918 .
  * Shepherd and Bremner (2009) D. Shepherd and M. J. Bremner, Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 465, 1413 (2009), arXiv:0809.0847 .
  * Shepherd (2010) D. Shepherd, arXiv e-prints (2010), arXiv:1005.1744 .
  * Bremner  _et al._ (2016) M. J. Bremner, A. Montanaro, and D. J. Shepherd, Physical Review Letters 117, 080501 (2016), arXiv:1504.07999 .
  * Bremner  _et al._ (2010) M. J. Bremner, R. Jozsa, and D. J. Shepherd, in  _Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences_ (The Royal Society, 2010) p. rspa20100301, arXiv:1005.1407 .
  * Eldar and Mehraban (2018) L. Eldar and S. Mehraban, in  _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2018) pp. 23–34, arXiv:1711.09457 .
  * Hell and Nešetřil (2004) P. Hell and J. Nešetřil,  _Graphs and homomorphisms_ (Oxford University Press, 2004).
  * Hell and Nešetřil (1990) P. Hell and J. Nešetřil, Journal of Combinatorial Theory, Series B 48, 92 (1990).
  * Dyer and Greenhill (2000) M. Dyer and C. Greenhill, Random Structures and Algorithms 17, 260 (2000).
  * Bulatov and Grohe (2005) A. Bulatov and M. Grohe, Theoretical Computer Science 348, 148 (2005).
  * Goldberg  _et al._ (2010) L. A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley, SIAM Journal on Computing 39, 3336 (2010), arXiv:0804.1932 .
  * Cai  _et al._ (2010) J.-Y. Cai, X. Chen, and P. Lu, in  _International Colloquium on Automata, Languages, and Programming_ (Springer, 2010) pp. 275–286, arXiv:0903.4728 .
  * Jerrum and Sinclair (1993) M. Jerrum and A. Sinclair, SIAM Journal on Computing 22, 1087 (1993).
  * Markov and Shi (2008) I. L. Markov and Y. Shi, SIAM Journal on Computing 38, 963 (2008), arXiv:quant-ph/0511069 .
  * Weitz (2006) D. Weitz, in  _Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing_ (ACM, 2006) pp. 140–149.
  * Sly (2010) A. Sly, in  _51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2010) pp. 287–296, arXiv:1005.5584 .