This paper investigates the impact of introducing disturbances into quadratic unconstrained binary optimization (QUBO) formulas to enhance the performance of both the quantum annealer (QA) and the GPU annealer (GPUA). We propose a disturbance insertion method to insert into QUBO formula coefficients some disturbances that are parameterized by the insertion ratio, Gaussian distribution mean, and standard deviation. By applying the proposed method to a QA (viz., the D-Wave Advantage annealer) and a GPUA (viz., the Compal Quantix solver) for solving two well-known combinatorial optimization problems, the traveling salesperson problem and the 0/1 knapsack problem, we identify appropriate disturbance parameters that facilitate the annealing process for better solving the two problems.
This paper investigates the impact of introducing disturbances into quadratic unconstrained binary optimization (QUBO) formulas to enhance the performance of both the quantum annealer (QA) and the GPU annealer (GPUA). We propose a disturbance insertion method to insert into QUBO formula coefficients some disturbances that are parameterized by the insertion ratio, Gaussian distribution mean, and standard deviation. By applying the proposed method to a QA (viz., the D-Wave Advantage annealer) and a GPUA (viz., the Compal Quantix solver) for solving two well-known combinatorial optimization problems, the traveling salesperson problem and the 0/1 knapsack problem, we identify appropriate disturbance parameters that facilitate the annealing process for better solving the two problems.
Annealers leverage quadratic unconstrained binary optimization (QUBO) formulas to address combinatorial optimization problems (COPs) and have shown potential to outperform classical computers. This paper examines three prominent types of annealers: quantum, digital, and GPU annealers. Quantum annealers (QAs) are exemplified by the D-Wave Advantage, which relies on the quantum tunneling phenomenon to rapidly locate the minimum-energy system state corresponding to the optimal solution to a COP. Digital annealers (DAs) are typified by the Fujitsu Digital Annealing Unit (DAU), which is based on a quantum-inspired digital architecture to perform parallel and real-time optimization calculations to solve a COP. GPU annealers (GPUAs) are exemplified by the Compal Quantix solver, which harnesses graphics processing units (GPUs) to conduct the diverse adaptive bulk search for the optimal COP solution. This paper first provides an introductory overview of the QA, DA, and GPUA, and then proceeds to benchmark their performance on solving various well-known COPs such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job-shop scheduling problems. Their performance is also compared with that of state-of-the-art algorithms running on classical computers. Through comprehensive performance benchmarks in terms of the solution quality and the execution time, we identify the strengths and weaknesses of each annealer. In addition, we also provide recommendations to improve the performance of each annealer. Specifically, we recommend using the genetic algorithm, the improved particle swarm optimization algorithm, and the ant colony optimization algorithm in all annealers, using quantum pausing, quenching, and reverse annealing in the QA, using built-in separated penalty terms, one-way/two-way one-hot constraints, and linear inequality constraints in the DA, and implementing some parallel algorithms in the GPUA for performance improvement.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related classical algorithms (CAs) running on classical computers in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.