Optimization or sampling of arbitrary pairwise Ising models, in a quantum annealing protocol of constrained interaction topology, can be enabled by a minor-embedding procedure. The logical problem of interest is transformed to a physical (device prog
rammable) problem, where one binary variable is represented by a logical qubit consisting of multiple physical qubits. In this paper we discuss tuning of this transformation for the cases of clique, biclique, and cubic lattice problems on the D-Wave 2000Q quantum computer. We demonstrate parameter tuning protocols in spin glasses and channel communication problems, focusing on anneal duration, chain strength, and mapping from the result on physical qubits back to the logical space. Inhomogeneities in effective coupling strength arising from minor-embedding are shown to be mitigated by an efficient reweighting of programmed couplings, accounting for logical qubit topology.
Sparse Code Division Multiple Access (CDMA), a variation on the standard CDMA method in which the spreading (signature) matrix contains only a relatively small number of non-zero elements, is presented and analysed using methods of statistical physic
s. The analysis provides results on the performance of maximum likelihood decoding for sparse spreading codes in the large system limit. We present results for both cases of regular and irregular spreading matrices for the binary additive white Gaussian noise channel (BIAWGN) with a comparison to the canonical (dense) random spreading code.
Inference methods are often formulated as variational approximations: these approximations allow easy evaluation of statistics by marginalization or linear response, but these estimates can be inconsistent. We show that by introducing constraints on
covariance, one can ensure consistency of linear response with the variational parameters, and in so doing inference of marginal probability distributions is improved. For the Bethe approximation and its generalizations, improvements are achieved with simple choices of the constraints. The approximations are presented as variational frameworks; iterative procedures related to message passing are provided for finding the minima.
Sampling from a Boltzmann distribution is NP-hard and so requires heuristic approaches. Quantum annealing is one promising candidate. The failure of annealing dynamics to equilibrate on practical time scales is a well understood limitation, but does
not always prevent a heuristically useful distribution from being generated. In this paper we evaluate several methods for determining a useful operational temperature range for annealers. We show that, even where distributions deviate from the Boltzmann distribution due to ergodicity breaking, these estimates can be useful. We introduce the concepts of local and global temperatures that are captured by different estimation methods. We argue that for practical application it often makes sense to analyze annealers that are subject to post-processing in order to isolate the macroscopic distribution deviations that are a practical barrier to their application.
Approximating marginals of a graphical model is one of the fundamental problems in the theory of networks. In a recent paper a method was shown to construct a variational free energy such that the linear response estimates, and maximum entropy estima
tes (for beliefs) are in agreement, with implications for direct and inverse Ising problems[1]. In this paper we demonstrate an extension of that method, incorporating new information from the response matrix, and we recover the adaptive-TAP equations as the first order approximation[2]. The method is flexible with respect to applications of the cluster variational method, special cases of this method include Naive Mean Field (NMF) and Bethe. We demonstrate that the new framework improves estimation of marginals by orders of magnitude over standard implementations in the weak coupling limit. Beyond the weakly coupled regime we show there is an improvement in a model where the NMF and Bethe approximations are known to be poor for reasons of frustration and short loops.
This paper develops results for the next nearest neighbour Ising model on random graphs. Besides being an essential ingredient in classic models for frustrated systems, second neighbour interactions interactions arise naturally in several application
s such as the colour diversity problem and graphical games. We demonstrate ensembles of random graphs, including regular connectivity graphs, that have a periodic variation of free energy, with either the ratio of nearest to next nearest couplings, or the mean number of nearest neighbours. When the coupling ratio is integer paramagnetic phases can be found at zero temperature. This is shown to be related to the locked or unlocked nature of the interactions. For anti-ferromagnetic couplings, spin glass phases are demonstrated at low temperature. The interaction structure is formulated as a factor graph, the solution on a tree is developed. The replica symmetric and energetic one-step replica symmetry breaking solution is developed using the cavity method. We calculate within these frameworks the phase diagram and demonstrate the existence of dynamical transitions at zero temperature for cases of anti-ferromagnetic coupling on regular and inhomogeneous random graphs.
Compressed sensing of sparse sources can be improved by incorporating prior knowledge of the source. In this paper we demonstrate a method for optimal selection of weights in weighted $L_1$ norm minimization for a noiseless reconstruction model, and
show the improvements in compression that can be achieved.
Methods for understanding classical disordered spin systems with interactions conforming to some idealized graphical structure are well developed. The equilibrium properties of the Sherrington-Kirkpatrick model, which has a densely connected structur
e, have become well understood. Many features generalize to sparse Erdos-Renyi graph structures above the percolation threshold, and to Bethe lattices when appropriate boundary conditions apply. In this paper we consider spin states subject to a combination of sparse strong interactions with weak dense interactions, which we term a composite model. The equilibrium properties are examined through the replica method, with exact analysis of the high temperature paramagnetic, spin glass and ferromagnetic phases by perturbative schemes. We present results of a replica symmetric variational approximations where perturbative approaches fail at lower temperature. Results demonstrate novel reentrant behaviors from spin glass to ferromagnetic phases as temperature is lowered, including transitions from replica symmetry broken to replica symmetric phases. The nature of high temperature transitions is found to be sensitive to the connectivity profile in the sparse sub-graph, with regular connectivity a discontinuous transition from the paramagnetic to ferromagnetic phases is apparent.
Code Division Multiple Access (CDMA) in which the spreading code assignment to users contains a random element has recently become a cornerstone of CDMA research. The random element in the construction is particular attractive as it provides robustne
ss and flexibility in utilising multi-access channels, whilst not making significant sacrifices in terms of transmission power. Random codes are generated from some ensemble, here we consider the possibility of combining two standard paradigms, sparsely and densely spread codes, in a single composite code ensemble. The composite code analysis includes a replica symmetric calculation of performance in the large system limit, and investigation of finite systems through a composite belief propagation algorithm. A variety of codes are examined with a focus on the high multi-access interference regime. In both the large size limit and finite systems we demonstrate scenarios in which the composite code has typical performance exceeding sparse and dense codes at equivalent signal to noise ratio.
