Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation.

Area of Science:

• Quantum Physics
• Computational Quantum Chemistry
• Quantum Algorithms

Background:

• Estimating ground state energies of many-body Hamiltonians is crucial across quantum physics.
• Existing methods often struggle with complex Hamiltonians, especially those with long-range interactions.

Purpose of the Study:

• To develop quantum algorithms for estimating ground state energies of general k-body Hamiltonians.
• To prepare quantum states corresponding to these ground state energies.
• To achieve a runtime that surpasses the standard Grover speedup.

Main Methods:

• Development of novel quantum algorithms applicable to any k-body Hamiltonian, irrespective of interaction geometry or locality.
• Leveraging the insight that a significant fraction of interactions can be neglected with controlled error.
• Analysis of algorithm runtime scaling as 2^{cn/2} for c<1.

Main Results:

• Quantum algorithms provide estimates of ground state energy within additive error ϵM with high probability.
• Algorithms can prepare quantum states with the estimated ground state energy.
• Demonstration of the first quantum algorithms for low-energy estimation that break the square root Grover speedup.

Conclusions:

• The developed quantum algorithms offer a significant advancement for studying many-body systems.
• These algorithms are applicable to a broad range of Hamiltonians, including those found in quantum chemistry.
• Arbitrary k-local Hamiltonians exhibit exploitable structure in their low-energy space, forming an exponential-dimensional subspace.