[m_dupont]

I'm a little late to the party but hopefully someone can still answer this question.

In order to solve the linear system of equations in this framework, you need to integrate a measurement of the system over some time greater than t_0 and tau. However in equation 12 you can see that t_0 and tau are functions of the eigenvalues and the norm of the matrix.

AFAIK the best runtime algorithms we have for computing matrix eigenvalues is still O(d²), so even if the thermodynamic part of algorithm is linear in d, computing how long you would need to run the algorithm for is still quadratic in d, so there's no real gain.

Or am I missing something here?

[kaelan123]

Indeed the bounds on convergence times t_0 and tau depend on quantities that are expensive to compute. For example, if we consider the norm of A, this quantity can itself be bound by the values the elements A can take itself, which is a requirement on the type of hardware we would be using (as the elements of A are mapped to component values in the hardware that is considered in the appendix). There are other heuristic tricks one could use.

To give a comparison with conjugate gradients, there the condition number is in the convergence bound, however computing it requires the maximum and minimum eigenvalues, hence people never compute it, and rely on heuristics for convergence.

[m_dupont]

thankyou, that actually cleared things up for me

[pama]

I’m not one of the authors and have only skimmed the paper thus far and found it interesting enough to warrant further study. I guess one could run the simulation in the hardware and monitor convergence as a function of time. I can also imagine cases where one could work on a class of problems that have a priori known worst case condition, or cases where the exact solution every time is not a hard requirement.