Integral tensor isomorphism decidable in quantum polynomial time
Integral Tensor Isomorphism via Cubic Rings and Lattice Methods
Computational Complexity
Summary
Determining when two complex 3D arrays of numbers are essentially the same is a difficult math problem. The authors show that this problem, for a specific size of arrays with integer entries, can be solved efficiently using quantum computers. They break the problem into smaller parts involving number theory and lattice structures, then use existing algorithms and quantum factorization to decide isomorphism. Their work connects advanced algebra and quantum computing to solve a problem previously unresolved in classical terms.
What this means in practice
- •For quantum algorithm developers: Use quantum algorithms to decide integral tensor isomorphism problems efficiently, potentially improving quantum complexity theory toolsets.
- •For cryptography engineers: Assess cryptographic protocols relying on lattice problems by understanding how integral tensor isomorphism can be solved in bounded-error quantum polynomial time.
A theory result. No direct application yet.
Authors
Thomas Huffstutler
Abstract
We prove that isomorphism of integral $2\times3\times3$ tensors under $\mathrm{GL}_2(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})$ is decidable in bounded-error quantum polynomial time. For a tensor $T=(A,B)$ with nonzero determinant form $\det(xA-yB)$, we use the parametrization of Wood by balanced modules to reduce the isomorphism problem to principality tests for compatible lattices, and use the algorithms of Bley, Hofmann, and Johnston to solve this in BQP. When the determinant form vanishes identically, we get either an integral $2\times2\times2$ core, or a polynomial kernel vector of degree one or two. The linear-kernel case yields another compatible lattice problem, while the quadratic-kernel case reduces to a fixed system of polynomial congruences and unimodular lifting. A quantifier-elimination argument decides these congruences in deterministic polynomial time given the prime factorization of the modulus, which quantum integer factorization supplies. Finally, we show that zero padding preserves integral $2\times2\times2$ tensor isomorphism, yielding a polynomial-time reduction from real-quadratic principality to the identically singular $2\times3\times3$ problem.