7
$\begingroup$

I'm doing some reading into Variational Quantum Eigensolvers (VQEs), Quantum Approximate Optimization Algorithms (QAOAs), and other similar algorithms.

I know that the point is to find the ground state of a Hamiltonian. I'm interested in making/finding a list of all the different problems that we know we can solve in this way.

For example, I've seen references to applications in chemistry, material science, and even graph theory. Can you point me to an existing list of applications, or list some places I can go to find more? Google searches for "applications of finding ground state of Hamiltonian" are not giving me anything interesting.

What I'm most interested in is how one can translate the problem into the specific Hamiltonian that they want to solve, and then specifically what they learn about the problem when they find the ground state energy.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Welcome to Quantum Computing StackExchange.

In general, finding the ground state energy of a k-local Hamiltonian is QMA-hard for k ≥ 2. That means, any problem in the complexity class QMA can be solved by reducing it to a k-local Hamiltonian and finding its ground state.

And since NP is a subclass of QMA, any NP problem can be solved this way including NP-complete problems.

Thousands of problems are known to be NP-complete. The book "Computers and Intractability" by Garey and Johnson includes over 300 of them.

This paper provides formulations for some well known NP-complete problems as Hamiltonians of an Ising spin glass that can be used with QAOA.

And this paper describes a systematic way to convert a problem into a Hamiltonian.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great, thanks for sharing! I didn't realize that such a large class of problems is reducible to finding the ground state energy! $\endgroup$
    – johndont
    Apr 24, 2021 at 20:43
  • $\begingroup$ Here is a paper listing QMA-complete problems: arxiv.org/pdf/1212.6312.pdf $\endgroup$
    – shashvat
    Apr 30, 2021 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.