Introduction

PyRoute is a user-centric route optimization and itinerary scheduling solution developed by AmplifiQation.

Adaptable, and engineered for scalability, PyRoute delivers quantum enhanced tools for:

• Evening and hang-out planning;
• Vacation and business-trip scheduling;
• and logistics and supply-chain management.

The Quantum Components

pyROUTE leverage fundamental quantum computing principles to accelerate optimization.

Random Number Generation

By preparing and measuring a Bell State, pyROUTE empowers the user with the truly random options.

Quantum-enhanced TSP (traveling salesman problem) solver

The quantum-enhanced TSP explanation paper.

By running the Dürr and Høyer algorithm [1] on precomputed Hamiltonian cycles, pyROUTE provides a quantum-enhanced routing optimizer.

[1] C. Dürr and P. Høyer, “A Quantum Algorithm for Finding the Minimum,” 1996. https://arxiv.org/abs/quant-ph/9607014.

Teams

PyRoute was developed during MIT iQuHACK 2023 by the AmplifiQation team. More on iQuHACK 2023 here.

Michael Luciuk (University of Toronto)
Chaitanya Kumar Mahajan (University of Toronto)
Kae-Yang Hsieh(Northeastern University)
Veronica Lekhtman (Northeastern University)
Karishma Bhargava (Northeastern University)

iQuHACK 2023

iQuHACK is a faced-paced, valuable learning experience accessible to all levels of quantum experience. The AmplifiQation team highly recommends you consider applying for further.

iQuHACK was made possible by a dedicated organizing committee and generous sponsor supports.

This is a project in the Intro to Quantum Computing course instructed by Professor Mariia Mykhailova at Northeastern University.
This post is part of the Q# Holiday Calendar 2022. Check out the calendar for more great posts!

What’s the puzzle we are going to solve?

In the rules of chess, a queen can move horizontally, vertically, or diagonally to any vacant square on the board. The N-Queens puzzle applies this same rule and challenges players to place N queens on an N x N chessboard without allowing any two queens to attack each other.

This puzzle was first introduced in the 19th century, and it is NP-complete.

The project also introduced a variation of the N-Queens puzzle called the N-Queens² puzzle. In this version, every square on the board is occupied by a queen, but there are N different colors of queens, and queens of the same color cannot attack each other.

Traditional Solution

A backtracking algorithm is used to solve the puzzle, and the highest order that has been solved is 27. The time complexity is O(N!), and the space complexity is O(N). A list of solutions is the following:

Quantum solution

Grover’s search algorithm is used to solve the two puzzles, and the steps are described below. Most of the steps are referred from [1].

N-Queens Puzzle

The solutions to the puzzle are specific permutations of a N x N chessboard. They can be described with three constraints. First, each row has only one queen. Second, each column has only one queen. Last, each diagonal has either zero or one queen.

To prepare for the initial state, N x N qubits are allocated to represent a chessboard. A ⎸0⟩ state indicates an empty square, and a ⎸1⟩ state indicates a queen is placed on the square. The initial state of a chessboard when N = 4 can be represented as,

Then, the row constraint can be prepared to a W state, which guarantees a row has only one queen. For example, when N = 4, a queen could be in one of the four positions in a row as,

The preparation of the W state can be found in QuantumKatas [5].
There are 4 rows, and the state of the chessboard can be represented as,

After the row constraint state is prepared, an oracle is created to apply the restrictions. The results of the column and diagonal checks are stored in the auxiliary qubits. The target qubit will be flipped when the restrictions are fulfilled, which means the auxiliary qubits are all in the ⎸1⟩ state.

The column constraint is checked by applying a controlled X gate on each square in the same column. The auxiliary qubits will be in the ⎸1⟩ state if the sum of the queens is odd. Since each row state ensures that there are a total of N queens on the board, if any one of the columns has an odd number of queens greater than one, then there must be two or more columns with no queens, and the corresponding auxiliary qubits will be in the ⎸0⟩ state.

Furthermore, only N-1 columns need to be examined, that is, only N-1 auxiliary qubits need to be allocated. If N 1s add up to N and 0 exists among them, then there must have an even number of 0s. It is impossible that the first N-1 column satisfies the requirement, but the last column has no queen or two more queens. So, only N-1 columns need to be checked. The following figures show how column checks are performed and an example that the column constraint is not satisfied.

Next, diagonal verifications proceeded between each pair of rows. There are N ⨉ (N-1) / 2 such checks that need to be performed, and the results are stored in auxiliary qubits. The auxiliary qubits are initialized in the ⎸1⟩ states. If two queens are in the same diagonal pair, the corresponding auxiliary qubit will be flipped to the ⎸0⟩ state by a CCNOT gate. If all the auxiliary qubits remain in the ⎸1⟩ state, it means that the diagonal requirement is satisfied. Because each row has only one queen, it is impossible to have more than one diagonal pair of queens, so the auxiliary qubits will not be flipped more than once. The following animation shows examples of diagonal checks.

Finally, the two auxiliary qubit arrays for the column and diagonal checks are concatenated and used to control the target qubit in the oracle. The target qubit will be flipped if all the requirements are satisfied, which indicates that a valid solution to the N-Queens puzzle has been found.

// psuedo code
operation OracleNQueensConstraint (register: Qubit[], target: Qubit) : Unit is Adj{        
      use auxQCol = Qubit[nQueens - 1];
      use auxQDia = Qubit[(nQueens * (nQueens - 1)) / 2];
      
      within {
          checkColumn();

          ApplyToEachA(X, auxQDia);
          checkDiagonal();
      } apply {
          Controlled X(auxQCol + auxQDia, target);
      }
}

N-Queens² Puzzle

The solutions to the N-Queens² puzzle are also particular permutations of the N ⨉ N chessboard. It requires that each row, column, and diagonal on the chessboard contain queens of different colors.

To represent the different colors of the queens, multiple qubits are used to represent one queen. For example, when N = 5, three qubits are used to represent the 5 different colors from 0 to 4 using little-endian notation.

The first step is to allocate N by N by M-color-bit qubits to represent each square on a chessboard. Where N is the number of queens, and M is the number of qubits needed to represent a color.

Then, each row can be prepared as a combination of different colors of queens. For example, when N = 3, one of the possible row combinations can be represented as,

As a result, each row has only one queen per color.
The preparation of the row state can be found in QuantumKatas [5].

There are 3 rows on a chessboard, so the chessboard can be represented as,

Similar to the N-Queens puzzle, auxiliary qubits are used in the oracle to store the results of column and diagonal checks. However, this expands to include each color per column. An auxiliary qubit is flipped to ⎸1⟩ when the number of queens of the same color on a column is even. Each column requires N auxiliary qubits to perform the check, and a total of N ⨉ (N-1) qubits are needed for all columns.

The row state preparation ensures that the colors on each row are different. If one of the columns has an odd number of queens of the same color, there must be at least two columns with no queens of that color. Therefore, only N-1 columns need to be examined, and only N ⨉ (N-1) auxiliary qubits need to be allocated. It is impossible for N-1 columns to have no repeated colors but for the last column to have repeated colors of queens. Figure 6 shows how column checks are performed when N = 3.

Next, diagonal verifications are performed between each pair of rows per color. There are N ⨉ N ⨉ (N-1) / 2 such checks that need to be performed, and the results are stored in auxiliary qubits. These qubits are initialized in the ⎸1⟩ state. If two queens of the same color are on the same diagonal, the corresponding auxiliary qubit is flipped to the ⎸0⟩ state using a controlled bit string gate. If all auxiliary qubits remain in the ⎸1⟩ state, it means that the diagonal requirement has been satisfied. Because each row and column has only one queen per color, it is impossible to have more than one diagonal pair of queens with the same color, so the auxiliary qubits will not be flipped more than once. The following videos are the process of diagonal checks.

To finish, the two arrays of auxiliary qubits for the column and diagonal checks are combined and used to control the target qubit in the oracle. If all requirements are satisfied, the target qubit will be flipped, indicating that a valid solution to the N-Queens² puzzle has been found.

// psuedo code
operation OracleNQueensSquareConstraint (register: Qubit[], target: Qubit) : Unit is Adj{        
      use auxQCol = Qubit[nQueens * (nQueens - 1)];
      use auxQDia = Qubit[nQueens * (nQueens * (nQueens - 1)) / 2];
      
      within {
          checkColumn();

          ApplyToEachA(X, auxQDia);
          checkDiagonal();
      } apply {
          Controlled X(auxQCol + auxQDia, target);
      }
}

Analysis

N-Queens

• The search space size is Nᴺ while each row has N possible combinations, and there are N rows.
• The qubits allocated explicitly are:

• The operations needed for columns: N ⨉ (N-1)
• The operations needed for diagonal:

N-Queens²

• The search space size is N!ᴺ while each row has N! possible combinations, and there are N rows.
• The qubits allocated explicitly are:

• The operations needed for columns: N ⨉ N ⨉ (N-1)
• The operations needed for diagonal:

Comparison

According to the analysis, the qubits needed for N-Queens² are too many for the local environment, so a modified version without the diagonal restriction is executed in the experiments. The following tables show a comparison between different parameters before the experiments.

Experiments

I implement the algorithm with Q# and Quantum Development Kit (QDK), and execute it on Azure Quantum. The full codes is here.

There are three methods used in the experiments.

• Quantum Development Kit (QDK) sparse simulator
• Azure Resource Estimator
• Azure Quantum — Rigetti

Results

N-Queens in Local Environment with Sparse Simulator

N-Queens on Azure Resource Estimator

The full results of N=4 and N=5 are linked.

N-Queens² without diagonal restriction in Local Environment with Sparse Simulator

Real Hardware (Rigetti Provider)

The resources estimator shows that only the Rigetti provider has enough qubits to execute the algorithm. However, the code cannot be executed on the Rigetti provider due to some limitations.

Discussions

The full-state simulator consumed too many memories for the local environment when N = 4 for the N-Queens solution. The sparse simulator can compute N = 6 without exhausting the hardware. The N-Queens² needed even more computing power, and the result of N-Queens² with diagonal restriction never be acquired running for days. A modified version without diagonal restriction is executed to verify the algorithm. The sparse simulator can compute N = 3 and N = 4 successfully.

The resources estimator showed an evaluation before submitting algorithms to real hardware. However, it cannot be verified this time while the algorithm has not been executed on a real quantum computer.

Conclusions

The time complexity of N-Queens is O(N³), and the space complexity is O(N²). Both of the complexity of N-Queens² increased by one, where the time complexity is O(N⁴), and the space complexity is O(N³).
The quantum algorithm showed theoretically faster than traditional computing, which reduces the time complexity from O(N!) to O(N³). However, more qubits are required to execute the algorithm to verify it. Also, a quantum counting method will be required when there is no solution number from the traditional computing method when N is greater than 27.

The N-Queens problem can be applied in load balancing, deadlock prevention, and satellite communication. For satellite communication, the queens can be replaced with satellites, and the configuration of the solution of the N-Queens puzzle will maximize the transmit area.

References

[1] Jha, R., Das, D., Dash, A., Jayaraman, S., Behera, B. K., & Panigrahi, P. K. (2018). A novel quantum N-Queens solver algorithm and its simulation and application to satellite communication using IBM quantum experience. arXiv preprint arXiv:1806.10221.

[2] Torggler, V., Aumann, P., Ritsch, H., & Lechner, W. (2019). A quantum n-queens solver. Quantum, 3, 149.

[3] Del Manzano, H. A., & Echevarıa, C. (2002). Quantum algorithm for n-queens problem. In Computing Research Conference, Mayagüez, Puerto Rico.

[4] http://oeis.org/A000170

[5] QuantumKatas

OpenCV是一個開放原始碼的電腦視覺程式庫，可以用來做影像處理

接下來會利用RPi處理影像以辨識車道的位置，因此要在RPi上安裝OpenCV

安裝步驟

登入RPi終端機後，按造順序輸入以下指令：

sudo apt-get update
sudo apt-get upgrade

安裝相關套件

sudo apt-get install build-essential cmake pkg-config libjpeg-dev libtiff5-dev libjasper-dev libpng12-dev libavcodec-dev libavformat-dev libswscale-dev libv4l-dev libxvidcore-dev libx264-dev libgtk2.0-dev libatlas-base-dev gfortran python2.7-dev python3-dev python3-pip python3-numpy git

其中 libjpeg-dev, libtiff5-dev, libjasper-dev, libpng12-dev 是讓opencv可以讀取jpg, png, tiff等照片格式、libavcodec-dev, libavformat-dev, libswscale-dev, libv4l-dev, libxvidcore-dev, libx264-dev 是影像串流相關的程式庫，以及libgtk2.0-dev用來顯示畫面等

從原始碼編譯、安裝OpenCV 3

下載OpenCV及contrib的原始碼

wget -O opencv https://github.com/opencv/opencv/archive/3.2.0.zip
wget -O opencv_contrib https://github.com/opencv/opencv_contrib/archive/3.2.0.zip

unzip opencv
unzip opencv_contrib
cd opencv-3.2.0
mkdir build
cd build

cmake -D CMAKE_BUILD_TYPE=RELEASE -D CMAKE_INSTALL_PREFIX=/usr/local -D INSTALL_PYTHON_EXAMPLES=OFF -D OPENCV_EXTRA_MODULES_PATH=~/opencv_contrib-3.2.0/modules -D BUILD_EXAMPLES=OFF ..

make -j2
sudo make install
sudo ldconfig

測試是否有安裝成功

python3
import cv2
cv2.__version__

如果有出現’3.2.0' 就是成功囉

樹莓派是一塊名片大小的電路板，可以安裝完整的作業系統，具有一般電腦的功能，也可以從感測器讀取訊號得到如溫度、濕度等資訊，或是輸出訊號控制電燈、馬達等。

下圖：Raspberry Pi 3 (RPi 3)

作業系統安裝：

RPi 3可以安裝許多種不同的作業系統如windows 10、Raspbian、Ubuntu等，詳細項目請見官網，這次將安裝擁有最多資源的Raspbian。

首先到官網下載 Raspbian Jessie (Jessie是版本的名稱)

若需要有圖形畫面的桌面版本請選左側，若不需要可以選擇右側檔案較小的版本。

將下載的ZIP檔解壓縮後會得到一個 .img檔

使用Etcher將此檔燒錄到SD卡(SD卡至少要4GB)

為了要可以在開機後使用SSH(一種與RPi溝通的方式)遠端登入，需要在SD卡內增加一個檔名為ssh的空檔案(無副檔名與內容，不是.txt檔)

完成後就可以裝到RPi上囉！

硬體裝配：

網路孔：接上有線網路，另一端接到路由器或是自己的筆電

（若另一端連接到路由器，請確認正在使用的電腦也是連在同一個路由器上）

電源：一般Ardroid充電線即可

SD卡插槽：插入剛剛燒錄好的SD卡

完成圖：

系統環境建置：

接下來要遠端登入使用RPi，但要先知道RPi在網路上的位置，也就是IP位址

使用Angry IP scanner找到RPi的IP（Mac, Linux, Windows均適用）：

1. 下載 Angry IP scanner
2. 找到自己的IP:

windows: 打開命令提示字元並輸入ipconfig

Linux或是Mac: 打開終端機並輸入ifconfig

3. 在Angry IP scanner的IP range兩個欄位輸入找到的前三組數字，最後一組分別是1及255

4. 找到Hostname為raspberrypi的IP並記下來

遠端連線登入RPi:

windows:

1. 下載Putty
2. 按下左側的Session
3. 在Hostname欄位填上上面查到的RPi IP
4. 按下面的open按鈕就會打開一個黑色的視窗寫著login:
5. 輸入 pi
6. 接下來要輸入密碼，預設是raspberry (輸入的時候螢幕不會出現任何字，要有信心打的字都是對的XD)

Linux 或 Mac:

1. 打開終端機
2. 輸入 ssh pi@192.168.xx.xx(上面查到的RPi IP)
3. 接著輸入密碼，預設是raspberry (輸入的時候螢幕不會出現任何字，要有信心打的字都是對的XD)

如果出現raspberry的終端機畫面就代表成功囉！

sudo iwlist wlan0 scan

修改WiFi設定檔

sudo nano /etc/wpa_supplicant/wpa_supplicant.conf

在檔案裡加入

network={
    ssid="WiFi名稱"
    psk="WiFi密碼"
 }

修改完後按 Ctrl+O 確認檔名後按 Enter確認存檔
再按 Ctrl + X 離開