Semiring induced valuation algebras: Exact and approximate local computation algorithms

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra.There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.

A Wavelet Approach to the Selective Computation of Domninant Eigenvalues

This paper introduces an algorithm that calculates the dominant eigenvalues (in terms of system stability) of a linear model and neglects the exact computation of the non-dominant eigenvalues. The method estimates all of the eigenvalues using wavelet based compression techniques. These estimates are used to find a suitable invariant subspace such that projection by this subspace will provide one containing the eigenvalues of interest. The proposed algorithm is exemplified by application to a power system model.

Self-consistent geometry in the computation of the vibrational spectra of molecules

An exact and general approach to study molecular vibrations is provided by the Watson Hamiltonian. Within this framework, it is customary to omit the contribution of the terms with the vibrational angular momentum and the Watson term, especially for the study of large systems. We discover that this omission leads to results which depend on the choice of the reference structure. The self-consistent solution proposed here yields a geometry that coincides with the quantum averaged geometry of the Watson Hamiltonian and appears to be a promising way for the computation of the vibrational spectra of strongly anharmonic systems.

Significance Driven Computation on Next-Generation Unreliable Platforms

In this paper, we propose a design paradigm for energy efficient and variation-aware operation of next-generation multicore heterogeneous platforms. The main idea behind the proposed approach lies on the observation that not all operations are equally important in shaping the output quality of various applications and of the overall system. Based on such an observation, we suggest that all levels of the software design stack, including the programming model, compiler, operating system (OS) and run-time system should identify the critical tasks and ensure correct operation of such tasks by assigning them to dynamically adjusted reliable cores/units. Specifically, based on error rates and operating conditions identified by a sense-and-adapt (SeA) unit, the OS selects and sets the right mode of operation of the overall system. The run-time system identifies the critical/less-critical tasks based on special directives and schedules them to the appropriate units that are dynamically adjusted for highly-accurate/approximate operation by tuning their voltage/frequency. Units that execute less significant operations can operate at voltages less than what is required for correct operation and consume less power, if required, since such tasks do not need to be always exact as opposed to the critical ones. Such scheme can lead to energy efficient and reliable operation, while reducing the design cost and overheads of conventional circuit/micro-architecture level techniques.

Exact and heuristic methods for solving Boolean games

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.

BSP -Style Computation: A Semantic Investigation

A BSP (Bulk Synchronous Parallelism) computation is characterized by the generation of asynchronous messages in packages during independent execution of a number of processes and their subsequent delivery at synchronization points. Bundling messages together represents a significant departure from the traditional ‘one communication at a time’ approach. In this paper the semantic consequences of communication packaging are explored. In particular, the BSP communication structure is identified with a general form of substitution—predicate substitution. Predicate substitution provides a means of reasoning about the synchronized delivery of asynchronous communications when the immediate programming context does not explicitly refer to the variables that are to be updated (unlike traditional operations, such as the assignment $x := e$, where the names of the updated variables can be extracted from the context). Proofs of implementations of Newton's root finding method and prefix sum are used to illustrate the practical application of the proposed approach.

Efficient quantum computation using coherent states

We study universal quantum computation using optical coherent states. A teleportation scheme for a coherent-state qubit is developed and applied to gate operations. This scheme is shown to be robust to detection inefficiency.

Vibrational coherent quantum computation

A long-lived coherent state and nonlinear interaction have been experimentally demonstrated for the vibrational mode of a trapped ion. We propose an implementation of quantum computation using coherent states of the vibrational modes of trapped ions. Differently from earlier experiments, we consider a far-off resonance for the interaction between external fields and the ion in a bidimensional trap. By appropriate choices of the detunings between the external fields, the adiabatic elimination of the ionic excited level from the Hamiltonian of the system allows for beam splitting between orthogonal vibrational modes, production of coherent states, and nonlinear interactions of various kinds. In particular, this model enables the generation of the four coherent Bell states. Furthermore, all the necessary operations for quantum computation, such as preparation of qubits and one-qubit and controlled two-qubit operations, are possible. The detection of the state of a vibrational mode in a Bell state is made possible by the combination of resonant and off-resonant interactions between the ion and some external fields. We show that our read-out scheme provides highly efficient discrimination between all the four Bell states. We extend this to a quantum register composed of many individually trapped ions. In this case, operations on two remote qubits are possible through a cavity mode. We emphasize that our remote-qubit operation scheme does not require a high-quality factor resonator: the cavity field acts as a catalyst for the gate operation.

An economical route to one-way quantum computation

We assess the effects of a realistic intrinsic model for imperfections in cluster states by introducing noisy cluster states and characterizing their role in the one-way computational model. A suitable strategy to counter-affect these non-idealities is represented by the use of small clusters, stripped of any redundancy, which leads to the search for compact schemes for one-way quantum computation. In light of this, we quantitatively address the behavior of a simple four-qubit cluster which simulates a controlled-NOT under the influences of our model for decoherence. Our scheme can be particularly useful in an all-optical setup and the strategy we address can be directly applied in those, experimental situations where small cluster states can be constucted.