Optimize Bit-flip post-processing

[abussy-pasqal]

Bit-flip post-processing can be very long with large QUBOs (size 1000) because it computes a lot of costs $z^\top Q z$

I tried a couple strategies :
1 - Memoization -> doesn't work well as only a slight percentage of bitstrings are seen again (< 5%)
2 - Computing a differential cost instead of a full cost

Solution 2 gives very promising results performance-wise. More testing is necessary to check that its results are correct.

Qubo Size	Actual	Solution 2
1000	40s	10s
2000	550s	35s

[abussy-pasqal]

Here is the algorithm.

For a given bitstring $z$, the flipped bitstring is $z \pm \delta_i$, where $i$ is the flipped bit and $\delta_i$ is the $i$-th unit vector. The sign depends on the flipped bit being $0$ or $1$.
The new cost can be computed as follow:

$$ (z \pm \delta_i)^\top Q (z \pm \delta_i) = z^\top Q z \pm z^\top Q \delta_i \pm \delta_i^\top Q z + \delta_i^\top Q \delta_i $$

Since $Q$ is symmetric ($Q = Q^\top$), we have $z^\top Q \delta_i = \delta_i^\top Q z$, so the two cross terms combine:

$$ = z^\top Q z \pm 2 z^\top Q \delta_i + \delta_i^\top Q \delta_i $$

Now, using the fact that $\delta_i$ is the $i$-th unit vector:

• $Q \delta_i = Q_{:,i}$ (the $i$-th column of $Q$), so $z^\top Q \delta_i = (Qz)_i$
• $\delta_i^\top Q \delta_i = Q_{ii}$

Which gives the final result:

$$ (z \pm \delta_i)^\top Q (z \pm \delta_i) = z^\top Q z \pm 2 (Qz)_i + Q_{ii} $$

For a base solution $z$, we therefore only need to compute $Qz$ once, and then the base cost $z^\top Q z$ once too.