Imagine we have two size $m$ sets (without order) of points $X=\{x^i\}_{i=1..m}, Y=\{y^i\}_{i=1..m} \subset \mathbb{R}^n$ and we want to answer the question if they differ only by rotation: if there exists othogonal $O^TO=OO^T=I$ such that $X=\{Oy^i:i=1..m\}$.
It simple to test in exponential time, the question is if it be answered in polynomial time (in both $m$ and $n$)?
While it might seem simple, it isn't - the most difficult cases of graph isomorphism problem: for strongly regular graphs (SRG) can be translated to above problem. We can assume that all points are on a sphere, for SRGs they form very regular high dimensional polyhedron (diagram below) having $m\approx 2n$ points.
Testing differing only by rotation is simple for symmetric matrices - they differ only by rotation if traces of all $n$ powers are equal ($\exists_O P=O^TQO \Leftrightarrow \forall_k \textrm{Tr}(P^k)=\textrm{Tr}(Q^k)$). Maybe we could use it for sets of points - by translating them into matrix e.g. $n\times n$: $$P_{ab} = \sum_{i=1..m} x^i_a x^i_b\qquad Q_{ab} = \sum_{i=1..m} y^i_a y^i_b \qquad \forall_{k=1..n}\textrm{Tr}(P^k)=^?\textrm{Tr}(Q^k).$$ Above formula looks like eigendecomposition $(P=\sum_i \lambda_i v^i v^{iT})$ if vectors are orthogonal and $m\leq n$, but generally it does not determine the used sets of points: for SRGs we have $m\approx 2n$ and above matrices turn out proportional to identity matrix like for POVMs.
One question is: for how many points above test works? (assume all have the same norm)
It trivially works for $m=1$ point, for two they can be opposite - zeroing the matrix, but it works otherwise (determining single angle), hence we need some independence assumption (?). Generally, for $m$ vectors spanning $n'$ dimensional subspace $(m\leq n'\leq n)$, they contain $m(n'-1)-n'(n'-1)/2=(m-n'/2)(n'-1)$ degrees of freedom modulo rotation, while above test uses $n$ degrees of freedom, from which all but $n'$ are trivial (zero eigenvalue). Hence we need $(m-n'/2)(n'-1)\leq n'$ condition. Is it sufficient?
We can also analogously use tests with higher order matrix (on tensor product) to increase the number of independent invariants, e.g. (corresponding to ladder-like graphs) $n^2 \times n^2$:
$$P_{ab,cd}=\sum_{ij} x^i_a x^i_c (x^i\cdot x^j) x^j_b x^j_d \qquad Q_{ab,cd}=\sum_{ij} y^i_a y^i_c (y^i\cdot y^j) y^j_b y^j_d$$ and testing if $\forall_{k=1..n^2 }\textrm{Tr}(P^k)=\textrm{Tr}(Q^k)$.
I have recently checked it for SRGs and it worked: distinguished all I have tested (up to 29 vertices). The question is how to prove it: what maximal number of points (assuming some independence) it always distinguishes? How this number changes with order of such method? Some example of third order: $P_{abc,def}=\sum_{ijk} x^i_a x^i_d x^j_b x^j_e x^k_c x^k_f (x^i\cdot x^j) (x^i\cdot x^k)(x^j\cdot x^k)$.
Any other way to test it in polynomial time?
Example of two non-isomorphic $m=16$ vertex SRGs of the same parameters we would like to distinguish (for any vertex permutation). Eigenspectrums of their adjacency matrices are highly degenerated - taking orthonomal basis of $n=6$ dimensional eigenspace, treating its columns(!) as vectors, they form very regular polyhedron: scalar products recreate neighborhood relation: has one value for all neighbors, second for all non-neighbors, like in schematic diagram on the right:
Update (2018-09-21): interesting comment from https://redd.it/9hdwnl : any graph isomorphism problem can be translated to above by putting points in basis $\{e_i\}$ and $\{e_i + e_j \textrm{ for each edge }(i,j)\}$. This construction restricts rotations to permutations. Hence, solving the above problem for $m\sim n^2$ would also solve graph isomorphism problem. For strongly regular graphs it suffice to do it for $m\sim 2n$.
Update (2018-09-22): there was pointed similarity to orthogonal Procrustes problem, which finds optimal rotation knowing which point should rotate to which. Here we don't know it - just have sets without order: there are $m!$ possibilities.