Determining an inner automorphism via queries

You could ask for the values of $\phi$ on a generating set of $G$ of smallest possible size. That would determine $\phi$ and hence $a$ modulo the centre. It is unlikely that you will find a better general solution than that.

Of course in specific groups, you might be able to calculate $a$ with fewer images. The extreme case is when $G$ is abelian, when you don't need to amke any queries, and any element $a$ is a correct answer.

So you would need to restrict the class of groups $G$ under consideration. I guess you are looking for a collections of elements $x_i$ of $G$ such that the intersection of their centralizers is the centre of $G$.

Two observations. If you know enough about your situation to be able to quotient out the center, that would be useful, since a unique solution is easier to find than a non-unique solution.

Second, if you have a faithful f.d. linear representation of your group, that would be helpful, because, by your queries, you have a lot of equations: $$ a x_i - y_i a = 0, $$ where $(x_i, y_i)$ are data and $a$ is the unknown. This are linear equations for the unknown matrix $a$. From the point of view of linear algebra, you may even get more useful information from any one query because $a x_i^k = y_i^k a$ for all $k$.

I don't know if this is only theoretical speculation, or if you actually want to do computations. If the latter, the big mathematics packages (Mathematica. ...) seem to have built in routines for this type of equation.