NASA - National Aeronautics and Space Administration

Quantum Adiabatic Evolution Algorithms for NP-Hard Problems and Quantum Spin Glasses

Phase transitions and Computational Complexity

One of the central open questions in the field of quantum computing is that of an existence of an efficient quantum algorithms for solving classically intractable instances of an optimization problem. Our project is devoted to the theoretical analysis of performance of quantum adiabatic evolution algorithm (QAA) proposed by Farhi and coworkers for NP-hard optimization problems. The algorithm is similar to simulated annealing but instead of thermal cooling the system at zero temperature is subjected to external magnetic field of slowly decreasing magnitude. Adiabatic theorem predicts that the system will remain in its ground state as the magnetic field is changed provided that the rate of change is sufficiently small.

The performance of quantum adiabatic algorithm can be studied empirically by simulating it on classical computer or performing experiments with real systems that implement certain types of classically intractable hard optimization problems. Because worst ­case complexity of QAA for the hardest constraint satisfaction problems is likely to be exponential it is of fundamental theoretical and practical interest to address the question if there is a large set of instances of the NP -hard optimization problem that are intractable on classical computer but solvable on quantum computer via QAA.

This problem directly related to studying a typical complexity of QAA and compare it with typical complexity of classical computation for the same set of instances. We address this problem by studying analytically the performance of QAA for randomly generated instances of Constraint Satisfaction problems that lie at the heart of theory of NP-completeness and can be formulated using an ensemble of random “hypergraphs”. Many properties of randomly generated instances almost surely (i.e. with probability that tends to 1) depend only on the ratio of the number of constraints to the number of variables. One such property is satisfiability (can all constraints be satisfied), the probability of which drops sharply from 1 to 0 when as the constraint ­to ­variable ratio exceeds some threshold. Many classical algorithms exhibit a threshold behavior as well. In satisfiable phase there is a critical threshold, below which solution can be found in linear time, and exponentially long above the threshold.

A measure of complexity of the problem is the logarithm of the time required to find a solution (divided by N the number of variables) as shown in the figure below.

      - Log of median runtime scaled by N T =aexp(-cN)

      - Proportion of satisfiable problem instances

Recent work on properties of random KSAT problem (M Mezard, G Parisi, R Zecchina, Science 2002) produced phase diagram with roughly 3 phases: replicasymmetric (RS) satisfiable and replica symmetrybroken (RSB), statisfiable and unsatisfiable. RSB phase corresponds to exponentially large number of clusters of solutions separated by high barriers as shown in figure to the left.

Replica method for the analysis of dilute ­infinite range quantum spin problems

We use replica method to study properties of the phase transition and critical behavior in quantum random K­ SAT problem that will shed the light on its quantum complexity properties. Earlier work has been confined exclusively to zero temperature classical problem. We developed new mathematical technique that allows for the first time to extend previous methods to include quantum effects (degree of "quantumness" is determined by the external magnetic field which controls tunneling. The limit of zero magnetic field is classical). The order parameters (aka relevant dynamical variables) that we had to introduce to describe the quantum problem reveal extreme richness of the problem.

For classical problem, the order parameter is the probability distribution of magnetizations (average values of variables in thermal equilibrium) for replica ­symmetric phase, whereas in RSB phase it is the distribution of distributions of magnetizations (fluctuations of magnetizations at each site can no longer be neglected). For quantum case, the order parameter is the distribution of distributions of magnetizations already at replica ­symmetric level. Special properties of K­SAT model allowed us to obtain the order parameter in simplified form in the limit of small magnetic fields.

Although replica ­symmetric ansatz is not always valid for zero ­temperature classical problem, it predicts phase transition between satisfiable and unsatisfiable phases with good precision [8]. We have analyzed the quantum problem at zero temperature. We have recently demonstrated that the true phase transition happens only at zero temperature and zero magnetic field that is in classical problem; in quantum regime it is replaced by a smooth crossover.

This implies the apparent lack of critical slowing down in quantum adiabatic evolution computation.

Numerical calculation of the complexity of Quantum Adiabatic Algorithm for NP-hard problems

In order to verify our theoretical findings we started a project in collaboration with Peter Young (UCSC) to study numerically the minimum gap in the quantum adiabatic evolution algorithm applied to random NP-­complete problems with unique satisfying assignment. We are using Quantum Monte Carlo simulations by computing asymptotic of a two ­time correlation function for a spin on imaginary time axis. This approach allows to understand the complexity of the quantum adiabatic algorithm for much large sizes than those accessible by direct integration of time ­dependent Schrödinger equation for a quantum spin system.

We applied this method to random Exact Cover problem with unique satisfying assignment. For a range of sizes, N < 128, where the classical Davis­Putnam algorithm shows exponential complexity, the quantum adiabatic algorithm shows polynomial 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). We currently study the modification of the Quantum Monte Carlo that will allow to study the algorithm complexity for much larger sizes N.

QMC results for the gap between the ground state and the first excited state as a function of the control parameter of quantum adiabatic evolution algorithm for one instance of Exact Cover problem (unique satisfying assignment) with N=64. The region around the minimum value of the is blown up in the inset.

A log-log plot of the median of the minimum gap obtained by QMC for instances of exact cover with a unique satisfying assignment (USA) as a function of the number of bits N up to N=128. From the satisfactory straight line fit, it is seen that the median decreases as a power law, with m = 0.73. The number of instances is 50 except for N=64 for which it is 45. The inset shows a loglinear plot. The pronounced curvature shows that the behavior is not exponential for this range of sizes, in contrast to the classical algorithms for this problem.

Download PDF