Efficient population transfer via non-ergodic extended states in quantum spin glass

Abstract

We analyze a new computational role of coherent multi-qubit quantum tunneling that gives rise to bands of non-ergodic extended (NEE) quantum states each formed by a superposition of a large number of computational states (deep local minima of the energy landscape) with similar energies. NEE provide a mechanism for population transfer (PT) between computational states and therefore can serve as a new quantum subroutine for quantum search, quantum parallel tempering and reverse annealing optimization algorithms. We study PT in a quantum n-spin system subject to a transverse field where the energy function $E(z)$ encodes a classical optimization problem over the set of spin configurations $z$. Given an initial spin configuration with low energy, PT protocol searches for other bitstrings at energies within a narrow window around the initial one. We provide an analytical solution for PT in a simple yet nontrivial model: $M$ randomly chosen marked bit-strings are assigned energies $E(z)$ within a narrow strip $[-n-W/2,n+W/2]$, while the rest of the states are assigned energy 0. We find that the scaling of a typical PT runtime with n and L is the same as that in the multi-target Grover's quantum search algorithm, except for a factor that is equal to $\exp (n/(2B^2))$ for finite transverse field $B\gg 1$. Unlike the Hamiltonians used in analog quantum unstructured search algorithms known so far, the model we consider is non-integrable and population transfer is not exponentially sensitive in n to the weight of the driver Hamiltonian. We study numerically the PT subroutine as a part of quantum parallel tempering algorithm for a number of examples of binary optimization problems on fully connected graphs.

arXiv comment16 pages, 7 figures; proceedings of TQC 2018

References in corpus (5)

• Quantum Computing in the NISQ era and beyond
• Reverse annealing for the fully connected $p$-spin model
• Quantum search by measurement
• Clustering of non-ergodic eigenstates in quantum spin glasses
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

Cited by in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Multifractal dimensions for random matrices, chaotic quantum maps, and many-body systems
• Robustness of delocalization to the inclusion of soft constraints in long-range random models
• Localization transition on the Random Regular Graph as an unstable tricritical point in a log-normal Rosenzweig-Porter random matrix ensemble
• From ergodic to non-ergodic chaos in Rosenzweig-Porter model
• Low depth mechanisms for quantum optimization
• Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization