Swap operators and the quantum max cut

 

Swap operators act on the space $(\mathbb{C}^d)^{\otimes{n}}$ of n qudits by exchanging tensor factors of $(\mathbb{C}^d)^{\otimes{n}}$. The algebra they generate (called the d-swap matrix algebra) is a subalgebra of $M_{d^n}(\mathbb{C}).$ Classically, in physics literature, the case d=2 of qubits has received the most attention. However, in this talk we discuss the properties of the d-swap matrix algebra for the case of a general d. This algebra is semisimple by Maschke’s theorem and its block decomposition can be computed by the Schur-Weyl duality. We also give a precise presentation of the d-swap matrix algebra.

 

As an application, we introduce and discuss the Quantum Max d-Cut (d-QMC) problem. It is a generalization of the QMC (Quantum Max d-Cut with d=2) that has emerged as a test-problem for designing approximation algorithms in quantum physics. For fixed n and a graph G on n vertices, the objective function, the d-QMC Hamiltonian, is defined as a linear expression in the swap operators on $(\mathbb{C}^d)^{\otimes{n}}$. Using the block decomposition of the swap operators, we compute the maximum eigenvalue of the d-QMC Hamiltonian for a clique. Moreover, using a suitable clique decomposition we solve the d-QMC problem for a larger class of graphs, including star graphs