Low-loss belief propagation decoder with Tanner graph in quantum error-correction codes

Dan-Dan Yan(顏丹丹), Xing-Kui Fan(范興奎), Zhen-Yu Chen(陳禎羽), and Hong-Yang Ma(馬鴻洋)

School of Sciences,Qingdao University of Technology,Qingdao 266033,China

Keywords: tanner graph,belief propagation decoder,augmented model,fourier transform

1. Introduction

With the rapid development of information network, the quantum computing and quantum communication have made great progress.[1]The quantum communication and quantum computing have been applied for capturing imaginations for almost 60 years. Currently, there are two important parts of quantum information science, which offer deeply paths to solve problems that could never be overcame by classical computing and communication.[2]In recent years, many scholars are studying in the quantum walking fields.[3]The quantum communication and quantum computing have closely related.[4]On the one hand, the former is the theoretical and environmental basis of the latter. On the other hand,the latter provides operational guarantee for the former.

The quantum computing and quantum communication have made a qualitative leap. For instance,quantum communication includes quantum key distribution and quantum secure direct communication.[4,5]Propagation in quantum network has been studied in Ref. [6]. In 2019, Qiet al. have been studied quantum many-body states in Ref.[7]with neural network used, and routing in quantum network has been studied in Ref.[8].Then,parity checks have been used in concentration and measurement.[9,10]In addition,low-density parity check (LDPC) codes have been extensively used in quantum secure direct communication,[11,12]and quantum errorcorrection has become one focus in quantum computing as shown in Ref. [13]. There is a huge challenge to reconstruct the existing decoders,[14,15]and the most difficult problem is how to resolve the node duplication of the existing decoders.[16,17]This paper mainly focused on resolving this problem and constructing a GF(4) augmented model belief propagation (BP) decoder with Tanner graph.[18-20]We not only use sparse matrix, bipartite graph and the properties of approaching Shannon limit for quantum low-density parity check (QLDPC) codes,[21-27]but also use the directivity of Tanner graph. From these properties we know that the length of the ring is at most one.[28-31]In 2019, Alex Rigbyet al. have been proposed an improved belief propagation decoder on QLDPC code.[26]The decoder was designed to correct the error of the quantum error-correction code and obtained the accurate sequence,and then the information can be transmitted.[32,33]

In this paper,combined with the properties of stabilizers,a novel QLDPC code based on the BP algorithm decoding is studied.[34,35]The BP algorithm can achieve hardware parallelization. Besides, the algorithm is calculated by a simply linear function related to the code length, thus, it has no error layer effect. Since the stabilizers are theoretically GF(4)linear codes,[36]a new GF(4) augmented model BP decoder with the Tanner graph is constructed by using the augmented model. We use the received information to carry out iterative operation between the variable node and check node,and to obtain the maximum decoding gain.[28,35,37]As mentioned above, the BP algorithm is based on a linear function related to the code length. Therefore, the parallel implementation in hardware can greatly improve the decoder speed.[38]The decoding frame error rate(FER)of BP algorithm decreases aptly with the increase of the signal-noise ratio (SNR) and it does not have the phenomenon of error floor (carpet effect).[39-41]Combining the BP decoder, a novel GF(4) augmented model BP decoder with the Tanner graph is constructed,and the decoder adds an augmented model with the Tanner graph that can check the repeated nodes.[42]The conditional probability distribution and marginal probability distribution are used to calculate the decoding FER. Since there is no node duplication on the decoder, the FER has been greatly reduced. The algorithm rules and commutative principle in GF(4)field,the inverse Fourier transform and Hadamard transform are used for decoding.[43-45]Finally,the result of simulation shows that compared with the existing decoders, the proposed decoder has stronger anti-interference ability and it can achieve better FER performance in terms of the random perturbation strength and the number of attempts.

The structure of the present paper is organized as follows.In Section 2,the quantum error-correcting codes and the Tanner graphs are introduced. In Section 3,the limitations of the original belief propagation decoder are analyzed.In Section 4,we propose a scheme of the GF(4) augmented model BP decoder with Tanner graph. In Section 5, the GF(4)augmented model BP decoder with Tanner graph has better FER performance than the existing decoders through the simulation. Finally,the conclusion is given in the last section.

2. Quantum error-correction codes and Tanner graph

2.1. Quantum error-correction codes

The QLDPC code in this paper is a quantum code based on stabilizer codes. It not only meets the sparse matrix of classical LDPC codes, which is close to Shannon’s limit performance,[26]but also meets the characteristics of cyclic difference sets of stabilizer codes. According to the above structural properties, the ring length is guaranteed to be no more than 1. In the Tanner graph, the problem of node duplication can be prevented and the efficiency of decoding can be improved. Therefore, the characteristics of QLDPC codes with Tanner graph provide a basic theory for the decoding process.

2.2. Tanner graph

which gives Tanner graph shown in Fig.1.[36]

Fig. 1. [[5,1,3]] Z-error or X-error Tanner graph. The blue arrow between the variable node and the error node represents the exchange and correction of the information.

In Fig. 1,{v1,v2,v3,v4,v5}represents the variable node of[[5,1,3]],and{c1,c2,c3,c4}represents its check node. The blue arrow in the check node indicates that the check node sequence has the property of cyclic difference set and solid lines at each node represent the transmission of information.

3. Limitations of belief propagation decoder

Belief propagation algorithm,also known as sum-product algorithm or message passing algorithm, is to treat the sumproduct operation in variable elimination method as a message and save it,which can save a lot of computing resources. For the general quantum low-density parity code,the length of its ring is 2 or more, there will be a defect of node duplication.When the decoder operation is carried out, many nodes may recalculate the number of times more than twice, resulting in a relatively high FER.

The following is the construction of belief propagation algorithm. All error statesE ∈Pncan affect then-bit quantum code,and only those that conform to the exchange law of the stabilizers and error operator can be used to measureSc. In other words,the conditional probability distribution under the error operatorsis

whereεScis coefficient.

However, belief propagation has its inherent the limitations that it cannot check for node duplication in a Tanner graph. Therefore, this paper improves the BP decoder via adding a GF(4) augmented model with Tanner graph. Such advantage is to solve the problem that node duplication cannot be checked in the BP decoder, which further reduces the decoding frame error rate (FER). The information shifted from the check node to the variable node can be expressed as

wheren(v)?crepresents all of the adjacent nodes ofvexcept nodec.

On the basis of the above belief propagation algorithm,for GF(2) and GF(4) belief propagation decoders, the variation trend of FER of[[5,1,3]]is plotted under the random perturbation strengthp=0.008-0.02. However, it can be seen from Fig.2 that,for the belief propagation decoder,the value of FER reaches only an order of magnitude of 10-2. Therefore,the efficiency and stability of the augmented model belief propagation decoder with Tanner graph is much higher than that of the belief propagation decoder,and the order of magnitude of FER is as low as 10-5.

Fig. 2. Comparing the relationship of p and FER in the GF(2) and GF(4) of [[5,1,3]]. Note that the FER of GF(2) and GF(4) overlaps when p=0.009-0.012,due to node duplication in GF(4),which leads to higher FER.

For Fig.3,the relationship between iterative attempts and FER of [[5,1,3]] is studied. As can be seen from the left figure,when the attempts between 5 and 15,there are two sharp points. The sharp points indicate that the gradient disappears,and this part of the simulation is invalid. In this case,the numerical simulation may not get the correct result. Comparatively, as can be seen from the right figure, the numerical results of GF(4) are more greatly impressive. The right figure of Fig.3 shows the simulation of[[5,1,3]]code on the GF(4)belief propagation decoder. With the increasing of attempts,FER shows an approximately linear decline,and the accuracy of FER reaches 10-7when the attempts are 100. In contrast,GF(2)is very unstable in the decoding process,and GF(4)has better FER performance and effects. As the code length is too short,it shows a downward trend with the increase of attempts.However, with the increase of code length, the FER also will gradually increase.

Fig. 3. Comparing the relationship of attempts and FER in the GF(2)and GF(4)of[[5,1,3]]. Specially,at about 5-15 in the left figure,there are two sharp point where the GF(2)decoder fails because the gradient disappears.

4. Schemes for implementing the augmented model BP decoder in quantum errorcorrection codes

4.1. The variable elimination method

Take the Bayesian network structure in Fig.4(a)as an example. Suppose the objective of the inference is to calculate the marginal probabilityp(x5). Obviously,in order to do this,we simply eliminate the variable{x1,x2,x3,x4}by addition,namely,

The variablexiis eliminated, wheren(i) represents the adjacency node of nodexi. In the belief propagation algorithm, this operation is treated as passing a messagemij(xj)fromxitoxj. Thus,the variable elimination process described by Eq. (5) can be described as the message passing process shown in Fig.4(b). It is not difficult to find that each message passing operation is only directly related to the variablexiand its adjacent nodes. In other words, the calculation related to message passing is limited to the local part of the graph.

In the belief propagation algorithm,a node can only send a message to another node after receiving messages from all other nodes. The marginal distribution of a node is proportional to the product of messages it receives,namely,

for example,in Fig.4(b),before nodex3can send a message tox5,it must receive a message from nodesx2andx4in advance,and the probability that messagem35(x5) gets tox5isP(x5).Figure 5 shows the diagram of belief propagation algorithm.

Fig.4. The variable elimination method and its corresponding messaging process.

Fig.5. Diagram of belief propagation algorithm.

4.2. The augmented model belief propagation

The augmented model decoder is the one novel decoder,which first appeared in classical binary code.[22]For QLDPC code,an augmented model decoder can be based on any coded GF(4) decoder. Re-decoding is performed by using a randomly generated augmented check matrix

In order to further optimize the calculation,the stabilizer code with the theory on the GF(4)field is associated. Suppose Pauli operator groupGis generated by{I,X,Z,Y=XZ}. The quaternion of GF(4)in Galois field is{0,1,ω,ˉω=ω2}. The following mapping is a one-to-one correspondence mapping of the Pauli operator inGto the GF(4)field,namely,

Here to be sure,G →GF(4)is not the only one. The relation between theX →ω,z →ˉω,Y →1 corresponding relation is adopted in some literatures.

4.3. Classical decoder decoding and GF(4) augmented model BP decoder decoding with Tanner graph

In particular, convolution can be converted to take the product of the Fourier transform and the inverse Fourier transform. The following is the belief propagation algorithm based on fast Fourier transform, namely, FFT-BP algorithm. It should be noted that the subscript operation of the convolution solution of the probability sequence belongs to the operation of GF(4),so the transformation can be regarded as a series of two-point FFT transformations in thep-dimensional space. In essence,the method adopts the Hadamard transform

5. Main results

In this paper, we mainly analyze and calculate the simulation of GF(2)augmented and GF(4)augmented of bicycle code[[450,200]]on the depolarizing channel. Compared with the random perturbation strength of the existing decoders,[47]the FER performance of decoders is as shown in Fig.6 below.

Figure 6 shows the relationship betweenpand FER for GF(2),GF(4),GF(2)augmented model and GF(4)augmented model,respectively.What is remarkable is the degree to which it helps,with a significantly greater relative gain than a novel GF(4) augmented model BP decoder with Tanner graph over other decoders. By comparing 3 and 4 in Fig.6 horizontally,it can be seen that whenp=0.0115-0.0116, the GF(4) augmented decoder is one order of magnitude lower than GF(2)augmented decoder,and the minimum value of FER for GF(4)augmented decoder is 7.1975×10-5whenp=0.0115. At this point, FER= 7.1975×10-5is the low-loss decoder of GF(4) augmented model BP decoder compared with the existing decoder. Furthermore, a longitudinal comparison is made to compare 1 and 3 in Fig. 6. It can be seen from the minimum value of each figure that GF(2) augmented model decoder can withstand greater random perturbation strength when FER is of the same order of magnitude, and the decoding effect is better than GF(2) decoder. Therefore, whenp=0.005-0.0115(0.0116), it shows a downward trend, and then the decoder plays a vital role. As shown in Fig.7,whenp=0.0115,the FER performance of the decoder is constantly changing under different attempts.

Fig. 6. The relationship between p and FER. As can be seen from the third and fourth pictures of Fig. 6, there is a small increment of FER before p=0.005,which is due to the influence caused by noise in the environment. The decoder also needs some time to adapt to the noise in the environment.

Fig.7. The relationship of attempts and FER in GF(2)Aug and GF(4)Aug.In the case of certain random perturbation strength,when the number of attempts is 50-80,the FER of GF(2)augmented model decoder appears negative number,at this point,it has a gradient disappearance,which indicates that it has failed.

As can be seen from Fig.7,the FER of GF(4)augmented model BP decoder does not change significantly with the increase of the number of attempts. However,GF(2)augmented model BP decoder fluctuates greatly.In effect,the novel GF(4)augmented model BP decoder has the highest efficiency and is more suitable to be used as a decoder for quantum errorcorrection codes. Moreover, at a given random perturbation strengthp=0.0115 and the number of attemptsN=60-70,its minimum FER can reach an order of magnitude of 10-5.Compared with GF(4) augmented decoder, the stability of GF(2)augmented decoder is far less than its.

6. Conclusion

The paper mainly includes two aspects. On the one hand,Tanner graph plays a key role in the construction of decoding algorithm. On the other hand,the characteristics of cyclic difference sets of QLDPC codes and the construction of sparse matrices provide a solid foundation for the belief propagation algorithm. Therefore,a new GF(4)augmented model belief propagation decoder with Tanner graph is found, which is suitable for the new code. According to the simulation of the GF(2) Aug decoder and the GF(4) Aug decoder of bicycle code [[450,200]] on the depolarizing channel, whenp=0.0115-0.0116 and number of attemptsN=60-70, the FER of the novel decoder is nearly zero decreased to 7.1975×10-5.The decoder has a wide range of applications,with better FER performance than the random perturbation decoder. Due to the construction of the Tanner graph is not unique, the Tanner graph can be found that is most suitable for this decoder.In the future, quantum fault tolerance and threshold or noise compression information will be further investigated.

Acknowledgements

Project supported by the National Natural Science Foundation of China (Grant Nos. 11975132 and 61772295), the Natural Science Foundation of Shandong Province, China(Grant No.ZR2019YQ01),and the Higher Education Science and Technology Program of Shandong Province,China(Grant No.J18KZ012).