We consider the problem of transforming a given symmetric matrix as close to block diagonal as possible by symmetric permutations of its rows and columns. Such a problem arises, for example, as a preprocessing for the block Jacobi method for the symmetric eigenvalue problem. To solve this problem on a quantum annealing machine, Teramoto et al. proposed its QUBO (Quadratic Unconstrained Binary Optimization) formulation and strategies for embedding the resulting QUBO into the Pegasus network of the D-Wave Advantage quantum annealer. In this paper, we propose two more embedding strategies based on the minimum-cost flow and integer multi-commodity flow. We also propose an alternative QUBO formulation for which the connectivity graph has a more local structure. Numerical experiments show that our new QUBO formulation requires less physical qubits when embedding the problem into D-Wave Advantage’s Pegasus network.