Quantum polynomial-time conjugacy in metabelian groups

Abstract

We prove that the conjugacy problem in finitely presented metabelian groups with a fixed number of generators is solvable in bounded-error quantum polynomial time, uniformly in the defining relations of the group. Both the group presentation and the words representing the elements are part of the input. The main ingredient is a quantum polynomial-time algorithm for computing all multiplicative relations among a fixed number of units in a commutative affine ℤ-algebra presented with a fixed number of variables. The algorithm reduces the problem to computations in finite-dimensional algebras over ℚ and finite rings by identifying the lattice of exponent vectors whose corresponding products are algebraic over the coefficient field. An effective arithmetic splitting combines the rational and finite-ring computations. The proof uses effective bounds for polynomial equations, algorithms for finite-dimensional commutative algebras, quantum integer factorization, and finite abelian hidden-subgroup algorithms.

Modular representations of metabelian groups
Lorenzo Traldi
arXiv26 Oct 2026PreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
Finite presentations of metabelian groups: effective enumeration via Laurent relations
Achyuth Jayadevan
arXiv9 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Logic & foundationsarXiv
Polynomial-time isomorphism test for solvable groups with abelian Sylow subgroups
Saveliy V. Skresanov
arXiv8 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
The Complexity of Conjugacy, Orbit Equivalence, and von Neumann Equivalence of Actions of Nonamenable Groups
Eusebio Gardella, Martino Lupini
Memoirs of the American Mathematical Society10 Jul 2026Peer-reviewedLicence not statedFull text6 citedMathematical physicsOpenAlex
Conjugacy and period in symmetric diagram groups
Matteo Tarocchi
arXiv4 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{miasnikov2026quantum,
  title = {{Quantum polynomial-time conjugacy in metabelian groups}},
  author = {Alexei Miasnikov and Alexander Ushakov},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27250},
  eprint = {2610.27250},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27250},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Quantum polynomial-time conjugacy in metabelian groups
AU  - Alexei Miasnikov
AU  - Alexander Ushakov
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.27250
UR  - https://arxiv.org/abs/2610.27250
AB  - We prove that the conjugacy problem in finitely presented metabelian groups with a fixed number of generators is solvable in bounded-error quantum polynomial time, uniformly in the defining relations of the group. Both the group presentation and the words representing the elements are part of the input. The main ingredient is a quantum polynomial-time algorithm for computing all multiplicative relations among a fixed number of units in a commutative affine ℤ-algebra presented with a fixed number of variables. The algorithm reduces the problem to computations in finite-dimensional algebras over ℚ and finite rings by identifying the lattice of exponent vectors whose corresponding products are algebraic over the coefficient field. An effective arithmetic splitting combines the rational and finite-ring computations. The proof uses effective bounds for polynomial equations, algorithms for finite-dimensional commutative algebras, quantum integer factorization, and finite abelian hidden-subgroup algorithms.
ER  -

Abstract

Related

Cite