[ Top page ]

« An IP simulator for learning | Main

Quantum computing

Four queens problem solved by quantum annealing

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())
>>> 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)2. 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)2. The third term concerns the number of queens, which must be 4. The term should be (Q1 + Q2 + Q3 + Q4 − 4)2. 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.


[T-Wave] T-QARD Crews, N-クイーン問題 を D-Waveマシンで解く

[Jha] Rounak Jha, Debaiudh Das, Avinash Dash, Sandhya Jayaraman, Bikash K. Behera, Prasanta K. Panigrahi, A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience

[Torggler] Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner, A Quantum N-Queens Solver, Quantum Journal, accepted.



TrackBack URL for this entry:

Post a comment


This page contains a single entry from the blog posted on January 7, 2020 8:11 AM.

Many more can be found on the main index page or by looking through the archives.

Creative Commons License
This weblog is licensed under a Creative Commons License.
Powered by Movable Type