Session Q38: Focus Session: Ground State Quantum Computing and Quantum Annealing

The Space-Time Circuit-to-Hamiltonian Construction and Its Applications

We discuss how the dynamics of a D-dimensional quantum circuit can be captured in the ground-state of a D$+$1-dimensional space-time Hamiltonian. The action of this Hamiltonian restricted to space-like surfaces (as given by the causal structure of the quantum circuit) is again D-dimensional and fully captures the interaction structure of the original quantum circuit. We show how one can use this construction for D$=$1 to do universal adiabatic computation using a 2D interacting particle Hamiltonian.   

Dimensionality reduction for adiabatic quantum optimizer in presence of local disorder

Adiabatic quantum optimization (AQO) is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of such gap is strongly limited by the exponential growth in dimensionality of quantum systems. Although many special-purpose methods have been devised to reduce the effective dimensionality of the Hilbert space, they are strongly limited to particular classes of problems with evident symmetries. Here, we propose and implement a reduction method that does not rely on any explicit symmetry and which requires, under certain but quite general conditions, only a polynomial amount of classical resources. A natural and important application is the analysis of AQO in presence of local disorder. In this respect, we show that AQO, even when affected by random noise, can still be faster than any classical algorithm.   

Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities

Recent tests performed on the D-Wave Two quantum annealer reveal no clear evidence of speedup over conventional technologies. Here, we present results from classical parallel-tempering Monte Carlo simulations of the archetypal benchmark problem, an Ising spin glass, on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case fidelity, i.e., the probability that the ground-state configuration is affected by random fields and random bond fluctuations found on the chip. We compute upper-bound success probabilities for different instance classes based on these simple error models and present strategies on how to develop robust and hard benchmark instances.   

Role of Classical Hardness for Quantum Annealers

The D-Wave Two chip presumably exploits quantum annealing effects to solve optimization problems. Whether D-wave's quantum annealer is capable of achieving real speedup over classical thermal annealers is a matter of investigation. In this context, specifically of importance is the question of how well quantum annealers perform on instances with rugged free-energy landscapes for which simulated annealing methods are expected to fail. I will describe attempts to identify very hard D-Wave-specific instances exhibiting ``temperature chaos'' by means of state-of-the-art methods (multi spin coding, parallel tempering simulations and stochastic time-series analysis), and present results pertaining to the performance of classical algorithms and the D-wave Two chip on these.   

Benchmarking using Frustrated Ising Problems with Planted Solutions

We introduce a method for generating families of benchmark problems that have a certain degree of tunable ``hardness,'' achieved by adjusting the amount of frustration. We construct such frustrated problems around ``planted solutions,'' representing a known ground state configuration. We construct such problems on the Chimera graph and use them to benchmark various optimization algorithms: simulated annealing (SA), simulated quantum annealing (SQA), the Shin-Smolin-Smith-Vazirani thermal rotor model (SSSV), and the Hamze-Freitas-Selby (HFS) algorithm, as well as the D-Wave device (DW2). We observe a universal hardness peak for all methods, and we observe that the optimal time for the numerical methods scales exponentially with the problem size.   

Annealing of Embedded Spin Glasses

We discuss recent results on thermal and quantum annealing of random spin glasses on fully-connected graphs and on fully-connected bipartite graphs. After the description of the embedding of their classical Hamiltonian onto Chimera graphs, we discuss what are the optimal embedding parameters, in relation with the signatures of the quantum phase transitions occurring during the annealing. Finally, we compare numerical simulations and analytical expectations for both the embedded spin glass models with results on the non-embedded models and with runs on D-Wave Machine installed at NASA Ames.   

Quantum annealing of a semiclassical spin chain with defects

We consider an Ising chain of ferromagnetically coupled large spins in a varying transverse magnetic field $H\equiv H_x$. The analysis is semiclassical. When the transverse field is strong, the energy spectrum has a gap. Once this gap goes to zero with decreasing $H$, for $H=H_c$ there is formed a Bogoliubov-type spatially uniform ``condensate", where the spin projections on the $z$-axis are $\propto (H_c-H)^{1/2}$. This opens a gap for excitations $\propto H_c-H$. We then consider a point defect that corresponds to the change $\delta J_n$ in the coupling constant between $n$ and $n+1$ spins. For $\delta J_n>0$, there emerges a pair of localized excitations for large $H$. As $H$ decreases, for some $\delta J_n$-dependent $H>H_c$ there is formed a local cloud of spins with nonzero $z$-component around the defect. It grows with further decreasing $H$. Remote defects interact very weakly. For small but nonzero temperatures, different defects should be able to align in the opposite directions, leading to nucleation of kinks between them. We study the evolution of the system as $H$ decreases, the possibility of forming kinks, kink tunneling, and the ultimate approach of the system to the ground state. We also study the case of antiferromagnetic defects.   

Investigations of a D-Wave Two: Ground States of Random Spanning Trees

The performance of a 496 qubit D-Wave Two quantum computer was investigated for two problems. The chip has a Chimera interaction graph G, an 8x8 lattice of clusters of 8 qubits. Problem input consists of values for the fields $h_j$ and for the two-qubit interactions $J_{i,j}$ of an Ising spin-glass problem formulated on G. Output is returned in terms of a spin configuration $\{s_j\}$, with $s_j$$=$$\pm 1$. We investigated spanning tree problems. A tree is a connected, undirected subgraph of G that contains no cycles, and a spanning tree is a tree which includes all of the vertices of G. We generated random spanning trees (RSTs), uniformly distributed over all spanning trees of G. In the first study, 100 RSTs with random $J_{i,j}$$\in$$\{-1,1\}$ and $h_j=0$ were generated on the full 8x8 graph G of the chip. Each RST problem was solved up to 100 times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs G', with dimensions ranging from 2x2 to 7x7. In the second study, the ground state was randomly chosen to be $s_j$$=$$\pm 1$, the $J_{i,j}$ and $h_j$ strengths were calculated from a quadratic Hamiltonian that had the given ground state, and the probability that the D-Wave Two found the ground state was measured.   

Reexamining classical and quantum models for the D-Wave One processor

We revisit the evidence for quantum annealing in the D-Wave One device (DW1) based on the study of random Ising instances. We consider measures that account for ground state degeneracy and the distributions of excited states, and present evidence [1] that for these new measures neither SQA nor the classical rotor model correlate perfectly with the DW1 experiments, despite both models correlating very well with the DW1 ground state success probabilities[2,3]. We thus provide evidence that SQA and the classical rotor model, both of which are classically efficient algorithms, do not satisfactorily explain all the DW1 data. \\[4pt] [1] T. Albash, T. F. R{\o}nnow, M. Troyer, and D. A. Lidar, arXiv:1409.3827. \\[0pt] [2] S. Boixo, T.F. R{\o}nnow, S.V. Isakov, Z. Wang, D. Wecker, D.A. Lidar, J.M. Martinis, M. Troyer, Nat. Phys. 10(3), 218 (2014).\\[0pt] [3] S. W. Shin, G. Smith, J. A. Smolin, and U. Vazirani, arXiv:1401.7087 (2014).   

Optimal quantum annealing in p-spin model

In this work we are looking to understand the physical mechanisms of quantum speedup in quantum annealing devices. We consider a simplified Hamiltonian that can be addressed analytically using a semiclassical approximation. The Hamiltonian models a typical potential barrier that can trap the system in a metastable state and thus prevent it from reaching the ground state. This situation is common in complex optimization problems such as a spin glass. The model we consider consists of Ising spins forming a fully connected graph with interaction energy proportional to a product of p individual spin operators (p=2 would correspond to the pair interaction in, for example, a ferromagnet). At p $>$ 2 this model demonstrates 1st order phase transition associated with exponential scaling of the quantum annealing computation time with the system size. We analyze the characteristics of the potential barrier that determine the efficiency of quantum annealing. We also identify the optimal regime for quantum annealing.   

Isothermal quantum annealing of the 1D transverse Ising chain

We present a quantum annealing strategy to solve optimization problems that relies on the effect of the external environment on the quantum system (isothermal protocol). We define the isothermal complexity as the scaling of the longest instantaneous relaxation time with the number of qubits in the region after the critical point where the first excitation gap equals to the temperature. We calculate this complexity for the case of 1D transverse field Ising chain coupled to the bosonic environment. We show that the quantum annealing complexity bottleneck is determined by the quantum diffusion limited recombination of the fermions that represent system excitations. We present the analytical results as well as numerical study of the system dynamics and annealing complexity.   

Computational Role of Collective Tunneling in a Quantum Annealer

We show that quantum resources in the D-Wave Two processor enhance the probability to reach the global minimum of an optimization problem. We implemented a series of structural primitives on the device governed by non-convex optimization landscapes consisting of just one global and one false local minima. The quantum adiabatic evolution path over product states connects the initial global minimum with the final false minimum. The final global minimum can only be reached by traversing an energy barrier. Experimentally we found that the D-Wave Two quantum annealer returns the solution that minimizes the energy with consistently higher probability than physically plausible models of the hardware that only employ product states and thermal activation over the barrier and do not allow for multiqubit tunneling transitions. On the contrary open system quantum mechanical models are in very close correspondence with the hardware data without using any fitting parameters. We additionally performed a series of experiments in which we varied the temperature of the chip. We find that the observed correlation between the temperature and success probability is consistent only with quantum models. We also demonstrate that the success probabilities of path integral Monte Carlo are consistently lo   

Collective disispative tunneling during quantum annealing on D-Wave II device

We develop theory based on NIBA Quantum Master Equation to describe the multiqubit tunneling in the evolution of a programmable quantum annealer. We describe D-Wave II performance in the non-convex problems realized by frustrated networks of qubit clusters with strong intra-cluster coupling. We show that the collective effect of the environment is suppressed near the avoided crossing leading to coherent tunneling in that region. In a later stage of the annealing z-magnetizations of qubit clusters increase steeply as a manifestation of the spontaneous symmetry breaking giving rise to a substantial polaronic effect. Transition to the final solution state proceeds via tunneling of one of the qubit clusters as a whole, accompanied by the reorganization of the environmental degrees of freedom and absorption of the residual energy from the qubit system. Transition rate decreases exponentially fast with time after avoided crossing leading to the freezing of the portion of population in the local minimum. We used noise parameters from the single qubit MRT experiments taken on the same device. Model predictions for multiqubit quantum annealing on the above problems are in a very close correspondence with the data collected on D-Wave II device without using any fitting parameters.   

Optimising simulated quantum annealing, simulated annealing and a mean-field algorithm to find ground states of Ising spin glasses

We report on benchmarks of finding the ground states of Ising spin glasses on chimera graphs using simulated annealing, simulated quantum annealing and a mean-field quantum annealing algorithm. We analyze the performance of these algorithms by calculating the empirical time-to-solution distribution function and extrapolating their tails, which describe the hard instances. All algorithms show an increasing fat-tail with larger system size, and therefore the average time-to-solution is dominated by the run-times of the hard instances. These tails can be significantly reduced by optimizing the annealing time and temperature. Especially the hard instances of simulated quantum annealing are solved much faster by using a shorter annealing time or higher temperature.