Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSize dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
377
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 (QAA) for much larger sizes than before. For a range of sizes, N <= 128, where the classical Davis-Putnam algorithm shows exponential median complexity, the QAA 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).
rate research
Read More
For the 2D Ising model, we analyzed dependences of thermodynamic characteristics on number of spins by means of computer simulations. We compared experimental data obtained using the Fisher-Kasteleyn algorithm on a square lattice with $N=l{times}l$ spins and the asymptotic Onsager solution ($Ntoinfty$). We derived empirical expressions for critical parameters as functions of $N$ and generalized the Onsager solution on the case of a finite-size lattice. Our analytical expressions for the free energy and its derivatives (the internal energy, the energy dispersion and the heat capacity) describe accurately the results of computer simulations. We showed that when $N$ increased the heat capacity in the critical point increased as $lnN$. We specified restrictions on the accuracy of the critical temperature due to finite size of our system. Also in the finite-dimensional case, we obtained expressions describing temperature dependences of the magnetization and the correlation length. They are in a good qualitative agreement with the results of computer simulations by means of the dynamic Metropolis Monte Carlo method.
We study the quantum version of the random $K$-Satisfiability problem in the presence of the external magnetic field $Gamma$ applied in the transverse direction. We derive the replica-symmetric free energy functional within static approximation and the saddle-point equation for the order parameter: the distribution $P[h(m)]$ of functions of magnetizations. The order parameter is interpreted as the histogram of probability distributions of individual magnetizations. In the limit of zero temperature and small transverse fields, to leading order in $Gamma$ magnetizations $m approx 0$ become relevant in addition to purely classical values of $m approx pm 1$. Self-consistency equations for the order parameter are solved numerically using Quasi Monte Carlo method for K=3. It is shown that for an arbitrarily small $Gamma$ quantum fluctuations destroy the phase transition present in the classical limit $Gamma=0$, replacing it with a smooth crossover transition. The implications of this result with respect to the expected performance of quantum optimization algorithms via adiabatic evolution are discussed. The replica-symmetric solution of the classical random $K$-Satisfiability problem is briefly revisited. It is shown that the phase transition at T=0 predicted by the replica-symmetric theory is of continuous type with atypical critical exponents.
Maximum entropy models provide the least constrained probability distributions that reproduce statistical properties of experimental datasets. In this work we characterize the learning dynamics that maximizes the log-likelihood in the case of large but finite datasets. We first show how the steepest descent dynamics is not optimal as it is slowed down by the inhomogeneous curvature of the model parameters space. We then provide a way for rectifying this space which relies only on dataset properties and does not require large computational efforts. We conclude by solving the long-time limit of the parameters dynamics including the randomness generated by the systematic use of Gibbs sampling. In this stochastic framework, rather than converging to a fixed point, the dynamics reaches a stationary distribution, which for the rectified dynamics reproduces the posterior distribution of the parameters. We sum up all these insights in a rectified Data-Driven algorithm that is fast and by sampling from the parameters posterior avoids both under- and over-fitting along all the directions of the parameters space. Through the learning of pairwise Ising models from the recording of a large population of retina neurons, we show how our algorithm outperforms the steepest descent method.
A quantum-thermal annealing method using a cluster-flip algorithm is studied in the two-dimensional spin-glass model. The temperature (T) and the transverse field (Gamma) are decreased simultaneously with the same rate along a linear path on the T-Gamma plane. We found that the additional pulse of the transverse field to the frozen local spins produces a good approximate solution with a low computational cost.
A complete understanding of real networks requires us to understand the consequences of the uneven interaction strengths between a systems components. Here we use the minimum spanning tree (MST) to explore the effect of weight assignment and network topology on the organization of complex networks. We find that if the weight distribution is correlated with the network topology, the MSTs are either scale-free or exponential. In contrast, when the correlations between weights and topology are absent, the MST degree distribution is a power-law and independent of the weight distribution. These results offer a systematic way to explore the impact of weak links on the structure and integrity of complex networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
