Polynomial Monogamy Relations for Entanglement Negativity.

The notion of nonclassical correlations is a powerful contrivance for explaining phenomena exhibited in quantum systems. It is well known, however, that quantum systems are not free to explore arbitrary correlations-the church of the smaller Hilbert space only accepts monogamous congregants. We demonstrate how to characterize the limits of what is quantum mechanically possible with a computable measure, entanglement negativity. We show that negativity only saturates the standard linear monogamy inequality in trivial cases implied by its monotonicity under local operations and classical communication, and derive a necessary and sufficient inequality which, for the first time, is a nonlinear higher degree polynomial. For very large quantum systems, we prove that the negativity can be distributed at least linearly for the tightest constraint and conjecture that it is at most linear.

Efficient robust conditional random fields.

Conditional random fields (CRFs) are a flexible yet powerful probabilistic approach and have shown advantages for popular applications in various areas, including text analysis, bioinformatics, and computer vision. Traditional CRF models, however, are incapable of selecting relevant features as well as suppressing noise from noisy original features. Moreover, conventional optimization methods often converge slowly in solving the training procedure of CRFs, and will degrade significantly for tasks with a large number of samples and features. In this paper, we propose robust CRFs (RCRFs) to simultaneously select relevant features. An optimal gradient method (OGM) is further designed to train RCRFs efficiently. Specifically, the proposed RCRFs employ the l1 norm of the model parameters to regularize the objective used by traditional CRFs, therefore enabling discovery of the relevant unary features and pairwise features of CRFs. In each iteration of OGM, the gradient direction is determined jointly by the current gradient together with the historical gradients, and the Lipschitz constant is leveraged to specify the proper step size. We show that an OGM can tackle the RCRF model training very efficiently, achieving the optimal convergence rate [Formula: see text] (where k is the number of iterations). This convergence rate is theoretically superior to the convergence rate O(1/k) of previous first-order optimization methods. Extensive experiments performed on three practical image segmentation tasks demonstrate the efficacy of OGM in training our proposed RCRFs.

Connectivity is a poor indicator of fast quantum search.

A randomly walking quantum particle evolving by Schrödinger's equation searches on d-dimensional cubic lattices in O(√N) time when d≥5, and with progressively slower runtime as d decreases. This suggests that graph connectivity (including vertex, edge, algebraic, and normalized algebraic connectivities) is an indicator of fast quantum search, a belief supported by fast quantum search on complete graphs, strongly regular graphs, and hypercubes, all of which are highly connected. In this Letter, we show this intuition to be false by giving two examples of graphs for which the opposite holds true: one with low connectivity but fast search, and one with high connectivity but slow search. The second example is a novel two-stage quantum walk algorithm in which the walking rate must be adjusted to yield high search probability.

Lattice gas simulations of dynamical geometry in two dimensions.

We present a hydrodynamic lattice gas model for two-dimensional flows on curved surfaces with dynamical geometry. This model is an extension to two dimensions of the dynamical geometry lattice gas model previously studied in one dimension. We expand upon a variation of the two-dimensional flat space Frisch-Hasslacher-Pomeau (FHP) model created by Frisch [Phys. Rev. Lett. 56, 1505 (1986)] and independently by Wolfram, and modified by Boghosian [Philos. Trans. R. Soc. London, Ser. A 360, 333 (2002)]. We define a hydrodynamic lattice gas model on an arbitrary triangulation whose flat space limit is the FHP model. Rules that change the geometry are constructed using the Pachner moves, which alter the triangulation but not the topology. We present results on the growth of the number of triangles as a function of time. Simulations show that the number of triangles grows with time as t(1/3), in agreement with a mean-field prediction. We also present preliminary results on the distribution of curvature for a typical triangulation in these simulations.

Periodicity and growth in a lattice gas with dynamical geometry.

We study a one-dimensional lattice gas "dynamical geometry model" in which local reversible interactions of counter-rotating groups of particles on a ring can create or destroy lattice sites. We exhibit many periodic orbits and show that all other solutions have asymptotically growing lattice length in both directions of time. We explain why the length grows as squareroot of t in all cases examined. We completely solve the dynamics for small numbers of particles with arbitrary initial conditions.

Lattice gas simulations of dynamical geometry in one dimension.

We present numerical results obtained using a lattice gas model with dynamical geometry. The (irreversible) macroscopic behaviour of the geometry (size) of the lattice is discussed in terms of a simple scaling theory and obtained numerically. The emergence of irreversible behaviour from the reversible microscopic lattice gas rules is discussed in terms of the constraint that the macroscopic evolution be reproducible. The average size of the lattice exhibits power-law growth with exponent at late times. The deviation of the macroscopic behaviour from reproducibility for particular initial conditions ('rogue states') is investigated as a function of system size. The number of such 'rogue states' is observed to decrease with increasing system size. Two mean-field analyses of the macroscopic behaviour are also presented.

Quantum computing classical physics.

In the past decade, quantum algorithms have been found which outperform the best classical solutions known for certain classical problems as well as the best classical methods known for simulation of certain quantum systems. This suggests that they may also speed up the simulation of some classical systems. I describe one class of discrete quantum algorithms which do so--quantum lattice-gas automata--and show how to implement them efficiently on standard quantum computers.

Towards the simplest hydrodynamic lattice-gas model.

It has been known since 1986 that it is possible to construct simple lattice-gas cellular automata whose hydrodynamics are governed by the Navier-Stokes equations in two dimensions. The simplest such model heretofore known has six bits of state per site on a triangular lattice. In this work, we demonstrate that it is possible to construct a model with only five bits of state per site on a Kagome lattice. Moreover, the model has a simple, deterministic set of collision rules and is easily implemented on a computer. In this work, we derive the equilibrium distribution function for this lattice-gas automaton and carry out the Chapman-Enskog analysis to determine the form of the Navier-Stokes equations.