We study the interplay between quantum annealing parameters in embedded problems, providing both deeper insights into the physics of these devices and pragmatic recommendations to improve performance on optimization problems. We choose as our test case the class of bounded-degree minimum-spanning-tree problems. Through runs on a D-Wave quantum annealer, we demonstrate that pausing in a specific time window in the anneal provides improvement in the probability of success and in the time to solution for these problems. The time window is consistent across problem instances and its location is within the region suggested by prior theory and seen in previous results on native problems. An approach to enable gauge transformations for problems with the qubit coupling strength in an asymmetric range is presented and shown to significantly improve performance. We also confirm that the optimal pause location exhibits a shift with the magnitude of the ferromagnetic coupling, , between physical qubits representing the same logical one. We extend the theoretical picture for pausing and thermalization in quantum annealing to the embedded case. This picture, along with perturbation-theory analysis and exact numerical results on small problems, confirms that the effective pause region moves earlier in the anneal as increases. It also suggests why pausing, while still providing significant benefit, has a less pronounced effect on embedded problems.
We investigate the occurrence of many-body localization (MBL) on a spin-1/2 transverse-field Ising model defined on a Chimera connectivity graph with random exchange interactions and longitudinal fields. We observe a transition from an ergodic phase to a nonthermal phase for individual energy eigenstates induced by a critical disorder strength for the Ising parameters. Our result follows from the analysis of both the mean half-system block entanglement and the energy-level statistics. We identify the critical point associated with this transition using the maximum variance of the block entanglement over the disorder ensemble as a function of the disorder strength. The calculated energy density phase diagram shows the existence of a mobility edge in the energy spectrum. In terms of the energy-level statistics, the system changes from the Gaussian orthogonal ensemble for weak disorder to a Poisson distribution limit for strong randomness, which implies localization behavior. We then realize the time-independent disordered Ising Hamiltonian experimentally using a reverse annealing quench-pause-quench protocol on a -wave 2000Q programmable quantum annealer. We characterize the transition from the thermal to the localized phase through magnetization measurements at the end of the annealing dynamics, and the results are compatible with our theoretical prediction for the critical point. However, the same behavior can be reproduced using a classical spin-vector Monte Carlo simulation, which suggests that genuine quantum signatures of the phase transition remain out of reach using this experimental platform and protocol.
Prior work showed the efficacy of pausing midanneal: such a pause improved the probability of success by orders of magnitude in a class of native problem instances and improved the time to solution in a class of embedded problem instances. A physics-based picture provides qualitative suggestions for where pausing midanneal is effective, for the interplay between annealing schedule parameters and other annealing properties and parameters such as embedding size and strength of the ferromagnetic coupling , and for the conditions under which pausing can improve the time to solution. Here, through demonstrations on an updated annealing architecture that has higher connectivity than previous annealers, and on multiple embedded problem classes, we are able to confirm various aspects of this picture. We demonstrate the robustness of the optimal pause parameters across platforms and problem classes, explore how to set to optimize performance in different scenarios, and provide empirical evidence that short pauses trump longer overall annealing times in time to solution. We also identify the number of different coefficients in a problem as a predictor of problem hardness, and explore its interplay with the optimal and embedding size. Based on these results we are able to present qualitative guidelines for parameter setting in quantum annealers.
We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses rounds of communication and messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by notation, revealing that advances are needed to render both the quantum and classical algorithms practical.
We demonstrate experimentally the ability of a quantum annealer to distinguish between sets of nonisomorphic graphs that share the same classical Ising spectrum. Utilizing the pause-and-quench features recently introduced into D-Wave quantum annealing processors, which allow the user to probe the quantum Hamiltonian realized in the middle of an anneal, we show that obtaining thermal averages of diagonal observables of “classically indistinguishable” nonisomorphic graphs encoded into transverse-field Ising Hamiltonians enable their discrimination. We discuss the significance of our results in the context of the graph isomorphism problem.