Cubature formulae for nearly singular and highly oscillating integrals

The paper deals with the approximation of integrals of the type

$$\begin{aligned} I(f;{\mathbf {t}})=\int _{{\mathrm {D}}} f({\mathbf {x}}) {\mathbf {K}}({\mathbf {x}},{\mathbf {t}}) {\mathbf {w}}({\mathbf {x}}) d{\mathbf {x}},\quad \quad {\mathbf {x}}=(x_1,x_2),\quad {\mathbf {t}}\in \mathrm {T}\subseteq \mathbb {R}^p, \ p\in \{1,2\} \end{aligned}$$

where \({\mathrm {D}}=[-\,1,1]^2\), f is a function defined on \({\mathrm {D}}\) with possible algebraic singularities on \(\partial {\mathrm {D}}\), \({\mathbf {w}}\) is the product of two Jacobi weight functions, and the kernel \({\mathbf {K}}\) can be of different kinds. We propose two cubature rules determining conditions under which the rules are stable and convergent. Along the paper we diffusely treat the numerical approximation for kernels which can be nearly singular and/or highly oscillating, by using a bivariate dilation technique. Some numerical examples which confirm the theoretical estimates are also proposed.

     

Parallel Multi-Block ADMM with <Emphasis Type="Italic">o</Emphasis>(1 / <Emphasis Type="Italic">k</Emphasis>) Convergence

This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints:

$$\begin{aligned} \text {minimize} ~~&f_1(\mathbf{x}_1) + \cdots + f_N(\mathbf{x}_N)\\ \text {subject to}~~&A_1 \mathbf{x}_1 ~+ \cdots + A_N\mathbf{x}_N =c,\\&\mathbf{x}_1\in {\mathcal {X}}_1,~\ldots , ~\mathbf{x}_N\in {\mathcal {X}}_N, \end{aligned}$$

where \(N \ge 2\), \(f_i\) are convex functions, \(A_i\) are matrices, and \({\mathcal {X}}_i\) are feasible sets for variable \(\mathbf{x}_i\). Our algorithm extends the alternating direction method of multipliers (ADMM) and decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This paper shows that the classic ADMM can be extended to the N-block Jacobi fashion and preserve convergence in the following two cases: (i) matrices \(A_i\) are mutually near-orthogonal and have full column-rank, or (ii) proximal terms are added to the N subproblems (but without any assumption on matrices \(A_i\)). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that \(\Vert {\mathbf {x}}^{k+1} - {\mathbf {x}}^k\Vert _M^2\) converges at a rate of o(1 / k) where M is a symmetric positive semi-definte matrix. Since the parameters used in the convergence analysis are conservative, we introduce a strategy for automatically tuning the parameters to substantially accelerate our algorithm in practice. We implemented our algorithm (for the case ii above) on Amazon EC2 and tested it on basis pursuit problems with >300 GB of distributed data. This is the first time that successfully solving a compressive sensing problem of such a large scale is reported.

     

On congruences of weak lattices

We characterize when an equivalence relation on the base set of a weak lattice \(\mathbf{L}=(L,\sqcup ,\sqcap )\) becomes a congruence on \(\mathbf{L}\) provided it has convex classes. We show that an equivalence relation on L is a congruence on \(\mathbf{L}\) if it satisfies the substitution property for comparable elements. Conditions under which congruence classes are convex are studied. If one fundamental operation of \(\mathbf{L}\) is commutative then \(\mathbf{L}\) is congruence distributive and all congruences of \(\mathbf{L}\) have convex classes.     

Microfluidic separation of magnetic particles with soft magnetic microstructures

This paper demonstrates simple and cost-effective microfluidic devices for enhanced separation of magnetic particles by using soft magnetic microstructures. By injecting a mixture of iron powder and polydimethylsiloxane (PDMS) into a prefabricated channel, an iron–PDMS microstructure was fabricated next to a microfluidic channel. Placed between two external permanent magnets, the magnetized iron–PDMS microstructure induces localized and strong forces on the magnetic particles in the direction perpendicular to the fluid flow. Due to the small distance between the microstructure and the fluid channel, the localized large magnetic field gradients result a vertical force on the magnetic particles, leading to enhanced separation of the particles. Numerical simulations were developed to compute the particle trajectories and agreed well with experimental data. Systematic experiments and numerical simulation were conducted to study the effect of relevant factors on the transport of superparamagnetic particles, including the shape of iron–PDMS microstructure, mass ratio of iron–PDMS composite, width of the microfluidic channel, and average flow velocity.     

On-board communication-based relative localization for collision avoidance in Micro Air Vehicle teams

To avoid collisions, Micro Air Vehicles (MAVs) flying in teams require estimates of their relative locations, preferably with minimal mass and processing burden. We present a relative localization method where MAVs need only to communicate with each other using their wireless transceiver. The MAVs exchange on-board states (velocity, height, orientation) while the signal strength indicates range. Fusing these quantities provides a relative location estimate. We used this for collision avoidance in tight areas, testing with up to three AR.Drones in a \(4\,\mathrm{m}~\mathbf {\times }~4\,\mathrm{m}\) area and with two miniature drones (\(\approx 50\,\mathrm{g}\)) in a \(2~\mathrm{m}~\mathbf {\times }~2~\mathrm{m}\) area. The MAVs could localize each other and fly several minutes without collisions. In our implementation, MAVs communicated using Bluetooth antennas. The results were robust to the high noise and disturbances in signal strength. They could improve further by using transceivers with more accurate signal strength readings.     

From LTL to deterministic automata

We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula \(\varphi \). The automaton is the product of a co-Büchi automaton for \(\varphi \) and an array of Rabin automata, one for each \({\mathbf {G}}\)-subformula of \(\varphi \). The Rabin automaton for \({\mathbf {G}}\psi \) is in charge of recognizing whether \({\mathbf {F}}{\mathbf {G}}\psi \) holds. This information is passed to the co-Büchi automaton that decides on acceptance. As opposed to standard procedures based on Safra’s determinization, the states of all our automata have a clear logical structure, which allows for various optimizations. Experimental results show improvement in the sizes of the resulting automata compared to existing methods.     

On topological systems

We establish the reflectivity of the subcategories of \(T_{0}\) and sober topological systems in the category \(\mathbf {TopSys}\) of topological systems. We also introduce a Sierpinski object in the category \(\mathbf {TopSys}\) and point out its connection with \(T_{0}\) and sober topological systems and also with injective \(T_{0}\)-topological systems.     

Two families of BCH codes and new quantum codes

In this paper, two families of non-narrow-sense (NNS) BCH codes of lengths \(n=\frac{q^{2m}-1}{q^2-1}\) and \(n=\frac{q^{2m}-1}{q+1}\) (\(m\ge 3)\) over the finite field \(\mathbf {F}_{q^2}\) are studied. The maximum designed distances \(\delta ^\mathrm{new}_\mathrm{max}\) of these dual-containing BCH codes are determined by a careful analysis of properties of the cyclotomic cosets. NNS BCH codes which achieve these maximum designed distances are presented, and a sequence of nested NNS BCH codes that contain these BCH codes with maximum designed distances are constructed and their parameters are computed. Consequently, new nonbinary quantum BCH codes are derived from these NNS BCH codes. The new quantum codes presented here include many classes of good quantum codes, which have parameters better than those constructed from narrow-sense BCH codes, negacyclic and constacyclic BCH codes in the literature.     

Constructive quantum scaling of unitary matrices

In this work, we present a method of decomposition of arbitrary unitary matrix \(U\in \mathbf {U}(2^k)\) into a product of single-qubit negator and controlled-\(\sqrt{\text{ NOT }}\) gates. Since the product results with negator matrix, which can be treated as complex analogue of bistochastic matrix, our method can be seen as complex analogue of Sinkhorn–Knopp algorithm, where diagonal matrices are replaced by adding and removing an one-qubit ancilla. The decomposition can be found constructively, and resulting circuit consists of \(O(4^k)\) entangling gates, which is proved to be optimal. An example of such transformation is presented.     

Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem

Dispatching rules can be automatically generated from scheduling data. This paper will demonstrate that the key to learning an effective dispatching rule is through the careful construction of the training data, \(\{\mathbf {x}_i(k),y_i(k)\}_{k=1}^K\in {\mathscr {D}}\), where (i) features of partially constructed schedules \(\mathbf {x}_i\) should necessarily reflect the induced data distribution \({\mathscr {D}}\) for when the rule is applied. This is achieved by updating the learned model in an active imitation learning fashion; (ii) \(y_i\) is labelled optimally using a MIP solver; and (iii) data need to be balanced, as the set is unbalanced with respect to the dispatching step k. Using the guidelines set by our framework the design of custom dispatching rules, for a particular scheduling application, will become more effective. In the study presented three different distributions of the job-shop will be considered. The machine learning approach considered is based on preference learning, i.e. which dispatch (post-decision state) is preferable to another.     

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.     

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.     

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.     

Spectral Numerical Exterior Calculus Methods for Differential Equations on Radial Manifolds

We analyse a class of nonoverlapping domain decomposition preconditioners for nonsymmetric linear systems arising from discontinuous Galerkin finite element approximations of fully nonlinear Hamilton–Jacobi–Bellman (HJB) partial differential equations. These nonsymmetric linear systems are uniformly bounded and coercive with respect to a related symmetric bilinear form, that is associated to a matrix \(\mathbf {A}\). In this work, we construct a nonoverlapping domain decomposition preconditioner \(\mathbf {P}\), that is based on \(\mathbf {A}\), and we then show that the effectiveness of the preconditioner for solving the nonsymmetric problems can be studied in terms of the condition number \(\kappa (\mathbf {P}^{-1}\mathbf {A})\). In particular, we establish the bound \(\kappa (\mathbf {P}^{-1}\mathbf {A})\lesssim 1+ p^6 H^3 /q^3 h^3\), where H and h are respectively the coarse and fine mesh sizes, and q and p are respectively the coarse and fine mesh polynomial degrees. This represents the first such result for this class of methods that explicitly accounts for the dependence of the condition number on q; our analysis is founded upon an original optimal order approximation result between fine and coarse discontinuous finite element spaces. Numerical experiments demonstrate the sharpness of this bound. Although the preconditioners are not robust with respect to the polynomial degree, our bounds quantify the effect of the coarse and fine space polynomial degrees. Furthermore, we show computationally that these methods are effective in practical applications to nonsymmetric, fully nonlinear HJB equations under h-refinement for moderate polynomial degrees.     

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.     

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.     

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

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