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.     

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.     

Power and welfare in bargaining for coalition structure formation

We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\)). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.     

Counter machines and crystallographic structures

One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages \(\mathcal {DCL}_d,\,d=0,1,2,\ldots \), within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class \(\mathcal {DCL}_d\). An intersection of d languages in \(\mathcal {DCL}_1\) defines \(\mathcal {DCL}_d\). We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in \(\mathcal {DCL}_d\). The proof uses the following result: given a digraph \(\Delta \) and a group G, there is a unique digraph \(\Gamma \) such that \(G\le \mathrm{Aut}\,\Gamma ,\,G\) acts freely on the structure, and \(\Gamma /G \cong \Delta \).     

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 \).     

Online scheduling of moldable parallel tasks

In this paper, we study an online scheduling problem with moldable parallel tasks on m processors. Each moldable task can be processed simultaneously on any number of processors of a parallel computer, and the processing time of a moldable task depends on the number of processors allotted to it. Tasks arrive one by one. Upon arrival of each task, the scheduler has to determine both the number of processors and the starting time for the task. Moreover, these decisions cannot be changed in the future. The objective is to attain a schedule such that the longest completion time over all tasks, i.e., the makespan, is minimized. First, we provide a general framework to show that any \(\rho \)-bounded algorithm for scheduling of rigid parallel tasks (the number of processors for a task is fixed a prior) can be extended to yield an algorithm for scheduling of moldable tasks with a competitive ratio of \(4\rho \) if the ratio \(\rho \) is known beforehand. As a consequence, we achieve the first constant competitive ratio, 26.65, for the moldable parallel tasks scheduling problem. Next, we provide an improved algorithm with a competitive ratio of at most 16.74.     

On the Distribution of Photon Counts with Censoring in Two-Photon Laser Scanning Microscopy

We address the problem of counting emitted photons in two-photon laser scanning microscopy. Following a laser pulse, photons are emitted after exponentially distributed waiting times. Modeling the counting process is of interest because photon detectors have a dead period after a photon is detected that leads to an underestimate of the count of emitted photons. We describe a model which has a Poisson \((\alpha )\) number N of photons emitted, and a dead period \(\Delta \) that is standardized by the fluorescence time constant \(\tau (\delta = \Delta /\tau )\), and an observed count D. The estimate of \(\alpha \) determines the intensity of a single pixel in an image. We first derive the distribution of D and study its properties. We then use it to estimate \(\alpha \) and \(\delta \) simultaneously by maximum likelihood. We show that our results improve the signal-to-noise ratio, hence the quality of actual images.     

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.     

Data assimilation and sampling in Banach spaces

This paper studies the problem of approximating a function f in a Banach space \(\mathcal{X}\) from measurements \(l_j(f)\), \(j=1,\ldots ,m\), where the \(l_j\) are linear functionals from \(\mathcal{X}^*\). Quantitative results for such recovery problems require additional information about the sought after function f. These additional assumptions take the form of assuming that f is in a certain model class \(K\subset \mathcal{X}\). Since there are generally infinitely many functions in K which share these same measurements, the best approximation is the center of the smallest ball B, called the Chebyshev ball, which contains the set \(\bar{K}\) of all f in K with these measurements. Therefore, the problem is reduced to analytically or numerically approximating this Chebyshev ball. Most results study this problem for classical Banach spaces \(\mathcal{X}\) such as the \(L_p\) spaces, \(1\le p\le \infty \), and for K the unit ball of a smoothness space in \(\mathcal{X}\). Our interest in this paper is in the model classes \(K=\mathcal{K}(\varepsilon ,V)\), with \(\varepsilon >0\) and V a finite dimensional subspace of \(\mathcal{X}\), which consists of all \(f\in \mathcal{X}\) such that \(\mathrm{dist}(f,V)_\mathcal{X}\le \varepsilon \). These model classes, called approximation sets, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance and algorithms for finding near optimal approximations. It builds on the initial analysis given in Maday et al. (Int J Numer Method Eng 102:933–965, 2015) for the case when \(\mathcal{X}\) is a Hilbert space, and further studied in Binev et al. (SIAM UQ, 2015). It is shown how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.     

The local–global conjecture for scheduling with non-linear cost

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time \(p_j\) and a priority weight \(w_j\), and for a given schedule a completion time \(C_j\). In this paper, we consider the problem of minimizing the objective value \(\sum _j w_j C_j^\beta \) for some fixed constant \(\beta >0\). This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For \(\beta =1\), the well-known Smith’s rule that orders job in the non-increasing order of \(w_j/p_j\) gives the optimum schedule. However, for \(\beta \ne 1\), the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.     

Tighter entanglement monogamy relations of qubit systems

Monogamy relations characterize the distributions of entanglement in multipartite systems. We investigate monogamy relations related to the concurrence C and the entanglement of formation E. We present new entanglement monogamy relations satisfied by the \(\alpha \)-th power of concurrence for all \(\alpha \ge 2\), and the \(\alpha \)-th power of the entanglement of formation for all \(\alpha \ge \sqrt{2}\). These monogamy relations are shown to be tighter than the existing ones.     

Effect of three-spin interaction on thermal entanglement in Heisenberg XXZ model

The effect of three-spin interaction k on thermal entanglement between alternate qubits is studied using pairwise concurrence C and energy-level diagram. It is found that k breaks the symmetry about the effect of magnetic field h on C. It shifts a dip structure and gradually effaces a boot structure when \(\left| k \right| <\left| J \right| \) (J is spin exchange coupling). A peak with C maintains 1 appears and expands, elbowing the dip backwards when \(\left| k \right| >\left| J \right| \). A sudden change in the concurrence occurs around \(\left| k \right| =\left| J \right| \), \(h=-k\). Similar conclusions about nearest-neighbor qubits are directly 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.     

Optimal noise functions for location privacy on continuous regions

Users of location-based services are highly vulnerable to privacy risks since they need to disclose, at least partially, their locations to benefit from these services. One possibility to limit these risks is to obfuscate the location of a user by adding random noise drawn from a noise function. In this paper, we require the noise functions to satisfy a generic location privacy notion called \(\ell \)-privacy, which makes the position of the user in a given region \(\mathcal {X}\) relatively indistinguishable from other points in \(\mathcal {X}\). We also aim at minimizing the loss in the service utility due to such obfuscation. While existing optimization frameworks regard the region \(\mathcal {X}\) restrictively as a finite set of points, we consider the more realistic case in which the region is rather continuous with a nonzero area. In this situation, we demonstrate that circular noise functions are enough to satisfy \(\ell \)-privacy on \(\mathcal {X}\) and equivalently on the entire space without any penalty in the utility. Afterward, we describe a large parametric space of noise functions that satisfy \(\ell \)-privacy on \(\mathcal {X}\), and show that this space has always an optimal member, regardless of \(\ell \) and \(\mathcal {X}\). We also investigate the recent notion of \(\epsilon \)-geo-indistinguishability as an instance of \(\ell \)-privacy and prove in this case that with respect to any increasing loss function, the planar Laplace noise function is optimal for any region having a nonzero area.     

Steering quantum-memory-assisted entropic uncertainty under unital and nonunital noises via filtering operations

In this work, we investigate the dynamic features of the entropic uncertainty for two incompatible measurements under local unital and nonunital channels. Herein, we choose Pauli operators \(\sigma _x \) and \(\sigma _z \) as a pair of observables of interest measuring on particle A, and the uncertainty can be predicted when particle A is entangled with quantum memory B. We explore the dynamics of the uncertainty for the measurement under local unitary (phase-damping) and nonunitary (amplitude-damping) channels, respectively. Remarkably, we derive the entropic uncertainty relation under three different kinds of measurements of Pauli-observable pair under various realistic noisy environments; it has been found that the entropic uncertainty has the same tendency of its evolution during the AD and PD channel when we choose \(\sigma _x \) and \(\sigma _y \) measurement. Besides, we find out that the entropic uncertainty will have an optimal value if one chooses \(\sigma _x \) and \(\sigma _z \) as the measurement incompatibility, comparing with others. Furthermore, in order to reduce the entropic uncertainty in noisy environment, we propose an effective strategy to steer the amount by means of implementing a filtering operation on the particle under the two types of channels, respectively. It turns out that this operation can greatly reduce the entropic uncertainty by modulation of the operation strength. Thus, our investigations might offer an insight into the dynamics and steering of the entropic uncertainty in an open system.     

How the Hawking radiation affect quantum Fisher information of Dirac particles in the background of a Schwarzschild black hole

In this work, the effect of Hawking radiation on the quantum Fisher information (QFI) of Dirac particles is investigated in the background of a Schwarzschild black hole. Interestingly, it has been verified that the QFI with respect to the weight parameter \(\theta \) of a target state is always independent of the Hawking temperature T. This implies that if we encode the information on the weight parameter, then we can affirm that the corresponding accuracy of the parameter estimation will be immune to the Hawking effect. Besides, it reveals that the QFI with respect to the phase parameter \(\phi \) exhibits a decay behavior with the increase in the Hawking temperature T and converges to a nonzero value in the limit of infinite Hawking temperature T. Remarkably, it turns out that the function \(F_\phi \) on \(\theta =\pi \big /4\) symmetry was broken by the influence of the Hawking radiation. Finally, we generalize the case of a three-qubit system to a case of a N-qubit system, i.e., \(|\psi \rangle _{1,2,3,\ldots ,N} =(\cos \theta | 0 \rangle ^{\otimes N}+\sin \theta \mathrm{e}^{i\phi }| 1 \rangle ^{\otimes N})\) and obtain an interesting result: the number of particles in the initial state does not affect the QFI \(F_\theta \), nor the QFI \(F_\phi \). However, with the increasing number of particles located near the event horizon, \(F_\phi \) will be affected by Hawking radiation to a large extent, while \(F_\theta \) is still free from disturbance resulting from the Hawking effects.     

Scheduling fully parallel jobs

We consider the following scheduling problem. We have m identical machines, where each machine can accomplish one unit of work at each time unit. We have a set of n fully parallel jobs, where each job j has \(s_j\) units of workload, and each unit workload can be executed on any machine at any time unit. A job is considered complete when its entire workload has been executed. The objective is to find a schedule that minimizes the total weighted completion time \(\sum w_j C_j\), where \(w_j\) is the weight of job j and \(C_j\) is the completion time of job j. We provide theoretical results for this problem. First, we give a PTAS of this problem with fixed m. We then consider the special case where \(w_j = s_j\) for each job j, and we show that it is polynomial solvable with fixed m. Finally, we study the approximation ratio of a greedy algorithm, the Largest-Ratio-First algorithm. For the special case, we show that the approximation ratio depends on the instance size, i.e. n and m, while for the general case where jobs have arbitrary weights, we prove that the upper bound of the approximation ratio is \(1 + \frac{m-1}{m+2}\).     

Actions Arising from Intersection and Union

An action is a pair of sets, C and S, and a function \(f:C\times S \rightarrow C\). Rothschild and Yalcin gave a simple axiomatic characterization of those actions arising from set intersection, i.e. for which the elements of C and S can be identified with sets in such a way that elements of S act on elements of C by intersection. We introduce and axiomatically characterize two natural classes of actions which arise from set intersection and union. In the first class, the \(\uparrow \!\!\downarrow \)-actions, each element of S is identified with a pair of sets \((s^\downarrow ,s^\uparrow )\), which act on a set c by intersection with \(s^\downarrow \) and union with \(s^\uparrow \). In the second class, the \(\uparrow \!\!\downarrow \)-biactions, each element of S is labeled as an intersection or a union, and acts accordingly on C. We give intuitive examples of these actions, one involving conversations and another a university’s changing student body. The examples give some motivation for considering these actions, and also help give intuitive readings of the axioms. The class of \(\uparrow \!\!\downarrow \)-actions is closely related to a class of single-sorted algebras, which was previously treated by Margolis et al., albeit in another guise (hyperplane arrangements), and we note this connection. Along the way, we make some useful, though very general, observations about axiomatization and representation problems for classes of algebras.     

General tracking control of arbitrary <Emphasis Type="Italic">N</Emphasis>-level quantum systems using piecewise time-independent potentials

Here we propose a tracking quantum control protocol for arbitrary N-level systems. The goal is to make the expected value of an observable \({\mathcal O}\) to follow a predetermined trajectory S(t). For so, we drive the quantum state \(|\varPsi (t) \rangle \) evolution through an external potential V which depends on \(M_V\) tunable parameters (e.g., the amplitude and phase (thus \(M_V = 2\)) of a laser field in the dipolar condition). At instants \(t_n\), these parameters can be rapidly switched to specific values and then kept constant during time intervals \(\Delta t\). The method determines which sets of parameters values can result in \(\langle \varPsi (t) | {\mathcal O} |\varPsi (t) \rangle = S(t)\). It is numerically robust (no intrinsic divergences) and relatively fast since we need to solve only nonlinear algebraic (instead of a system of coupled nonlinear differential) equations to obtain the parameters at the successive \(\Delta t\)’s. For a given S(t), the required minimum \(M_V = M_{\min }\) ‘degrees of freedom’ of V attaining the control is a good figure of merit of the problem difficulty. For instance, the control cannot be unconditionally realizable if \(M_{\min } > 2\) and V is due to a laser field (the usual context in real applications). As it is discussed and exemplified, in these cases a possible procedure is to relax the control in certain problematic (but short) time intervals. Finally, when existing the approach can systematically access distinct possible solutions, thereby allowing a relatively simple way to search for the best implementation conditions. Illustrations for 3-, 4-, and 5-level systems and some comparisons with calculations in the literature are presented.