Generalization Learning in a Perceptron with Binary Synapses

We consider the generalization problem for a perceptron with binary synapses, implementing the Stochastic Belief-Propagation-Inspired (SBPI) learning algorithm which we proposed earlier, and perform a mean-field calculation to obtain a differential equation which describes the behaviour of the device in the limit of a large number of synapses N. We show that the solving time of SBPI is of order \(N\sqrt{\log N}\), while the similar, well-known clipped perceptron (CP) algorithm does not converge to a solution at all in the time frame we considered. The analysis gives some insight into the ongoing process and shows that, in this context, the SBPI algorithm is equivalent to a new, simpler algorithm, which only differs from the CP algorithm by the addition of a stochastic, unsupervised meta-plastic reinforcement process, whose rate of application must be less than \(\sqrt{2/(\pi N)}\) for the learning to be achieved effectively. The analytical results are confirmed by simulations.     

Quantum Cryptography,Quantum Communication,and Quantum Computer in a Noisy Environment

First, we study several information theories based on quantum computing in a desirable noiseless situation. (1) We present quantum key distribution based on Deutsch’s algorithm using an entangled state. (2) We discuss the fact that the Bernstein-Vazirani algorithm can be used for quantum communication including an error correction. Finally, we discuss the main result. We study the Bernstein-Vazirani algorithm in a noisy environment. The original algorithm determines a noiseless function. Here we consider the case that the function has an environmental noise. We introduce a noise term into the function f(x). So we have another noisy function g(x). The relation between them is g(x) = f(x) ± O(??). Here O(??) ? 1 is the noise term. The goal is to determine the noisy function g(x) with a success probability. The algorithm overcomes classical counterpart by a factor of N in a noisy environment.     

Efficiency of the microcanonical over-relaxation algorithm for vector spins analyzing first and second order transitions

We simulate vectorial spin systems solely with the microcanonical over-relaxation algorithm where the temperature is calculated by a formula of Nurdin and Schotte. We show that this procedure is the most efficient local algorithm besides the nonlocal cluster algorithm not only for first order transitions but also for second order ones. A comparison is made with the Metropolis, heat bath, multicanonical and the Creutzs demon algorithms. We study, using these algorithms, the frustrated J1-J2 model on a cubic lattice for XY, Heisenberg and O(4) spins. These models have a breakdown of symmetry Z3 SO(N)/SO(N-1) for the number N = 2,3,4 of spin components leading to transitions of first order. We show that they are strongly first order. Then, to test the over-relaxation update for second order transitions, we study a ferromagnet on a cubic lattice and a frustrated antiferromagnet on a stacked triangular lattice. We finally point out the advantages and the flaws of the over-relaxation procedure.     

Searches for new particles using cone and cluster jet algorithms: a comparative study

We discuss the reconstruction of the hadronic decays of heavy particles using jet algorithms. The ability to reconstruct the mass of the decaying particles is compared between a traditional cone-type algorithm and a recently proposed cluster-type algorithm. The specific examples considered are the semileptonic decays of a heavy Higgs boson at TeV, and of top quark-antiquark pairs at TeV. We find that the cluster algorithm offers considerable advantages in the former case, and a slight advantage in the latter. We briefly discuss the effects of calorimeter energy resolution, and show that a typical resolution dilutes these advantages, but does not remove them entirely.     

Adaptive sampling by information maximization

The investigation of input-output systems often requires a sophisticated choice of test inputs to make the best use of limited experimental time. Here we present an iterative algorithm that continuously adjusts an ensemble of test inputs on-line, subject to the data already acquired about the system under study. The algorithm focuses the input ensemble by maximizing the mutual information between input and output. We apply the algorithm to simulated neurophysiological experiments and show that it serves to extract the ensemble of stimuli that a given neural system "expects" as a result of its natural history.     

Direct characterization of quantum dynamics

The characterization of quantum dynamics is a fundamental and central task in quantum mechanics. This task is typically addressed by quantum process tomography (QPT). Here we present an alternative "direct characterization of quantum dynamics" (DCQD) algorithm. In contrast to all known QPT methods, this algorithm relies on error-detection techniques and does not require any quantum state tomography. We illustrate that, by construction, the DCQD algorithm can be applied to the task of obtaining partial information about quantum dynamics. Furthermore, we argue that the DCQD algorithm is experimentally implementable in a variety of prominent quantum-information processing systems, and show how it can be realized in photonic systems with present day technology.     

Flat histogram version of the pruned and enriched Rosenbluth method

In this Letter we present a flat histogram algorithm based on the pruned and enriched Rosenbluth method. This algorithm incorporates in a straightforward manner microcanonical reweighting techniques, leading to "flat histogram" sampling in the chosen parameter space. As an additional benefit, our algorithm is completely parameter free and, hence, easy to implement. We apply this algorithm to interacting self-avoiding walks, the generic lattice model of polymer collapse.     

Join- and-cut algorithm for self-avoiding walks with variable length and free endpoints

We introduce a new Monte Carlo algorithm for generating self-avoiding walks of variable length and free endpoints. The algorithm works in the unorthodox ensemble consisting of all pairs of SAWs such that the total number of stepsN _tot in the two walks is fixed. The elementary moves of the algorithm are fixed-N (e.g., pivot) moves on the individual walks, and a novel join- and-cut move that concatenates the two walks and then cuts them at a random location. We analyze the dynamic critical behavior of the new algorithm, using a combination of rigorous, heuristic, and numerical methods. In two dimensions the autocorrelation time in CPU units grows as N^1.5, and the behavior improves in higher dimensions. This algorithm allows high-precision estimation of the critical exponent.     

Intermittent dynamics of critical fluctuations

We argue that the fluctuations of the order parameter in a complex system at the critical point can be described in terms of intermittent dynamics of type I. Based on this observation we develop an algorithm to calculate the isothermal critical exponent delta for a "thermal" critical system. We apply successfully our approach to the 3D Ising model. The intermittent character of these "critical" dynamics guides to the introduction of a new exponent which extends the notion of the exponent delta to nonthermal systems.     

Finding jets and summing soft gluons: a new algorithm

We examine a new algorithm for finding jets ine ⁺ e ^– annihilation, using a jet measure based on relative transverse momentum. We perform an analytic calculation of the three-jet fraction at lowest order, and compare our result with the standard jet-finding algorithm. For soft gluons in an abelian theory it is shown that the leading double logarithms exponentiate, unlike the situation for the commonly used algorithm based on invariant mass. In QCD we find that there are leading non-abelian logarithms, and we calculate these explicitly atO( _s ² ). We discuss the modifications to the algorithm which are needed when the mass of a parton cluster is taken into account. The hope is that the new algorithm will allow an improved theoretical analysis at smaller values of the resolution parametery _T , and hence an improved fit to the experimental data.Nick Brown was tragically killed on 13th June, 1991. This paper is dedicated to his memory     

Cut-and-Permute Algorithm for Self-Avoiding Walks in the Presence of Surfaces

We present a dynamic nonlocal hybrid Monte Carlo algorithm consisting of pivot and cut-and-permute moves. The algorithm is suitable for the study of polymers in semiconfined geometries at the ordinary transition, where the pivot algorithm exhibits quasi-ergodic problems. The dynamic properties of the proposed algorithm are studied in d=3. The hybrid dynamics is ergodic and exhibits the same optimal critical behavior as the pivot algorithm in the bulk.     

A Modified Quantum Search Algorithm

We show that by adding a workspace qubit to Ahmed Younes, et al. algorithm (Younes et al. AIP Conf. Proc. 734:171, 2004, 2008), and applying newly defined partial diffusion operators on subsystems, the algorithm’s performance is improved. We consider an unstructured list of N items and M matches, 1 ≤ M ≤ N.     

Stochastic simulation of the reaction-diffusion systemA+B→inert in integer and fractal dimensions

We present a stochastic simulation of the reaction-diffusion systemA+Binert based upon the algorithm of the minimal process method. In order to overcome the well known problems of this algorithm when selecting a reaction or diffusion event according to its rate contribution we introduce the concept of logarithmic classes which accelerates the algorithm by an order of magnitude. We simulate the systemA+Binert for integer dimensionsd=1,2,3,4 and confirm the predictions of the scaling theory by Kang and Redner. We extend our simulations to fractal structures, namely the Sierpinski carpet, triangle, the Menger sponge and HLA-clusters. Again we find agreement with the scaling theory if the fractal dimensions are defined as the spectral dimension.     

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a "duality computer" and show its advantage over other algorithms.     

{\mathbb{Z}_{2}} Invariants of Topological Insulators as Geometric Obstructions

We consider a gapped periodic quantum system with time-reversal symmetry of fermionic (or odd) type, i.e. the time-reversal operator squares to \({-\mathbb{1}}\). We investigate the existence of periodic and time-reversal invariant Bloch frames in dimensions 2 and 3. In 2d, the obstruction to the existence of such a frame is shown to be encoded in a \({\mathbb{Z}_2}\)-valued topological invariant, which can be computed by a simple algorithm. We prove that the latter agrees with the Fu-Kane index. In 3d, instead, four \({\mathbb{Z}_2}\) invariants emerge from the construction, again related to the Fu-Kane-Mele indices. When no topological obstruction is present, we provide a constructive algorithm yielding explicitly a periodic and time-reversal invariant Bloch frame. The result is formulated in an abstract setting, so that it applies both to discrete models and to continuous ones.     

Measuring clock jumps using pulsar timing

In this paper,we investigate the statistical signal-processing algorithm to measure the instant local clock jump from the timing data of multiple pulsars.Our algorithm is based on the framework of Bayesian statistics.In order to make the Bayesian algorithm applicable with limited computational resources,we dedicated our efforts to the analytic marginalization of irrelevant parameters.We found that the widely used parameter for pulsar timing systematics,the"Efac"parameter,can be analytically marginalized.This reduces the Gaussian likelihood to a function very similar to the Student’s t-distribution.Our iterative method to solve the maximum likelihood estimator is also explained in the paper.Using pulsar timing data from the Yunnan Kunming 40-m radio telescope,we demonstrate the application of the method,where 80-ns level precision for the clock jump can be achieved.Such a precision is comparable to that of current commercial time transferring service using satellites.We expect that the current method could help developing the autonomous pulsar time scale.     

Accurate evolutions of orbiting black-hole binaries without excision

We present a new algorithm for evolving orbiting black-hole binaries that does not require excision or a corotating shift. Our algorithm is based on a novel technique to handle the singular puncture conformal factor. This system, based on the Baumgarte-Shapiro-Shibata-Nakamura formulation of Einstein's equations, when used with a "precollapsed" initial lapse, is nonsingular at the start of the evolution and remains nonsingular and stable provided that a good choice is made for the gauge. As a test case, we use this technique to fully evolve orbiting black-hole binaries from near the innermost stable circular orbit regime. We show fourth-order convergence of waveforms and compute the radiated gravitational energy and angular momentum from the plunge. These results are in good agreement with those predicted by the Lazarus approach.     

Inhomogeneous Relaxation in Vibrated Granular Media: Consolidation Waves

We investigate the spatial dependence of the density of vibrated granular beds, using simulations based on a hybrid Monte Carlo algorithm. We find that the initial consolidation is typically inhomogeneous, both in the presence of a constant shaking intensity and when the granular bed is subjected to "annealed shaking". We also present a theoretical model which explains such inhomogeneous relaxation in terms of a "consolidation wave", in good qualitative agreement with our simulations. Our results are also in qualitative agreement with recent experiments.     

Improved Quantum Image Filtering in the Spatial Domain

We investigate the quantum image filtering in spatial domain proposed by Yuan et al. (Int. J. Theor. Phys. 56(8), 2495–2511, 2017). Although the complexity of this algorithm is much better than the classical exhaustive algorithm, there may be a defect in it: the quantum multiplication was replaced by quantum addition. There are two shortcomings: 1) We should know exactly the value of the filter coefficients before each filtering behavior. 2) This method is only suitable for integer filter coefficients but not for decimal filter coefficients. In this paper, an improved version is proposed which takes full advantage of the quantum multiplication and can overcome these two shortcomings. The theoretical analysis indicates that the time complexity is the same as the previous algorithm. So this algorithm is also efficient.