Finding Hadamard matrices by a quantum annealing machine
Finding a Hadamard matrix (H-matrix) among the set of all binary matrices of corresponding order is a hard problem. We propose a method to formulate the Hamiltonian of finding H-matrix problem and address its implementation limitation on existing quantum annealing machine (QAM) that allows up to only 2 interacting qubits, whereas the problem naturally introduces higher order terms. For an M-order H-matrix, such a limitation increases the complexity from O(M^2) to O(M^3), which makes the formulation of the Hamiltonian too exhaustive to do by hand. We use symbolic computing techniques to manage this problem. Three related cases are discussed: (1) finding N<M orthogonal binary vectors, (2) finding M orthogonal binary vectors which is equivalent to finding a H-matrix, and (3) finding N-deleted vectors of an M-order H-matrix. Tentative solutions of the problems by a 2-body simulated annealing software, the D-Wave’s neal, and on an actual quantum annealing hardware by using D-Wave quantum annealer DW2000Q, are also discussed.