Finding Self-dual Stabilizer code distance using QUBO approach

This Jupyter Notebook constructs a QUBO cost function whose minimization corresponds to finding the Hamming distance of a self-dual Stabilizer code. Solving the minimization problem can be done using classical algorithms like Simulated Annealing (SA) or quantum ones like Quantum Annealing (QA) or using hybrid approaches, ex QBsolv. More details can be found in this paper (link will soon be posted on arxiv) along with an investigation into the efficiency of the three approaches. This code was written in collaboration between Refat Ismail and Ashish Kakkar, while the paper was in collaboration with Anatoly Dymarsky too.

Installation

To install the correct package versions use "environment.txt". Download the file and run

pip install -r "filepath/requirements.txt"

to install.

Working with code

The code constructs the QUBO and solves it using Neal's Simulated Annealing Sampler. It can be easily adjusted to run using other classical, quantum, and hybrid algorithms depending on the user's purpose.

The uploaded program is a minimalist implementation of the code to show the core ideas using code instances from Grassl database. The program constructs the QUBO matrix using the generator matrix "G" of a circulant self-dual code: $G^T=(I_n|B)$ with B a circulant matrix and $I_n$ the nxn identity matrix. We introduce auxiliary variables to write the QUBO -see details in the paper (link will be posted soon)-. Our cost function can then be written as: $\mathbf{\text{cost function}}=\underset{z}{min}{z}^{T}Qz$ Where z is a list of binary variables consisting of: our original variables $x_i$ and the auxiliary variables $y_{i,j}$, arranged as $z=[x_1,x_2,...,x_n,y_{1,1},y_{2,1},...,y_{n,1},y_{1,2},...,y_{n,r}]$. The Q matrix will be made of multiple blocks as shown:

$$Q=\left[\begin{array}{ccccc}{I}_n+B^2-B& 2^0(I_n-2B)& 2^1(I_n-2B)& \dots & 2^{r-1}(I_n-2B)\\ 2^0(I_n-2B)& 2^2{I}_n& 2^3{I}_n& \dots & 2^{r+1}{I}_n\\ 2^1(I_n-2B)& 2^3{I}_n& \ddots & \ddots & 2^{r+2}{I}_n\\ ⋮& ⋮& \ddots & \ddots & ⋮& \\ 2^{r-1}(I_n-2B)& 2^{r+1}{I}_n& 2^{r+2}{I}_n& \dots & 2^{2r}{I}_n\end{array}\right]$$

This can be straightforwardly extended to non-circulant and non-self dual codes as well (see the paper for info).