Invited Speaker 23rd International Society of Magnetic Resonance Conference 2023

The exponential complexity scaling wall and how it fell in Magnetic Resonance (#186)

Ilya Kuprov 1
  1. University of Southampton, Southampton, HAMPSHIRE, United Kingdom

This lecture presents a mathematical and historical overview of a major recent development in magnetic resonance theory and software: the adoption of incomplete basis sets and the resulting improvement in the efficiency of numerical simulations from exponential complexity scaling to low-order polynomial scaling, whereupon time domain simulations (including accurate treatment of relaxation, chemical kinetics, and spatial transport) of biological systems with hundreds of interacting spins have become feasible.

Magnetic resonance simulations used to be hard because the dimension of the density matrix goes at least as 2^n with the number of spins - hence the exponential complexity scaling. Some corners can be cut using symmetries, conservation laws, and sparse array storage, but this does not solve the fundamental scaling problem. DMRG type methods likewise cannot handle long-range time evolution of irregular polycyclic dissipative interaction networks that are common in biological spin systems. The problem was widely believed to be insoluble.

Things improved in 2007 with the introduction of restricted state spaces [1] and their special case later called low correlation order approximation [2]. It turned out that most of the quantum mechanical state space of weakly interacting dissipative spin systems at room temperature is dynamically unreachable [1,3] and local reduced basis sets [4] are an excellent approximation. It was later shown that these methods sometimes work in solid state magnetic resonance [2,5], where the powder averaging operation makes the dynamics effectively dissipative [6]. The mathematics of state space restriction is complicated (the dynamical manifold is not only a linear space, but also a Lie algebra [7]), but a convenient software implementation now exists [8] that covers the whole of magnetic resonance spectroscopy and imaging. At the time of writing, over 15 years of work has gone into a variety of numerical efficiency tweaks [9].

There are still cases (for example, crystalline solids at low temperatures) where the complexity of spin dynamics simulations scales exponentially, but in the daily life of a magnetic resonance spectroscopist such systems are few and far between; as of 2023, Spinach package [8] would run most real-life magnetic resonance simulations on a good laptop.

  1. [1] Kuprov, I., Wagner-Rundell, N. and Hore, P.J., 2007. Polynomially scaling spin dynamics simulation algorithm based on adaptive state-space restriction. Journal of Magnetic Resonance, 189(2), pp.241-250. (https://doi.org/10.1016/j.jmr.2007.09.014)
  2. [2] Butler, M.C., Dumez, J.N. and Emsley, L., 2009. Dynamics of large nuclear-spin systems from low-order correlations in Liouville space. Chemical Physics Letters, 477(4-6), pp.377-381. (https://doi.org/10.1016/j.cplett.2009.07.017)
  3. [3] Karabanov, A., Kuprov, I., Charnock, G.T.P., van der Drift, A., Edwards, L.J. and Köckenberger, W., 2011. On the accuracy of the state space restriction approximation for spin dynamics simulations. The Journal of chemical physics, 135(8), p.084106. (https://doi.org/10.1063/1.3624564)
  4. [4] Edwards, L.J., Savostyanov, D.V., Welderufael, Z.T., Lee, D. and Kuprov, I., 2014. Quantum mechanical NMR simulation algorithm for protein-size spin systems. Journal of Magnetic Resonance, 243, pp.107-113. (https://doi.org/10.1016/j.jmr.2014.04.002)
  5. [5] Perras, F.A. and Pruski, M., 2019. Linear-scaling ab initio simulations of spin diffusion in rotating solids. The Journal of Chemical Physics, 151(3), p.034110. (https://doi.org/10.1063/1.5099146)
  6. [6] Edwards, L.J., Savostyanov, D.V., Nevzorov, A.A., Concistre, M., Pileio, G. and Kuprov, I., 2013. Grid-free powder averages: On the applications of the Fokker–Planck equation to solid state NMR. Journal of Magnetic Resonance, 235, pp.121-129. (https://doi.org/10.1016/j.jmr.2013.07.011)
  7. [7] Kuprov, I., 2023. Incomplete Basis Sets. In Spin: From Basic Symmetries to Quantum Optimal Control (pp. 291-312). Cham: Springer International Publishing. (https://doi.org/10.1007/978-3-031-05607-9_7)
  8. [8] Hogben, H.J., Krzystyniak, M., Charnock, G.T., Hore, P.J. and Kuprov, I., 2011. Spinach–a software library for simulation of spin dynamics in large spin systems. Journal of Magnetic Resonance, 208(2), pp.179-194. (https://doi.org/10.1016/j.jmr.2010.11.008)
  9. [9] Kuprov, I., 2023. SPIN: From Basic Symmetries to Quantum Optimal Control. Springer Nature. (https://doi.org/10.1007/978-3-031-05607-9)