Complexity of Ab Initio quantum computation of bulk properties

Question

Background

• I'm an undergrad studying Computer Engineering, however I switched from ChemE.
• I just completed Physics 2, however I've a cursory understanding of higher level Physics concepts (Hamilton Mechanics, QM, Stat. Mech) from my own personal reading.

For many years Computational Chemists have used approximate methods like Hartree-Frock and DFT for Ab initio simulation of molecular dynamics. Studies (1,2) of the melting point of water seem to give decent results, however there is still room for improvement. I'm particularity interested in the computational complexity of molecular dynamics simulations and calculating macroscopic properties that would be useful for chemical engineering applications (e.g. activity coeffcients, phase change temperatures, viscosity etc.).

NIST says that computation of the partition function is BQP-Complete and "every thermodynamic quantity can be calculated by taking an appropriate partial derivative of the partition function."

Another answer on this forum suggested that finding Hamiltonians for quantum ground states is QMA-complete

Questions

Can Quantum computing give exact answers or really good approximations to the following in polynomial time:

1. Let there be a system composed of $n$ ($n|n<\infty$) molecules (e.g. a mole of water). Calculate ab initio the following properties:

   • Melting Point, Boiling Point, Viscosity, Enthalpy of Formation etc.
2. Given a hetergenous mixture of molecules calculate ab initio:
   • Activity coeffcients for Liquid-Liquid Extraction, Distillation

How might Exascale computation coupled with Machine learning (quantum ML? {doi:10.1038/nature23474}) and a QPU help solve this problem?

Relevant References (Mostly Keywords but also looking for books, papers etc.) would be greatly appreciated.

Answer 1

Interesting questions, but very broad.

The statements about the (quantum) computational complexities do not in principle have much to do with the questions of what is feasible with QC, referring to worst-case scenarios (it may actually be an interesting question for cstheory how much these statements are relevant to the more commonly occurring cases). Also, they are not per se statements about the complexity of simulating a quantum system, but refer to harder problems.

The answer to the question of whether QC can solve in polynomial time (and resources) the 2 problems you mention is generally yes. A quantum computer can, in principle, solve efficiently the problem of simulating a quantum system. Indeed, this will probably the main application of a quantum device, and very likely the first instance of a real world problem solved thanks to one (I'm referring to quantum chemistry simulations).

However, efficiently doesn't mean easily. It will be a long time before a "full" quantum simulation of something like a mole of water will be feasible (or even conceivable for that matter). I mean, a mole is a lot of stuff: to simulate $\sim\!10^{23}$ molecules, you will need something of the order of $10^{23}$ qubits (if you think in the framework of quantum computation with qubits). And then to simulate such a system means to choose some simplified model of the molecules and implement that on your quantum device, so the amount of resources needed will depend heavily on the kind of model you want to use. If one is only interested in extracting some particular feature of the system, say, its melting point, then you may be able to exploit some symmetries and pull off the simulation with much less resources, but the main point still stands. I won't even go into the amount of open problems, both on the technological and theoretical side, that will have to be figured out before something of this scale can be realised. You may find interesting this recent nature insight on quantum software to read something more on the open problems (it doesn't directly delve with quantum chemistry simulations though). I'm not expert in quantum chemistry so I can't say much more than this, but if you are interested, a leading group that comes to mind that works on quantum simulation of quantum chemistry system is Alan Aspuru-Guzik's group in Harvard, so you can check out their list of publication to see what kind of things are being done.

How might Exascale computation coupled with Machine learning (quantum ML? {doi:10.1038/nature23474}) and a QPU help solve this problem?

This one is really hard to answer. The field of quantum machine learning is still in its infancy and very rapidly moving. I don't think I've read of any connection between exascale computing and quantum machine learning. A quick googling led me to this news article about a partnering between D-Wave computing and some exascale computing laboratory. I couldn't find a better source and don't know anything about it though, so I can't comment.

Broadly speaking, I don't think it is expected that neither ML, QML, nor Exascale computing will just magically "solve" the problems mentioned above. QML, and in particular ML applied to problems in quantum mechanics/computing (see the distinction on the wiki page), can (possibly) help in solving some of the problems related to scaling up quantum computing devices and performing quantum simulations. High performance computing is always helpful to push forward simulations and accelerate research, and together with smart ML techniques can speed up the research needed to figure out how to scale up quantum devices (as well as many other things). Apart from Biamonte et al.'s review that you linked, you may have a look at some of the recent reviews from (mostly) NASA's D-Wave group: On the readiness of quantum optimization machines for industrial applications, A NASA Perspective on Quantum Computing: Opportunities and Challenges and Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers. Also Quantum machine learning: a classical perspective may interest you.

At this point I'm starting to get into the realm of speculation though so I will just stop. If you want more detail on some point (there are many points and plenty of detail for each) you should ask for it with separate questions.