Sparse random Hamiltonians are quantumly easy

Abstract

A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. For this task, there is a well-studied quantum algorithm that performs quantum phase estimation on an initial trial state that has a nonnegligible overlap with a low-energy state. However, it is notoriously hard to give theoretical guarantees that such a trial state can be prepared efficiently. Moreover, the heuristic proposals that are currently available, such as with adiabatic state preparation, appear insufficient in practical cases. This paper shows that, for most random sparse Hamiltonians, the maximally mixed state is a sufficiently good trial state, and phase estimation efficiently prepares states with energy arbitrarily close to the ground energy. Furthermore, any low-energy state must have nonnegligible quantum circuit complexity, suggesting that low-energy states are classically nontrivial and phase estimation is the optimal method for preparing such states (up to polynomial factors). These statements hold for two models of random Hamiltonians: (i) a sum of random signed Pauli strings and (ii) a random signed $d$-sparse Hamiltonian. The main technical argument is based on some new results in nonasymptotic random matrix theory. In particular, a refined concentration bound for the spectral density is required to obtain complexity guarantees for these random Hamiltonians.

arXiv comment33 pages, 4 figures

References in corpus (23)

• Gapless Spin-Fluid Ground State in a Random Quantum Heisenberg Magnet
• Comments on the Sachdev-Ye-Kitaev model
• Quantum computational chemistry
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• A random compiler for fast Hamiltonian simulation
• Local random quantum circuits are approximate polynomial-designs
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
• Low Depth Quantum Simulation of Electronic Structure
• Quantum computing enhanced computational catalysis
• A quantum-inspired classical algorithm for recommendation systems
• Random Matrices and Chaos in Nuclear Physics: Nuclear Reactions
• Fixed-point quantum search with an optimal number of queries
• The power of quantum systems on a line
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Random matrix techniques in quantum information theory
• Phase Transition in the Density of States of Quantum Spin Glasses
• Does the SYK model have a spin glass phase?
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Quenched vs Annealed: Glassiness from SK to SYK
• Extremal eigenvalues of local Hamiltonians
• Optimizing sparse fermionic Hamiltonians

Cited by in corpus (6)

• High ground state overlap via quantum embedding methods
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• Energy Spectra of Compressed Quantum States
• Optimizing Sparse SYK
• A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation