We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians. Our method involves expanding the interaction-picture Hamiltonian as a sum of generalized permutations, which leads to an integral-free Dyson series of the ti
me-evolution operator. Under this representation, we perform a quantum simulation for the time-evolution operator by means of the linear combination of unitaries technique. We optimize the time steps of the evolution based on the Hamiltonians dynamical characteristics, leading to a gate count that scales with an $L^1$-norm-like scaling with respect only to the norm of the interaction Hamiltonian, rather than that of the total Hamiltonian. We demonstrate that the cost of the algorithm is independent of the Hamiltonians frequencies, implying its advantage for systems with highly oscillating components, and for time-decaying systems the cost does not scale with the total evolution time asymptotically. In addition, our algorithm retains the near optimal $log(1/epsilon)/loglog(1/epsilon)$ scaling with simulation error $epsilon$.
With current semiconductor technology reaching its physical limits, special-purpose hardware has emerged as an option to tackle specific computing-intensive challenges. Optimization in the form of solving Quadratic Unconstrained Binary Optimization (
QUBO) problems, or equivalently Ising spin glasses, has been the focus of several new dedicated hardware platforms. These platforms come in many different flavors, from highly-efficient hardware implementations on digital-logic of established algorithms to proposals of analog hardware implementing new algorithms. In this work, we use a mapping of a specific class of linear equations whose solutions can be found efficiently, to a hard constraint satisfaction problem (3-regular 3-XORSAT, or an Ising spin glass) with a golf-course shaped energy landscape, to benchmark several of these different approaches. We perform a scaling and prefactor analysis of the performance of Fujitsus Digital Annealer Unit (DAU), the D-Wave Advantage quantum annealer, a Virtual MemComputing Machine, Toshibas Simulated Bifurcation Machine (SBM), the SATonGPU algorithm from the JANUS collaboration, and our implementation of parallel tempering. We identify the SATonGPU and DAU as currently having the smallest scaling exponent for this benchmark, with SATonGPU having a small scaling advantage and in addition having by far the smallest prefactor thanks to its use of massive parallelism. Our work provides an objective assessment and a snapshot of the promise and limitations of dedicated optimization hardware relative to a particular class of optimization problems.
Although stoquastic Hamiltonians are known to be simulable via sign-problem-free quantum Monte Carlo (QMC) techniques, the non-stoquasticity of a Hamiltonian does not necessarily imply the existence of a QMC sign problem. We give a sufficient and nec
essary condition for the QMC-simulability of Hamiltonians in a fixed basis in terms of geometric phases associated with the chordless cycles of the weighted graphs whose adjacency matrices are the Hamiltonians. We use our findings to provide a construction for non-stoquastic, yet sign-problem-free and hence QMC-simulable, quantum many-body models. We also demonstrate why the simulation of truly sign-problematic models using the QMC weights of the stoquasticized Hamiltonian is generally sub-optimal. We offer a superior alternative.
The Dyson series is an infinite sum of multi-dimensional time-ordered integrals, which serves as a formal representation of the quantum time evolution operator in the interaction picture. Using the mathematical tool of divided differences, we introdu
ce an alternative representation for the series that is entirely free from both time ordering and integrals. In this new formalism, the Dyson expansion is given as a sum of efficiently-computable divided differences of the exponential function, considerably simplifying the calculation of the Dyson expansion terms, while also allowing for time-dependent perturbation calculations to be performed directly in the Schr{o}dinger picture. We showcase the utility of this novel representation by studying a number of use cases. We also discuss several immediate applications.
We propose an efficient quantum algorithm for simulating the dynamics of general Hamiltonian systems. Our technique is based on a power series expansion of the time-evolution operator in its off-diagonal terms. The expansion decouples the dynamics du
e to the diagonal component of the Hamiltonian from the dynamics generated by its off-diagonal part, which we encode using the linear combination of unitaries technique. Our method has an optimal dependence on the desired precision and, as we illustrate, generally requires considerably fewer resources than the current state-of-the-art. We provide an analysis of resource costs for several sample models.
Quantum fluctuations driven by non-stoquastic Hamiltonians have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with adiabatic optimization. We introduce a transformation that maps every
non-stoquastic adiabatic path ending in a classical Hamiltonian to a corresponding stoquastic adiabatic path by appropriately adjusting the phase of each matrix entry in the computational basis. We compare the spectral gaps of these adiabatic paths and find both theoretically and numerically that the paths based on non-stoquastic Hamiltonians have generically smaller spectral gaps between the ground and first excited states, suggesting they are less useful than stoquastic Hamiltonians for quantum adiabatic optimization. These results apply to any adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal in the computational basis.
Motivated by two recent experiments in which thermal properties of complex many-body systems were successfully reproduced on a commercially available quantum annealer, we examine the extent to which quantum annealing hardware can reliably sample from
the thermal state associated with a target quantum Hamiltonian. We address this question by studying the thermal properties of the canonical one-dimensional transverse-field Ising model on a D-Wave 2000Q quantum annealing processor. We find that the quantum processor fails to produce the correct expectation values predicted by Quantum Monte Carlo. Comparing to master equation simulations, we find that this discrepancy is best explained by how the measurements at finite transverse fields are enacted on the device. Specifically, measurements at finite transverse field require the system to be quenched from the target Hamiltonian to a Hamiltonian with negligible transverse field, and this quench is too slow. We elaborate on how the limitations imposed by such hardware make it an unlikely candidate for studying the thermal properties of generic quantum many-body systems.
The sign problem is a key challenge in computational physics, encapsulating our inability to properly understand many important quantum many-body phenomena in physics, chemistry and the material sciences. Despite its centrality, the circumstances und
er which the problem arises or can be resolved as well as its interplay with the related notion of `non-stoquasticity are often not very well understood. In this study, we make an attempt to elucidate the circumstances under which the sign problem emerges and to clear up some of the confusion surrounding this intricate computational phenomenon. To that aim, we make use of the recently introduced off-diagonal series expansion quantum Monte Carlo scheme with which we analyze in detail a number of examples that capture the essence of our results.
We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal
terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.
Quantum annealing has the potential to provide a speedup over classical algorithms in solving optimization problems. Just as for any other quantum device, suppressing Hamiltonian control errors will be necessary before quantum annealers can achieve s
peedups. Such analog control errors are known to lead to $J$-chaos, wherein the probability of obtaining the optimal solution, encoded as the ground state of the intended Hamiltonian, varies widely depending on the control error. Here, we show that $J$-chaos causes a catastrophic failure of quantum annealing, in that the scaling of the time-to-solution metric becomes worse than that of a deterministic (exhaustive) classical solver. We demonstrate this empirically using random Ising spin glass problems run on the two latest generations of the D-Wave quantum annealers. We then proceed to show that this doomsday scenario can be mitigated using a simple error suppression and correction scheme known as quantum annealing correction (QAC). By using QAC, the time-to-solution scaling of the same D-Wave devices is improved to below that of the classical upper bound, thus restoring hope in the speedup prospects of quantum annealing.
