## 3 Proposed Neighborhood Structure  
The strictly monotonic expanding neighborhood structure used in the VNS algorithm is tenable. However, there is no guarantee that this expansion type will always result in a better solution. To exploit this technique to solve any QUBO problem, we propose the use of binomial distribution to create a neighborhood structure. As the proposed algorithm is based on the VNS algorithm, it takes advantage of the characteristics of the VNS algorithm, while aiming to reduce the computation time required. Our proposed structure enables the algorithm to expand the neighborhood, by following a random schema. However, it is good to maintain a gradual expansion trend. In the basic VNS algorithm, the neighboring point \(\mathbf{X}^{\prime}\in N_{k}(\mathbf{X})\) is obtained by flipping \(k\) numbers of the element of \(\mathbf{X}\). The flipped elements are chosen randomly. As a result, some elements are changed, from 1 to 0 or vice versa, while some remain. Instead of applying this basic neighborhood structure, we propose a mechanism of determining whether each element should be flipped or not. Each element will be flipped, by considering a flip probability. The proposed neighborhood structure is as follows: we define a trial \(T\), to flip each element of a vector \(\mathbf{X}=(x_{1},x_{2},...,x_{n})\), to obtain \(\mathbf{X}^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},...,x_{n}^{\prime})\in N(\mathbf{X})\), in accordance with the following rule:  
\[x_{i}^{\prime}= \begin{cases}flip(x_{i})&\text{, with probability }p\in[\,0,1]\\ x_{i}&\text{, with probability }(1-p)\end{cases} , \tag{3}\]  
where  
\[flip(x_{i})= \begin{cases}1-x_{i}&\text{, for }\{0,1\}\text{ encode}\\ -x_{i}&\text{, for }\pm 1\text{ encode}\end{cases} . \tag{4}\]  
This trial satisfies binomial requirements, as it is repeated \(n\) times, where \(n\) corresponds to the vector length and sets a fixed probability \(p\). Suppose a random variable \(A\) represents the number of flipped elements, and let a random variable \(D\) represent the obtained Hamming distance \(d\). Then, there is a clear correspondence between random variable \(A\) and \(D\). Take any vector \(X\) and generate a vector \(Y\), by following Equation (3), and suppose that \(m\) random elements of \(X\) were flipped based on this process; from this supposition, we have \(d(X,Y)=|X-Y|=m\). As the flip is controlled by probability \(p\), by following binomial distribution we have  
Figure 1: VNS algorithm. (**a**) The algorithm gradually expands its neighborhood structure according to \(k\) for going out from a local optimum trap [32]. (**b**) The distance of \(k\) is gradually increased by one to build a broader neighborhood structure. \[\mu_{D}=np, \tag{5}\] \[\sigma_{D}=\sqrt{np(1-p)}. \tag{6}\]  
Based on binomial distribution, the distance at approximately \(np\) has a high probability of occurring. In the VNS algorithm, the distance is equal to variable \(k\) and is limited by the parameter \(k_{max}\). Therefore, \(k_{max}\) is the maximum distance that can be reached, when constructing a neighborhood structure. To replace this concept, our proposed method uses a parameter \(p_{max}\in[\,0,1\,]\) as a limitation. To apply the gradual expansion mechanism, we divide the \(p_{max}\) into several equal chunks. Then, we ensure that the flip probability \(p\) corresponds to these chunks. \[p_{c}=cp_{max}/C, \tag{7}\]  
for \(c=1,2,..,C\), where \(C\in\mathbb{N}\) is a parameter for chunk size. This construction is applied every time a neighboring point \(\mathbf{X}^{\prime}\) needs to be generated. Thus, this binomial neighborhood structure does not depend on variable \(k\) but, instead, on flip probability \(p_{c}\), which corresponds to chunk \(c\). \[N_{c}(X)=\{Y:D_{(Y,X)}\sim Binom(p_{c},n)\}, \tag{8}\]  
for \(c=1,2,...,C\) considering (7), \(D_{(Y,X)}\) is the Hamming distance between \(Y\) and \(X\), where \(Y\) is generated by applying Equation (3).