It should be reasonably fast to iterate over the composer paths for a given class name MyClass.php and use the class-to-file package to covert the found file to an FQN.

The service should provide 2 operations: returning a list of candidates and including the use statement (or could this be better done by VIM?).