We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. We accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. The result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.

We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. We accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. The result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.

In this paper we introduce a model of default contagion in the financail market. The structure of the companies are represented by a Heavy Gravity Portfolio, where we assume there are N sectors in the market and in each sector i, there is one big trader and ni supply companies.The supply companies in each sector are directly inuenced by the bigtrader and the big traders are also pairwise interacting with each other.This development of the Ising model is called Heavy gravity portfolioand according to this, the relation between expectation and correlationof the default of companies are derived by means of simulations utilisingthe Gibbs sampler. Finally methods for maximum likelihood estimationand for a likelihood ratio test of the interaction parameter in the modelare derived.

This thesis presents research of two novel magnetic materials, LiHoF4 and Tb2Ti2O7. Experiments were performed at low temperatures and in an applied magnetic field to study thermal expansion and magnetostriction using a capacitive dilatometer designed during this project. This thesis presents 3 distinct topics. This manuscript begins with a thermodynamic description of thermal expansion and magnetostriction. The design of a capacitive dilatometer suitable for use at ultra-low temperatures and in high magnetic fields is presented. The thermal expansion of oxygen free high conductivity copper is used as a test of the absolute accuracy of the dilatometer. The first material studied using this dilatometer was LiHoF4. Pure LiHoF4 is a dipolar coupled Ising ferromagnet and in an applied transverse magnetic field is a good representation of the transverse field Ising model. An ongoing discrepancy between theoretical and experimental work motivates further study of this textbook material. Presented here are thermal expansion and magnetostriction measurements of LiHoF4 in an applied transverse field. We find good agreement with existing experimental work. This suggests that there is some aspect of LiHoF4 or the effect of quantum mechanical fluctuations at finite temperatures which is not well understood. The second material studied is the spin liquid Tb2Ti2O7. Despite theoretical predictions that Tb2Ti2O7 will order at finite temperature, a large body of experimental evidence demonstrates that spins within Tb2Ti2O7 remain dynamic to the lowest temperatures studied. In addition Tb2Ti2O7 also exhibits anomalous thermal expansion below 20K, giant magnetostriction, and orders in an applied magnetic field. Thermal expansion and magnetostriction measurements of Tb2Ti2O7 are presented in applied longitudinal and transverse fields. Zero-field thermal expansion measurements do not repeat the previously observed anomalous thermal expansion. A large feature is observed in thermal expansion at 100mK, in rough agreement with existing experimental work. Longitudinal and transverse magnetic fields were applied to Tb2Ti2O7. Longitudinal magnetostriction measurements show qualitatively di erent behavior than previous observations. These measurements were taken along di erent crystal axes so direct comparison cannot be made. Thermal expansion measurements in an applied transverse field show evolution with the strength of the applied field. This evolution may relate to an ordering transition, however difficulties in repeatability in a transverse field require that these results be repeated in an improved setup.

No description available.

Die vorliegende Arbeit befasst sich mit dem Versuch der Optimierung von Simulated Annealing. Genauer gesagt, werden Simulationsergebnisse für einfache Spinglassysteme in Abhängigkeit von verschiedenen Nachbarschaftsmodellen berechnet – jeweils unter Verwendung des optimalen Abkühlverlaufs. Ziel ist es, eine Faustregel für die dynamische Anpassung der Nachbarschaftsbeziehung während einer Annealing-Simulation zu finden. / The thesis at hand presents an attempt to optimize simulated annealing. In particular, annealing results are computed based on different move class definitions for Ising spin systems while simultaneously applying an existing algorithm to determine the optimal temperature schedule for each case. The aim is to find a rule of thumb for dynamic adjustment of the move class during an annealing run.

Thèse doctorat : Physique statistique : Nancy 1 : 2006. Thèse doctorat : Physique statistique : University of Szeged (Hongrie) : 2006. / Thèse soutenue en co-tutelle. Titre provenant de l'écran-titre.

A majority of the data transmitted and processed today has an inherent structured high-dimensional nature, either because of the process of encoding using high-dimensional codebooks for providing a systematic structure, or dependency of the data on a large number of agents or variables. As a result, many problem setups associated with transmission and processing of data have a structured high-dimensional aspect to them. This dissertation takes a look at two such problems, namely, communication over networks using network coding, and learning the structure of graphical representations like Markov networks using observed data, from an information-theoretic perspective. Such an approach yields intuition about good coding architectures as well as the limitations imposed by the high-dimensional framework. Th e dissertation studies the problem of network coding for networks having multiple transmission sessions, i.e., multiple users communicating with each other at the same time. The connection between such networks and the information-theoretic interference channel is examined, and the concept of interference alignment, derived from interference channel literature, is coupled with linear network coding to develop novel coding schemes off ering good guarantees on achievable throughput. In particular, two setups are analyzed – the first where each user requires data from only one user (multiple unicasts), and the second where each user requires data from potentially multiple users (multiple multicasts). It is demonstrated that one can achieve a rate equalling a signi ficant fraction of the maximal rate for each transmission session, provided certain constraints on the network topology are satisfi ed. Th e dissertation also analyzes the problem of learning the structure of Markov networks from observed samples – the learning problem is interpreted as a channel coding problem and its achievability and converse aspects are examined. A rate-distortion theoretic approach is taken for the converse aspect, and information-theoretic lower bounds on the number of samples, required for any algorithm to learn the Markov graph up to a pre-speci fied edit distance, are derived for ensembles of discrete and Gaussian Markov networks based on degree-bounded graphs. The problem of accurately learning the structure of discrete Markov networks, based on power-law graphs generated from the con figuration model, is also studied. The eff ect of power-law exponent value on the hardness of the learning problem is deduced from the converse aspect – it is shown that discrete Markov networks on power-law graphs with smaller exponent values require more number of samples to ensure accurate recovery of their underlying graphs for any learning algorithm. For the achievability aspect, an effi cient learning algorithm is designed for accurately reconstructing the structure of Ising model based on power-law graphs from the con figuration model; it is demonstrated that optimal number of samples su ffices for recovering the exact graph under certain constraints on the Ising model potential values. / text

The first part of the dissertation concerns the Ising problem proposed to Ernst Ising by his supervisor Wilhelm Lenz in the early 20s. The Ising model, or perhaps more correctly the Lenz-Ising model, tries to capture the behaviour of phase transitions, i.e. how local rules of engagement can produce large scale behaviour. Two decades later Lars Onsager solved the Ising problem for the quadratic lattice without an outer field. Using his ideas solutions for other lattices in two dimensions have been constructed. We describe a method for calculating the Ising partition function for immense square grids, up to linear order 320 (i.e. 102400 vertices). In three dimensions however only a few results are known. One of the most important unanswered questions is at which temperature the Ising model has its phase transition. In this dissertation it is shown that an upper bound for the critical coupling Kc, the inverse absolute temperature, is 0.29 for the tree dimensional cubic lattice. To be able to get more information one has to use different statistical methods. We describe one sampling method that can use simple state generation like the Metropolis algorithm for large lattices. We also discuss how to reconstruct the entropy from the model, in order to obtain parameters as the free energy. The Ising model gives a partition function associated with all finite graphs. In this dissertation we show that a number of interesting graph invariants can be calculated from the coefficients of the Ising partition function. We also give some interesting observations about the partition function in general and show that there are, for any N, N non-isomorphic graphs with the same Ising partition function. The second part of the dissertation is about matrix operations. We consider the problem of multiplying them when the entries are elements in a finite semiring or in an additively finitely generated semiring. We describe a method that uses O(n3 / log n) arithmetic operations. We also consider the problem of reducing n x n matrices over a finite field of size q using O(n2 / logq n) row operations in the worst case.

This thesis presents research of two novel magnetic materials, LiHoF4 and Tb2Ti2O7. Experiments were performed at low temperatures and in an applied magnetic field to study thermal expansion and magnetostriction using a capacitive dilatometer designed during this project. This thesis presents 3 distinct topics. This manuscript begins with a thermodynamic description of thermal expansion and magnetostriction. The design of a capacitive dilatometer suitable for use at ultra-low temperatures and in high magnetic fields is presented. The thermal expansion of oxygen free high conductivity copper is used as a test of the absolute accuracy of the dilatometer. The first material studied using this dilatometer was LiHoF4. Pure LiHoF4 is a dipolar coupled Ising ferromagnet and in an applied transverse magnetic field is a good representation of the transverse field Ising model. An ongoing discrepancy between theoretical and experimental work motivates further study of this textbook material. Presented here are thermal expansion and magnetostriction measurements of LiHoF4 in an applied transverse field. We find good agreement with existing experimental work. This suggests that there is some aspect of LiHoF4 or the effect of quantum mechanical fluctuations at finite temperatures which is not well understood. The second material studied is the spin liquid Tb2Ti2O7. Despite theoretical predictions that Tb2Ti2O7 will order at finite temperature, a large body of experimental evidence demonstrates that spins within Tb2Ti2O7 remain dynamic to the lowest temperatures studied. In addition Tb2Ti2O7 also exhibits anomalous thermal expansion below 20K, giant magnetostriction, and orders in an applied magnetic field. Thermal expansion and magnetostriction measurements of Tb2Ti2O7 are presented in applied longitudinal and transverse fields. Zero-field thermal expansion measurements do not repeat the previously observed anomalous thermal expansion. A large feature is observed in thermal expansion at 100mK, in rough agreement with existing experimental work. Longitudinal and transverse magnetic fields were applied to Tb2Ti2O7. Longitudinal magnetostriction measurements show qualitatively di erent behavior than previous observations. These measurements were taken along di erent crystal axes so direct comparison cannot be made. Thermal expansion measurements in an applied transverse field show evolution with the strength of the applied field. This evolution may relate to an ordering transition, however difficulties in repeatability in a transverse field require that these results be repeated in an improved setup.