A new cluster algorithm for the Baxter-Wu model

We propose a new cluster algorithm for the Baxter-Wu model that significantly reduces critical slowing down. We examine the behavior of the created clusters as we vary the temperature and then specify dynamic exponents. Comparison is made with the Metropolis algorithm and with the other existing cluster algorithm.     

On the Estimation of the Large Deviations Spectrum

We propose an estimation algorithm for large deviations spectra of measures and functions. The algorithm converges for natural examples of multifractals.     

Computing communities in complex networks using the Dirichlet processing Gaussian mixture model with spectral clustering

Community detection becomes a significant tool for the complex network analysis. The study of the community detection algorithms has received an enormous amount of attention. It is still an open question whether a highly accurate and efficient algorithm is found in most data sets. We propose the Dirichlet Processing Gaussian Mixture Model with Spectral Clustering algorithm for detecting the community structures. The combination of traditional spectral algorithm and new non-parametric Bayesian model provides high accuracy and quality. We compare the proposed algorithm with other existing community detecting algorithms using different real-world data sets and computer-generated synthetic data sets. We show that the proposed algorithm results in high modularity, and better accuracy in a wide range of networks. We find that the proposed algorithm works best for the large size of the data sets.     

Computing the topological entropy of maps

We give an algorithm for determining the topological entropy of a unimodal map of the interval given its kneading sequence. We also show that this algorithm converges exponentially in the number of letters of the kneading sequence.     

Continued Fractions and the d-Dimensional Gauss Transformation

In this paper we study a multidimensional continued fraction algorithm which is related to the Modified Jacobi–Perron algorithm considered by Podsypanin and Schweiger. We demonstrate that this algorithm has many important properties which are natural generalisations of properties of one-dimensional continued fractions. For this reason, we call the transformation associated to the algorithm the d-dimensional Gauss transformation. We construct a coordinate system for the natural extension which reveals its symmetries and allows one to give an explicit formula for the density of its invariant measure. We also discuss the ergodic properties of this invariant measure. Received: 4 February 2000 / Accepted: 23 May 2000     

Dynamic critical behavior of the worm algorithm for the Ising model

We study the dynamic critical behavior of the worm algorithm for the two- and three-dimensional Ising models, by Monte Carlo simulation. The autocorrelation functions exhibit an unusual three-time-scale behavior. As a practical matter, the worm algorithm is slightly more efficient than the Swendsen-Wang algorithm for simulating the two-point function of the three-dimensional Ising model.     

Implementation of the Deutsch-Jozsa algorithm violates nonlocal realism

The theoretical resource state for the implementation of the Deutsch-Jozsa algorithm is a multiqubit pure uncorrelated state. We show that N-qubit pure uncorrelated quantum states cannot admit rotationally invariant nonlocal realistic theories with a violation factor of 3^N. We find the violation factor 3^Nwhen the measurement setup is entire range of settings for each of the observers, that is, considering rotationally invariant nonlocal realistic theories along with the property of a correlation function in the quantum theory. The implementation of the Deutsch-Jozsa algorithm theoretically relying on N-qubit pure uncorrelated states rules out rotationally invariant nonlocal realism with a violation factor of 3^Nin an ideal case. Our analysis relies on the property of theoretical resource states for the algorithm. We cannot simulate the Deutsch-Jozsa algorithm by using rotationally invariant nonlocal realistic theories due to the property of theoretical resource states for the algorithm.     

Notes on the Algorithm for Calculating Betweenness

We investigate a common used algorithm [Phys. Rev. E 64 （2001） 016132] to calculate the betweenness centrality for all vertices. The inaccurateness of that algorithm is pointed out and a corrected algorithm, also with O（MN） time complexity, is given. In addition, the comparison of calculating results for these two algorithm aiming at the protein interaction network of yeast is shown.     

An algorithm for calculating the chemical potential in associating and reacting fluids

We present a Monte Carlo algorithm to determine the chemical potential of associating and reacting fluids. The algorithm is based on the fact that the chemical potential of a component is the same in the monomer (unbonded) state as in any bonded state. We demonstrate that the chemical potential of the unbonded specie can be calculated at relatively low cost and with high accuracy. The algorithm is applicable to both homogeneous as well as inhomogeneous systems. We compare the results of the presented algorithm against the findings of Widom's single stage particle insertion method for four commonly encountered inhomogeneous systems of associating fluids in phase equilibria studies. The constancy of the chemical potential throughout an inhomogeneous system under equilibrium is used as an independent test of the algorithm. The uncertainty in chemical potential values over the system for the cases studied was on an average 30 times smaller in the new algorithm, with at least 5 times fewer insertions than in the traditional Widom's method.     

Metaheuristic Algorithms Based on Compromise Programming for the Multi-Objective Urban Shipment Problem

The Vehicle Routing Problem (VRP) and its variants are found in many fields, especially logistics. In this study, we introduced an adaptive method to a complex VRP. It combines multi-objective optimization and several forms of VRPs with practical requirements for an urban shipment system. The optimizer needs to consider terrain and traffic conditions. The proposed model also considers customers’ expectations and shipper considerations as goals, and a common goal such as transportation cost. We offered compromise programming to approach the multi-objective problem by decomposing the original multi-objective problem into a minimized distance-based problem. We designed a hybrid version of the genetic algorithm with the local search algorithm to solve the proposed problem. We evaluated the effectiveness of the proposed algorithm with the Tabu Search algorithm and the original genetic algorithm on the tested dataset. The results show that our method is an effective decision-making tool for the multi-objective VRP and an effective solver for the new variation of VRP.     

Size dependence of the minimum excitation gap in the quantum adiabatic algorithm

We study the typical (median) value of the minimum gap in the quantum version of the exact cover problem using quantum Monte Carlo simulations, in order to understand the complexity of the quantum adiabatic algorithm for much larger sizes than before. For a range of sizes N< or =128, where the classical Davis-Putnam algorithm shows exponential median complexity, the quantum adiabatic algorithm shows polynomial median complexity. The bottleneck of the algorithm is an isolated avoided-crossing point of a Landau-Zener type (collision between the two lowest energy levels only).     

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.     

The quadratic speedup in Grover's search algorithm from the entanglement perspective

We show that Grover's algorithm can be described as an iterative change of the bipartite entanglement, which leads to a necessary and sufficient condition for quadratic speedup. This allows us to reestablish, from the entanglement perspective, that Grover's search algorithm is the only optimal pure state search algorithm.     

虚拟社区网络的演化过程研究

模拟了虚拟社区网络的演化过程并研究其拓扑结构.发现虚拟社区网络在演化过程中,节点的加入、边的加入、网络中度分布、节点的度与其加入网络时间的关系、平均度随时间的变化等方面与传统的无标度网络有所不符.根据国内某论坛的实际网络数据统计与分析,提出了虚拟社区网络的演化机理——虚拟社区网络构造算法.仿真结果表明,模拟以互联网论坛为代表的虚拟社区网络时,该模型能够得到与真实网络相符的特性. 关键词： 复杂网络 虚拟社区 无标度网络     

A Time Domain Algorithm on the Reconstruction of Rough Surfaces

We consider the inverse scattering problem of a perfectly conducting one-dimensional rough surface in the case that the incident field is unnecessary to be time harmonic. Based on our previous investigation of the frequency domain algorithm, a new time domain algorithm is proposed, in which we approximate the incident pulse by a finite sum of time harmonic fields and then apply the frequency domain algorithm for time harmonic waves. Numerical experiments indicate that the time domain algorithm shows great accuracy of reconstruction of the surface profile and yields significant improvement than the frequency domain algorithm.     

A Parallel Quantum Algorithm for the Satisfiability Problem

In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.     

Grover量子搜索算法及改进

简单地介绍了量子搜索算法中的相位匹配条件、 改进的成功率为100%的量子搜索算法和量子搜索算法中的主要误差等. We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.     

Accelerating dynamical-fermion computations using the rational hybrid Monte Carlo algorithm with multiple pseudofermion fields

There has been much recent progress in the understanding and reduction of the computational cost of the hybrid Monte Carlo algorithm for lattice QCD as the quark mass parameter is reduced. In this letter we present a new solution to this problem, where we represent the fermionic determinant using n pseudofermion fields, each with an nth root kernel. We implement this within the framework of the rational hybrid Monte Carlo algorithm. We compare this algorithm with other recent methods in this area and find it is competitive with them.     

算法对混沌体系逃逸率的影响

以Hénon-Heiles体系为例，研究算法对混沌体系运动轨道和逃逸率计算结果的影响.比较了新发现的四阶辛算法和一种非辛的高阶算法得到的结果.发现两种算法给出的轨迹之间的距离随时间增大，增加的速度可以作为体系相空间混沌的度量.通过跟踪大数量的粒子轨迹，提取出了逃逸率随体系能量的变化.发现由两种算法得到的逃逸率相互符合得很好. 关键词： 逃逸率 Hénon-Heiles体系 辛算法