Efficient learning of decomposable models with a bounded clique size

The learning of probability distributions from data is a ubiquitous problem in the fields of Statistics and Artificial Intelligence. During the last decades several learning algorithms have been proposed to learn probability distributions based on decomposable models due to their advantageous theoretical properties. Some of these algorithms can be used to search for a maximum likelihood decomposable model with a given maximum clique size, k, which controls the complexity of the model. Unfortunately, the problem of learning a maximum likelihood decomposable model given a maximum clique size is NP-hard for k > 2. In this work, we propose a family of algorithms which approximates this problem with a computational complexity of O(k · n^2 log n) in the worst case, where n is the number of implied random variables. The structures of the decomposable models that solve the maximum likelihood problem are called maximal k-order decomposable graphs. Our proposals, called fractal trees, construct a sequence of maximal i-order decomposable graphs, for i = 2, ..., k, in k − 1 steps. At each step, the algorithms follow a divide-and-conquer strategy based on the particular features of this type of structures. Additionally, we propose a prune-and-graft procedure which transforms a maximal k-order decomposable graph into another one, increasing its likelihood. We have implemented two particular fractal tree algorithms called parallel fractal tree and sequential fractal tree. These algorithms can be considered a natural extension of Chow and Liu’s algorithm, from k = 2 to arbitrary values of k. Both algorithms have been compared against other efficient approaches in artificial and real domains, and they have shown a competitive behavior to deal with the maximum likelihood problem. Due to their low computational complexity they are especially recommended to deal with high dimensional domains.

Nonperturbative dynamical decoupling with random control

Parametric fluctuations or stochastic signals are introduced into the rectangular pulse sequence to investigate the feasibility of random dynamical decoupling. In a large parameter region, we find that the out-of-order control pulses work as well as the regular pulses for dynamical decoupling and dissipation suppression. Calculations and analysis are enabled by and based on a nonperturbative dynamical decoupling approach allowed by an exact quantum-state-diffusion equation. When the average frequency and duration of the pulse sequence take proper values, the random control sequence is robust, fault-tolerant, and insensitive to pulse strength deviations and interpulse temporal separation in the quasi-periodic sequence. This relaxes the operational requirements placed on quantum control devices to a great deal.

Digital Quantum Simulation of Spin Models with Circuit Quantum Electrodynamics

Systems of interacting quantum spins show a rich spectrum of quantum phases and display interesting many-body dynamics. Computing characteristics of even small systems on conventional computers poses significant challenges. A quantum simulator has the potential to outperform standard computers in calculating the evolution of complex quantum systems. Here, we perform a digital quantum simulation of the paradigmatic Heisenberg and Ising interacting spin models using a two transmon-qubit circuit quantum electrodynamics setup. We make use of the exchange interaction naturally present in the simulator to construct a digital decomposition of the model-specific evolution and extract its full dynamics. This approach is universal and efficient, employing only resources that are polynomial in the number of spins, and indicates a path towards the controlled simulation of general spin dynamics in superconducting qubit platforms.

Long-Term Growth and Persistence with Endogenous Depreciation: Theory and Evidence

Previous research has shown a strong positive correlation between short-term persistence and long-term output growth as well as between depreciation rates and long-term output growth. This evidence, therefore, contradicts the standard predictions from traditional neoclassical or AK-type growth models with exogenous depreciation. In this paper, we first confirm these findings for a larger sample of 101 countries. We then study the dynamics of growth and persistence in a model where both the depreciation rate and growth are endogenous and procyclical. We find that the model s predictions become consistent with the empirical evidence on persistence, long-term growth and depreciation rates.

Strategic Votes and Sincere Counterfactuals

The Random Utility Model (RUM) of voting behavior can account for strategic voting by making use of proxy indicators that measure voter incentives to vote strategically. The contribution of this paper is to propose a new method to estimate the RUM in the presence of strategic voters, without having to construct proxy measures of strategic voting incentives. Our method can be used to infer the counterfactual sincere vote of those who vote strategically and provides an estimate of the size of strategic voting. We illustrate the procedure using post-electoral survey data from Spain. Our calculations indicate that strategic voting in Spain is about 2.19 per cent

The Determinants of Energy Efficiency Investments in the U.S.

31 p.