Clocks and fisher information

In a broad sense, any parametric family of quantum states can be viewed as a quantum clock. The time, which is the parameter, is encoded in the corresponding quantum states. The quality of such a clock depends on how precisely we can distinguish the states or, equivalently, estimate the parameter. In view of the quantum Cramér—Rao inequalities, the quality of quantum clocks can be characterized by the quantum Fisher information. We address the issue of quantum clock synchronization in terms of quantum Fisher information and demonstrate its fundamental difference from the classical paradigm. The key point is the superadditivity of Fisher information, which always holds in the classical case but can be violated in quantum mechanics. The violation can occur for both pure and mixed states. Nevertheless, we establish the superadditivity of quantum Fisher information for any classical-quantum state. We also demonstrate an alternative form of superadditivity and propose a weak form of superadditivity. The violation of superadditivity can be exploited to enhance quantum clock synchronization.     

Fisher information inequalities and the central limit theorem

We give conditions for an O(1/n) rate of convergence of Fisher information and relative entropy in the Central Limit Theorem. We use the theory of projections in L² spaces and Poincaré inequalities, to provide a better understanding of the decrease in Fisher information implied by results of Barron and Brown. We show that if the standardized Fisher information ever becomes finite then it converges to zero.OTJ is a Fellow of Christs College, Cambridge, who helped support two trips to Yale University during which this paper was written.Mathematics Subject Classification (2000):Primary: 62B10 Secondary: 60F05, 94A17     

Wigner-Yanase skew information vs. quantum Fisher information

Among concepts describing the information contents of quantum mechanical density operators, both the Wigner-Yanase skew information and the quantum Fisher information defined via symmetric logarithmic derivatives are natural generalizations of the classical Fisher information. We will establish a relationship between these two fundamental quantities and show that they are comparable.

     

Mixing mixed-integer inequalities

Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure. Received: April 1998 / Accepted: January 2001?Published online April 12, 2001     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

On a refinement of Heisenberg uncertainty relation by means of quantum Fisher information

We show that an uncertainty relation proved by Luo and Yanagi and related to Wigner-Yanase-Dyson information cannot hold for an arbitrary quantum Fisher information. We show that, by changing a costant, a similar trace inequality holds in full generality.     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

A cutting plane algorithm for the General Routing Problem

The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it is capable of providing very strong lower bounds and, in most cases, optimal solutions. Received: November 1998 / Accepted: September 2000?Published online March 22, 2001     

Metric adjusted skew information and uncertainty relation

We show that an uncertainty relation for Wigner-Yanase-Dyson skew information proved by Yanagi (2010) [10] can hold for an arbitrary quantum Fisher information under some conditions. This is a refinement of the result of Gibilisco and Isola (2011) [4].     

Trace inequalities on a generalized Wigner-Yanase skew information

We introduce a generalized Wigner-Yanase skew information and then derive the trace inequality related to the uncertainty relation. This inequality is a non-trivial generalization of the uncertainty relation derived by S. Luo for the quantum uncertainty quantity excluding the classical mixture. In addition, several trace inequalities on our generalized Wigner-Yanase skew information are argued.     

Nonlinear 0–1 programming: II. Dominance relations and algorithms

A nonlinear 0–1 program can be restated as a multilinear 0–1 program, which in turn is known to be equivalent to a linear 0–1 program with generalized covering (g.c.) inequalities. In a companion paper [6] we have defined a family of linear inequalities that contains more compact (smaller cardinality) linearizations of a multilinear 0–1 program than the one based on the g.c. inequalities. In this paper we analyze the dominance relations between inequalities of the above family. In particular, we give a criterion that can be checked in linear time, for deciding whether a g.c. inequality can be strengthened by extending the cover from which it was derived. We then describe a class of algorithms based on these results and discuss our computational experience. We conclude that the g.c. inequalities can be strengthened most of the time to an extent that increases with problem density. In particular, the algorithm using the strengthening procedure outperforms the one using only g.c. inequalities whenever the number of nonlinear terms per constraint exceeds about 12–15, and the difference in their performance grows with the number of such terms. Research supported by the National Science Foundation under grant ECS 7902506 and by the Office of Naval Research under contract N00014-75-C-0621 NR 047-048.     

Direct approach to the problem of strong local minima in calculus of variations

Let (M,g) be a two-dimensional compact Riemannian manifold. In this paper, we use the method of blowing up analysis to prove several Moser–Trudinger type inequalities for vector bundle over (M,g). We also derive an upper bound of such inequalities under the assumption that blowing up occurs. The research of the second author was partially supported by NSFC grant and the Foundation of Shanghai for Priority Academic Discipline.     

Direct approach to quantum extensions of Fisher information

By manipulating classical Fisher information and employing various derivatives of density operators, and using entirely intuitive and direct methods, we introduce two families of quantum extensions of Fisher information that include those defined via the symmetric logarithmic derivative, via the right logarithmic derivative, via the Bogoliubov-Kubo-Mori derivative, as well as via the derivative in terms of commutators, as special cases. Some fundamental properties of these quantum extensions of Fisher information are investigated, a multi-parameter quantum Cramér-Rao inequality is established, and applications to characterizing quantum uncertainty are illustrated.      

The 0-1 Knapsack problem with a single continuous variable

Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented. Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998     

Galois objects for algebraic quantum groups

The basic elements of Galois theory for algebraic quantum groups were given in the paper ‘Galois Theory for Multiplier Hopf Algebras with Integrals’ by Van Daele and Zhang. In this paper, we supplement their results in the special case of Galois objects: algebras equipped with a Galois coaction by an algebraic quantum group, such that only the scalars are coinvariants. We show how the structure of these objects is as rich as the one of the quantum groups themselves: there are two distinguished weak K.M.S. functionals, related by a modular element, and there is an analogue of the antipode squared. We show how to reflect the quantum group across a Galois object to obtain a (possibly) new algebraic quantum group. We end by considering an example.     

A branch and cut approach to the cardinality constrained circuit problem

The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most k edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits, and a branch-and-cut solution approach using these inequalities. Received: April 1998 / Accepted: October 2000?Published online October 26, 2001     

The stable admissions polytope

The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities. It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been fruitful in the analysis of the stable marriage problem. Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000     

Fisher information under restriction of Shannon information in multi-terminal situations

Fisher information generally decreases by summarizing observed data into encoded messages. The present paper studies the amount of Fisher information included in independently summarized messages from correlated information sources; that is, the amount of Fisher information when sequences x ^N and y ^N of N independent observations of random variables x and y are encoded (summarized) independently of each other into meassages m _X and m _Y . The problem is to obtain the maximal amount of Fisher information when the size of the summarized data or Shannon message information is limited. The problem is solved in the case of completely compressed symmetric data summarization. An achievable bound is given in the general case. Information geometry, which is a powerful new differential geometrical method applicable to statistics and systems theory, is applied to this problem, proving its usefulness in information theory as well.The present work is supported in part by Grant-in-Aid for Scientific Research #61030014, Ministry of Education, Science and Culture of Japan.     

Some inequalities related to the Stam inequality

Zamir showed in 1998 that the Stam classical inequality for the Fisher information (about a location parameter)