The panpositionable panconnectedness of crossed cubes

In many parallel and distributed multiprocessor systems, the processors are connected based on different types of interconnection networks. The topological structure of an interconnection network is typically modeled as a graph. Among the many kinds of network topologies, the crossed cube is one of the most popular. In this paper, we investigate the panpositionable panconnectedness problem with respect to the crossed cube. A graph G is r-panpositionably panconnected if for any three distinct vertices x, y, z of G and for any integer \(l_1\) satisfying \(r \le l_1 \le |V(G)| - r - 1\), there exists a path \(P = [x, P_1, y, P_2, z]\) in G such that (i) \(P_1\) joins x and y with \(l(P_1) = l_1\) and (ii) \(P_2\) joins y and z with \(l(P_2) = l_2\) for any integer \(l_2\) satisfying \(r \le l_2 \le |V(G)| - l_1 - 1\), where |V(G)| is the total number of vertices in G and \(l(P_1)\) (respectively, \(l(P_2)\)) is the length of path \(P_1\) (respectively, \(P_2\)). By mathematical induction, we demonstrate that the n-dimensional crossed cube \(CQ_n\) is n-panpositionably panconnected. This result indicates that the path embedding of joining x and z with a mediate vertex y in \(CQ_n\) is extremely flexible. Moreover, applying our result, crossed cube problems such as panpositionable pancyclicity, panpositionably Hamiltonian connectedness, and panpositionable Hamiltonicity can be solved.     

Extremal properties of conditional entropy and quantum discord for XXZ,symmetric quantum states

For the XXZ subclass of symmetric two-qubit X states, we study the behavior of quantum conditional entropy \(S_{cond}\) as a function of measurement angle \(\theta \in [0,\pi /2]\). Numerical calculations show that the function \(S_{cond}(\theta )\) for X states can have at most one local extremum in the open interval from zero to \(\pi /2\) (unimodality property). If the extremum is a minimum, the quantum discord displays region with variable (state-dependent) optimal measurement angle \(\theta ^*\). Such \(\theta \)-regions (phases, fractions) are very tiny in the space of X-state parameters. We also discover the cases when the conditional entropy has a local maximum inside the interval \((0,\pi /2)\). It is remarkable that the maxima exist in surprisingly wide regions, and the boundaries for such regions are defined by the same bifurcation conditions as for those with a minimum.     

Monogamy and polygamy for multi-qubit W-class states using convex-roof extended negativity of assistance and Rényi-$$\alpha $$ entropy

We present some new analytical polygamy inequalities satisfied by the x-th power of convex-roof extended negativity of assistance with \(x\ge 2\) and \(x\le 0\) for multi-qubit generalized W-class states. Using Rényi-\(\alpha \) entropy (R\(\alpha \)E) with \(\alpha \in [(\sqrt{7}-1)/2, (\sqrt{13}-1)/2]\), we prove new monogamy and polygamy relations. We further show that the monogamy inequality also holds for the \(\mu \)th power of Rényi-\(\alpha \) entanglement. Moreover, we study two examples in multipartite higher-dimensional system for those new inequalities.     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.     

No nexiste nce of n-qubit u nexte ndible product bases of size $$2^ n-5$$2 n-5

It is known that the n-qubit system has no unextendible product bases (UPBs) of cardinality \(2^n-1\), \(2^n-2\) and \(2^n-3\). On the other hand, the n-qubit UPBs of cardinality \(2^n-4\) exist for all \(n\ge 3\). We prove that they do not exist for cardinality \(2^n-5\).     

Construction of quantum caps in projective space <Emphasis Type="Italic">PG</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, 4) and quantum codes of distance 4

Constructions of quantum caps in projective space PG(r, 4) by recursive methods and computer search are discussed. For each even n satisfying \(n\ge 282\) and each odd z satisfying \(z\ge 275\), a quantum n-cap and a quantum z-cap in \(PG(k-1, 4)\) with suitable k are constructed, and \([[n,n-2k,4]]\) and \([[z,z-2k,4]]\) quantum codes are derived from the constructed quantum n-cap and z-cap, respectively. For \(n\ge 282\) and \(n\ne 286\), 756 and 5040, or \(z\ge 275\), the results on the sizes of quantum caps and quantum codes are new, and all the obtained quantum codes are optimal codes according to the quantum Hamming bound. While constructing quantum caps, we also obtain many large caps in PG(r, 4) for \(r\ge 11\). These results concerning large caps provide improved lower bounds on the maximal sizes of caps in PG(r, 4) for \(r\ge 11\).     

Pure state ‘really’ informationally complete with rank-1 POVM

What is the minimal number of elements in a rank-1 positive operator-valued measure (POVM) which can uniquely determine any pure state in d-dimensional Hilbert space \(\mathcal {H}_d\)? The known result is that the number is no less than \(3d-2\). We show that this lower bound is not tight except for \(d=2\) or 4. Then we give an upper bound \(4d-3\). For \(d=2\), many rank-1 POVMs with four elements can determine any pure states in \(\mathcal {H}_2\). For \(d=3\), we show eight is the minimal number by construction. For \(d=4\), the minimal number is in the set of \(\{10,11,12,13\}\). We show that if this number is greater than 10, an unsettled open problem can be solved that three orthonormal bases cannot distinguish all pure states in \(\mathcal {H}_4\). For any dimension d, we construct \(d+2k-2\) adaptive rank-1 positive operators for the reconstruction of any unknown pure state in \(\mathcal {H}_d\), where \(1\le k \le d\).     

Creating maximally entangled states by gluing

We introduce a general method of gluing multi-partite states and show that entanglement swapping is a special class of a wider range of gluing operations. The gluing operation of two m and n qudit states consists of an entangling operation on two given qudits of the two states followed by operations of measurements of the two qudits in the computational basis. Depending on how many qudits (two, one or zero) we measure, we have three classes of gluing operation, resulting respectively in \(m+n-2\), \(m+n-1\), or \(m+n\) qudit states. Entanglement swapping belongs to the first class and has been widely studied, while the other two classes are presented and studied here. In particular, we study how larger GHZ and W states can be constructed when we glue the smaller GHZ and W states by the second method. Finally we prove that when we glue two states by the third method, the k-uniformity of the states is preserved. That is when a k-uniform state of m qudits is glued to a \(k'\)-uniform state of n qudits, the resulting state will be a \(\hbox {min}(k,k')\)-uniform of \(m+n\) qudits.     

Local distinguishability of generalized Bell states

We investigate the distinguishability of orthogonal generalized Bell states (GBSs) in \(d\otimes d\) system by local operations and classical communication (LOCC), where d is a prime. We show that |S| is no more than \(d+1\) for any l GBSs, i.e., \(|S|\le d+1\), where S is maximal set which is composed of pairwise noncommuting pairs in \({\varDelta } U\). If \(|S|\le d\), then the l GBSs can be distinguished by LOCC according to our main Theorem. Compared with the results (Fan in Phys Rev Lett 92:177905, 2004; Tian et al. in Phys Rev A 92:042320, 2015), our result is more general. It can determine local distinguishability of \(l (> k)\) GBSs, where k is the number of GBSs in Fan’s and Tian’s results. Only for \(|S|=d+1\), we do not find the answer. We conjecture that any l GBSs cannot be distinguished by one-way LOCC if \(|S|=d+1\). If this conjecture is right, the problem about distinguishability of GBSs with one-way LOCC is completely solved in \(d\otimes d\).     

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines,small looseness,and small slack

We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\), a deadline \(d_j\), and a processing time \(p_j\), on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \(|d_j-t_j|\le \lambda {}p_j\) and \(|d_j-t_j|\le p_j +\sigma \) and showed the problem to be NP-hard for any \(\lambda >1\) and for any \(\sigma \ge 2\). We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\), the problem remains weakly NP-hard even for \(m=2\) and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and \(\lambda \) and a fixed-parameter tractability result for the parameter m combined with \(\sigma \).     

Coherence of one-dimensional quantum walk on cycles

Quantum coherence plays a central role in quantum mechanics and provides essential power for quantum information processing. In this paper, we study the dynamics of the \(l_1\) norm coherence in one-dimensional quantum walk on cycles for two initial states. For the first initial state, the walker starts from a single position. The coherence increases with the number of steps at the beginning and then fluctuates over time after approaching to saturation. The coherence with odd number of sites is much larger than that with even number of sites. Another initial state, i.e., the equally superposition state, is also considered. The coherence of the whole system is proved to be \(N-1\) (\(2N-1\)) for any odd (even) time step where N is the number of sites. We also investigate the influence of two unitary noises, i.e., noisy Hadamard operator and broken link, on the coherence evolution.     

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.     

Preparing large-scale maximally entangled <Emphasis Type="Italic">W</Emphasis> states in optical system

We propose an optical scheme to prepare large-scale maximally entangled W states by fusing arbitrary-size polarization entangled W states via polarization-dependent beam splitter. Because most of the currently existing fusion schemes are suffering from the qubit loss problem, that is the number of the output entangled qubits is smaller than the sum of numbers of the input entangled qubits, which will inevitably decrease the fusion efficiency and increase the number of fusion steps as well as the requirement of quantum memories, in our scheme, we design a effect fusion mechanism to generate \(W_{m+n}\) state from a n-qubit W state and a m-qubit W state without any qubit loss. As the nature of this fusion mechanism clearly increases the final size of the obtained W state, it is more efficient and feasible. In addition, our scheme can also generate \(W_{m+n+t-1}\) state by fusing a \(W_m\), a \(W_n\) and a \(W_t\) states. This is a great progress compared with the current scheme which has to lose at least two particles in the fusion of three W states. Moreover, it also can be generalized to the case of fusing k different W states, and all the fusion schemes proposed here can start from Bell state as well.     

Two Mixed Finite Element Methods for Time-Fractional Diffusion Equations

Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis.     

In All But Finitely Many Possible Worlds: Model-Theoretic Investigations on ‘<Emphasis Type="Italic">Overwhelming Majority</Emphasis>’ Default Conditionals

Defeasible conditionals are statements of the form ‘if A then normally B’. One plausible interpretation introduced in nonmonotonic reasoning dictates that (\(A\Rightarrow B\)) is true iff B is true in ‘most’ A-worlds. In this paper, we investigate defeasible conditionals constructed upon a notion of ‘overwhelming majority’, defined as ‘truth in a cofinite subset of \(\omega \)’, the first infinite ordinal. One approach employs the modal logic of the frame \((\omega , <)\), used in the temporal logic of discrete linear time. We introduce and investigate conditionals, defined modally over \((\omega , <)\); several modal definitions of the conditional connective are examined, with an emphasis on the nonmonotonic ones. An alternative interpretation of ‘majority’ as sets cofinal (in \(\omega \)) rather than cofinite (subsets of \(\omega \)) is examined. For these modal approaches over \((\omega , <)\), a decision procedure readily emerges, as the modal logic \({\mathbf {K4DLZ}}\) of this frame is well-known and a translation of the conditional sentences can be mechanically checked for validity; this allows also for a quick proof of \(\mathsf {NP}\)-completeness of the satisfiability problem for these logics. A second approach employs the conditional version of Scott-Montague semantics, in the form of \(\omega \)-many possible worlds, endowed with neighborhoods populated by collections of cofinite subsets of \(\omega \). This approach gives rise to weak conditional logics, as expected. The relative strength of the conditionals introduced is compared to (the conditional logic ‘equivalent’ of) KLM logics and other conditional logics in the literature.     

About the Decidability of Polyhedral Separability in the Lattice $$\mathbb {Z}^d$$

The recognition of primitives in digital geometry is deeply linked with separability problems. This framework leads us to consider the following problem of pattern recognition : given a finite lattice set \(S\subset \mathbb {Z}^d\) and a positive integer n, is it possible to separate S from \(\mathbb {Z}^d \setminus S\) by n half-spaces? In other words, does there exist a polyhedron P defined by at most n half-spaces satisfying \(P\cap \mathbb {Z}^d = S\)? The difficulty comes from the infinite number of constraints generated by all the points of \(\mathbb {Z}^d\setminus S\). It makes the decidability of the problem non-straightforward since the classical algorithms of polyhedral separability can not be applied in this framework. We conjecture that the problem is nevertheless decidable and prove it under some assumptions: in arbitrary dimension, if the interior of the convex hull of S contains at least one lattice point or if the dimension d is 2 or if the dimension \(d=3\) and S is not in a specific configuration of lattice width 0 or 1. The proof strategy is to reduce the set of outliers \(\mathbb {Z}^d\setminus S\) to its minimal elements according to a partial order “is in the shadow of.” These minimal elements are called the lattice jewels of S. We prove that under some assumptions, the set S admits only a finite number of lattice jewels. The result about the decidability of the problem is a corollary of this fundamental property.     

Ordering states with Tsallis relative $$\alpha $$-entropies of coherence

In this paper, we study the ordering states with Tsallis relative \(\alpha \)-entropies of coherence and \(l_{1}\) norm of coherence for single-qubit states. Firstly, we show that any Tsallis relative \(\alpha \)-entropies of coherence and \(l_{1}\) norm of coherence give the same ordering for single-qubit pure states. However, they do not generate the same ordering for some high-dimensional states, even though these states are pure. Secondly, we also consider three special Tsallis relative \(\alpha \)-entropies of coherence for \(\alpha =2, 1, \frac{1}{2}\) and show these three measures and \(l_{1}\) norm of coherence will not generate the same ordering for some single-qubit mixed states. Nevertheless, they may generate the same ordering if we only consider a special subset of single-qubit mixed states. Furthermore, we find that any two of these three special measures generate different ordering for single-qubit mixed states. Finally, we discuss the degree of violation of between \(l_{1}\) norm of coherence and Tsallis relative \(\alpha \)-entropies of coherence. In a sense, this degree can measure the difference between these two coherence measures in ordering states.     

Invariance of bipartite separability and PPT-probabilities over Casimir invariants of reduced states

Milz and Strunz (J Phys A 48:035306, 2015) recently studied the probabilities that two-qubit and qubit–qutrit states, randomly generated with respect to Hilbert–Schmidt (Euclidean/flat) measure, are separable. They concluded that in both cases, the separability probabilities (apparently exactly \(\frac{8}{33}\) in the two-qubit scenario) hold constant over the Bloch radii (r) of the single-qubit subsystems, jumping to 1 at the pure state boundaries (\(r=1\)). Here, firstly, we present evidence that in the qubit–qutrit case, the separability probability is uniformly distributed, as well, over the generalized Bloch radius (R) of the qutrit subsystem. While the qubit (standard) Bloch vector is positioned in three-dimensional space, the qutrit generalized Bloch vector lives in eight-dimensional space. The radii variables r and R themselves are the lengths/norms (being square roots of quadratic Casimir invariants) of these (“coherence”) vectors. Additionally, we find that not only are the qubit–qutrit separability probabilities invariant over the quadratic Casimir invariant of the qutrit subsystem, but apparently also over the cubic one—and similarly the case, more generally, with the use of random induced measure. We also investigate two-qutrit (\(3 \times 3\)) and qubit–qudit (\(2 \times 4\)) systems—with seemingly analogous positive partial transpose-probability invariances holding over what has been termed by Altafini the partial Casimir invariants of these systems.     

Generation of singlet states with Rydberg blockade mechanism and driven by adiabatic passage

A single state is a special state that entangles multi-state quantum systems and plays a significant role in the field of quantum computation. In this paper, we propose a scheme to realize the generation of single states for Rydberg atoms, where one Rydberg atom is trapped in an optical potential and the others are trapped in an adjacent optical potential. Moreover, combining Rydberg blockade and adiabatic-passage technologies, an N-atom singlet state can be generated with the interaction of an N-dimensional Rydberg atom and an (\(N-1\))-atom singlet state. Compared to previous schemes, the advantage of our proposal is that an N-particle N-level singlet state with \(N\ge 3\) may be realized more simply.