Let $G$ be a finite group. Define the Hurwitz action of $B_{n}$ on $G^{n}$ by letting $(x_{1},...,x_{n})\sigma_{i}=(x_{1},...,x_{i}x_{i+1}x_{i}^{-1},x_{i},x_{i+2},...,x_{n})$. I wonder what algorithms exist that produce a small circuit $C$ such that $C(x_{1},...,x_{n})=(x_{1},...,x_{n})b$ for all $x_{1},...,x_{n}\in G$.

$\textbf{Algorithm 1:}$ Let $b$ be a braid. Then a braid word $w$ representing $b$ is said to be a geodesic braid word if $w$ has minimal length among all braids that represent $b$. The set of all braids in $B_{\infty}$ is a $co-NP$-complete problem. However, while the geodesic braid word of a braid $w$ is $co-NP$-complete, in practice, there is an approximate algorithms for finding nearly geodesic braid words for a braid.

In particular, in this paper, the authors have observed that Dehornoy's handle reduction usually replaces a braid word $w$ with an equivalent but shorter braid word $w'$. The authors therefore proposed alternating between left handle reductions and right handle reductions as an algorithm for finding very short braid words $w^{\sharp}$ for a given braid $b$. Therefore, when we consider the nearly geodesic braid word $w^{\sharp}$ as a circuit, then the word $w^{\sharp}$ is a quite short circuit that computes $(x_{1},...,x_{n})\mapsto(x_{1},...,x_{n})b$.

$\textbf{Possible algorithm 2: The fast Hurwitz action}$

Let $\Delta_{n}=(\sigma_{1}...\sigma_{n-1})(\sigma_{1}...\sigma_{n-2})... (\sigma_{1}\sigma_{2})\sigma_{1}$. Then $\Delta_{n}$ is known as the fundamental braid.

Then while the braid $\Delta_{n}$ has $\frac{n(n-1)}{2}$, elements, the action $(x_{1},...,x_{n})\mapsto(x_{1},...,x_{n})\Delta_{n}$ can be computed by performing $O(n)$ many group operations on $G$ (instead of the $O(n^{2})$ operations which one has to do if one applies the braid $\Delta_{n}$ directly).

Suppose that $(x_{1},...,x_{n})\in G$. Then compute $(y_{1},...,y_{n})$ recursively by letting $y_{1}=e$ and $y_{n+1}=y_{n}\cdot x_{n}$. Then $$(x_{1},...,x_{n})\Delta_{n}=(y_{n}x_{n}y_{n}^{-1},y_{n-1}x_{n-1}y_{n-1}^{-1},...,y_{2}x_{2}y_{2}^{-1},y_{1}x_{1}y_{1}^{-1}).$$ Therefore, one obtains a fast algorithm for computing $(x_{1},...,x_{n})\Delta_{n}$ using $O(n)$ group operations rather than $O(n^{2})$ group operations. The fast Hurwitz action also allows us to compute $(x_{1},...,x_{n})(\sigma_{1}...\sigma_{i_{1}})...(\sigma_{1}...\sigma_{i_{k}})$ where $i_{1}>...>i_{k}$ in $O(n)$ steps as well.

Is there any way to generalize this fast Hurwitz action to other braids? Does there exist a braid form in which one is able to easily apply the fast Hurwitz action or a generalized fast Hurwitz action? Is there a good way to in general decompose a braid $b$ as the composition of braids in which one can apply the fast Hurwitz action? If algorithm 2 can be applied to all braids in a reasonable manner, does algorithm 2 in general use more or less gates than algorithm 1?

The braids $(\sigma_{1}...\sigma_{i_{1}})...(\sigma_{1}...\sigma_{i_{k}})$ look very similar to the simple braids which one obtains from the Garside normal form of a braid, but I have not yet been able to apply the fast Hurwitz action to simple braids in general.

$\textbf{A possible application to cryptography}$ If one defines the length $\ell(b)$ of the braid $b$ to be the number of gates in a suitably optimized circuit $C$ with $C(x_{1},...,x_{n})=(x_{1},...,x_{n})b$, then the length function $\ell$ may be useful in constructing length based attacks against various braid group cryptosystems. However, one needs to optimize the circuit size $\ell(b)$ in order for this length based attack to be effective.