Four queens problem solved by quantum annealing (Small and Large Stones of Programming)

I wrote a four-queens program using quantum annealing. This program is mostly extended to solve the N queens, but still N is fixed to 4.

I wrote about quantum four queens program in my blog (in Japanese), but I translate it to English here. This program solves the four queens problem, but not the N queens or famous eight queens because I wanted to try a problem that can be solved with minimum number of quantum bits. I found many researches that tried to solve the N queens problem, but a solution closest to my program is [T-Wave]. Jha [Jha] is an example that solves the four queens by quantum gate computing.

My program is here. The execution process is as follows.

$ python3
Python 3.8.0 (v3.8.0:fa919fdf25, Oct 14 2019, 10:23:27) 
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from QuantumQueensE import queens, pprint
>>> pprint(queens.sa())
.Q..
...Q
Q...
..Q.
>>> exit()

Each square of a 4-by-4 "chess board" is assigned to a row and a column of QUBO (which has 16 rows and 16 columns). The value of each element of the QUBO is 1 when a queen stays there or 0 when no queen stays there. The QUBO consists of three terms. The first term concerns the sum of a row or a column (i.e., Q1 + Q2 + Q3 + Q4). Each sum must be 1, so the term should be (Q1 + Q2 + Q3 + Q4 − 1)². The second term concerns the sum of squares of diagonal direction (i.e., Q1 + Q2 + Q3 + Q4, Q1 + Q2 + Q3, or Q1 + Q2). Each sum is 0 or 1, so the term should be (Q1 + ... + Qn − 0.5)². The third term concerns the number of queens, which must be 4. The term should be (Q1 + Q2 + Q3 + Q4 − 4)². The coefficients of these terms are tentatively 1. I found the third term is not required (i.e., the coefficient may be 0) to solve the four queens.

I have not yet found appropriate values for parameters, such as queens.Ts or the coefficients described above. The program can solve the four queens problem by using default values for the parameters. However, while using the simulater (wildqat), it takes non-short time to get a solution of four queens. If the program is simply extended, it will probably take much time to solve N queens when N is large. This program can probably easily extended to N queens (N > 4), but currently N is fixed to 4. I have not yet tried a D-Wave machine because N is fixed to 4.

P.S. A problem of this program is that the search space is very large because the number of queens (i.e., 4) can be varied, and the number of queens in a row or a column (i.e., 1) is not fixed. The are usually fixed in symbolic programs, so the search is more efficient.