Session C45: Adiabatic Quantum Computation and Quantum Annealing: Tunneling, Speedup and Noise Effects

Tunneling and Speedup in Permutation-Invariant Quantum Optimization Problem

Tunneling is often claimed to be the key mechanism underlying possible speedups in quantum optimization via the quantum adiabatic algorithm. Restricting ourselves to qubit-permutation invariant problems, we show that tunneling in these problems can be understood using the semi-classical potential derived from the spin-coherent path integral formalism. Using this, we show that the class of problems that fall under Reichardt's bound (1), i.e., have a constant gap and hence can be efficiently solved using the quantum adiabatic algorithm, do not exhibit tunneling in the large system-size limit. We proceed to construct problems that do not fall under Reichardt's bound but numerically have a constant gap and do exhibit tunneling. However, perhaps counter-intuitively, tunneling does not provide the most efficient mechanism for finding the solution to these problems. Instead, an evolution involving a sequence of diabatic transitions through many avoided level-crossings, involving no tunneling, is optimal and outperforms tunneling in the adiabatic regime. In yet another twist, we show that in this case, classical spin-vector dynamics is as efficient as the diabatic quantum evolution (2).\\ (1) B. W. Reichardt, in Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC ’04 (ACM, New York, NY, USA, 2004) pp. 502–510.\\ (2) S. Muthukrishnan, T. Albash, D.A. Lidar, arXiv:1505.01249.   

Understanding Quantum Tunneling through Quantum Monte Carlo Simulations

The tunneling between the two ground states of an Ising ferromagnet is a typical example of many-body tunneling processes between two local minima, as they occur during quantum annealing. Performing quantum Monte Carlo (QMC) simulations we find that the QMC tunneling rate displays the same scaling (in the exponent) with system size, as the rate of incoherent tunneling. The scaling in both cases is $O(\Delta^2)$, where $\Delta$ is the tunneling splitting. An important consequence is that QMC simulations can be used to predict the performance of a quantum annealer for tunneling through a barrier. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, we obtain a quadratic speedup for QMC, and achieve linear scaling in $\Delta$. We provide a physical understanding of these results and their range of applicability based on an instanton picture.   

Coupled Quantum Fluctuations and Quantum Annealing

We study the relative effectiveness of coupled quantum fluctuations, compared to single spin fluctuations, in the performance of quantum annealing. We focus on problem Hamiltonians resembling the the Sherrington-Kirkpatrick model of Ising spin glass and compare the effectiveness of different types of fluctuations by numerically calculating the relative success probabilities and residual energies in fully-connected spin systems. We find that for a small class of instances coupled fluctuations can provide improvement over single spin fluctuations and analyze the properties of the corresponding class. Disclaimer: This research was funded by ODNI, IARPA via MIT Lincoln Laboratory under Air Force Contract No. FA8721-05-C-0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government.   

Performance of error suppresion schemes for adiabatic quantum computation in the presence of Markovian noise

We investigate the performance of error suppression schemes for adiabatic quantum computation. Assuming a Markovian environment and using an adiabatic master equation we compare the rate of excitation from the ground subspace of the encoded Hamiltonian during the evolution to that of the unprotected Hamiltonian. For different forms of Markovian environments — such as sub-Ohmic, Ohmic and super-Ohmic — we identify the parameter thresholds for which encoding starts exhibiting its benefits.   

Coping with noise in programmable quantum annealers

Solving real-world applications with quantum annealing algorithms requires overcoming several challenges, ranging from translating the computational problem at hand to the quantum-machine language, to tuning several other parameters of the quantum algorithm that have a significant impact on performance of the device. In this talk, we discuss these challenges, strategies developed to enhance performance, and also a more efficient implementation of several applications. For example, in http://arxiv.org/abs/1503.05679 we proposed an method to measure residual systematic biases in the programmable parameters of large-scale quantum annealers. Although the method described there works from a practical point of view, a few questions were left unanswered. One of these puzzles was the observation of a broad distribution in the estimated effective qubit temperatures throughout the device . In this talk, we will present our progress in understanding these puzzles and how these new insights allow for a more effective bias correction protocol. We will present the impact of these new parameter setting and bias correction protocols in the performance of hard discrete optimization problems and in the successful implementation of quantum-assisted machine-learning algorithms.   

Does finite-temperature decoding deliver better optima for noisy Hamiltonians?

The minimization of an Ising spin-glass Hamiltonian is an NP-hard problem. Because many problems across disciplines can be mapped onto this class of Hamiltonian, novel efficient computing techniques are highly sought after. The recent development of quantum annealing machines promises to minimize these difficult problems more efficiently. However, the inherent noise found in these analog devices makes the minimization procedure difficult. While the machine might be working correctly, it might be minimizing a different Hamiltonian due to the inherent noise. This means that, in general, the ground-state configuration that correctly minimizes a noisy Hamiltonian might not minimize the noise-less Hamiltonian. Inspired by rigorous results that the energy of the noise-less ground-state configuration is equal to the expectation value of the energy of the noisy Hamiltonian at the (nonzero) Nishimori temperature [J. Phys. Soc. Jpn., 62, 40132930 (1993)], we numerically study the decoding probability of the original noise-less ground state with noisy Hamiltonians in two space dimensions, as well as the D-Wave Inc.~Chimera topology. Our results suggest that thermal fluctuations might be beneficial during the optimization process in analog quantum annealing machines.   

Estimation of effective temperatures in a quantum annealer: Towards deep learning applications

Sampling is at the core of deep learning and more general machine learning applications; an increase in its efficiency would have a significant impact across several domains. Recently, quantum annealers have been proposed as a potential candidate to speed up these tasks, but several limitations still bar them from being used effectively. One of the main limitations, and the focus of this work, is that using the device's experimentally accessible temperature as a reference for sampling purposes leads to very poor correlation with the Boltzmann distribution it is programmed to sample from. Based on quantum dynamical arguments, one can expect that if the device indeed happens to be sampling from a Boltzmann-like distribution, it will correspond to one with an instance-dependent effective temperature. Unless this unknown temperature can be unveiled, it might not be possible to effectively use a quantum annealer for Boltzmann sampling processes. In this work, we propose a strategy to overcome this challenge with a simple effective-temperature estimation algorithm. We provide a systematic study assessing the impact of the effective temperatures in the quantum-assisted training of Boltzmann machines, which can serve as a building block for deep learning architectures.   

Hard scheduling problems for early quantum annealer

We present a parameterized family of single machine scheduling problem that exhibits an easy-hard-easy phase transition. As the parameter is varied, the problem goes through a fast transition from being almost trivial to find a solution to almost always has no solution, this sharp transition accompanies a peak in computational effort. While implementing realistic-sized problems on an early quantum annealing device is still a challenge in near future, using a benchmarking problem set of small size but in a well-defined hard family, one can gain insight to a how the solving time scales for the whole family.[1] We will report quantum annealing results on this and other related problems. [1] E. G. Rieffel, D. Venturelli, B. OGorman, M. B. Do, E. M. Prystay, and V. N. Smelyanskiy, Quantum Information Processing 14, 1 (2015).   

Accurate Variational Description of Adiabatic Quantum Optimization

Adiabatic quantum optimization (AQO) is a quantum computing protocol where a system is driven by a time-dependent Hamiltonian. The initial Hamiltonian has an easily prepared ground-state and the final Hamiltonian encodes some desired optimization problem. An adiabatic time evolution then yields a solution to the optimization problem. Several challenges emerge in the theoretical description of this protocol: on one hand, the exact simulation of quantum dynamics is exponentially complex in the size of the optimization problem. On the other hand, approximate approaches such as tensor network states (TNS) are limited to small instances by the amount of entanglement that can be encoded. I will present here an extension of the time-dependent Variational Monte Carlo approach to problems in AQO. This approach is based on a general class of (Jastrow-Feenberg) entangled states, whose parameters are evolved in time according to a stochastic variational principle. We demonstrate this approach for optimization problems of the Ising spin-glass type. A very good accuracy is achieved when compared to exact time-dependent TNS on small instances. We then apply this approach to larger problems, and discuss the efficiency of the quantum annealing scheme in comparison with its classical counterpart.   

Optimizing Quantum Adiabatic Algorithm

In quantum adiabatic algorithm, as the adiabatic parameter $s(t)$ changes slowly from zero to one with finite rate, a transition to excited states inevitably occurs and this induces an intrinsic computational error. We show that this computational error depends not only on the total computation time $T$ but also on the time derivatives of the adiabatic parameter $s(t)$ at the beginning and the end of evolution. Previous work (Phys. Rev. A 82, 052305) also suggested this result. With six typical paths, we systematically demonstrate how to optimally design an adiabatic path to reduce the computational errors. Our method has a clear physical picture and also explains the pattern of computational error. In this paper we focus on quantum adiabatic search algorithm although our results are general.   

Learning quantum annealing

We propose and develop a new quantum algorithm, whereby a quantum system can learn to anneal to a desired ground state. We demonstrate successful learning of entanglement for a two-qubit system, then bootstrap to larger systems. We also show that the method is robust to noise and decoherence.   

Josephson Circuits as Vector Quantum Spins

While superconducting circuits based on Josephson junction technology can be engineered to represent spins in the quantum transverse-field Ising model, no circuit architecture to date has succeeded in emulating the vector quantum spin models of interest for next-generation quantum annealers and quantum simulators. Here, we present novel Josephson circuits which may provide these capabilities. We discuss our rigorous quantum-mechanical simulations of these circuits, as well as the larger architectures they may enable. This research was funded by the Office of the Director of National Intelligence (ODNI) and the Intelligence Advanced Research Projects Activity (IARPA) under Air Force Contract No. FA8721-05-C-0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government.   

Distortion of a reduced equilibrium density matrix

We study a system coupled to external degrees of freedom, called bath, where we assume that the total system, consisting of system and bath is in equilibrium. An expansion in the coupling between system and bath leads to a general form of the reduced density matrix of the system as a function of the bath selfenergy. The coupling to the bath results in a renormalization of the energies of the system and in a change of the eigenbasis. We study the influence of bosonic degrees of freedom on the state of a six qubit system similar to the eight qubit unit cell of a quantum annealing processor examined by Lanting et al.\footnote{T. Lanting et al., Phys. Rev. X 4, 021041 (2014).}.   

Quantum annealing via quantum diffusion mediated by environment

We show that quantum diffusion near the quantum critical point can provide an efficient mechanism of open-system quantum annealing. The analysis refers to an Ising spin chain in a slowly decreasing transverse field coupled to bosonic heat bath. The diffusion facilitates recombination of collective (multi-spin) excitations in the chain. It sharply slows down as the system moves away from the quantum critical region, leading to significant spatial fluctuations even in the absence of disorder. The excitation density reached by then non-monotonically depends on the annealing rate. We find that obtaining an approximate solution via diffusion-mediated quantum annealing can be faster than via classical Glauber dynamics or the closed-system Kibble-Zurek mechanism. We study the scaling of the excitation density with the temperature and coupling constant to environment.