  Quantum annealing and D-Wave quantum annealer attracted considerable
attention for their ability to solve combinatorial optimization problems. In
order to solve other type of optimization problems, it is necessary to apply
certain kinds of mathematical transformations. However, linear constraints
reduce the size of problems that can be represented in quantum annealers, owing
to the sparseness of connections between qubits. For example, the quadratic
assignment problem (QAP) with linear equality constraints can be solved only up
to size 12 in the quantum annealer D-Wave Advantage, which has 5640 qubits. To
overcome this obstacle, Ohzeki developed a method for relaxing the linear
equality constraints and numerically verified the effectiveness of this method
with some target problems, but others remain unsolvable. In particular, it is
difficult to obtain feasible solutions to problems with hard constraints, such
as the QAP. We therefore propose a method for solving the QAP with quantum
annealing by applying a post-processing bit-flip heuristic algorithm to
solutions obtained by the Ohzeki method. In a numerical experiment, we solved a
sparse QAP by the proposed method. This sparse QAP has been used in areas such
as item listing on an E-commerce website. We successfully solved a QAP of size
19 with high accuracy for the first time using D-Wave Advantage. We also
confirmed that the bit-flip heuristic algorithm moves infeasible solutions to
nearby feasible solutions in terms of Hamming distance with good computational
efficiency.
