Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

Problem Relaxation Methods for Quantum Minimum Fill-in Algorithm

Tomoko Komiyama, Tomohiro Suzuki

Published Jan 1, 2023• 0 citations
Publisher

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.

DOI
10.1109/access.2023.3324378

Related papers

Sparse Matrix Ordering Method with a Quantum Annealing Approach and its Parameter Tuning

Tomoko Komiyama, Tomohiro Suzuki

Quantum annealing realizes quantum computers specialized for combinatorial optimization problems (COPs). A COP is formulated as a Hamiltonian, and quantum annealing obtains a solution by finding the ground state of the Hamiltonian. The ease of finding a solution depends on the weights assigned to the cost and constraint functions when formulating the problem. In other words, parameter tuning is essential in solving problems with quantum annealing. In the present paper, the problem of searching an ordering that reduces the fill-in for a sparse direct solver is formulated as a Hamiltonian, and quantum annealing finds the solution to this problem. We discuss the necessity and effectiveness of parameter tuning for solving COPs with quantum annealing. The results after weight tuning show that we can improve the rate of an optimal solution obtained by a maximum of 94% for${5\,\times \,5}$matrices, 68% for${6\,\times \,6}$matrices, and 27% for${7\,\times \,7}$matrices. Moreover, it is shown that giving high weights to the constraints we want to satisfy will not provide an optimal solution.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 1, 2021•9 citations

QUBO formulation using inequalities for problems with complex constraints

Tomoko Komiyama, Tomohiro Suzuki

Quantum annealing is an optimization technique that uses quantum fluctuation effects to search for solutions and is being applied as a metaheuristic method. Quantum annealing solves a problem expressed as quadratic unconstrained binary optimization (QUBO). Many practical problems have complex constraints, and formulating them can lead to third-order or higher expressions. In such cases, higher-order expressions have been converted to QUBO by order reduction. Various order reduction methods have been used, but they have issues, such as the need to add more auxiliary variables and difficulty in obtaining optimal solutions. This paper discusses a method for formulating problems with complex constraints using inequalities. In this approach, each constraint is defined as a linear function and added together to form an inequality. The inequality is then transformed to QUBO by introducing a slack variable. The application to the quantum minimum fill-in algorithm, a fill-in reduction ordering algorithm for sparse matrices, and the maximum satisfiability problem are also presented. The results of solving these problems with a quantum-inspired annealing machine show that higher-quality solutions are obtained with fewer variables than when using higher-order expressions with order reduction.

International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia)•Jan 18, 2024•5 citations

Generating Presence-Absence Matrices by Quantum Annealing

Philippe Codognet

We consider the problem of generating binary matrices with fixed sums for their rows and columns coefficients, i.e. with fixed margins. Such presence-absence (0/1) matrices are widely used in ecological research, for instance to represent the presence or absence of particular species in a particular habitat. Generating random matrices with fixed sums for their rows and their columns is an important issue in order to compare some given matrix presenting field data versus randomly generated matrices with similar characteristics (same sums on rows and columns) in order to test some hypothesis, i.e. when performing null model statistical analysis. We propose to model this problem in QUBO (Quadratic Unconstrained Binary Optimization) in order to solve it by quantum annealing. QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of “quantum-inspired” annealing solvers based on dedicated classical hardware. We present some experimental results achieved on the D-Wave Advantage quantum computer and on the Fixstars Amplify Annealing Engine.

IEEE/ACM International Workshop on Quantum Software Engineering (Q-SE)•May 1, 2023•2 citations

Experimental Analysis of Quantum Annealing for Satisfiability Problems

Remma Ukaku, Tomohisa Kawakami, Hiroyuki Tomiyama

Quantum computing has emerged as a promising method for solving combinatorial optimization problems. These problems are often encoded as the Satisfiability (SAT) problem. In this study, we explore the quantum annealing based approach to solving the SAT problems. We conduct experiments on uniformly random 3-CNF instances that have 400 propositional variables and 1,000 to 2,499 clauses. We measure the time required to solve them using Fixstars Amplify Annealing Engine. The results show that the monotonic increase in solving time as the number of clauses increases, except for a discontinuity point at approximately 1,800 clauses. In addition, we observe some cases of false UNSAT reports. Our findings demonstrate both the characteristics and the limitations of this quantum annealing based solver. We plan to reproduce the solver on a local machine to inspect the performance when varying the parameters of the quantum annealing and the environment.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Oct 12, 2025•0 citations

RSQC: Recursive Sparse QUBO Construction for Quantum Annealing Machines

Jianwen Luo, Yuhao Shu, Yajun Ha

Quantum annealing algorithms have shown commercial potential in solving some instances of combinatorial optimization problems. However, existing mapping for general optimization problems into a compatible format for quantum annealing yields dense topology and complicated weighting, which limits the size of solvable problems on practical quantum annealing machines. To address this issue, we propose a novel mapping framework with three new techniques. First, to address the issue from general constraints, we introduce a recursive methodology to map constraints into interconnected Boolean gates and small algebraic cliques, which yields sparse topology and hardware-friendly biases/interactions. Second, to better address frequently-used constraints, we introduce a specialized penalty set based on this methodology with detailed optimizations. Third, to address the issue from the objective, we reformulate the complicated objective into a single multi-bit variable and apply binary search to its range, which turns each search step into a constraint-only problem. Compared with the state-of-the-art, experimental results and analysis over an exhaustive scan for operand bit-widths from 1 to 64 show that: (1) the growth order of the number of physical qubits with regard to operand bit-widths is reduced fromO(w2) toO(w), while the number is reduced by a factor of 10-1 in the best case; (2) the dynamic range of biases/interactions is reduced fromO(22w) to−2in the best case. For the same optimization problem, our framework reduces the requirement of the number of physical qubits and machine precision, and shortens the time from problem to machine.

IEEE Transactions on Computers•Apr 4, 2025•2 citations

Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm

Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata

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.

arXiv:2012.10135•IEEE International Conference on Industrial Engineering and Applications (ICIEA)•Apr 23, 2021•20 citations
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.
Quantum annealing realizes quantum computers specialized for combinatorial optimization problems (COPs). A COP is formulated as a Hamiltonian, and quantum annealing obtains a solution by finding the ground state of the Hamiltonian. The ease of finding a solution depends on the weights assigned to the cost and constraint functions when formulating the problem. In other words, parameter tuning is essential in solving problems with quantum annealing. In the present paper, the problem of searching an ordering that reduces the fill-in for a sparse direct solver is formulated as a Hamiltonian, and quantum annealing finds the solution to this problem. We discuss the necessity and effectiveness of parameter tuning for solving COPs with quantum annealing. The results after weight tuning show that we can improve the rate of an optimal solution obtained by a maximum of 94% for5 × 5{5\,\times \,5}5×5matrices, 68% for6 × 6{6\,\times \,6}6×6matrices, and 27% for7 × 7{7\,\times \,7}7×7matrices. Moreover, it is shown that giving high weights to the constraints we want to satisfy will not provide an optimal solution.
Quantum annealing is an optimization technique that uses quantum fluctuation effects to search for solutions and is being applied as a metaheuristic method. Quantum annealing solves a problem expressed as quadratic unconstrained binary optimization (QUBO). Many practical problems have complex constraints, and formulating them can lead to third-order or higher expressions. In such cases, higher-order expressions have been converted to QUBO by order reduction. Various order reduction methods have been used, but they have issues, such as the need to add more auxiliary variables and difficulty in obtaining optimal solutions. This paper discusses a method for formulating problems with complex constraints using inequalities. In this approach, each constraint is defined as a linear function and added together to form an inequality. The inequality is then transformed to QUBO by introducing a slack variable. The application to the quantum minimum fill-in algorithm, a fill-in reduction ordering algorithm for sparse matrices, and the maximum satisfiability problem are also presented. The results of solving these problems with a quantum-inspired annealing machine show that higher-quality solutions are obtained with fewer variables than when using higher-order expressions with order reduction.
We consider the problem of generating binary matrices with fixed sums for their rows and columns coefficients, i.e. with fixed margins. Such presence-absence (0/1) matrices are widely used in ecological research, for instance to represent the presence or absence of particular species in a particular habitat. Generating random matrices with fixed sums for their rows and their columns is an important issue in order to compare some given matrix presenting field data versus randomly generated matrices with similar characteristics (same sums on rows and columns) in order to test some hypothesis, i.e. when performing null model statistical analysis. We propose to model this problem in QUBO (Quadratic Unconstrained Binary Optimization) in order to solve it by quantum annealing. QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of “quantum-inspired” annealing solvers based on dedicated classical hardware. We present some experimental results achieved on the D-Wave Advantage quantum computer and on the Fixstars Amplify Annealing Engine.
Quantum computing has emerged as a promising method for solving combinatorial optimization problems. These problems are often encoded as the Satisfiability (SAT) problem. In this study, we explore the quantum annealing based approach to solving the SAT problems. We conduct experiments on uniformly random 3-CNF instances that have 400 propositional variables and 1,000 to 2,499 clauses. We measure the time required to solve them using Fixstars Amplify Annealing Engine. The results show that the monotonic increase in solving time as the number of clauses increases, except for a discontinuity point at approximately 1,800 clauses. In addition, we observe some cases of false UNSAT reports. Our findings demonstrate both the characteristics and the limitations of this quantum annealing based solver. We plan to reproduce the solver on a local machine to inspect the performance when varying the parameters of the quantum annealing and the environment.
Quantum annealing algorithms have shown commercial potential in solving some instances of combinatorial optimization problems. However, existing mapping for general optimization problems into a compatible format for quantum annealing yields dense topology and complicated weighting, which limits the size of solvable problems on practical quantum annealing machines. To address this issue, we propose a novel mapping framework with three new techniques. First, to address the issue from general constraints, we introduce a recursive methodology to map constraints into interconnected Boolean gates and small algebraic cliques, which yields sparse topology and hardware-friendly biases/interactions. Second, to better address frequently-used constraints, we introduce a specialized penalty set based on this methodology with detailed optimizations. Third, to address the issue from the objective, we reformulate the complicated objective into a single multi-bit variable and apply binary search to its range, which turns each search step into a constraint-only problem. Compared with the state-of-the-art, experimental results and analysis over an exhaustive scan for operand bit-widths from 1 to 64 show that: (1) the growth order of the number of physical qubits with regard to operand bit-widths is reduced fromO(w2) toO(w), while the number is reduced by a factor of 10-1 in the best case; (2) the dynamic range of biases/interactions is reduced fromO(22w) to−2in the best case. For the same optimization problem, our framework reduces the requirement of the number of physical qubits and machine precision, and shortens the time from problem to machine.
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.