Spectral gap amplification

DOI10.1137/120871997zbMATH Open1271.68108arXiv1110.2494OpenAlexW3101249570MaRDI QIDQ2840985FDOQ2840985

S. Boixo, R. D. Somma

Publication date: 24 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: A large number of problems in science can be solved by preparing a specific eigenstate of some Hamiltonian H. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of H for that eigenstate and the cost of evolving with H for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian H' with the same eigenstate as H but a bigger spectral gap, requiring that constant-time evolutions with H' and H are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when H satisfies a frustration-free property and give H' for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states (PEPS), which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.

Full work available at URL: https://arxiv.org/abs/1110.2494

Recommendations

• On the gap of Hamiltonians for the adiabatic simulation of quantum circuits
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• When a local Hamiltonian must be frustration-free
• scientific article; zbMATH DE number 1984609
• Complexity of stoquastic frustration-free Hamiltonians

zbMATH Keywords

adiabatic quantum computingquantum algorithmsquantum Monte-Carlo

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (6)

• ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS
• Error suppression and error correction in adiabatic quantum computation: non-equilibrium dynamics
• Grover search inspired alternating operator ansatz of quantum approximate optimization algorithm for search problems
• A universal quantum algorithm for weighted maximum cut and Ising problems
• Local gap threshold for frustration-free spin systems
• Large spectral gap induced by small delay and its application to reduction

This page was built for publication: Spectral gap amplification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840985)