Random perfect lattices and the sphere packing problem
Andreanov A., Motivated by the search for best lattice sphere packings in Euclidean spaces of large dimensions we study randomly generated perfect lattices in moderately large dimensions (up to d=19 included). Perfect lattices are relevant in the solution of the problem of lattice sphere packing, because the best lattice packing is a perfect lattice and because they can be generated easily. Their number, however, grows superexponentially with the dimension, so to get an idea of their properties we propose to study a randomized version of the generating algorithm and to define a random ensemble with an effective temperature in a way reminiscent of a Monte Carlo simulation. We therefore study the distribution of packing fractions and kissing numbers of these ensembles and show how as the temperature is decreased the best known packers are easily recovered. We find that, even at infinite temperature, the typical perfect lattices are considerably denser than known families (like A d and D d ), and we propose two hypotheses between which we cannot distinguish in this paper: one in which they improve the Minkowsky bound φ∼2 -(0.84 ±0.06 )d, and a competitor in which their packing fraction decreases superexponentially, namely, φ∼d -ad but with a very small coefficient a=0.06±0.04. We also find properties of the random walk which are suggestive of a glassy system already for moderately small dimensions. We also analyze local structure of network of perfect lattices conjecturing that this is a scale-free network in all dimensions with constant scaling exponent 2.6±0.1. © 2012 American Physical Society.
Quantum adiabatic algorithm and scaling of gaps at first-order quantum phase transitions
Laumann C.R., Moessner R., Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii)it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing. © 2012 American Physical Society.
Statistical mechanics of classical and quantum computational complexity
Laumann C., Moessner R., The quest for quantum computers is motivated by their potential for solving problems that defy existing, classical, computers. The theory of computational complexity, one of the crown jewels of computer science, provides a rigorous framework for classifying the hardness of problems according to the computational resources, most notably time, needed to solve them. Its extension to quantum computers allows the relative power of quantum computers to be analyzed. This framework identifies families of problems which are likely hard for classical computers ("NP-complete") and those which are likely hard for quantum computers ("QMA-complete") by indirect methods. That is, they identify problems of comparable worst-case difficulty without directly determining the individual hardness of any given instance. Statistical mechanical methods can be used to complement this classification by directly extracting information about particular families of instances-typically those that involve optimization-by studying random ensembles of them. These pose unusual and interesting (quantum) statistical mechanical questions and the results shed light on the difficulty of problems for large classes of algorithms as well as providing a window on the contrast between typical and worst case complexity. In these lecture notes we present an introduction to this set of ideas with older work on classical satisfiability and recent work on quantum satisfiability as primary examples. We also touch on the connection of computational hardness with the physical notion of glassiness. © 2012 Springer-Verlag Berlin Heidelberg.
Statistical distribution of the local purity in a large quantum system
De Pasquale A., Facchi P., Giovannetti V., Parisi G., Pascazio S., The local purity of large many-body quantum systems can be studied by following a statistical mechanical approach based on a random matrix model. Restricting the analysis to the case of global pure states, this method proved to be successful, and a full characterization of the statistical properties of the local purity was obtained by computing the partition function of the problem. Here we generalize these techniques to the case of global mixed states. In this context, by uniformly sampling the phase space of states with assigned global mixedness, we determine the exact expression of the first two moments of the local purity and a general expression for the moments of higher order. This generalizes previous results obtained for globally pure configurations. Furthermore, through the introduction of a partition function for a suitable canonical ensemble, we compute the approximate expression of the first moment of the marginal purity in the high-temperature regime. In the process, we establish a formal connection with the theory of quantum twirling maps that provides an alternative, possibly fruitful, way of performing the calculation.
Structure of typical states of a disordered Richardson model and many-body localization
Buccheri F., De Luca A., We present a thorough numerical study of the Richardson model with quenched disorder (a fully connected XX model with longitudinal random fields). We find that for any value of the interaction the eigenstates occupy an exponential number of sites on the unperturbed Fock space but that single-spin observables do not thermalize, as tested by a microcanonical version of the Edwards-Anderson order parameter. We therefore do not observe many-body localization in this model. We find a relation between the inverse participation ratio and the average Hamming distance between spin configurations covered by a typical eigenstate for which we hypothesize a remarkably simple form for the thermodynamic limit. We also studied the random process defined by the spread of a typical eigenstate on configuration space, highlighting several similarities with hopping on percolated hypercube, a process used to mimic the slow relaxation of spin glasses. A nearby nonintegrable model is also considered where delocalization is instead observed, although the presence of a phase transition at infinite temperature is questionable. © 2011 American Physical Society.
How many eigenvalues of a Gaussian random matrix are positive?
Majumdar S.N., Nadal C., We study the probability distribution of the index N+ , i.e., the number of positive eigenvalues of an N×N Gaussian random matrix. We show analytically that, for large N and large N+ with the fraction 0≤c=N+ /N≤1 of positive eigenvalues fixed, the index distribution P(N+ =cN,N)~exp[-βN2Φ(c)] where β is the Dyson index characterizing the Gaussian ensemble. The associated large deviation rate function Φ(c) is computed explicitly for all 0≤c≤1. It is independent of β and displays a quadratic form modulated by a logarithmic singularity around c=1/2. As a consequence, the distribution of the index has a Gaussian form near the peak, but with a variance Δ(N) of index fluctuations growing as Δ(N)-lnN/βπ2 for large N. For β=2, this result is independently confirmed against an exact finite-N formula, yielding Δ(N)=lnN/2π2+C+O(N-1) for large N, where the constant C for even N has the nontrivial value C=(γ+1+3ln2)/2π2-0.185- 248⋯ and γ=0.5772⋯ is the Euler constant. We also determine for large N the probability that the interval [ζ1 , ζ2 ] is free of eigenvalues. Some of these results have been announced in a recent letter. © 2011 American Physical Society.
Product, generic, and random generic quantum satisfiability
Laumann C.R., Läuchli A.M., Moessner R., We report a cluster of results on k-QSAT, the problem of quantum satisfiability for k-qubit projectors which generalizes classical satisfiability with k-bit clauses to the quantum setting. First we define the NP-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT-unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for k=3 and k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone. © 2010 The American Physical Society.
Distribution of partition function zeros of the ± J model on the Bethe lattice
Matsuda Y., Müller M., Nishimori H., Obuchi T., The distribution of partition function zeros is studied for the J model of spin glasses on the Bethe lattice. We find a relation between the distribution of complex cavity fields and the density of zeros, which enables us to obtain the density of zeros for the infinite system size by using the cavity method. The phase boundaries thus derived from the location of the zeros are consistent with the results of direct analytical calculations. This is the first example in which the spin-glass transition is related to the distribution of zeros directly in the thermodynamical limit. We clarify how the spin-glass transition is characterized by the zeros of the partition function. It is also shown that in the spin-glass phase a continuous distribution of singularities touches the axes of real field and temperature. © 2010 IOP Publishing Ltd.
Phase transitions and metastability in the distribution of the bipartite entanglement of a large quantum system
De Pasquale A., Facchi P., Parisi G., Pascazio S., We study the distribution of the Schmidt coefficients of the reduced density matrix of a quantum system in a pure state. By applying general methods of statistical mechanics, we introduce a fictitious temperature and a partition function and translate the problem in terms of the distribution of the eigenvalues of random matrices. We investigate the appearance of two phase transitions, one at a positive temperature, associated with very entangled states, and one at a negative temperature, signaling the appearance of a significant factorization in the many-body wave function. We also focus on the presence of metastable states (related to two-dimensional quantum gravity) and study the finite size corrections to the saddle point solution. © 2010 The American Physical Society.
Random quantum satisfiabiilty
Laumann C.R., Moessner R., Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA1 -complete quantum satisfiability (QSAT) problem introduced by Bravyi [1]. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for any hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density. © Rinton Press.
Quantum Zeno effect in a model multilevel molecule
Bruno D., Facchi P., Longo S., Minelli P., Pascazio S., We study the dynamics of the populations of a model molecule endowed with two sets of rotational levels of different parity, whose ground levels are energetically degenerate and coupled by a constant interaction. The relaxation rate from one set of levels to the other one has an interesting dependence on the average collision frequency of the molecules in the gas. This is interpreted as a quantum Zeno effect due to the decoherence effects provoked by the molecular collisions. © 2009 American Chemical Society.
Index Distribution of Gaussian Random Matrices
Majumdar S.N., Nadal C., We compute analytically, for large N, the probability distribution of the number of positive eigenvalues (the index N+) of a random N×N matrix belonging to Gaussian orthogonal (β=1), unitary (β=2) or symplectic (β=4) ensembles. The distribution of the fraction of positive eigenvalues c=N+/N scales, for large N, as P(c,N)□exp□[-βN2Φ(c)] where the rate function Φ(c), symmetric around c=1/2 and universal (independent of β), is calculated exactly. The distribution has non-Gaussian tails, but even near its peak at c=1/2 it is not strictly Gaussian due to an unusual logarithmic singularity in the rate function. © 2009 The American Physical Society.
Statistical properties of determinantal point processes in high-dimensional Euclidean spaces
The goal of this paper is to quantitatively describe some statistical properties of higher-dimensional determinantal point processes with a primary focus on the nearest-neighbor distribution functions. Toward this end, we express these functions as determinants of N×N matrices and then extrapolate to N→. This formulation allows for a quick and accurate numerical evaluation of these quantities for point processes in Euclidean spaces of dimension d. We also implement an algorithm due to Hough for generating configurations of determinantal point processes in arbitrary Euclidean spaces, and we utilize this algorithm in conjunction with the aforementioned numerical results to characterize the statistical properties of what we call the Fermi-sphere point process for d=1-4. This homogeneous, isotropic determinantal point process, discussed also in a companion paper, is the high-dimensional generalization of the distribution of eigenvalues on the unit circle of a random matrix from the circular unitary ensemble. In addition to the nearest-neighbor probability distribution, we are able to calculate Voronoi cells and nearest-neighbor extrema statistics for the Fermi-sphere point process, and we discuss these properties as the dimension d is varied. The results in this paper accompany and complement analytical properties of higher-dimensional determinantal point processes developed in a prior paper. © 2009 The American Physical Society.
On quantum spin glasses with finite connectivity: Cavity method and applications
Laumann C., We discuss quantum spin glasses with finite connectivity by presenting an extension of the cavity method used in studies of classical spin glasses. © 2009 IOP Publishing Ltd.
Point processes in arbitrary dimension from fermionic gases, random matrix theory, and number theory
Torquato S., It is well known that one can map certain properties of random matrices, fermionic gases, and zeros of the Riemann zeta function to a unique point process on the real line . Here we analytically provide exact generalizations of such a point process in d-dimensional Euclidean space for any d, which are special cases of determinantal processes. In particular, we obtain the n-particle correlation functions for any n, which completely specify the point processes in . We also demonstrate that spin-polarized fermionic systems in have these same n-particle correlation functions in each dimension. The point processes for any d are shown to be hyperuniform, i.e., infinite wavelength density fluctuations vanish, and the structure factor (or power spectrum) S(k) has a non-analytic behavior at the origin given by S(k)∼|k| (). The latter result implies that the pair correlation function g2 (r) tends to unity for large pair distances with a decay rate that is controlled by the power law 1/rd+1, which is a well-known property of bosonic ground states and more recently has been shown to characterize maximally random jammed sphere packings. We graphically display one-and two-dimensional realizations of the point processes in order to vividly reveal their 'repulsive' nature. Indeed, we show that the point processes can be characterized by an effective 'hard core' diameter that grows like the square root of d. The nearest-neighbor distribution functions for these point processes are also evaluated and rigorously bounded. Among other results, this analysis reveals that the probability of finding a large spherical cavity of radius r in dimension d behaves like a Poisson point process but in dimension d+1, i.e., this probability is given by exp[-κ(d)rd+1] for large r and finite d, where κ(d) is a positive d-dependent constant. We also show that as d increases, the point process behaves effectively like a sphere packing with a coverage fraction of space that is no denser than 1/2d. This coverage fraction has a special significance in the study of sphere packings in high-dimensional Euclidean spaces. © 2008 IOP Publishing Ltd.
Cavity method for quantum spin glasses on the Bethe lattice
Laumann C., We propose a generalization of the cavity method to quantum spin glasses on fixed connectivity lattices. Our work is motivated by the recent refinements of the classical technique and its potential application to quantum computational problems. We numerically solve for the phase structure of a connectivity q=3 transverse field Ising model on a Bethe lattice with ±J couplings and investigate the distribution of various classical and quantum observables. © 2008 The American Physical Society.
Bipartite quantum systems: On the realignment criterion and beyond
Lupo C., Aniello P., Inspired by the 'computable cross norm' or 'realignment' criterion, we propose a new point of view about the characterization of the states of bipartite quantum systems. We consider a Schmidt decomposition of a bipartite density operator. The corresponding Schmidt coefficients, or the associated symmetric polynomials, are regarded as quantities that can be used to characterize bipartite quantum states. In particular, starting from the realignment criterion, a family of necessary conditions for the separability of bipartite quantum states are derived. We conjecture that these conditions, which are weaker than the parent criterion, can be strengthened in such a way to obtain a new family of criteria that are independent of the original one. This conjecture is supported by numerical examples for the low dimensional cases. These ideas can be applied to the study of quantum channels, leading to a relation between the rate of contraction of a map and its ability to preserve entanglement. © 2008 IOP Publishing Ltd.
Phase transitions of bipartite entanglement
Facchi P., Marzolino U., Parisi G., Pascazio S., We analyze the statistical properties of the entanglement of a large bipartite quantum system. By framing the problem in terms of random matrices and a fictitious temperature, we unveil the existence of two phase transitions, characterized by different spectra of the reduced density matrices. © 2008 The American Physical Society.
Griffiths-McCoy singularities, Lee-Yang zeros, and the cavity method in a solvable diluted ferromagnet
Laumann C., We study the diluted Ising ferromagnet on the Bethe lattice as a case study for the application of the cavity method to problems with Griffiths-McCoy singularities. Specifically, we are able to make much progress at infinite coupling where we compute, from the cavity method, the density of Lee-Yang zeros in the paramagnetic Griffiths region as well as the properties of the phase transition to the ferromagnet. This phase transition is itself of a Griffiths-McCoy character albeit with a power law distribution of cluster sizes. © 2008 The American Physical Society.
Estimates of the optimal density of sphere packings in high dimensions
The problem of finding the asymptotic behavior of the maximal density φmax of sphere packings in high Euclidean dimensions is one of the most fascinating and challenging problems in discrete geometry. One century ago, Minkowski obtained a rigorous lower bound on φmax that is controlled asymptotically by 1 2d, where d is the Euclidean space dimension. An indication of the difficulty of the problem can be garnered from the fact that exponential improvement of Minkowski's bound has proved to be elusive, even though existing upper bounds suggest that such improvement should be possible. Using a statistical-mechanical procedure to optimize the density associated with a "test" pair correlation function and a conjecture concerning the existence of disordered sphere packings [S. Torquato and F. H. Stillinger, Exp. Math. 15, 307 (2006)], the putative exponential improvement on φmax was found with an asymptotic behavior controlled by 1 2 (0.77865) d. Using the same methods, we investigate whether this exponential improvement can be further improved by exploring other test pair correlation functions corresponding to disordered packings. We demonstrate that there are simpler test functions that lead to the same asymptotic result. More importantly, we show that there is a wide class of test functions that lead to precisely the same putative exponential improvement and therefore the asymptotic form 1 2 (0.77865) d is much more general than previously surmised. This class of test functions leads to an optimized average kissing number that is controlled by the same asymptotic behavior as the one found in the aforementioned paper. © 2008 American Institute of Physics.