Service scheduling optimization for multiple tower cranes considering the interval time of the cross-tasks

1.   Introduction

Quantum error-correcting plays a vital role in both quantum computing and quantum communication. Errors caused by noises are inevitable in the processing of quantum information. Fortunately, it has been found that quantum information can be protected under some reasonable physical assumptions by encoding it into quantum error-correcting codes (QECCs). Since the pioneering work of Shor ^[1] and Steane ^[2], QECCs has been developed rapidly in the past decades. In 1996, Calderbank et al. ^[2,3] proposed the first systematic method for constructing binary QECCs, the $CSS$ construction. Afterwards, Steane et al. ^[4] improved the $CSS$ construction by using two self-orthogonal codes with inclusion relations and proposed the Steane construction. Whereafter, $CSS$ construction ^[5,6] and Steane construction ^[7,8] were generalized to the non-binary cases.

Lemma 1. ^[7,8](Steane construction) Let $C_1$ and $C_2$ be $[n, k_1, d_1]_q$ and $[n, k_2, d_2]_q$ linear codes, respectively. If $C_1^\bot\subset C_1\subset C_2$, and $k_1+2\leq k_2$, then there exists an $\left [\left [n, k_1+k_2-n, \min\left \{ d_1, \left \lceil \frac{q+1}{q} d_2 \right \rceil \right \} \right] \right]_q$ pure QECC.

As a special kind of linear codes, self-dual codes has attracted many scholars to study it deeply because of its unique properties. In ^[9], Rains et al. reviewed the achievements of self-dual codes before 1998. In ^[10], Grassl et al. constructed a large number of self-dual codes with Euclidean or Hermitian inner products over small finite fields. Therewith, Harada et al. ^[11] improved the construction methods to obtain a large number of ternary self-dual codes, and established a database of self-dual codes of short lengths in ^[12].

According to the theory of classical groups, any self-orthogonal code is a subcode of a self-dual code or a maximal self-orthogonal code. Therefore, it is a feasible way to construct self-orthogonal codes by searching for subcodes of self-dual codes and self-orthogonal codes. Li et al. ^[13] introduced the concept of $S$-chain over $F_2$, and obtained a batch of binary QECCs by searching $S$-chains of binary self-dual codes. In ^[14], Freibert et al. constructed many optimal self-orthogonal codes by searching for some binary self-dual codes. In ^[15,16], Fan et al. constructed many record-breaking binary QECCs by searching for subcode pairs of self-orthogonal codes or self-dual codes. However, due to constraints in practical situations, these studies are less concerned with the algebraic structure of subcodes. In this work, we reveal the relationship between the dual distance of linear code and its subcodes, and design a computer-supported $S$-chain search method. Here we give the definition of $S$-chain over $F_q$ as follows.

Definition 1. Let $C_{k_i, n}$ be $[n, k_i, d_i]$ $(i = 1, 2, \dots, t)$ linear codes over $F_q$. If $C_{k_i, n}^{\perp} \subset C_{k_i, n} \subset C_{k_{i+1}, n}$, then $C_{k_1, n} \subset C_{k_2, n} \cdots \subset C_{k_t, n}$ is called an $S$-chain.

Obviously, for linear codes, one can construct $S$-chains by searching for subcode chains. Consequently, the construction of QECCs using $S$-chains can be decomposed into two subproblems.

1). Which kind of codes have potential subcodes with large dual distance?

2). For a linear code $C$, how to find a subcode chain with large dual distances?

In the study, we find that for a linear code $C$, if the covering radius of its dual code is larger, then the probability of searching for subcodes with a large dual distance is higher, so the first question is answered. However, if $C$ is an $[n, k]$ code $F_q$, then the number of subcode chains ^[17] is $\prod_{t = 2}^{k} Q[t, t-1] = \prod_{t = 2}^{k} \frac{q^{t}-1}{q-1}$, where $Q[t, r]$ is $q-ary$ Gaussian binomial coefficient $\prod_{j = 0}^{r-1} \frac{q^{t-j}-1}{q^{r-j}-1}$. Hence, it will be tough for large dimension to determine $S$-chains of $C$ by a brute-force search. Thus, we transform the problem of constructing $S$-chains into an optimization problem by virtue of covering radius, and design a feasible algorithm, so that the second problem is partially solved.

Just like classical case, one of the central tasks of quantum error-correcting is to construct QECCs with good parameters. When the length $n$ and dimension $k$ are fixed, we want to obtain a large minimum distance $d$. Conversely, when the minimum distance $d$ is equal, we want the rate $\frac{k}{n}$ to be larger. There are some bounds that are helpful to judge the performance of QECCs, among which the quantum Gilbert-Vashamov ($GV$) bounds ^[18] are widely used.

Lemma 2. ^[18](quantum $GV$ bound) Suppose that $n > k_{GV}\ge 2$, and $n\equiv k_{GV} \left (\bmod \ 2 \right)$, $d\ge 2$.Then, there exists an $[[n, k_{GV}, d]]_q$ pure QECC if the inequality is satisfied.

With reference to ^[18], if an $[[n, k, d]]_q$ QECC beats this bound, i.e., $k\ge k_{GV}$, then it has excellent parameters.

The organizational structure of this paper is as follows. In Section 2, basic knowledge of linear codes are introduced. In Section 3, the relation between linear codes and the dual distances of its subcodes is deduced, and a new $S$-chain search method is proposed. In Section 4, we construct 11 self-orthogonal codes by shortening 5 known extremal self-dual codes, and 18 $S$-chains are obtained through our method. The related QECCs are obtained from our $S$-chains by Steane construction and a comparison of the QECCs is shown. Conclusion is given in Section 5.

2.   Preliminaries

Firstly, we give some basic knowledge on linear codes. For more details, we refer the readers to standard textbook ^[19].

Let $F_3 = \{0, 1, 2\}$ be the Galois field with three elements, and let $F^n_3$ be the $n$-dimensional vector space over $F_3$. An $[n, k]_3$ linear code is a $k$-dimensional linear subspace of $F_3^n$. The Hamming weight $wt(\mathbf{v})$ of a vector $\mathbf{v} = (v_1, v_2, \dots, v_n)$ is the number of non-zero coordinates in it. The minimum Hamming distance of a linear code is $d(C) = \min\left\{ wt(\mathbf{u}-\mathbf{v}) \mid \mathbf{u, v}\in C, \mathbf{u} \ne \mathbf{v}\right\}$. An $[n, k]$ linear code with minimum distance $d$ over $F_3$ is expressed as an $[n, k, d]_3$ code, $\frac{k}{n}$ is called information rate of $C$. If a linear code $C$ is generated by $G$, we can denote as $C = \left \langle G \right \rangle$. A subspace $\widehat{C}$ of code $C$ is a subcode of $C$, which can be denoted as $\widehat{C} \subset C$.

For $\mathbf{x} = (x_1, x_2, \dots, x_n)$, $\mathbf{y} = (y_1, y_2, \dots, y_n)$ $\in F_3^n$, the Euclidean inner product of vectors $\mathbf{x}, \mathbf{y}$ is defined as $(\mathbf{x}, \mathbf{y}) = \mathbf{x} \mathbf{y}^T = x_1 y_1+x_2 y_2+\dots+x_n y_n$. If $(\mathbf{x}, \mathbf{y}) = 0$, then $\mathbf{x}$ and $\mathbf{y}$ are orthogonal. For a linear code $C \subset F^n_3$, the Euclidean dual code of $C$ is $C^\perp = \{x \in F^n_3 | (x, c) = 0, c \in C\}$. If $C \subset C^\perp$, then $C$ is a self-orthogonal code, if $C = C^\perp$, then $C$ is a self-dual code. The lengths of all ternary self-dual codes satisfy $n \equiv 0 \pmod{4}$, and their minimum distance $d$ is bounded by $d\le 3[n/12]+3$, if $d = 3[n/12]+3$, then the code is called extremal. For any ternary self-orthogonal codes over $F_3$, its minimum distance $d$ is a multiple of 3.

Let $\mathbf{r} = (r_0, r_1, \dots, r_{n-1})$ be a vector of length $n$. If $A$ is generated by $\mathbf{r}$, then it can be denoted as: $A = gcirc(\mathbf{r}, \eta)$, where

If $\eta = 1$ then $A$ is a circulant matrix generated by $\mathbf{r}$, if $\eta = -1$ then $A$ is called nega-circulant, both of which can be employed to construct self-dual codes. And circulant matrices that used in this paper are all nega-circulant.

Two construction methods of self-dual codes are applied in this paper. The first one is called pure double circulant, which is used in ^[10], and generator matrix of this method is $G = \left (I_n\mid A \right)$, where $A$ is an $n \times n$ circulant matrix.

The second is called two-block circulant, in which two circulant matrices are used to construct a generator matrix, and many optimal self-dual codes over $F_3$ are constructed in ^[11] by this method. The generator matrix is

where $A$ and $B$ are circulant matrices of order $n$ satisfying $A A^{T}+B B^{T} = -I_n$.

In this paper, some extremal self-dual codes in ^[10,11] are involved and we give them in Table 1. And a generator matrix $G^2_{20}$ of self-dual code $C^2_{20}$ in ^[12] is also given below.

3.   New method of searching for $S$-chains

This section presents a method for determining upper bound on the dual distance of subcodes, which allows us to evaluate the search potential of linear codes. Then, a feasible $S$-chain search algorithm is designed accordingly.

3.1.   The upper bound on the dual distance of subcodes

Let $C$ be an $[n, k, d]$ linear code over $F_q$. The dual code of $C$ is denoted as $C^\perp$. In ^[19], covering radius of $C$ is defined as following lemma.

Lemma 3. ^[19] Let $C$ be an $[n, k, d]$ code over $F_q$. The covering radius of $C$, $\rho(C)$ is the smallest integer $s$ such that $F^n_q$ is the union of the spheres of radius $s$ centered at the codewords of $C$. Equivalently,

According to Lemma 3, it is easy to deduce that the following lemma holds.

Lemma 4. For two linear codes $C_1$, $C_2$, if $C_1 \subset C_2$, then $\rho(C_2) \le \rho(C_1)$.

In addition, we find that there is a bounded relationship between $\rho(C^\perp)$ and $d(\widehat{C}^\perp)$, as shown in Theorem 3.1.

Theorem 1. Let $C$ be an $[n, k, d]$ linear code over $F_q$, then for any subcode $\widehat{C}$ of $C$, the following hold:

(1) $d(\widehat{C}^\perp)\leq \rho(C^\perp)$;

(2) $\rho(\widehat{C}^\perp)\leq \rho(C^\perp)$;

Proof: According to Lemma 3,

there is,

Furthermore,

So $d(\widehat{C}^{\perp}) \leq \rho(C^\perp).$

Similarly, by Lemma 4, $\rho(\widehat{C}^{ \perp}) \leq \rho(C^\perp)$.

By Theorem 1, it is easy to conclude that covering radius of dual code $C^{\perp}$ is the upper bound on the dual distance of subcode $\widehat{C}$. In addition, we find that if $d(C^\perp) \ge \rho(C^\perp)$, then the subcodes that reach the upper bound on the dual distance can always be obtained by our searching method. Thus, for linear code $C$, the larger $d(C^\perp)$ and $\rho(C^\perp)$, the more likely to search for subcodes with large dual distances, i.e., $C$ has greater search potential. It is easy to determine that extremal self-dual codes have good search potential in accordance with this criterion. Therefore, this paper chooses extremal self-dual codes as the object of study and constructs self-orthogonal codes by shortening them. Next, we refer to linear code with lager $d(C^\perp)$ and $\rho(C^\perp)$ as code have good search potential. The following $S$-chain search algorithm is designed accordingly.

3.2.   Algorithm for searching $S$-chain

Let $G_{k, n}$ be a generator matrix for an $[n, k]$ linear code $C_{k, n}$ over $F_3$. And denote $D_{k-1, k} = \left(I_{k-1} \mid \alpha_{k-1}\right)$, where $\alpha_{k-1}$ is a column vector of length $k-1$. We will refer to $\alpha$ as dimension reduction vector. According to the theory of classical groups, subcodes of linear code $C_{k, n}$ can be constructed in the following way,

An $[n, k-1]$ subcode $C_{k-1, n}$ of $C_{k, n}$ can be generated by $G_{k-1, n}$. Thus, by searching $\alpha_{k-1}$, we can find subcodes $C_{k-1, n}$ with large dual distance. Inspired by ^{[14,15,16,17]}, we design the following subcodes search optimization model.

where $w_1$, $w_2$ are weight factors, and $w_1, w_2\in (0, 1)$. For a linear code $C_{k, n}$, $d(C_{k-1, n}^{\perp})$ and $\rho(C_{k-1, n}^{\perp})$ sometimes cannot be maximized simultaneously, so their priorities need to be set. Therefore, we determine the priority of $d(C_{k-1, n}^{\perp})$ and $\rho(C_{k-1, n}^{\perp})$ by using $w_1$ and $w_2$ to decide which subcode to be selected as the search target for the next round.

The priority of $d(C_{k-1, n}^{\perp})$ and $\rho(C_{k-1, n}^{\perp})$ can be determined by setting $w_1\ge w_2+0.5$ or $w_1+0.5\le w_2$, which corresponds to two search strategies, dual distance priority(DDP) and covering radius priority(CRP), both of which are used in this paper. In most cases, DDP strategy performs well and can be complemented by CRP strategy when its results are not good. Thus, DDP strategy is often used as the primary search strategy, while CRP strategy is used as an alternative. Sometimes a combination of these two strategies can achieve better results than either single strategy. Here we give our $S$-chain search algorithm based on these two strategies.

Algorithm for searching $S$-chain: An algorithm to construct $S$-chain by searching for subcode chain with optimal or near optimal dual distance distance.

(i) Input: Begin with a self-dual code or a self-orthogonal code $C_{k, n}$ with parameters $[n, k, d]$.

(ii) Output: Produce a related $S$-chain, $S = \{C_{i, n}|C_{n-k, n}\subset C_{n-k+1, n}\subset \dots \subset C_{n-1, n}\}$.

(a) Let $i = k$, and initialize the set $B$ = $\{ C_{i, n} \}$.

(b) Build a set $B_{i-1}$ of all subcodes $C_{i-1, n}$ of dimension $1$ lower of $C_{i, n}\in B$ by $C_{i-1, n} = \left \langle (I_{i-1}\mid \alpha _{i-1})\cdot G_{i, n} \right \rangle$, where $\alpha_{i-1} \in F_3^{i-1}$.

(c) Add $C_{i-1, n}$ to $B$ by selecting from $B_{i-1}$ according to DDP strategy or CRP strategy, then repeat step(b) by $i$ minus one.

(d) Stop once $i = 1$, and let $S$ be the dual chain of $B$, $S = \{ C^\perp \mid C^\perp \in B \} = \{C_{i, n}\mid C_{n-k, n}\subset C_{n-k+1, n}\subset \dots \subset C_{n-1, n}\}$.

For self-dual codes or self-orthogonal codes of short length $n\le28$, we can traverse $\alpha_{i-1}$ from $F_3^{i-1}$ in step (b), which performs well and running time is also acceptable. However, as the search space increases with length and dimension, the running time will increase exponentially. Therefore, as a simplification, a random algorithm can be obtained by replacing the generation method of $\alpha_{i-1}$ in step (b) with a random selection from $F_3^{i-1}$. In our study, the random algorithm also performs well for self-dual codes or self-orthogonal codes of length $28\le n\le36$.

4.   Construction of $S$-chains and related QECCs

This section focuses on constructing QECCs by searching for $S$-chains with large distances. Firstly, we construct 11 self-orthogonal codes by shortening 5 known extremal self-dual codes in Section 2, and 18 $S$-chains are obtained by our searching method. Further, many good quantum codes are derived via Steane construction, some of which improve existing results.

4.1.   Construction of self-orthogonal codes

In Section 3, we give criterion to evaluate the search potential of linear code. By applying our criterion to codes in ^[10,11,12], eight extremal self-dual codes with search potential are selected, which have been given in Section 2, in which $C^1_{32}$ and $C^1_{20}$ are used only to construct self-orthogonal codes by shortening. In Table 2, covering radius of the codes in Section 2 is given. According to ^[9], there is only one non-equivalent extremal self-dual code $C_{36}$. Unfortunately, we are unable to calculate covering radius of $C_{36}$ directly due to insufficient computational effort, so our estimates is given.

Furthermore, by shortening extremal self-dual codes in Section 2, we construct 11 self-orthogonal codes with good search potential, which are given in Table 3. Similar to $C_{36}$, covering radius of $C_{35}^\perp$ is also estimated value.

4.2.   Construction of $S$-chains and related QECCs

Next, 18 $S$-chains with large distances are obtained from extremal self-dual codes or self-orthogonal codes through our method. In particular, two of resulting $S$-chains are of length 20, and they are obtained by two different strategies, so that some parameters of these two chains are complementary. All $S$-chains are summarized in Theorem 4.1. For details please see "Appendix". It is easy to check that many codes in our $S$-chains are optimal by comparing them with linear codes in ^[20]. The symbol * in Theorem 4.1 means that those codes are optimal linear codes.

Theorem 4.1. For $n \in \{16, 18, 20, 21, \dots, 36 \} \setminus \{26, 27 \}$, there exists the following $S$-chains:

Many QECCs can be obtained from these $S$-chains by Steane construction, and the part that beats the quantum $GV$-bound is given in Corollary 1.

Corollary 1. Let $n \in \{16, 18, 20, 21, \dots, 36 \} \setminus \{26, 27 \}$, then the following QECCs over $F_3$ exists.

(1) $[[16,2,6]]_3$, $[[16,10,3]]_3$; $[[20,5,6]]_3$, $[[20,4,6]]_3$, $[[20,7,5]]_3$, $[[20,10,4]]_3$, $[[20,14,3]]_3$; $[[24,2,8]]_3$, $[[24,4,7]]_3$, $[[24,8,6]]_3$, $[[24,10,5]]_3$, $[[24,14,4]]_3$, $[[24,18,3]]_3$; $[[28,2,9]]_3$, $[[28,4,8]]_3$, $[[28,8,7]]_3$, $[[28,7,7]]_3$, $[[28,11,6]]_3$, $[[28,21,3]]_3$; $[[32,14,6]]_3$, $[[32,25,3]]_3$; $[[36,2,11]]_3$, $[[36,17,6]]_3$, $[[36,29,3]]_3$.

(2) $[[18,13,3]]_3$; $[[21,6,6]]_3$, $[[21,11,4]]_3$, $[[21,15,3]]_3$; $[[22,4,7]]_3$, $[[22,6,6]]_3$, $[[22,12,4]]_3$, $[[22,16,3]]_3$; $[[23,4,7]]_3$, $[[23,13,4]]_3$, $[[23,17,3]]_3$; $[[25,9,6]]_3$, $[[25,8,6]]_3$, $[[25,15,4]]_3$; $[[29,11,6]]_3$, $[[29,22,3]]_3$; $[[30,12,6]]_3$, $[[30,23,3]]_3$; $[[31,13,6]]_3$, $[[31,18,4]]_3$; $[[33,15,6]]_3$, $[[33,26,3]]_3$; $[[34,4,10]]_3$, $[[34,27,3]]_3$; $[[35,4,10]]_3$, $[[35,16,6]]_3$, $[[35,28,3]]_3$.

In order to illustrate that our QECCs has good parameters, the following Table 4 is provided, in which our QECCs are compared with those in ^[21,22], respectively. It is obvious that our QECCs improves the existing results.

5.   Conclusions

In this work, we construct many good quantum codes from $S$-chains of extremal self-dual codes or self-orthogonal codes over $F_3$. Firstly, with covering radius of linear codes, we determine the relationship between linear codes and the dual distance of its subcodes. Then, we identify the criterion to judge the search potential of linear codes and design a feasible algorithm. Finally, 18 $S$-chains with good parameters are obtained by our algorithm, and many good QECCs are derived via Steane construction, some of which improve existing results. In future studies, we will work to investigate the construction of optimal self-orthogonal codes, dual-containing codes, or quantum codes by searching for subcode chains of self-orthogonal codes with different inner products.

Acknowledgments

This work is supported by National Natural Science Foundation of China under Grant No. U21A20428, 11901579, 11801564, Natural Science Foundation of Shaanxi under Grant No. 2021JM-216, 2021JQ-335 and the Graduate Scientific Research Foundation of Fundamentals Department of Air Force Engineering University.

Conflict of interest

The authors declare no conflicts of interest regarding the publication of this paper.

Appendix

In Tables 5–22, $G^i_n$ denotes the generator matrix of $C^i_n$, where $C^i_n$ are given in Section II or IV. $\alpha_i$ is column vector, which are used for reducing dimension.

In particular, nested pairs that match the Steane construction condition can be used to construct quantum codes. In this paper, they are code pairs with distances: $(\ge11, 8), (\ge10, 7), (\ge9, 7)(\ge8, 6), (\ge7, 5), (\ge 6, 4), (\ge5, 4), (\ge4, 3), (\ge3, 2)$, and the difference between the dimensions of them is not less than 2.

For example, in Table 5, $[[16,2,6]]_3$ is derived from $[16,8,6]_3$$\subset$$[16,10,4]_3$. $[[16,6,4]]_3$ is derived from $[16,10,4]_3 \subset [16,12,3]_3$. $[[16,10,3]]_3$ is derived from $[16,12,3]_3 \subset [16,14,2]_3$. The quantum codes in Table 6–22 are also obtained by a similar way.

The symbol * in tables means that these codes are optimal codes. And the symbol $\diamond$ means those quantum codes beats the quantum GV bound.