A projected gradient method for optimization over density matrices

An ensemble of quantum states can be described by a Hermitian, positive semidefinite and unit trace matrix called density matrix. Thus, the study of methods for optimizing a certain function (energy, entropy) over the set of density matrices has a direct application to important problems in quantum information and computation. We propose a projected gradient method for solving such problems. By exploiting the geometry of the feasible set, which is the intersection of the cone of Hermitian positive semidefinite matrices with the hyperplane defined by the unit trace constraint, we describe an efficient procedure to compute the projection onto this set using the Frobenius norm. Some important applications, such as quantum state tomography, are described and numerical experiments illustrate the effectiveness of the method when compared to previous methods based on fixed-point iterations or semidefinite programming.     

Laplacian matrices of weighted digraphs represented as quantum states

Representing graphs as quantum states is becoming an increasingly important approach to study entanglement of mixed states, alternate to the standard linear algebraic density matrix-based approach of study. In this paper, we propose a general weighted directed graph framework for investigating properties of a large class of quantum states which are defined by three types of Laplacian matrices associated with such graphs. We generalize the standard framework of defining density matrices from simple connected graphs to density matrices using both combinatorial and signless Laplacian matrices associated with weighted directed graphs with complex edge weights and with/without self-loops. We also introduce a new notion of Laplacian matrix, which we call signed Laplacian matrix associated with such graphs. We produce necessary and/or sufficient conditions for such graphs to correspond to pure and mixed quantum states. Using these criteria, we finally determine the graphs whose corresponding density matrices represent entangled pure states which are well known and important for quantum computation applications. We observe that all these entangled pure states share a common combinatorial structure.     

Hybrid reconstruction of quantum density matrix: when low-rank meets sparsity

Both the mathematical theory and experiments have verified that the quantum state tomography based on compressive sensing is an efficient framework for the reconstruction of quantum density states. In recent physical experiments, we found that many unknown density matrices in which people are interested in are low-rank as well as sparse. Bearing this information in mind, in this paper we propose a reconstruction algorithm that combines the low-rank and the sparsity property of density matrices and further theoretically prove that the solution of the optimization function can be, and only be, the true density matrix satisfying the model with overwhelming probability, as long as a necessary number of measurements are allowed. The solver leverages the fixed-point equation technique in which a step-by-step strategy is developed by utilizing an extended soft threshold operator that copes with complex values. Numerical experiments of the density matrix estimation for real nuclear magnetic resonance devices reveal that the proposed method achieves a better accuracy compared to some existing methods. We believe that the proposed method could be leveraged as a generalized approach and widely implemented in the quantum state estimation.     

Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases

In this paper we present an algorithm for the computation of a diagonal form of a matrix over non-commutative Euclidean domain over a field with the help of Gröbner bases. We propose a general framework of Ore localizations of non-commutative G-algebras and show its merits and constructiveness. It allows us to handle, among others, common operator algebras with rational coefficients.We introduce the splitting of the computation of a normal form (like the Jacobson form over simple domain) for matrices over Ore localizations into the diagonalization (the computation of a diagonal form of a matrix) and the normalization (the computation of the normal form of a diagonal matrix). These ideas are also used for the computation of the Smith normal form in the commutative case. We give a special algorithm for the normalization of a diagonal matrix over the rational Weyl algebra and present counterexamples to its idea over rational shift and q-Weyl algebras.Our implementation of the algorithm in Singular:Plural relies on the fraction-free polynomial strategy, details of which will be described in the forthcoming article. It shows quite an impressive performance, compared with methods which directly use fractions. In particular, we experience quite a moderate swell of coefficients and obtain uncomplicated transformation matrices. We leave questions on the algorithmic complexity of this algorithm open, but we stress the practical applicability of the proposed method to a large class of non-commutative algebras.     

A strong tracking extended Kalman observer for nonlineardiscrete-time systems

The authors show how the extended Kalman filter, used as an observer for nonlinear discrete-time systems or extended Kalman observer (EKO), becomes a useful state estimator when the arbitrary matrices, namely R_k and Q_k, are adequately chosen. As a first step, we use the linearization technique given by Boutayed et al. (1997), which consists of introducing unknown diagonal matrices to take the approximation errors into account. It is shown that the decreasing Lyapunov function condition leads to a linear matrix inequality (LMI) problem, which points out the connection between a good convergence behavior of the EKO and the instrumental matrices R_k and Q _k. In order to satisfy the obtained LMI, a particular design of Q_k is given. High performances of the proposed technique are shown through numerical examples under the worst conditions     

Determination of relaxation factors for high cell peclet number flow simulation

For the numerical simulation of transport problems with high cell Peclet number, the coefficient matrix of finite difference equations may lose the diagonal dominance if a scheme more accurate than the first-order upwind is used to approximate the convection terms. Hence, in many cases it is difficult to choose a suitable relaxation factor a priori for these schemes when the commonly used iterative method is applied to obtain the convergent solution. However, it is found that after appropriate normalization, an easier determined relaxation factor useful to all three schemes studied here, i.e., second-order central differencing, second-order upwinding, and QUICK, exists. Two model problems are used to compare the performances among the three schemes. The second-order central differencing is found to be less efficient in the cases investigated. Without the aid of the normalization, the second-order upwind scheme has the widest range of allowable values for the relaxation factor. Yet QUICK may be computationally more efficient after normalization. This is mainly because the number of iterations needed for QUICK is less sensitive to the choice of the relaxation factor when the optimum value isn't known. For a flow problem with non-constant velocities, the present method becomes the iterative algorithm with different relaxation parameters for different points, i.e., a local relaxation method. It is demonstrated that, in addition to helping choose the relaxation factors, this idea may also substantially reduce the computing time compared with the iterative algorithm with the uniform relaxation factor for all the grid points.     

Optimal conditions for Bell-inequality violation in the presence of decoherence and errors

We obtain the set of all detector configurations providing the maximal violation of the Bell inequality in the Clauser–Horne–Shimony–Holt form for a general (pure or mixed) state of two qubits. Next, we analyze optimal conditions for the Bell-inequality violations in the presence of local decoherence, which includes energy relaxation at the zero temperature and arbitrary pure dephasing. We reveal that in most cases the Bell inequality violation is maximal for the “even” two-qubit state. Combined effects of measurement errors and decoherence on the Bell inequality violation are also discussed.     

Improved Approximations for Guarding 1.5-Dimensional Terrains

We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629–640, 2006). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.     

Methods of computing weighted pseudoinverse matrices with singular weights

Three iterative processes are constructed and investigated for computing weighted pseudoinverse matrices with singular weights and ML-weighted pseudoinverse matrices. Two of them are based on the decompositions of the weighted pseudoinverse matrix with singular weights into matrix power series, and the third is a generalization of the Schulz method to nonsingular square matrices. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 150–169, September–October, 1999.     

A Contribution to the Feasibility of the Interval Gaussian Algorithm

We apply the interval Gaussian algorithm to an n × n interval matrix [A] whose comparison matrix 〈[A]〉 is generalized diagonally dominant. For such matrices we prove conditions for the feasibility of this method, among them a necessary and sufficient one. Moreover, we prove an equivalence between a well-known sufficient criterion for the algorithm on H matrices and a necessary and sufficient one for interval matrices whose midpoint is the identity matrix. For the more general class of interval matrices which also contain the identity matrix, but not necessarily as midpoint, we derive a criterion of infeasibility. For general matrices [A] we show how the feasibility of reducible interval matrices is connected with that of irreducible ones. Dedicated to Professor Dr. H. J. Stetter, Wien, on the occasion of his 75th birthday     

Separable decompositions of bipartite mixed states

We present a practical scheme for the decomposition of a bipartite mixed state into a sum of direct products of local density matrices, using the technique developed in Li and Qiao (Sci. Rep. 8:1442, 2018). In the scheme, the correlation matrix which characterizes the bipartite entanglement is first decomposed into two matrices composed of the Bloch vectors of local states. Then, we show that the symmetries of Bloch vectors are consistent with that of the correlation matrix, and the magnitudes of the local Bloch vectors are lower bounded by the correlation matrix. Concrete examples for the separable decompositions of bipartite mixed states are presented for illustration.     

Decentralized robust H<Subscript>∞</Subscript> output feedback control for value bounded uncertain large-scale interconnected systems

In this paper, decentralized robust H_∞ output feedback control problem for large-scale interconnected system with value bounded uncertainties in the state, control input and interconnection matrices is investigated. A new bounded real lemma for the large-scale interconnected systems is derived by Lyapunov stability theory and linear matrix inequality method. Based on the new bounded real lemma, a sufficient condition expressed as matrix inequalities for the existence of a decentralized robust H_∞ output feedback controller is obtained. The controller which enables the closed-loop large-scale system robust stable and satisfies the given H_∞ performance is designed through a homotopy iterative method. Finally, a numerical example is given to illustrate the effectiveness of the proposed method.     

Efficient solution of nonlinear elliptic problems using hierarchical matrices with Broyden updates

Summary The numerical solution of nonlinear problems is usually connected with Newton’s method. Due to its computational cost, variants (so-called inexact and quasi–Newton methods) have been developed in which the arising inverse of the Jacobian is replaced by an approximation. In this article we present a new approach which is based on Broyden updates. This method does not require to store the update history since the updates are explicitly added to the matrix. In addition to updating the inverse we introduce a method which constructs updates of the LU decomposition. To this end, we present an algorithm for the efficient multiplication of hierarchical and semi-separable matrices. Since an approximate LU decomposition of finite element stiffness matrices can be efficiently computed in the set of hierarchical matrices, the complexity of the proposed method scales almost linearly. Numerical examples demonstrate the effectiveness of this new approach. This work was supported by the DFG priority program SPP 1146 “Modellierung inkrementeller Umformverfahren”.     

Density matrix formalism of duality quantum computer and the solution of zero-wave-function paradox

Duality quantum computer can accommodate both unitary and non-unitary operations. In this paper, we derive the mathematical theory of duality quantum computer in terms of density matrix using the duality mode of quantum computers. We give a solution to the ‘zero-wave-function’ paradox of duality quantum computer raised by Zou et al. (Quantum Inf Process 8:37–50 2009) where in duality quantum computer the final wave function may be zero, which contradicts the general understanding of an normalized wave function for a quantum system. We show that it is natural for zero wave function to occur in duality quantum computer because we only consider a part of the wave function in duality quantum computer. In addition, the conditions for zero wave function are presented in both pure state formalism and mixed state formalism.     

Matrix power series method for nonlinear problems of optimal regulator construction

We propose a relatively simple and efficient method for solving the problem of analytic construction of optimal regulators for multidimensional control objects with polynomial nonlinearities based on the A.A. Krasovskii’s generalized work criterion. Our method employs an extension of the power series method which is based on using matrix theory with Kroneker (direct) product. The matrix formalism has let us establish a simple recursive relation for the matrices of coefficients of the Bellman-Lyapunov function, with which the control problem can be solved with any reasonable precision on modern computers.     

切换时滞线性系统的状态反馈H∞控制

研究一类由任意有限个时滞线性子系统组成的切换系统的状态反馈 控制问题。利用Lyapunov函数方法和凸组合技术,给出由矩阵不等式表示的控制器存在的充分条件,设计相应的子控制器和切换规则。采用变量替代方法,将该矩阵不等式转化为一组线性矩阵不等式。给出一个求解状态反馈控制器增益矩阵的仿真算例。     

Restoration of matrix fields by second-order cone programming

Summary Wherever anisotropic behavior in physical measurements or models is encountered matrices provide adequate means to describe this anisotropy. Prominent examples are the diffusion tensor magnetic resonance imaging in medical imaging or the stress tensor in civil engineering. As most measured data these matrix-valued data are also polluted by noise and require restoration. The restoration of scalar images corrupted by noise via minimization of an energy functional is a well-established technique that offers many advantages. A convenient way to achieve this minimization is second-order cone programming (SOCP). The goal of this article is to transfer this method to the matrix-valued setting. It is shown how SOCP can be applied to minimize various energy functionals defined for matrix fields. These functionals couple the different matrix channels taking into account the relations between them. Furthermore, new functionals for the regularization of matrix data are proposed and the corresponding Euler–Lagrange equations are derived by means of matrix differential calculus. Numerical experiments substantiate the usefulness of the proposed methods for the restoration of matrix fields.      

An improved FCMBP fuzzy clustering method based on evolutionary programming

In current PC computing environment, the fuzzy clustering method based on perturbation (FCMBP) is failed when dealing with similar matrices whose orders are higher than tens. The reason is that the traversal process adopted in FCMBP is exponential complexity. This paper treated the process of finding fuzzy equivalent matrices with smallest error from an optimization point of view and proposed an improved FCMBP fuzzy clustering method based on evolutionary programming. The method seeks the optimal fuzzy equivalent matrix which is nearest to the given fuzzy similar matrix by evolving a population of candidate solutions over a number of generations. A new population is formed from an existing population through the use of a mutation operator. Better solutions survive into next generation and finally the globally optimal fuzzy equivalent matrix could be obtained or approximately obtained. Compared with FCMBP, the improved method has the following advantages: (1) Traversal searching is avoided by introducing an evolutionary programming based optimization technique. (2) For low-order matrices, the method has much better efficiency in finding the globally optimal fuzzy equivalent matrix. (3) Matrices with hundreds of orders could be managed. The method could quickly get a more accurate solution than that obtained by the transitive closure method and higher precision requirement could be achieved by further iterations. And the method is adaptable for matrices of higher order. (4) The method is robust and not sensitive to parameters.