Practical entanglement distillation scheme using recurrence method and quantum low density parity check codes

Many entanglement distillation schemes use either universal random hashing or breeding as their final step to obtain almost perfect shared EPR pairs. In spite of a high yield, the hardness of decoding a random linear code makes the use of random hashing and breeding infeasible in practice. In this pilot study, we analyze the performance of the recurrence method, a well-known entanglement distillation scheme, with its final random hashing or breeding procedure being replaced by various efficiently decodable quantum codes. Among all the replacements investigated, the one using a certain adaptive quantum low density parity check (QLDPC) code is found to give the highest yield for Werner states over a wide range of noise level—the yield for using this QLDPC code is higher than the first runner up by more than 25% over a wide parameter range. In this respect, the effectiveness of using QLDPC codes in practical entanglement distillation is illustrated.     

Designing parity check matrix to achieve linear encoding time in LDPC codes

Low-density parity-check (LDPC) codes have become the part of various communication standards due to their excellent error correcting performance. Existing methods require matrix inverse computation for obtaining a systematic generator matrix from parity check matrix. With the change in code rate or code length the process is repeated and hence, a large number of pre-processing computations time and resources are required. In the existing methods, the complexity of encoding is essentially quadratic with respect to the block length. In this paper, it is shown that the parity check matrix can be constructed using patterned sub-matrix structure such that the matrix inverse operation is replaced by matrix multiplication of sparse matrices. The sparseness of matrices is then utilized to obtain efficient encoders which can achieve encoding in real time with reduced pre-computation complexity. Hardware implementation of encoder and simulation results show that the proposed encoder achieves throughput in excess of 1 Gbps with the same error correcting performance as the conventional designs.     

A special class of quasi-cyclic low-density parity-check codes based on repetition codes and permutation matrices

We propose a new ensemble of binary low-density parity-check codes with paritycheck matrices based on repetition codes and permutation matrices. The proposed class of codes is a subensemble of quasi-cyclic codes. For the constructed ensemble, we obtain minimum distance estimates. We present simulation results for the proposed code constructions under the (Sum-Product) iterative decoding algorithm for transmission over an additive white Gaussian noise channel using binary phase-shift keying.     

多进制低密度奇偶校验码的扩展最小和译码算法研究

综述了多进制LDPC码的几种常用译码算法,重点讲解分析了其中的扩展最小和算法,并采用对比的方法证明其优越性。     

Erasure correction by low-density codes

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.     

A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

This paper concerns a domination problem in graphs with parity constraints. The task is to find a subset of the vertices with minimum cost such that for every vertex the number of chosen vertices in its neighbourhood has a prespecified parity. This problem is known to be ${\mathcal NP}$ -hard for general graphs. A linear time algorithm was developed for series-parallel graphs and trees with unit cost and restricted to closed neighbourhoods. We present a linear time algorithm for the parity domination problem with open and closed neighbourhoods and arbitrary cost functions on graphs with bounded treewidth and distance-hereditary graphs.     

Classes of quantum codes derived from self-dual orientable embeddings of complete multipartite graphs

Quantum Information Processing - Semi-quantum protocols that allow some of the users to remain classical are proposed for a large class of problems associated with secure communication and secure...     

A new class of quaternary codes

In this paper we introduce a new concept of modified Butson-Hadamard matrices and construct two families of quaternary codes derived from the corresponding families of modified complex matrices with entries from a finite cyclic group of order 4. These nonlinear codes have parameters lying very close to the Plotkin bound and admit very easy construction and decoding procedures.     

A new class of nonlinear Q-ary codes

In this paper we construct two new families of nonlinear q-ary codes derived from the corresponding families of modified Butson Hadamard matrices. These codes have very easy construction and decoding procedures, and their parameters are rather close to the Plotkin bound.     

A new class of nonlinear sensary codes

In this paper we construct two new families of nonlinear senary codes derived from the corresponding families of modified Butson-Hadamard matrices. These codes have easy construction and decoding procedures, and their parameters are very close to the Plotkin bound.     

量子纠错码[[7,1,4]]_p(p>3)存在性的图论构造方法

利用由Schingemann和Werner两人提出的构造量子纠错码的图论方法,证明了量子纠错码[[7,1,4]]p(p>3)的存在性。     

Low complexity construction for quasi-cyclic low-density parity-check codes by Progressive-Block Growth

In this paper, a novel method for constructing quasi-cyclic LDPC codes with low complexity is proposed. By choosing each circulant permutation matrix sequentially, the proposed method ensures that the current circulant permutation matrix forms no cycles of length smaller than g with the existent circulant permutation matrices. The construction complexity of the proposed algorithm is much lower than that of the random construction. Simulation results show that the proposed QC-LDPC codes can outperf...     

Two families of BCH codes and new quantum codes

In this paper, two families of non-narrow-sense (NNS) BCH codes of lengths \(n=\frac{q^{2m}-1}{q^2-1}\) and \(n=\frac{q^{2m}-1}{q+1}\) (\(m\ge 3)\) over the finite field \(\mathbf {F}_{q^2}\) are studied. The maximum designed distances \(\delta ^\mathrm{new}_\mathrm{max}\) of these dual-containing BCH codes are determined by a careful analysis of properties of the cyclotomic cosets. NNS BCH codes which achieve these maximum designed distances are presented, and a sequence of nested NNS BCH codes that contain these BCH codes with maximum designed distances are constructed and their parameters are computed. Consequently, new nonbinary quantum BCH codes are derived from these NNS BCH codes. The new quantum codes presented here include many classes of good quantum codes, which have parameters better than those constructed from narrow-sense BCH codes, negacyclic and constacyclic BCH codes in the literature.     

Optimal binary codes and binary construction of quantum codes

This paper discusses optimal binary codes and pure binary quantum codes created using Steane construction. First, a local search algorithm for a special subclass of quasi-cyclic codes is proposed, then five binary quasi-cyclic codes are built. Second, three classical construction methods are generalized for new codes from old such that they are suitable for constructing binary self-orthogonal codes, and 62 binary codes and six subcode chains of obtained self-orthogonal codes are designed. Third, six pure binary quantum codes are constructed from the code pairs obtained through Steane construction. There are 66 good binary codes that include 12 optimal linear codes, 45 known optimal linear codes, and nine known optimal self-orthogonal codes. The six pure binary quantum codes all achieve the performance of their additive counterparts constructed by quaternary construction and thus are known optimal codes.     

A comparison of approaches for finding minimum identifying codes on graphs

In order to formulate mathematical conjectures likely to be true, a number of base cases must be determined. However, many combinatorial problems are NP-hard and the computational complexity makes this research approach difficult using a standard brute force approach on a typical computer. One sample problem explored is that of finding a minimum identifying code. To work around the computational issues, a variety of methods are explored and consist of a parallel computing approach using MATLAB, an adiabatic quantum optimization approach using a D-Wave quantum annealing processor, and lastly using satisfiability modulo theory (SMT) and corresponding SMT solvers. Each of these methods requires the problem to be formulated in a unique manner. In this paper, we address the challenges of computing solutions to this NP-hard problem with respect to each of these methods.     

Construction of nonbinary quantum cyclic codes by using graph method

~~Construction of nonbinary quantum cyclic codes by using graph method1. Wootters, W. K., Zurek, W. H., A single quantum cannot be cloned, Nature, 1982, 299: 802-803. 2. Shor, P. W., Scheme for reducing decoherence in quantum memory, Phys. Rev. A, 1995, 52: 2493. 3. Steane, A. M., Multiple particle interference and quantum error correction, Proc. Roy. Soc. London A, 1996, 452: 2551-2557. 4. Calderbank, A. R., Rains, E. M., Shor, P. W. et al., Quantum error correction via c…     

A new approach to constructing CSS codes based on factor graphs

A novel, practical and convenient approach to constructing Calderbank-Shor-Steane (CSS) codes based on factor graphs is presented in this paper. Our proposed method is applied to solve two problems associated with constructing CCS codes. One is judging whether a code is a weakly self-dual code or not, the other is finding the generator matrix and parity-check matrix of a weakly self-dual code. The novelty, practicality and convenience of the approach are shown as follows. First, the approach is a hitherto unexplored one to constructing CSS codes. Second, the judgment of a weakly self-dual code is entirely based on factor graphs. Namely, we consider a code a weakly self-dual one when the Tanner graph or convolutional factor graph of its dual code can be obtained by that of its own via our proposed transform T_R→L. Finally, we can obtain the generator matrix and parity-check matrix of a weakly self-dual code via factor graphs other than conventional algebra methods, which allow us avoid matrix computation to get them. An example is given to show how to construct quantum CSS code based on factor graphs. The method can be extended to other CSS codes.     

Controllability of quantum walks on graphs

In this paper, we consider discrete time quantum walks on graphs with coin, focusing on the decentralized model, where the coin operation is allowed to change with the vertex of the graph. When the coin operations can be modified at every time step, these systems can be looked at as control systems and techniques of geometric control theory can be applied. In particular, the set of states that one can achieve can be described by studying controllability. Extending previous results, we give a characterization of the set of reachable states in terms of an appropriate Lie algebra. Controllability is verified when any unitary operation between two states can be implemented as a result of the evolution of the quantum walk. We prove general results and criteria relating controllability to the combinatorial and topological properties of the walk. In particular, controllability is verified if and only if the underlying graph is not a bipartite graph and therefore it depends only on the graph and not on the particular quantum walk defined on it. We also provide explicit algorithms for control and quantify the number of steps needed for an arbitrary state transfer. The results of the paper are of interest in quantum information theory where quantum walks are used and analyzed in the development of quantum algorithms.