Self-orthogonal codes with dual distance three and quantum codes with distance three over \mathbb F _5

Self-orthogonal codes with dual distance three and quantum codes with distance three constructed from self-orthogonal codes over $\mathbb F _5$ are discussed in this paper. Firstly, for given code length $n\ge 5$ , a $[n,k]_{5}$ self-orthogonal code with minimal dimension $k$ and dual distance three is constructed. Secondly, for each $n\ge 5$ , two nested self-orthogonal codes with dual distance two and three are constructed, and consequently quantum code of length $n$ and distance three is constructed via Steane construction. All of these quantum codes constructed via Steane construction are optimal or near optimal according to the quantum Hamming bound.     

Asymmetric quantum codes: new codes from old

In this paper we extend to asymmetric quantum error-correcting codes the construction methods, namely: puncturing, extending, expanding, direct sum and the $({ \mathbf u}| \mathbf{u}+{ \mathbf v})$ construction. By applying these methods, several families of asymmetric quantum codes can be constructed. Consequently, as an example of application of quantum code expansion developed here, new families of asymmetric quantum codes derived from generalized Reed-Muller codes, quadratic residue, Bose-Chaudhuri-Hocquenghem, character codes and affine-invariant codes are constructed.     

New asymmetric quantum codes over $$F_{q}$$

Two families of new asymmetric quantum codes are constructed in this paper. The first family is the asymmetric quantum codes with length \(n=q^{m}-1\) over \(F_{q}\), where \(q\ge 5\) is a prime power. The second one is the asymmetric quantum codes with length \(n=3^{m}-1\). These asymmetric quantum codes are derived from the CSS construction and pairs of nested BCH codes. Moreover, let the defining set \(T_{1}=T_{2}^{-q}\), then the real Z-distance of our asymmetric quantum codes are much larger than \(\delta _\mathrm{max}+1\), where \(\delta _\mathrm{max}\) is the maximal designed distance of dual-containing narrow-sense BCH code, and the parameters presented here have better than the ones available in the literature.     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

Higher dimensional bipartite composite systems with the same density matrix: separable,free entangled,or PPT entangled?

Given the density matrix of a bipartite quantum state, could we decide whether it is separable, free entangled, or PPT entangled? Here, we give a negative answer to this question by providing a lot of concrete examples of $16 \times 16$ density matrices, some of which are well known. We find that both separability and distillability are dependent on the decomposition of the density matrix. To be more specific, we show that if a given matrix is considered as the density operators of different composite systems, their entanglement properties might be different. In the case of $16 \times 16$ density matrices, we can look them as both $2 \otimes 8$ and $4 \otimes 4$ bipartite quantum states and show that their entanglement properties (i.e., separable, free entangled, or PPT entangled) are completely irrelevant to each other.     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

A representation of extra-special 2-group, entanglement, and Berry phase of two qubits in Yang-Baxter system

In this paper we show another representations of extra-special 2-groups. Based on this new representation, we infer a ${\mathbb{M}}$ matrix which obeys the extra-special 2-groups algebra relations. We also derive a unitary ${\breve{R}(\theta,\varphi)}$ matrix from the ${\mathbb{M}}$ using the Yang-Baxterization process. A Hamiltonian for the two qubits is constructed from the unitary ${\breve{R}(\theta,\varphi)}$ matrix. In this way, we study the Berry phase and entanglement of the two-qubit system. The results also establish relations between topological and holonomic quantum computation.     

New quantum codes from dual-containing cyclic codes over finite rings

Let \(R=\mathbb {F}_{2^{m}}+u\mathbb {F}_{2^{m}}+\cdots +u^{k}\mathbb {F}_{2^{m}}\), where \(\mathbb {F}_{2^{m}}\) is the finite field with \(2^{m}\) elements, m is a positive integer, and u is an indeterminate with \(u^{k+1}=0.\) In this paper, we propose the constructions of two new families of quantum codes obtained from dual-containing cyclic codes of odd length over R. A new Gray map over R is defined, and a sufficient and necessary condition for the existence of dual-containing cyclic codes over R is given. A new family of \(2^{m}\)-ary quantum codes is obtained via the Gray map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R. In particular, a new family of binary quantum codes is obtained via the Gray map, the trace map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R.     

Decoherence dynamics of geometric measure of quantum discord and measurement induced nonlocality for noninertial observers at finite temperature

Quantum discord quantifies the total non-classical correlations in mixed states. It is the difference between total correlation, measured by quantum mutual information, and the classical correlation. Another step forward towards the quantification of quantum discord was by Daki? et al. (Phys Rev Lett 105:190502, 2010) who introduced the geometric measure of quantum discord (GMQD) and derived an explicit formula for a two-qubit state. Recently, Luo and Fu (Phys Rev Lett 106:120401, 2011) introduced measurement-induced nonlocality (MIN) as a measure of nonlocality for a bipartite quantum system. The dynamics of GMQD is recently considered by Song et al. (arXiv: quant/ph.1203.3356) and Zhang et al. (Eur Phys J D 66:34, 2012) for inertial observers. However, the topic requires due attention in noninertial frames, particularly, from the perspective of MIN. Here I consider $X$ -structured bipartite quantum system in noninertial frames and analyze the decoherence dynamics of GMQD and MIN at finite temperature. The dynamics under the influence of amplitude damping, depolarizing and phase flip channels is discussed. It is worth-noting that initial state entanglement plays an important role in bipartite states. It is possible to distinguish the Bell, Werner and general type initial quantum states using GMQD. Sudden transition in the behaviour of GMQD and MIN occurs depending upon the mean photon number of the local environment. The transition behaviour disappears for larger values of $\bar{n},$ i.e. $\bar{n}>0.3.$ It becomes more prominent, when environmental noise is introduced in the system. In the presence of environmental noise, as we increase the value of acceleration $r$ , GMQD and MIN decay due to Unruh effect. The effect is prominent for the phase flip and amplitude damping channels. However, in case of depolarizing channel, no sudden change in the behaviour of GMQD and MIN is observed. The environmental noise has stronger affect on the dynamics of GMQD and MIN as compared to the Unruh effect. Furthermore, Werner like states are more robust than General type initial states at finite temperature.     

New q-ary quantum MDS codes with distances bigger than $$\frac{ q}{2}$$

The construction of quantum MDS codes has been studied by many authors. We refer to the table in page 1482 of (IEEE Trans Inf Theory 61(3):1474–1484, 2015) for known constructions. However, there have been constructed only a few q-ary quantum MDS \([[n,n-2d+2,d]]_q\) codes with minimum distances \(d>\frac{q}{2}\) for sparse lengths \(n>q+1\). In the case \(n=\frac{q^2-1}{m}\) where \(m|q+1\) or \(m|q-1\) there are complete results. In the case \(n=\frac{q^2-1}{m}\) while \(m|q^2-1\) is neither a factor of \(q-1\) nor \(q+1\), no q-ary quantum MDS code with \(d> \frac{q}{2}\) has been constructed. In this paper we propose a direct approach to construct Hermitian self-orthogonal codes over \(\mathbf{F}_{q^2}\). Then we give some new q-ary quantum codes in this case. Moreover many new q-ary quantum MDS codes with lengths of the form \(\frac{w(q^2-1)}{u}\) and minimum distances \(d > \frac{q}{2}\) are presented.     

Join-Reachability Problems in Directed Graphs

For a given collection \(\mathcal{G}\) of directed graphs we define the join-reachability graph of \(\mathcal{G}\) , denoted by \(\mathcal{J}(\mathcal{G})\) , as the directed graph that, for any pair of vertices u and v, contains a path from u to v if and only if such a path exists in all graphs of  \(\mathcal{G}\) . Our goal is to compute an efficient representation of  \(\mathcal{J}(\mathcal{G})\) . In particular, we consider two versions of this problem. In the explicit version we wish to construct the smallest join-reachability graph for  \(\mathcal{G}\) . In the implicit version we wish to build an efficient data structure, in terms of space and query time, such that we can report fast the set of vertices that reach a query vertex in all graphs of  \(\mathcal{G}\) . This problem is related to the well-studied reachability problem and is motivated by emerging applications of graph-structured databases and graph algorithms. We consider the construction of join-reachability structures for two graphs and develop techniques that can be applied to both the explicit and the implicit problems. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.     

On the construction of stabilizer codes with an arbitrary binary matrix

This paper proposes a simple framework for constructing a stabilizer code with an arbitrary binary matrix. We define a relation between A ₁ and A ₂ of a binary check matrix A = (A ₁|A ₂) associated with stabilizer generators of a quantum error-correcting code. Given an arbitrary binary matrix, we can derive a pair of A ₁ and A ₂ by the relation. As examples, we illustrate two kinds of stabilizer codes: quantum LDPC codes and quantum convolutional codes. By the nature of the proposed framework, the stabilizer codes covered in this paper belong to general stabilizer (non-CSS) codes.     

Partition Into Triangles on Bounded Degree Graphs

We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm. We also show that this problem becomes $\mathcal{NP}$ -complete on graphs of maximum degree four. Moreover, we show that there is no subexponential-time algorithm for this problem on graphs of maximum degree four unless the Exponential-Time Hypothesis fails. However, the Partition Into Triangles problem on graphs of maximum degree at most four is in many cases practically solvable as we give an algorithm for this problem that runs in $\mathcal{O}(1.02220^{n})$ time and linear space.     

Characterization of quantum circulant networks having perfect state transfer

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph G, which is characterized by its circulant adjacency matrix A. Formally, we say that there exists a perfect state transfer (PST) between vertices ${a,b\in V(G)}$ if |F(τ) _ab | = 1, for some positive real number τ, where F(t) = exp(i At). Saxena et al. (Int J Quantum Inf 5:417–430, 2007) proved that |F(τ) _aa | = 1 for some ${a\in V(G)}$ and ${\tau\in \mathbb {R}^+}$ if and only if all eigenvalues of G are integer (that is, the graph is integral). The integral circulant graph ICG _n (D) has the vertex set Z _n = {0, 1, 2, . . . , n ? 1} and vertices a and b are adjacent if ${\gcd(a-b,n)\in D}$ , where ${D \subseteq \{d : d \mid n, \ 1 \leq d < n\}}$ . These graphs are highly symmetric and have important applications in chemical graph theory. We show that ICG _n (D) has PST if and only if ${n\in 4\mathbb {N}}$ and ${D=\widetilde{D_3} \cup D_2\cup 2D_2\cup 4D_2\cup \{n/2^a\}}$ , where ${\widetilde{D_3}=\{d\in D\ |\ n/d\in 8\mathbb {N}\}, D_2= \{d\in D\ |\ n/d\in 8\mathbb {N}+4\}{\setminus}\{n/4\}}$ and ${a\in\{1,2\}}$ . We have thus answered the question of complete characterization of perfect state transfer in integral circulant graphs raised in Angeles-Canul et al. (Quantum Inf Comput 10(3&4):0325–0342, 2010). Furthermore, we also calculate perfect quantum communication distance (distance between vertices where PST occurs) and describe the spectra of integral circulant graphs having PST. We conclude by giving a closed form expression calculating the number of integral circulant graphs of a given order having PST.     

Randomness Buys Depth for Approximate Counting

We show that the promise problem of distinguishing n-bit strings of relative Hamming weight \({1/2 + \Omega(1/{\rm lg}^{d-1} n)}\) from strings of weight \({1/2 - \Omega(1/{\rm \lg}^{d - 1} n)}\) can be solved by explicit, randomized (unbounded fan-in) poly(n)-size depth-d circuits with error \({\leq 1/3}\) , but cannot be solved by deterministic poly(n)-size depth-(d+1) circuits, for every \({d \geq 2}\) ; and the depth of both is tight. Our bounds match Ajtai’s simulation of randomized depth-d circuits by deterministic depth-(d + 2) circuits (Ann. Pure Appl. Logic; ’83) and provide an example where randomization buys resources. To rule out deterministic circuits, we combine Håstad’s switching lemma with an earlier depth-3 lower bound by the author (Computational Complexity 2009). To exhibit randomized circuits, we combine recent analyses by Amano (ICALP ’09) and Brody and Verbin (FOCS ’10) with derandomization. To make these circuits explicit, we construct a new, simple pseudorandom generator that fools tests \({A_1 \times A_2 \times \cdots \times A_{{\rm lg}{n}}}\) for \({A_i \subseteq [n], |A_{i}| = n/2}\) with error 1/n and seed length O(lg n), improving on the seed length \({\Omega({\rm lg}\, n\, {\rm lg}\, {\rm lg}\, n)}\) of previous constructions.     

Improved constructions for quantum maximum distance separable codes

In this work, we further improve the distance of the quantum maximum distance separable (MDS) codes of length \(n=\frac{q^2+1}{10}\). This yields new families of quantum MDS codes. We also construct a family of new quantum MDS codes with parameters \([[\frac{q^2-1}{3}, \frac{q^2-1}{3}-2d+2, d]]_{q}\), where \(q=2^m\), \(2\le d\le \frac{q-1}{3}\) if \(3\mid (q+2)\), and \(2\le d\le \frac{2q-1}{3}\) if \(3\mid (q+1)\). Compared with the known quantum MDS codes, these quantum MDS codes have much larger minimum distance.     

Construction of general quantum channel for quantum teleportation

We investigate teleportation and controlled teleportation of an arbitrary $N$ -qubit state by using a multipartite entanglement channel. By establishing one-to-one correspondence between an $N$ -qubit quantum state and a high-dimension quantum state, we construct a general quantum channel for quantum teleportation and controlled teleportation of an arbitrary $N$ -qubit state. Furthermore, we generalize the definition of bipartite maximally entangled state for a multi-qubit system, and show that our teleportation protocols can be utilized not only to construct a variety of genuine multipartite entangled states, but also to identify and explore the capability of multipartite entanglement for quantum teleportation and controlled teleportation.     

Exact and Parameterized Algorithms for Max Internal Spanning Tree

We consider the $\mathcal{NP}$ -hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form $\mathcal{O}^{*}(c^{n})$ with c≤2. For graphs with bounded degree, c<2. The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of $\mathcal{O}(1.8612^{n})$ when analyzed with respect to the number of vertices. We also show that its running time is $2.1364^{k} n^{\mathcal{O}(1)}$ when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.     

Quantum discord in spin systems with dipole–dipole interaction

The behavior of total quantum correlations (discord) in dimers consisting of dipolar-coupled spins 1/2 are studied. We found that the discord $Q=0$ at absolute zero temperature. As the temperature $T$ increases, the quantum correlations in the system increase at first from zero to its maximum and then decrease to zero according to the asymptotic law $T^{-2}$ . It is also shown that in absence of external magnetic field $B$ , the classical correlations $C$ at $T\rightarrow 0$ are, vice versa, maximal. Our calculations predict that in crystalline gypsum $\hbox {CaSO}_{4}\cdot \hbox {2H}_{2}{\hbox {O}}$ the value of natural $(B=0)$ quantum discord between nuclear spins of hydrogen atoms is maximal at the temperature of 0.644  $\upmu $ K, and for 1,2-dichloroethane $\hbox {H}_{2}$ ClC– $\hbox {CH}_{2}{\hbox {Cl}}$ the discord achieves the largest value at $T=0.517~\upmu $ K. In both cases, the discord equals $Q\approx 0.083$  bit/dimer what is $8.3\,\%$ of its upper limit in two-qubit systems. We estimate also that for gypsum at room temperature $Q\sim 10^{-18}$  bit/dimer, and for 1,2-dichloroethane at $T=90$  K the discord is $Q\sim 10^{-17}$  bit per a dimer.     

Quantum random walk polynomial and quantum random walk measure

In the paper, we introduce a quantum random walk polynomial (QRWP) that can be defined as a polynomial $\{P_{n}(x)\}$ , which is orthogonal with respect to a quantum random walk measure (QRWM) on $[-1, 1]$ , such that the parameters $\alpha _{n},\omega _{n}$ are in the recurrence relations $$\begin{aligned} P_{n+1}(x)= (x - \alpha _{n})P_{n}(x) - \omega _{n}P_{n-1}(x) \end{aligned}$$ and satisfy $\alpha _{n}\in \mathfrak {R},\omega _{n}> 0$ . We firstly obtain some results of QRWP and QRWM, in which case the correspondence between measures and orthogonal polynomial sequences is one-to-one. It shows that any measure with respect to which a quantum random walk polynomial sequence is orthogonal is a quantum random walk measure. We next collect some properties of QRWM; moreover, we extend Karlin and McGregor’s representation formula for the transition probabilities of a quantum random walk (QRW) in the interacting Fock space, which is a parallel result with the CGMV method. Using these findings, we finally obtain some applications for QRWM, which are of interest in the study of quantum random walk, highlighting the role played by QRWP and QRWM.