Geometric discord and measurement-induced nonlocality for well known bound entangled states

We employ geometric discord and measurement induced nonlocality to quantify quantumness of some well-known bipartite bound entangled states, namely the two families of Horodecki’s ( $2\otimes 4, 3\otimes 3$ and $4\otimes 4$ dimensional) bound entangled states and that of Bennett et al.’s in $3\otimes 3$ dimension. In most of the cases our results are analytic and both the measures attain relatively small value. The amount of quantumness in the $4\otimes 4$ bound entangled state of Benatti et al. and the $2\otimes 8$ state having the same matrix representation (in computational basis) is same. Coincidently, the $2m\otimes 2m$ Werner and isotropic states also exhibit the same property, when seen as $2\otimes 2m^2$ dimensional states.     

Optimal quadrature formulas in the sense of Sard in W_2^{(m,m-1)} space

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the $W_2^{(m,m-1)}(0,1)$ space. Using the Sobolev’s method we obtain new optimal quadrature formulas of such type for $N+1\ge m$ , where $N+1$ is the number of the nodes. Moreover, explicit formulas of the optimal coefficients are obtained. We investigate the order of convergence of the optimal formula for $m=1$ and prove an asymptotic optimality of such a formula in the Sobolev space $L_2^{(1)}(0,1)$ . It turns out that the error of the optimal quadrature formula in $W_2^{(1,0)}(0,1)$ is less than the error of the optimal quadrature formula given in the $L_2^{(1)}(0,1)$ space. The obtained optimal quadrature formula in the $W_2^{(m,m-1)}(0,1)$ space is exact for $\exp (-x)$ and $P_{m-2}(x)$ , where $P_{m-2}(x)$ is a polynomial of degree $m-2$ . Furthermore, some numerical results, which confirm the obtained theoretical results of this work, are given.     

On matrices, automata, and double counting in constraint programming

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.     

Null controllability of Kolmogorov-type equations

We study the null controllability of Kolmogorov-type equations $\partial _t f + v^\gamma \partial _x f - \partial _v^2 f = u(t,x,v) 1_{\omega }(x,v)$ in a rectangle $\Omega $ , under an additive control supported in an open subset $\omega $ of $\Omega $ . For $\gamma =1$ , with periodic-type boundary conditions, we prove that null controllability holds in any positive time, with any control support $\omega $ . This improves the previous result by Beauchard and Zuazua (Ann Ins H Poincaré Anal Non Linéaire 26:1793–1815, 2009), in which the control support was a horizontal strip. With Dirichlet boundary conditions and a horizontal strip as control support, we prove that null controllability holds in any positive time if $\gamma =1$ or if $\gamma =2$ and $\omega $ contains the segment $\{v=0\}$ , and only in large time if $\gamma =2$ and $\omega $ does not contain the segment $\{v=0\}$ . Our approach, inspired from Benabdallah et al. (C R Math Acad Sci Paris 344(6):357–362, 2007), Lebeau and Robbiano (Commun Partial Differ Equ 20:335–356, 1995), is based on two key ingredients: the observability of the Fourier components of the solution of the adjoint system, uniformly with respect to the frequency, and the explicit exponential decay rate of these Fourier components.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

Distinguishing and relating higher-order and first-order processes by expressiveness

This is a paper on distinguishing and relating two important kinds of calculi through expressiveness, settling some critical but long unanswered questions. The delimitation of higher-order and first-order process calculi is a basic and pivotal topic in the study of process theory. Particularly, expressiveness studies mutual encodability, which helps decide whether process-passing or name-passing is more fundamental, and the way they ought to be used in both theory and practice. In this paper, we contribute to such demarcation with three major results. Firstly $\pi $ (first-order pi-calculus) can faithfully express $\varPi $ (basic higher-order pi-calculus). The calculus $\varPi $ has the elementary operators (input, output, composition and restriction). This actually is a corollary of a more general result, that $\pi $ can encode $\varPi ^r$ ( $\varPi $ enriched with the relabelling operator). Secondly $\varPi $ cannot interpret $\pi $ reasonably. This is of more significance since it separates $\varPi $ and $\pi $ by drawing a well-defined boundary. Thirdly an encoding from $\pi $ to $\varPi ^r$ is revisited and discussed, which not only implies how to make $\varPi $ more useful but also stresses the importance of name-passing in $\pi $ .     

Solving Convection-Diffusion Problems on Curved Domains by Extensions from Subdomains

We present a technique for numerically solving convection-diffusion problems in domains $\varOmega $ with curved boundary. The technique consists in approximating the domain $\varOmega $ by polyhedral subdomains $\mathsf{{D}}_h$ where a finite element method is used to solve for the approximate solution. The approximation is then suitably extended to the remaining part of the domain $\varOmega $ . This approach allows for the use of only polyhedral elements; there is no need of fitting the boundary in order to obtain an accurate approximation of the solution. To achieve this, the boundary condition on the border of $\varOmega $ is transferred to the border of $\mathsf{D }_h$ by using simple line integrals. We apply this technique to the hybridizable discontinuous Galerkin method and provide extensive numerical experiments showing that, whenever the distance of $\mathsf{{D}}_h$ to $\partial \varOmega $ is of order of the meshsize $h$ , the convergence properties of the resulting method are the same as those for the case in which $\varOmega =\mathsf{{D}}_h$ . We also show numerical evidence indicating that the ratio of the $L^2(\varOmega )$ norm of the error in the scalar variable computed with $d>0$ to that of that computed with $d=0$ remains constant (and fairly close to one), whenever the distance $d$ is proportional to $\min \{h,Pe^{-1}\}/(k+1)^2$ , where $Pe$ is the so-called Péclet number.     

Reduced ordered binary decision diagram with implied literals: a new knowledge compilation approach

Reduced ordered binary decision diagram (ROBDD) is one of the most influential knowledge compilation languages. We generalize it by associating some implied literals with each node to propose a new language called ROBDD with implied literals (ROBDD- $L$ ) and show that ROBDD- $L$ can meet most of the querying requirements involved in the knowledge compilation map. Then, we discuss a kind of subsets of ROBDD- $L$ called ROBDD- $L_i$ with precisely $i$ implied literals $(0\le i\le \infty )$ , where ROBDD- $L_0$ is isomorphic to ROBDD. ROBDD- $L_i$ has uniqueness over any given linear order of variables. We mainly focus on ROBDD- $L_\infty $ and demonstrate that: (a) it is a canonical representation on any given variable order; (b) it is the most succinct subset in ROBDD- $L$ and thus also meets most of the querying requirements; (c) given any logical operation ROBDD supports in polytime, ROBDD- $L_\infty $ can also support it in time polynomial in the sizes of the equivalent ROBDDs. Moreover, we propose an ROBDD- $L_i$ compilation algorithm for any $i$ and an ROBDD- $L_\infty $ compilation algorithm, and then we implement an ROBDD- $L$ package called BDDjLu. Our preliminary experimental results indicate that: (a) the compilation results of ROBDD- $L_\infty $ are significantly smaller than those of ROBDD; (b) the standard d-DNNF compiler c2d and our ROBDD- $L_\infty $ compiler do not dominate the other, yet ROBDD- $L_\infty $ has canonicity and supports more querying requirements and relatively efficient logical operations; and (c) the method that first compiles knowledge base into ROBDD- $L_\infty $ and then converts ROBDD- $L_\infty $ into ROBDD provides an efficient ROBDD compiler.     

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.     

Self-Referential Justifications in Epistemic Logic

This paper is devoted to the study of self-referential proofs and/or justifications, i.e., valid proofs that prove statements about these same proofs. The goal is to investigate whether such self-referential justifications are present in the reasoning described by standard modal epistemic logics such as  $\mathsf{S4}$ . We argue that the modal language by itself is too coarse to capture this concept of self-referentiality and that the language of justification logic can serve as an adequate refinement. We consider well-known modal logics of knowledge/belief and show, using explicit justifications, that $\mathsf{S4}$ , $\mathsf{D4}$ , $\mathsf{K4}$ , and  $\mathsf{T}$ with their respective justification counterparts  $\mathsf{LP}$ , $\mathsf{JD4}$ , $\mathsf{J4}$ , and  $\mathsf{JT}$ describe knowledge that is self-referential in some strong sense. We also demonstrate that self-referentiality can be avoided for  $\mathsf{K}$ and  $\mathsf{D}$ . In order to prove the former result, we develop a machinery of minimal evidence functions used to effectively build models for justification logics. We observe that the calculus used to construct the minimal functions axiomatizes the reflected fragments of justification logics. We also discuss difficulties that result from an introduction of negative introspection.     

Two-Grid Methods for Hermitian positive definite linear systems connected with an order relation

Given a multigrid procedure for linear systems with coefficient matrices $A_n,$ we discuss the optimality of a related multigrid procedure with the same smoother and the same projector, when applied to properly related algebraic problems with coefficient matrices $B_n$ : we assume that both $A_n$ and $B_n$ are Hermitian positive definite with $A_n\le \vartheta B_n,$ for some positive $\vartheta $ independent of $n.$ In this context we prove the Two-Grid Method optimality. We apply this elementary strategy for designing a multigrid solution for modifications of multilevel structured linear systems, in which the Hermitian positive definite coefficient matrix is banded in a multilevel sense. As structured matrices, Toeplitz, circulants, Hartley, sine ( $\tau $ class) and cosine algebras are considered. In such a way, several linear systems arising from the approximation of integro–differential equations with various boundary conditions can be efficiently solved in linear time (with respect to the size of the algebraic problem). Some numerical experiments are presented and discussed, both with respect to Two-Grid and multigrid procedures.     

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.     

Interpolation splines minimizing a semi-norm

Using S.L. Sobolev’s method, we construct the interpolation splines minimizing the semi-norm in $K_2(P_2)$ , where $K_2(P_2)$ is the space of functions $\phi $ such that $\phi ^{\prime } $ is absolutely continuous, $\phi ^{\prime \prime } $ belongs to $L_2(0,1)$ and $\int _0^1(\varphi ^{\prime \prime }(x)+\varphi (x))^2dx<\infty $ . Explicit formulas for coefficients of the interpolation splines are obtained. The resulting interpolation spline is exact for the trigonometric functions $\sin x$ and $\cos x$ . Finally, in a few numerical examples the qualities of the defined splines and $D^2$ -splines are compared. Furthermore, the relationship of the defined splines with an optimal quadrature formula is shown.     

\lambda -Statistical convergence of fuzzy numbers and fuzzy functions of order \theta

In this paper, we introduce the concept of $\lambda $ -statistical convergence of order $\theta $ and strong $\lambda $ -summability of order $\theta $ for the sequence of fuzzy numbers. Further the same concept is extended to the sequence of fuzzy functions and introduce the spaces like $S_\lambda ^\theta (\hat{f})$ and $\omega _{\lambda p} ^\theta (\hat{f})$ . Some inclusion relations in those spaces and also the underlying relation between these two spaces are also obtained.     

On the Exact Complexity of Evaluating Quantified k -CNF

We relate the exponential complexities 2 ^s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 ^cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma.     

Uncertainty and certainty relations for complementary qubit observables in terms of Tsallis’ entropies

Uncertainty relations for more than two observables have found use in quantum information, though commonly known relations pertain to a pair of observables. We present novel uncertainty and certainty relations of state-independent form for the three Pauli observables with use of the Tsallis $\alpha $ -entropies. For all real $\alpha \in (0;1]$ and integer $\alpha \ge 2$ , lower bounds on the sum of three $\alpha $ -entropies are obtained. These bounds are tight in the sense that they are always reached with certain pure states. The necessary and sufficient condition for equality is that the qubit state is an eigenstate of one of the Pauli observables. Using concavity with respect to the parameter $\alpha $ , we derive approximate lower bounds for non-integer $\alpha \in (1;+\infty )$ . In the case of pure states, the developed method also allows to obtain upper bounds on the entropic sum for real $\alpha \in (0;1]$ and integer $\alpha \ge 2$ . For applied purposes, entropic bounds are often used with averaging over the individual entropies. Combining the obtained bounds leads to a band, in which the rescaled average $\alpha $ -entropy ranges in the pure-state case. A width of this band is essentially dependent on $\alpha $ . It can be interpreted as an evidence for sensitivity in quantifying the complementarity.     

A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications

A pair of unit clauses is called conflicting if it is of the form (x), $(\bar{x})$ . A CNF formula is unit-conflict free (UCF) if it contains no pair of conflicting unit clauses. Lieberherr and Specker (J. ACM 28:411?C421, 1981) showed that for each UCF CNF formula with m clauses we can simultaneously satisfy at least $\hat{ \varphi } m$ clauses, where $\hat{ \varphi }=(\sqrt{5}-1)/2$ . We improve the Lieberherr-Specker bound by showing that for each UCF CNF formula F with m clauses we can find, in polynomial time, a?subformula F?? with m?? clauses such that we can simultaneously satisfy at least $\hat{ \varphi } m+(1-\hat{ \varphi })m'+(2-3\hat {\varphi })n''/2$ clauses (in F), where n?? is the number of variables in F which are not in F??. We consider two parameterized versions of MAX-SAT, where the parameter is the number of satisfied clauses above the bounds m/2 and $m(\sqrt{5}-1)/2$ . The former bound is tight for general formulas, and the later is tight for UCF formulas. Mahajan and Raman (J. Algorithms 31:335?C354, 1999) showed that every instance of the first parameterized problem can be transformed, in polynomial time, into an equivalent one with at most 6k+3 variables and 10k clauses. We improve this to 4k variables and $(2\sqrt{5}+4)k$ clauses. Mahajan and Raman conjectured that the second parameterized problem is fixed-parameter tractable (FPT). We show that the problem is indeed FPT by describing a polynomial-time algorithm that transforms any problem instance into an equivalent one with at most $(7+3\sqrt{5})k$ variables. Our results are obtained using our improvement of the Lieberherr-Specker bound above.     

Parallel black box \mathcal {H}-LU preconditioning for elliptic boundary value problems

Hierarchical ( $\mathcal {H}$ -) matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an $\mathcal {H}$ -matrix are (a) the hierarchical construction of a matrix block partition, and (b) the blockwise approximation of matrix data by low rank matrices. In the context of finite element discretisations of elliptic boundary value problems, $\mathcal {H}$ -matrices can be used for the construction of preconditioners such as approximate $\mathcal {H}$ -LU factors. In this paper, we develop a new black box approach to construct the necessary partition. This new approach is based on the matrix graph of the sparse stiffness matrix and no longer requires geometric data associated with the indices like the standard clustering algorithms. The black box clustering and a subsequent $\mathcal {H}$ -LU factorisation have been implemented in parallel, and we provide numerical results in which the resulting black box $\mathcal {H}$ -LU factorisation is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation.     

Characterization of extended filters in residuated lattices

We give a characterization theorem of extended filters on residuated lattices, from which many results are immediately obtained. We show that, for a bounded integral commutative residuated lattice X, (1) an extended filter $E_F (B)$ associated with $B$ is characterized by $E_F (B) = [B) \rightarrow F$ , where $B\subseteq X$ and $F$ is a filter of $X$ ; (2) the class $E(B)$ of all extended filters associated with $B$ is a complete Heyting algebra. (3) the class $S(B)$ of all stable filters relative to $B\subseteq X$ is also a complete Heyting algebra.     

Cell Cycle Control and Bifurcation for a Free Boundary Problem Modeling Tissue Growth

We consider a free boundary problem for a system of partial differential equations, which arise in a model of cell cycle with a free boundary. For the quasi steady state system, it depends on a positive parameter $\beta $ , which describes the signals from the microenvironment. Upon discretizing this model, we obtain a family of polynomial systems parameterized by $\beta $ . We numerically find that there exists a radially-symmetric stationary solution with boundary $r = R$ for any given positive number $R$ by using numerical algebraic geometry method. By homotopy tracking with respect to the parameter $\beta $ , there exist branches of symmetry-breaking stationary solutions. Moreover, we proposed a numerical algorithm based on Crandall–Rabinowitz theorem to numerically verify the bifurcation points. By continuously changing $\beta $ using a homotopy, we are able to compute non-radially symmetric solutions. We additionally discuss control function $\beta $ .