A quantum algorithm for $2\times 2\times 2$ tensor isomorphism over $\mathbb{Z}$

3:00pm, Wednesday 29 October 2025

Abstract

We present a quantum polynomial-time algorithm that decides whether two tensors in $\mathbb{Z}^2\otimes\mathbb{Z}^2\otimes\mathbb{Z}^2$ are in the same orbit under the natural action of $\mathrm{GL}(2, \mathbb{Z})\times\mathrm{GL}(2, \mathbb{Z})\times\mathrm{GL}(2, \mathbb{Z})$. This algorithm is a natural consequence of the works of Gauss (on composition laws), Bhargava (on higher composition laws), and Hallgren (on quantum algorithms for the principal ideal problem). An intriguing question is the case of $\mathbb{Z}^3\otimes\mathbb{Z}^3\otimes\mathbb{Z}^3$.