Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm
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 Qu...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10285083/ |
| _version_ | 1797654015597608960 |
|---|---|
| author | Tomoko Komiyama Tomohiro Suzuki |
| author_facet | Tomoko Komiyama Tomohiro Suzuki |
| author_sort | Tomoko Komiyama |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T16:53:15Z |
| format | Article |
| id | doaj.art-44d4e94365484208a6387467e2e9906a |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-11T16:53:15Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-44d4e94365484208a6387467e2e9906a2023-10-20T23:00:30ZengIEEEIEEE Access2169-35362023-01-011111442411443110.1109/ACCESS.2023.332437810285083Problem Relaxation Methods for Quantum Minimum Fill-in AlgorithmTomoko Komiyama0https://orcid.org/0009-0000-9276-9498Tomohiro Suzuki1https://orcid.org/0000-0002-3091-1302Integrated Graduate School of Medicine, Engineering, and Agricultural Sciences, University of Yamanashi, Kofu, JapanIntegrated Graduate School of Medicine, Engineering, and Agricultural Sciences, University of Yamanashi, Kofu, JapanCurrent 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.https://ieeexplore.ieee.org/document/10285083/Quantum annealingsparse matrixfill-in reductionorderingrelaxation method |
| spellingShingle | Tomoko Komiyama Tomohiro Suzuki Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm IEEE Access Quantum annealing sparse matrix fill-in reduction ordering relaxation method |
| title | Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm |
| title_full | Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm |
| title_fullStr | Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm |
| title_full_unstemmed | Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm |
| title_short | Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm |
| title_sort | problem relaxation methods for quantum minimum fill in algorithm |
| topic | Quantum annealing sparse matrix fill-in reduction ordering relaxation method |
| url | https://ieeexplore.ieee.org/document/10285083/ |
| work_keys_str_mv | AT tomokokomiyama problemrelaxationmethodsforquantumminimumfillinalgorithm AT tomohirosuzuki problemrelaxationmethodsforquantumminimumfillinalgorithm |