Editing Computational chemistry (section)

== Computational costs in chemistry algorithms ==
{{main|Computational complexity|List of complexity classes}}

The computational cost and algorithmic complexity in chemistry are used to help understand and predict chemical phenomena. They help determine which algorithms/computational methods to use when solving chemical problems. This section focuses on the scaling of computational complexity with molecule size and details the algorithms commonly used in both domains.<ref>{{Cite journal |last1=Jäger |first1=Jonas |last2=Krems |first2=Roman V. |date=2023-02-02 |title=Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines |journal=Nature Communications |language=en |publisher=Nature |volume=14 |issue=1 |pages=576 |arxiv=2207.05865 |bibcode=2023NatCo..14..576J |doi=10.1038/s41467-023-36144-5 |issn=2041-1723 |pmc=9895068 |pmid=36732519}}</ref>

In quantum chemistry, particularly, the complexity can grow exponentially with the number of electrons involved in the system. This exponential growth is a significant barrier to simulating large or complex systems accurately.<ref>{{Cite book |title=Modern electronic structure theory. 1 |date=1995 |publisher=World Scientific |isbn=978-981-02-2987-0 |series=Advanced series in physical chemistry |location=Singapore}}</ref>

Advanced algorithms in both fields strive to balance accuracy with computational efficiency. For instance, in MD, methods like [[Verlet integration]] or [[Beeman's algorithm]] are employed for their computational efficiency. In quantum chemistry, hybrid methods combining different computational approaches (like QM/MM) are increasingly used to tackle large biomolecular systems.<ref>{{Cite journal |last1=Adcock |first1=Stewart A. |last2=McCammon |first2=J. Andrew |date=2006-05-01 |title=Molecular Dynamics: Survey of Methods for Simulating the Activity of Proteins |journal=Chemical Reviews |language=en |volume=106 |issue=5 |pages=1589–1615 |doi=10.1021/cr040426m |issn=0009-2665 |pmc=2547409 |pmid=16683746}}</ref>

=== Algorithmic complexity examples ===
The following list illustrates the impact of computational complexity on algorithms used in chemical computations. It is important to note that while this list provides key examples, it is not comprehensive and serves as a guide to understanding how computational demands influence the selection of specific computational methods in chemistry.

=== Molecular dynamics ===

{{see also|Molecular dynamics}}

==== Algorithm ====
Solves Newton's equations of motion for atoms and molecules.<ref>{{Cite journal |last1=Durrant |first1=Jacob D. |last2=McCammon |first2=J. Andrew |date=2011-10-28 |title=Molecular dynamics simulations and drug discovery |journal=BMC Biology |volume=9 |issue=1 |page=71 |doi=10.1186/1741-7007-9-71 |issn=1741-7007 |pmc=3203851 |pmid=22035460 |doi-access=free}}</ref>
[[File:A Molecular Dynamics Simulation of Liquid Water at 298 K.webm|thumb|Molecular dynamics simulation of liquid water at 298 K]]

==== Complexity ====

The standard pairwise interaction calculation in MD leads to an <math>\mathcal{O}(N^2)</math>complexity for <math>N</math> particles. This is because each particle interacts with every other particle, resulting in <math>\frac{N(N-1)}{2}</math> interactions.<ref>{{Cite journal |last1=Stephan |first1=Simon |last2=Horsch |first2=Martin T. |last3=Vrabec |first3=Jadran |last4=Hasse |first4=Hans |date=2019-07-03 |title=MolMod – an open access database of force fields for molecular simulations of fluids |url=https://www.tandfonline.com/doi/full/10.1080/08927022.2019.1601191 |journal=Molecular Simulation |language=en |volume=45 |issue=10 |pages=806–814 |arxiv=1904.05206 |doi=10.1080/08927022.2019.1601191 |issn=0892-7022 |s2cid=119199372}}</ref> Advanced algorithms, such as the Ewald summation or Fast Multipole Method, reduce this to <math>\mathcal{O}(N \log N)</math> or even <math>\mathcal{O}(N)</math> by grouping distant particles and treating them as a single entity or using clever mathematical approximations.<ref>{{Cite journal |last1=Kurzak |first1=J. |last2=Pettitt |first2=B. M. |date=September 2006 |title=Fast multipole methods for particle dynamics |journal=Molecular Simulation |language=en |volume=32 |issue=10–11 |pages=775–790 |doi=10.1080/08927020600991161 |issn=0892-7022 |pmc=2634295 |pmid=19194526}}</ref><ref>{{Cite journal |last1=Giese |first1=Timothy J. |last2=Panteva |first2=Maria T. |last3=Chen |first3=Haoyuan |last4=York |first4=Darrin M. |date=2015-02-10 |title=Multipolar Ewald Methods, 1: Theory, Accuracy, and Performance |journal=Journal of Chemical Theory and Computation |language=en |volume=11 |issue=2 |pages=436–450 |doi=10.1021/ct5007983 |issn=1549-9618 |pmc=4325605 |pmid=25691829}}</ref>

=== Quantum mechanics/molecular mechanics (QM/MM) ===
{{see also|QM/MM}}

==== Algorithm ====

Combines quantum mechanical calculations for a small region with molecular mechanics for the larger environment.<ref>{{Citation |last=Groenhof |first=Gerrit |title=Introduction to QM/MM Simulations |date=2013 |work=Biomolecular Simulations: Methods and Protocols |volume=924 |pages=43–66 |editor-last=Monticelli |editor-first=Luca |series=Methods in Molecular Biology |place=Totowa, NJ |publisher=Humana Press |language=en |doi=10.1007/978-1-62703-017-5_3 |isbn=978-1-62703-017-5 |pmid=23034745 |editor2-last=Salonen |editor2-first=Emppu |hdl=11858/00-001M-0000-0010-15DF-C |hdl-access=free}}</ref>

==== Complexity ====

The complexity of QM/MM methods depends on both the size of the quantum region and the method used for quantum calculations. For example, if a Hartree-Fock method is used for the quantum part, the complexity can be approximated as <math>\mathcal{O}(M^2)</math>, where <math>M</math> is the number of basis functions in the quantum region. This complexity arises from the need to solve a set of coupled equations iteratively until self-consistency is achieved.<ref>{{Cite journal |last1=Tzeliou |first1=Christina Eleftheria |last2=Mermigki |first2=Markella Aliki |last3=Tzeli |first3=Demeter |date=January 2022 |title=Review on the QM/MM Methodologies and Their Application to Metalloproteins |journal=Molecules |language=en |volume=27 |issue=9 |page=2660 |doi=10.3390/molecules27092660 |issn=1420-3049 |pmc=9105939 |pmid=35566011 |doi-access=free}}</ref>
[[File:Hartree-Fock.png|thumb|Algorithmic flowchart illustrating the Hartree–Fock method]]

=== Hartree-Fock method ===
{{See also|Hartree–Fock method}}

==== Algorithm ====
Finds a single Fock state that minimizes the energy.<ref name="Lucas-2014">{{Cite journal |last=Lucas |first=Andrew |date=2014 |title=Ising formulations of many NP problems |journal=Frontiers in Physics |volume=2 |page=5 |arxiv=1302.5843 |bibcode=2014FrP.....2....5L |doi=10.3389/fphy.2014.00005 |issn=2296-424X |doi-access=free}}</ref>

==== Complexity ====

NP-hard or NP-complete as demonstrated by embedding instances of the [[Ising model]] into Hartree-Fock calculations. The Hartree-Fock method involves solving the Roothaan-Hall equations, which scales as <math>\mathcal{O}(N^3)</math> to <math>\mathcal{O}(N)</math> depending on implementation, with <math>N</math> being the number of basis functions. The computational cost mainly comes from evaluating and transforming the two-electron integrals. This proof of NP-hardness or NP-completeness comes from embedding problems like the Ising model into the Hartree-Fock formalism.<ref name="Lucas-2014" />
[[File:Acrolein-s-trans-GED-MW-3D-sf.png|thumb|An [[acrolein]] molecule. DFT gives good results in the prediction of sensitivity of some nanostructures to environmental pollutants such as Acrolein.<ref>{{Cite journal |last1=Rastegar |first1=Somayeh F. |last2=Hadipour |first2=Nasser L. |last3=Tabar |first3=Mohammad Bigdeli |last4=Soleymanabadi |first4=Hamed |date=2013-09-01 |title=DFT studies of acrolein molecule adsorption on pristine and Al- doped graphenes |url=http://link.springer.com/10.1007/s00894-013-1898-5 |journal=Journal of Molecular Modeling |language=en |volume=19 |issue=9 |pages=3733–3740 |doi=10.1007/s00894-013-1898-5 |pmid=23793719 |s2cid=41375235 |issn=1610-2940}}</ref>]]

=== Density functional theory  ===
{{See also|Density functional theory|l1=Density functional theory}}

==== Algorithm ====
Investigates the [[electronic structure]] or [[nuclear structure]] of [[Many-body problem|many-body systems]] such as atoms, molecules, and the [[condensed phase]]s.<ref>{{Cite journal |last1=Kohn |first1=W. |last2=Sham |first2=L. J. |date=1965-11-15 |title=Self-Consistent Equations Including Exchange and Correlation Effects |journal=Physical Review |volume=140 |issue=4A |pages=A1133–A1138 |bibcode=1965PhRv..140.1133K |doi=10.1103/PhysRev.140.A1133 |doi-access=free}}</ref>

==== Complexity ====

Traditional implementations of DFT typically scale as <math>\mathcal{O}(N^3)</math>, mainly due to the need to diagonalize the [[Kohn–Sham equations|Kohn-Sham matrix]].<ref>{{Cite journal |last1=Michaud-Rioux |first1=Vincent |last2=Zhang |first2=Lei |last3=Guo |first3=Hong |date=2016-02-15 |title=RESCU: A real space electronic structure method |url=https://www.sciencedirect.com/science/article/pii/S0021999115008335 |journal=Journal of Computational Physics |volume=307 |pages=593–613 |arxiv=1509.05746 |bibcode=2016JCoPh.307..593M |doi=10.1016/j.jcp.2015.12.014 |issn=0021-9991 |s2cid=28836129}}</ref> The diagonalization step, which finds the eigenvalues and eigenvectors of the matrix, contributes most to this scaling. Recent advances in DFT aim to reduce this complexity through various approximations and algorithmic improvements.<ref>{{Cite journal |last1=Motamarri |first1=Phani |last2=Das |first2=Sambit |last3=Rudraraju |first3=Shiva |last4=Ghosh |first4=Krishnendu |last5=Davydov |first5=Denis |last6=Gavini |first6=Vikram |date=2020-01-01 |title=DFT-FE – A massively parallel adaptive finite-element code for large-scale density functional theory calculations |url=https://www.sciencedirect.com/science/article/pii/S0010465519302309 |journal=Computer Physics Communications |volume=246 |page=106853 |arxiv=1903.10959 |bibcode=2020CoPhC.24606853M |doi=10.1016/j.cpc.2019.07.016 |issn=0010-4655 |s2cid=85517990}}</ref>

=== Standard CCSD and CCSD(T) method ===
{{See also|Coupled cluster}}

==== Algorithm ====
CCSD and CCSD(T) methods are advanced electronic structure techniques involving single, double, and in the case of CCSD(T), perturbative triple excitations for calculating electronic correlation effects.<ref name="Sengupta-2016">{{Cite journal |last1=Sengupta |first1=Arkajyoti |last2=Ramabhadran |first2=Raghunath O. |last3=Raghavachari |first3=Krishnan |date=2016-01-15 |title=Breaking a bottleneck: Accurate extrapolation to "gold standard" CCSD(T) energies for large open shell organic radicals at reduced computational cost |url=https://onlinelibrary.wiley.com/doi/10.1002/jcc.24050 |journal=Journal of Computational Chemistry |language=en |volume=37 |issue=2 |pages=286–295 |doi=10.1002/jcc.24050 |issn=0192-8651 |pmid=26280676 |s2cid=23011794}}</ref>

==== Complexity ====

===== CCSD =====

Scales as <math>\mathcal{O}(M^6)</math> where <math>M</math> is the number of basis functions. This intense computational demand arises from the inclusion of single and double excitations in the electron correlation calculation.<ref name="Sengupta-2016" />

===== CCSD(T) =====

With the addition of perturbative triples, the complexity increases to <math>\mathcal{O}(M^7)</math>.  This elevated complexity restricts practical usage to smaller systems, typically up to 20-25 atoms in conventional implementations.<ref name="Sengupta-2016" />
[[File:Methan 2a1.png|thumb|[[Electron density]] plot of the 2a1 molecular orbital of [[methane]] at the CCSD(T)/cc-pVQZ level. Graphic created with [[Molden]] based on correlated geometry optimization with CFOUR at the CCSD(T) level in cc-pVQZ basis.]]

=== Linear-scaling CCSD(T) method ===
{{See also|Coupled cluster}}

==== Algorithm ====

An adaptation of the standard CCSD(T) method using local natural orbitals (NOs) to significantly reduce the computational burden and enable application to larger systems.<ref name="Sengupta-2016" />

==== Complexity ====

Achieves linear scaling with the system size, a major improvement over the traditional fifth-power scaling of CCSD. This advancement allows for practical applications to molecules of up to 100 atoms with reasonable basis sets, marking a significant step forward in computational chemistry's capability to handle larger systems with high accuracy.<ref name="Sengupta-2016" />

Proving the complexity classes for algorithms involves a combination of mathematical proof and computational experiments. For example, in the case of the Hartree-Fock method, the proof of NP-hardness is a theoretical result derived from complexity theory, specifically through reductions from known [[NP-hardness|NP-hard]] problems.<ref name="xlink.rsc.org">{{Cite journal |last1=Whitfield |first1=James Daniel |last2=Love |first2=Peter John |last3=Aspuru-Guzik |first3=Alán |date=2013 |title=Computational complexity in electronic structure |url=http://xlink.rsc.org/?DOI=C2CP42695A |journal=Phys. Chem. Chem. Phys. |language=en |volume=15 |issue=2 |pages=397–411 |arxiv=1208.3334 |bibcode=2013PCCP...15..397W |doi=10.1039/C2CP42695A |issn=1463-9076 |pmid=23172634 |s2cid=12351374}}</ref>

For other methods like MD or DFT, the computational complexity is often empirically observed and supported by algorithm analysis. In these cases, the proof of correctness is less about formal mathematical proofs and more about consistently observing the computational behaviour across various systems and implementations.<ref name="xlink.rsc.org" />