7
$\begingroup$

Inverse Ising Problem

The inverse ising problem means fitting the coupling $J_{ij}$ and field $h_{i}$ parameters given a sample of configurations of spins.

Each spin $s_{i}$ is either +1 or -1. The Hamiltonian of one configuration of spins $\vec{s}$ is:

$$ H(\vec{s}, \mathcal{J}, \mathcal{h}) = \sum_{i} h_{i} s_{i} + \sum_{i \ne j}J_{ij} s_{i}s_{j} $$

The probability of the configuration of spins $\vec{s}$ is:

$$ P(\vec{s}, \mathcal{J}, \mathcal{h}) = \frac{1}{Z(\mathcal{J}, \mathcal{h})} \exp \left [ H(\vec{s}, \mathcal{J}, \mathcal{h}) \right] $$

where the partition function is

$$Z(\mathcal{J}, \mathcal{h}) = \sum_{\vec{r}} \exp \left [ H(\vec{r}, \mathcal{J}, \mathcal{h}) \right]$$

The summation is over all possible configurations.

Fitting the parameters means maximizing the log-likelihood of the sample.

This PDF contains some slides for inverse Ising problem.


There is a link between the Ising model and quadratic unconstrained binary optimization (QUBO).

Question: Can QUBO solve inverse Ising problem?

$\endgroup$

2 Answers 2

5
$\begingroup$

Yes it is possible, but it may not be as efficient as the other methods listed in that PDF file. In fact, I'm still not sure there's any problem for which QUBO is the best way to solve it (see this: What are some real-world applications of QUBO?, and if interested in this area you may also find this one interesting: Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?). I'll also say that there's currently an open bounty worth up to 300 points on this question: Where/when did the fields of Operations Research and Spin Physics or Molecular Dynamics begin to cross-pollinate?. Now for my answer to your question:

Let's start with a simpler case:

Say we have the energy $E$, for the spin Hamiltonian $H = Js_1s_2 + hs_1$ at the configuration $(s_1,s_2) = (1,1)$:

$$ \tag{1} E = Js_1s_2 + hs_1. $$

This implies:

$$\tag{2} E - Js_1s_2 - hs_1 = 0. $$

Now the following miniminization is equivalent to solving for the unknowns $J$ and $h$ in Eq. 2:

$$\tag{3} \min_{J,h}\left( E - Js_1s_2 - hs_1 \right)^2, $$

because the function we're minimizing is a square of a real number, so it cannot be negative, and therefore the minimum cannot be less than 0, and since we know that Eq. 1 is true, we know that the function can be 0 (so the minimum is 0).

Now if we represent $J$ and $h$ in binary, we get:

\begin{align}\tag{4} J &= J_02^0 + J_12^1 + J_2 2^2 + J_32^3 + \ldots + J_N2^N\\\tag{5} h &= h_02^0 + h_12^1 + h_2 2^2 + h_32^3 + \ldots + h_N2^N, \end{align}

where $\left(J_0,J_1,J_2,J_3,\ldots J_N,h_0,h_1,h_2,h_3,\ldots,h_N\right)$ are all either 0 or 1, and then we use:

$$\tag{6} s_i = 2b_i - 1, $$

where $b_i$ are the binary variables such as $J_i$ and/or $h_i$, then we have Eqs. 4-5 in terms of $s$ variables (-1,1 rather than 0,1), and Eq. 3 is then in QUBO form!

If we had more than one energy, such as:

\begin{align}\tag{7} E_1 = Js_1s_2 + hs_1, (s_1,s_2)=(1,1)\\\tag{8} E_2 = Js_1s_2 + hs_1, (s_1,s_2)=(1,0), \end{align}

then instead of Eq. 3 we can have:

$$\tag{9} \min_{J,h}\left( \left(E_1 - J(1)(1) - h(1) \right)^2 + \left( E_2 - J(1)(0) - h(1)\right)^2\right). $$

This is how myself and others have converted the problem of factoring numbers into QUBO: see Eqs 10 and 11 of "Quantum factorization of 56153 with only 4 qubits" and how they are formed from Eqs 7-9 of that paper.

Now for the "inverse Ising problem" defined in the PDF you gave:

Instead of Eq. 1 we have:

$$\tag{10} P = \frac{e^{\left(Js_1s_2 + hs_1\right)}}{\sum_{s_1,s_2} e^{\left(Js_1s_2 + hs_1\right)}}, $$

and the same techniques can be used to form the QUBO problem again. If you need more assistance on that, then I suggest you ask another question on how to exponentiate binary variables in QUBO-type problems, since it's a mathematical technique that would be a bit of a tangent to the main thrust of this answer, but would need even more space to explain. It's a bit more complicated than doing the exponential in the case where no actual variables have to be exponentiated, as in the other question you asked here: How to exponentiate binary variables in QUBO-type problems?.

$\endgroup$
6
  • $\begingroup$ I think most of methods in that pdf file are approximations that depend on various assumptions about the parameters. I also tried the adaptive cluster expansion method in another paper. But that one didn't work well for me. $\endgroup$ Jul 24, 2021 at 22:39
  • $\begingroup$ @QuriousCube You're right, for example the Monte Carlo method suggested there will likely give you an approximate solution rather than an exact one. Also, QUBO problems beyond a few dozen variables, are usually solved until an approximate minimum is found (not an absolute minimum). $\endgroup$ Jul 24, 2021 at 22:42
  • $\begingroup$ I have 50 spins and about 5 x 50 coupling parameters. That is the minimal number of parameters to make the whole thing useful. $\endgroup$ Jul 24, 2021 at 22:44
  • $\begingroup$ I'd be very happy to talk to you in chat! $\endgroup$ Jul 24, 2021 at 22:46
  • $\begingroup$ Equation 1 assumes that the energy $E$ is provided. Likewise, Equation 10 assumes $P$ is known. However, from the pdf we don't know what the corresponding $P$ is of a given sample $\endgroup$
    – algor207
    Jul 25, 2021 at 22:03
4
$\begingroup$

The log-likelihood function $L$ is continuous while QUBO is discrete. If you really wanted to formulate it as a QUBO, this is how I would do it. In summary, the steps would be as follows:

$L \to \text{ Discrete-}L \to \text{ Binary-} L \to \text{Higher-Order-Binary-} L \to \text{ QUBO } L$

  1. $L \to \text{ Discrete-}L$
    • This step would simply be restricting the variables $J_{ij}, h_i$ to $\mathbb{Z}$
  2. $\text{ Discrete-}L \to \text{ Binary-} L$
    • Binary expansion of the integer variables
    • Note: at this step, the function is not necessarily a polynomial
  3. $\text{ Binary-} L \to \text{Higher-Order-Binary-} L $.
    • Find a binary polynomial that approximates the function in the previous step
    • This will end up being a Higher-Order Binary Optimization problem (HOBO)
  4. $ \text{Higher-Order-Binary-} L \to \text{ QUBO } L$
    • Convert the HOBO to a QUBO using known HOBO to QUBO techiques

Perhaps there are some interesting applications where we directly know that $J_{ij}, h_i \in \{0,1\}$, in that case all you would need is step 3 and 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.