This question comes to me via a friend, and apparently has something to do with quantum physics. However, stripped of all physics, it seems interesting enough on its own. I assume someone has asked this question before, but I have no idea what to search for:


Suppose we have points $P$ and $Q$ on $S^2$, and two available rotations: specifically, I am interested in rotations by $\pi/4$ radians about the $x$ and $z$ axes. Given $\varepsilon > 0$, is there an effective algorithm for applying these rotations to $P$ so that it is within Euclidean distance $\varepsilon$ of $Q$?


**Edit:** Update retracted. I'm curious about the general situation as well, where the two rotations are arbitrary (and, obviously, send $P$ to a dense subset of $S^2$).



Maneuvering with limited moves on $S^2$
\**More comments at end on finding group elements with small word length \**


If you're willing to accept an element of the group (as distinguished from a word expressing an element) there is an algorithm that will produce such an element moving $P$ to within $\epsilon$ of $Q$ that is polynomial as a function of the number of bits of $\epsilon$, that is, $|\log(\epsilon)|$. If you need a word, there are algorithms that are at least as good as polynomial in $1/\epsilon$.


First: this group is dense, because the only finite subgroups of $SO(3)$ that are not contained in $O(2) \times O(1)$ have elements of orders only 2, 3, 4 and 5. There are good descriptions of all such subgroups in various places, but I won't go over this here --- I an explain if pressed. A rotation by $\pi/4$ has order 8, and the group, by inspection does not preserve a splitting. Therefore, the group is infinite. Any infinite subgroup of any Lie group is dense in some closed subgroup. The only possibility is that it is dense in $SO(3)$.


The basic phenomenon that helps for approximation is that in any Lie group with any Riemannian metric, there is a radius $r$ such that for $g, h \in B\_r$ (the ball of radius $r$), the commutator $[g, h]$ is contained in the much ball $B\_{2 r^2}$, which is much smaller if $r$ is small. This follows from Taylor approximation of the commutator in a neighborhood of $[1,1]$. More concretely,
$|[g,h]| < 2|g| |h|$, where $||$ denotes distance from the identity.


Furthermore, for two isometries of $S^2$ that move a point $X$ a small distance, $[g,h]$ is nearly a translation, since the group $SO(2)$ of possible first derivatives with respect to some local frame field is abelian.


Using this, you can get from $P$ to $Q$ by successive approximation. If we denote the two generators $X$ and $Z$, we can first, take $Q$ roughly to within striking distance of $P$ by some element of the form
$X^k Z^j$. Or, use some other word; this first step has fixed finite cost, and can be done by exhaustive search through some set of words in $X$ and $Y$.


Now, use commutators of smallish elements to find still smaller elements, and use these
to bring $Q$ still closer to $P$. It is easy to generate approximate translations of all scales, by judiciously choosing commutators of elements on larger scales. The computations in $O(3)$ to desired accuracy can be done in polynomial time. 


One concrete tool to actually implement this would be to reduce the question to the case that $P$ is a fixed point of an element $W$ of infinite order. (It is easy to find such elements, using a $p$-adic valuation). Given one approximate translation that moves $P$ a small distance, conjugates of it by powers of $W$ are translations approximating any desired direction. If you take the commutator with a fixed approximate translation of medium size, it is an approximate translation of size approximately say $1/3$ the original.


In this process, elements of the group are generated recursively, and the wordlength in original generators typically grows exponentially in the number of steps, but they have exponentially increasing accuracy of moving $Q$ to $P$. If you unroll the process, it takes polynomial length words in $1/\epsilon$ to move $Q$ to within $\epsilon$ of $P$.


**Addendum**. Any finitely-generated subgroup of $SO(3)$ generated by matrices with algebraic integer entries (such as this) has a faithful discrete action on a product of spheres, hyperbolic planes, and hyperbolic 3-spaces, by a general construction for algebraic groups, from which it follows that it is either virtually abelian or has exponential growth and in fact it contains a free subgroup. It seems likely that these group elements have orbits on $S^2$ that are reasonably uniformly distributed, although I don't know what's proven about it. If so, by just counting elements it would follow that $P$ can be take to within $\epsilon$ of $Q$ using a word of length linear in $\log(\epsilon)|$.


It looks like an interesting challenge to try to find a polynomial-time algorithm that will find such a word. Once $P$ is within a small negihbrohood of $Q$ and you have a modest selection of moderate-length words that look almost like translations in a magnification of this small neighborhood, one strategy would be to make a first approximation of getting closer by adding vectors. But they are not exactly addition of a vector, and the many different possible orders in which you could multiply them give many different results.
If you could systematically analyze and control the effects of changing the orde it might be possible to systematically improve the approximtion. In other words: instead of multiplying
by higher and higher commutators at the end, actually commute elements in the produt.


However, this is more of a challenge than I feel like plunging in to here.


