Connecting unextendible maximally entangled base with partial Hadamard matrices

We study the unextendible maximally entangled bases (UMEB) in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\) and connect the problem to the partial Hadamard matrices. We show that for a given special UMEB in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\), there is a partial Hadamard matrix which cannot be extended to a Hadamard matrix in \(\mathbb {C}^{d}\). As a corollary, any \((d-1)\times d\) partial Hadamard matrix can be extended to a Hadamard matrix, which answers a conjecture about \(d=5\). We obtain that for any d there is a UMEB except for \(d=p\ \text {or}\ 2p\), where \(p\equiv 3\mod 4\) and p is a prime. The existence of different kinds of constructions of UMEBs in \(\mathbb {C}^{nd}\bigotimes \mathbb {C}^{nd}\) for any \(n\in \mathbb {N}\) and \(d=3\times 5 \times 7\) is also discussed.     

Non-determinism in Gödel’s System <Emphasis Type="Italic">T</Emphasis>

The calculus T^? is a successor-free version of Gödel’s T. It is well known that a number of important complexity classes, like e.g. the classes logspace, \(\textsc{p}\), \(\textsc{linspace}\), \(\textsc{etime}\) and \(\textsc{pspace}\), are captured by natural fragments of T^? and related calculi. We introduce the calculus T^∽, which is a non-deterministic variant of T^?, and compare the computational power of T^∽ and T^?. First, we provide a denotational semantics for T^∽ and prove this semantics to be adequate. Furthermore, we prove that \(\textsc{linspace}\subseteq \mathcal {G}^{\backsim }_{0} \subseteq \textsc{linspace}\) and \(\textsc{etime}\subseteq \mathcal {G}^{\backsim }_{1} \subseteq \textsc{pspace}\) where \(\mathcal {G}^{\backsim }_{0}\) and \(\mathcal {G}^{\backsim }_{1}\) are classes of problems decidable by certain fragments of T^∽. (It is proved elsewhere that the corresponding fragments of T^? equal respectively \(\textsc{linspace}\) and \(\textsc{etime}\).) Finally, we show a way to interpret T^∽ in T^?.     

Spatial-spectral-combined sparse representation-based classification for hyperspectral imagery

Recently, sparse representation-based classification (SRC), which assigns a test sample to the class with minimum representation error via a sparse linear combination of all the training samples, has successfully been applied to hyperspectral imagery. Alternatively, spatial information, which means the adjacent pixels belong to the same class with a high probability, is a valuable complement to the spectral information. In this paper, we have presented a new spectral-spatial-combined SRC method, abbreviated as SSSRC or \(\mathrm{S}^{3}\mathrm{RC}\), to jointly consider the spectral and spatial neighborhood information of each pixel to explore the spectral and spatial coherence by the SRC method. Furthermore, a fast interference-cancelation operation is adopted to accelerate the classification procedure of \(\mathrm{S}^{3}\mathrm{RC}\), named \(\mathrm{FS}^{3}\mathrm{RC}\). Experimental results have shown that both the proposed SRC-based approaches, \(\mathrm{S}^{3}\mathrm{RC}\) and \(\mathrm{FS}^{3}\mathrm{RC}\), could achieve better performance than the other state-of-the-art methods.     

Mutually unbiased maximally entangled bases in $$\mathbb {C}^d\otimes \mathbb {C}^d$$

We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3).     

Subspace Learning by $$\ell ^{0}$$-Induced Sparsity

Subspace clustering methods partition the data that lie in or close to a union of subspaces in accordance with the subspace structure. Such methods with sparsity prior, such as sparse subspace clustering (SSC) (Elhamifar and Vidal in IEEE Trans Pattern Anal Mach Intell 35(11):2765–2781, 2013) with the sparsity induced by the \(\ell ^{1}\)-norm, are demonstrated to be effective in subspace clustering. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. However, these assumptions are not guaranteed to hold in practice and they limit the application of existing sparse subspace clustering methods. In this paper, we propose \(\ell ^{0}\)-induced sparse subspace clustering (\(\ell ^{0}\)-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that \(\ell ^{0}\)-SSC guarantees the subspace-sparse representation, a key element in subspace clustering, for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We also present the “no free lunch” theorem which shows that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding \(\ell ^{0}\) sparse representation problem of \(\ell ^{0}\)-SSC. A novel approximate algorithm named Approximate \(\ell ^{0}\)-SSC (A\(\ell ^{0}\)-SSC) is developed which employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of \(\ell ^{0}\)-SSC with theoretical guarantee. The sub-optimal solution is used to build a sparse similarity matrix upon which spectral clustering is performed for the final clustering results. Extensive experimental results on various data sets demonstrate the superiority of A\(\ell ^{0}\)-SSC compared to other competing clustering methods. Furthermore, we extend \(\ell ^{0}\)-SSC to semi-supervised learning by performing label propagation on the sparse similarity matrix learnt by A\(\ell ^{0}\)-SSC and demonstrate the effectiveness of the resultant semi-supervised learning method termed \(\ell ^{0}\)-sparse subspace label propagation (\(\ell ^{0}\)-SSLP).     

Master Lovas–Andai and equivalent formulas verifying the $$\frac{8}{33}$$ two-qubit Hilbert–Schmidt separability probability and companion rational-valued conjectures

We begin by investigating relationships between two forms of Hilbert–Schmidt two-rebit and two-qubit “separability functions”—those recently advanced by Lovas and Andai (J Phys A Math Theor 50(29):295303, 2017), and those earlier presented by Slater (J Phys A 40(47):14279, 2007). In the Lovas–Andai framework, the independent variable \(\varepsilon \in [0,1]\) is the ratio \(\sigma (V)\) of the singular values of the \(2 \times 2\) matrix \(V=D_2^{1/2} D_1^{-1/2}\) formed from the two \(2 \times 2\) diagonal blocks (\(D_1, D_2\)) of a \(4 \times 4\) density matrix \(D= \left||\rho _{ij}\right||\). In the Slater setting, the independent variable \(\mu \) is the diagonal-entry ratio \(\sqrt{\frac{\rho _{11} \rho _ {44}}{\rho _ {22} \rho _ {33}}}\)—with, of central importance, \(\mu =\varepsilon \) or \(\mu =\frac{1}{\varepsilon }\) when both \(D_1\) and \(D_2\) are themselves diagonal. Lovas and Andai established that their two-rebit “separability function” \(\tilde{\chi }_1 (\varepsilon )\) (\(\approx \varepsilon \)) yields the previously conjectured Hilbert–Schmidt separability probability of \(\frac{29}{64}\). We are able, in the Slater framework (using cylindrical algebraic decompositions [CAD] to enforce positivity constraints), to reproduce this result. Further, we newly find its two-qubit, two-quater[nionic]-bit and “two-octo[nionic]-bit” counterparts, \(\tilde{\chi _2}(\varepsilon ) =\frac{1}{3} \varepsilon ^2 \left( 4-\varepsilon ^2\right) \), \(\tilde{\chi _4}(\varepsilon ) =\frac{1}{35} \varepsilon ^4 \left( 15 \varepsilon ^4-64 \varepsilon ^2+84\right) \) and \(\tilde{\chi _8} (\varepsilon )= \frac{1}{1287}\varepsilon ^8 \left( 1155 \varepsilon ^8-7680 \varepsilon ^6+20160 \varepsilon ^4-25088 \varepsilon ^2+12740\right) \). These immediately lead to predictions of Hilbert–Schmidt separability/PPT-probabilities of \(\frac{8}{33}\), \(\frac{26}{323}\) and \(\frac{44482}{4091349}\), in full agreement with those of the “concise formula” (Slater in J Phys A 46:445302, 2013), and, additionally, of a “specialized induced measure” formula. Then, we find a Lovas–Andai “master formula,” \(\tilde{\chi _d}(\varepsilon )= \frac{\varepsilon ^d \Gamma (d+1)^3 \, _3\tilde{F}_2\left( -\frac{d}{2},\frac{d}{2},d;\frac{d}{2}+1,\frac{3 d}{2}+1;\varepsilon ^2\right) }{\Gamma \left( \frac{d}{2}+1\right) ^2}\), encompassing both even and odd values of d. Remarkably, we are able to obtain the \(\tilde{\chi _d}(\varepsilon )\) formulas, \(d=1,2,4\), applicable to full (9-, 15-, 27-) dimensional sets of density matrices, by analyzing (6-, 9, 15-) dimensional sets, with not only diagonal \(D_1\) and \(D_2\), but also an additional pair of nullified entries. Nullification of a further pair still leads to X-matrices, for which a distinctly different, simple Dyson-index phenomenon is noted. C. Koutschan, then, using his HolonomicFunctions program, develops an order-4 recurrence satisfied by the predictions of the several formulas, establishing their equivalence. A two-qubit separability probability of \(1-\frac{256}{27 \pi ^2}\) is obtained based on the operator monotone function \(\sqrt{x}\), with the use of \(\tilde{\chi _2}(\varepsilon )\).     

An optimal discrimination of two mixed qubit states with a fixed rate of inconclusive results

In this paper we consider the optimal discrimination of two mixed qubit states for a measurement that allows a fixed rate of inconclusive results. Our strategy is to transform the problem of two qubit states into a minimum error discrimination for three qubit states by adding a specific quantum state \(\rho _{0}\) and a prior probability \(q_{0}\), which behaves as an inconclusive degree. First, we introduce the beginning and the end of practical interval of inconclusive result, \(q_{0}^{(0)}\) and \(q_{0}^{(1)}\), which are key ingredients in investigating our problem. Then we obtain the analytic form of them. Next, we show that our problem can be classified into two cases \(q_{0}=q_{0}^{(0)}\) (or \(q_{0}=q_{0}^{(1)}\)) and \(q_{0}^{(0)}<q_{0}<q_{0}^{(1)}\). In fact, by maximum confidences of two qubit states and non-diagonal element of \(\rho _{0}\), our problem is completely understood. We provide an analytic solution of our problem when \(q_{0}=q_{0}^{(0)}\) (or \(q_{0}=q_{0}^{(1)}\)). However, when \(q_{0}^{(0)}<q_{0}<q_{0}^{(1)}\), we rather supply the numerical method to find the solution, because of the complex relation between inconclusive degree and corresponding failure probability. Finally we confirm our results using previously known examples.     

An extended nonsymmetric block Lanczos method for model reduction in large scale dynamical systems

In this paper, we propose an extended block Krylov process to construct two biorthogonal bases for the extended Krylov subspaces \(\mathbb {K}_{m}^e(A,V)\) and \(\mathbb {K}_{m}^e(A^{T},W)\), where \(A \in \mathbb {R}^{n \times n}\) and \(V,~W \in \mathbb {R}^{n \times p}\). After deriving some new theoretical results and algebraic properties, we apply the proposed algorithm with moment matching techniques for model reduction in large scale dynamical systems. Numerical experiments for large and sparse problems are given to show the efficiency of the proposed method.     

Indistinguishability of pure orthogonal product states by LOCC

We construct two sets of incomplete and extendible quantum pure orthogonal product states (POPS) in general bipartite high-dimensional quantum systems, which are all indistinguishable by local operations and classical communication. The first set of POPS is composed of two parts which are \(\mathcal {C}^m\otimes \mathcal {C}^{n_1}\) with \(5\le m\le n_1\) and \(\mathcal {C}^m\otimes \mathcal {C}^{n_2}\) with \(5\le m \le n_2\), where \(n_1\) is odd and \(n_2\) is even. The second one is in \(\mathcal {C}^m\otimes \mathcal {C}^n\) \((m, n\ge 4)\). Some subsets of these two sets can be extended into complete sets that local indistinguishability can be decided by noncommutativity which quantifies the quantumness of a quantum ensemble. Our study shows quantum nonlocality without entanglement.     

Generalized differentiability and integrability for fuzzy set-valued functions on time scales

This paper deals with the fuzzy set-valued functions of real variables on time scale whose values are normal, convex, upper semicontinuous and compactly supported fuzzy sets in \(\mathbb {R}^{n}\). We introduce and study the fundamental properties of new class of derivative called generalized delta derivative (\(\Delta _{g}\)-derivative) and generalized delta integral (\(\Delta _{g}\)-integral) for such fuzzy functions.     

Improved Algorithms for Maximum Agreement and Compatible Supertrees

Consider a set of labels L and a set of unordered trees \(\mathcal{T}=\{\mathcal{T}^{(1)},\mathcal{T}^{(2)},\ldots ,\allowbreak \mathcal{T}^{(k)}\}\) where each tree \(\mathcal{T}^{(i)}\) is distinctly leaf-labeled by some subset of L. One fundamental problem is to find the biggest tree (denoted as supertree) to represent \(\mathcal{T}\) which minimizes the disagreements with the trees in \(\mathcal{T}\) under certain criteria. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for k≥3. This paper gives improved algorithms for both MASP and MCSP. In particular, our results imply the first polynomial time algorithms for both MASP and MCSP when both k and the maximum degree D of the input trees are constant.     

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.     

Finite approximation of the first passage models for discrete-time Markov decision processes with varying discount factors

This paper deals with the finite approximation of the first passage models for discrete-time Markov decision processes with varying discount factors. For a given control model \(\mathcal {M}\) with denumerable states and compact Borel action sets, and possibly unbounded reward functions, under reasonable conditions we prove that there exists a sequence of control models \(\mathcal {M}_{n}\) such that the first passage optimal rewards and policies of \(\mathcal {M}_{n}\) converge to those of \(\mathcal {M}\), respectively. Based on the convergence theorems, we propose a finite-state and finite-action truncation method for the given control model \(\mathcal {M}\), and show that the first passage optimal reward and policies of \(\mathcal {M}\) can be approximated by those of the solvable truncated finite control models. Finally, we give the corresponding value and policy iteration algorithms to solve the finite approximation models.     

ν-twin support vector machine with Universum data for classification

A novel ν-twin support vector machine with Universum data (\(\mathfrak {U}_{\nu }\)-TSVM) is proposed in this paper. \(\mathfrak {U}_{\nu }\)-TSVM allows to incorporate the prior knowledge embedded in the unlabeled samples into the supervised learning. It aims to utilize these prior knowledge to improve the generalization performance. Different from the conventional \(\mathfrak {U}\)-SVM, \(\mathfrak {U}_{\nu }\)-TSVM employs two Hinge loss functions to make the Universum data lie in a nonparallel insensitive loss tube, which makes it exploit these prior knowledge more flexibly. In addition, the newly introduced parameters ν₁, ν₂ in the \(\mathfrak {U}_{\nu }\)-TSVM have better theoretical interpretation than the penalty factor c in the \(\mathfrak {U}\)-TSVM. Numerical experiments on seventeen benchmark datasets, handwritten digit recognition, and gender classification indicate that the Universum indeed contributes to improving the prediction accuracy. Moreover, our \(\mathfrak {U}_{\nu }\)-TSVM is far superior to the other three algorithms (\(\mathfrak {U}\)-SVM, ν-TSVM and \(\mathfrak {U}\)-TSVM) from the prediction accuracy.     

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.     

An Advection-Robust Hybrid High-Order Method for the Oseen Problem

In this work, we study advection-robust Hybrid High-Order discretizations of the Oseen equations. For a given integer \(k\geqslant 0\), the discrete velocity unknowns are vector-valued polynomials of total degree \(\leqslant \, k\) on mesh elements and faces, while the pressure unknowns are discontinuous polynomials of total degree \(\leqslant \,k\) on the mesh. From the discrete unknowns, three relevant quantities are reconstructed inside each element: a velocity of total degree \(\leqslant \,(k+1)\), a discrete advective derivative, and a discrete divergence. These reconstructions are used to formulate the discretizations of the viscous, advective, and velocity–pressure coupling terms, respectively. Well-posedness is ensured through appropriate high-order stabilization terms. We prove energy error estimates that are advection-robust for the velocity, and show that each mesh element T of diameter \(h_T\) contributes to the discretization error with an \(\mathcal {O}(h_{T}^{k+1})\)-term in the diffusion-dominated regime, an \(\mathcal {O}(h_{T}^{k+\frac{1}{2}})\)-term in the advection-dominated regime, and scales with intermediate powers of \(h_T\) in between. Numerical results complete the exposition.     

Shrinking one-way cellular automata

We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata (\(\text{OCA}\)) with the additional property that during a computation any cell of the \(\text{OCA}\) has the ability to dissolve itself, so-called shrinking one-way cellular automata (\(\text{SOCA}\)). It turns out that real-time \(\text{SOCA}\) are more powerful than real-time \(\text{OCA}\), since they can accept certain linear-time \(\text{OCA}\) languages. On the other hand, linear-time \(\text{OCA}\) are more powerful than real-time \(\text{SOCA}\), which is witnessed even by a unary language. Additionally, a construction is provided that enables real-time \(\text{SOCA}\) to accept the reversal of real-time iterative array languages. Finally, restricted real-time \(\text{SOCA}\) are investigated. We distinguish two limitations for the dissolving of cells. One restriction is to bound the total number of cells that are allowed to dissolve by some function. In this case, an infinite strict hierarchy of language classes is obtained. The second restriction is inspired by an approach to limit the amount of nondeterminism in \(\text{OCA}\). Compared with the first restriction, the total number of cells that may dissolve is still unbounded, but the number of time steps at which a cell may dissolve is bounded. The possibility to dissolve is allowed only in the first k time steps, where \(k\ge 0\) is some constant. For this mode of operation an infinite, tight, and strict hierarchy of language classes is obtained as well.     

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.     

Flexible bandwidth assignment with application to optical networks

We introduce two scheduling problems, the flexible bandwidth allocation problem (\(\textsc {FBAP}\)) and the flexible storage allocation problem (\(\textsc {FSAP}\)). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In \(\textsc {FBAP}\), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in \(\textsc {FSAP}\) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore \(\text {NP-hard}\). Our main results are a 3-approximation algorithm for \(\textsc {FBAP}\) and a \((3+\epsilon )\)-approximation algorithm for \(\textsc {FSAP}\), for any fixed \(\epsilon >0 \). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a \((2+\epsilon )\)-approximation algorithm for \(\textsc {SAP}\), for any fixed \(\epsilon >0 \), thus improving the best known ratio of \(\frac{2e-1}{e-1} + \epsilon \). Our study is motivated also by critical resource allocation problems arising in all-optical networks.