Hyperdeterminants are Hard in Four Dimensions

Hyperdeterminants are high dimensional analogues of determinants, associated with tensors of formats generalizing square matrices. First conceived for 222 tensors by Cayley, they were developed in generality by Gelfand, Kapranov and Zelevinsky. Yet, hyperdeterminants in three or more dimensions are long conjectured to be VNP-Hard to compute, akin to permanents and unlike determinants. Even deciding if the hyperdeterminant of a given tensor is zero is conjectured to be NP-Hard. We prove this decision problem is NP-Hard under randomised reductions, in four or more dimensions. In quantum information, hyperdeterminants measure quantum entanglement, under the name ``tangle''. Our reduction implies that it is hard to tell if four or more qudits are tangled, unless quantum computers can efficiently solve NP-complete problems.

‍