Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm

Abstract

Current quantum annealing and quantum-inspired annealing devices have many usage limitations and are difficult to apply to real-scale problems. In particular, a major hardware limitation is the limited number of available variables (qubits). This paper proposes a problem relaxation method for the Quantum Minimum Fill-in (QMF) algorithm. QMF finds the ordering of matrix rows and columns that minimizes the incidence of fill-ins that occur when a direct solver is used to solve linear equations with sparse matrices. In general, the first few steps in the forward elimination of sparse matrices add the most fill-ins. Therefore, QMF was relaxed to order the rows and columns in only the first few steps. The results obtained using the Fixstars Amplify Annealing Engine, a quantum-inspired annealing device, show that the problem relaxation can be computed with 20 % – 60 % of the qubits for the original problem and that relaxation can be applied to larger problems. Furthermore, it is found that more solutions that satisfy the constraints can be obtained with problem relaxation and that the number of fill-ins is reduced. These results confirm that the proposed problem relaxation is effective for QMF.

Keywords

• Quantum annealing
• sparse matrix
• fill-in reduction
• ordering
• relaxation method