Solving the Turbine Balancing Problem using Quantum Annealing
2405.06412
0
0
🌀
Abstract
Quantum computing has the potential for disruptive change in many sectors of industry, especially in materials science and optimization. In this paper, we describe how the Turbine Balancing Problem can be solved with quantum computing, which is the NP-hard optimization problem of analytically balancing rotor blades in a single plane as found in turbine assembly. Small yet relevant instances occur in industry, which makes the problem interesting for early quantum computing benchmarks. We model it as a Quadratic Unconstrained Binary Optimization problem and compare the performance of a classical rule-based heuristic and D-Wave Systems' Quantum Annealer Advantage_system4.1. In this case study, we use real-world as well as synthetic datasets and observe that the quantum hardware significantly improves an actively used heuristic's solution for small-scale problem instances with bare disk imbalance in terms of solution quality. Motivated by this performance gain, we subsequently design a quantum-inspired classical heuristic based on simulated annealing that achieves extremely good results on all given problem instances, essentially solving the optimization problem sufficiently well for all considered datasets, according to industrial requirements.
Create account to get full access
Overview
- The paper explores how quantum computing can be used to solve the Turbine Balancing Problem, which is a complex optimization problem in materials science and engineering.
- The researchers model the problem as a Quadratic Unconstrained Binary Optimization problem and compare the performance of a classical rule-based heuristic and a quantum annealer from D-Wave Systems.
- The results show that the quantum hardware significantly improves the solution quality for small-scale problem instances compared to the classical heuristic.
- Motivated by this performance gain, the researchers design a quantum-inspired classical heuristic based on simulated annealing that achieves extremely good results on all the problem instances.
Plain English Explanation
The paper discusses how quantum computers could be used to solve a specific engineering problem called the Turbine Balancing Problem. This is a tricky optimization problem that comes up when assembling turbines, where you need to analytically balance the rotor blades in a single plane.
The researchers took this problem and modeled it as a type of optimization problem that quantum computers are well-suited for. They compared how a classical computer algorithm and a quantum computer (specifically, D-Wave's Quantum Annealer) performed on this problem. For small-scale versions of the problem, the quantum computer was able to find significantly better solutions than the classical algorithm.
Inspired by this, the researchers then designed a new classical algorithm that was based on the quantum approach. This new classical algorithm was able to solve the optimization problem very well for all the test cases, meeting the requirements for real-world industrial use.
The key insight here is that quantum computers have the potential to outperform classical computers on certain types of optimization problems, like the Turbine Balancing Problem. While quantum computers are still quite new and limited, this research suggests they could be useful tools for solving complex optimization challenges, particularly in fields like materials science and engineering.
Technical Explanation
The researchers modeled the Turbine Balancing Problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, which is a type of optimization problem that is well-suited for quantum computers. They compared the performance of a classical rule-based heuristic algorithm against D-Wave's Quantum Annealer Advantage_system4.1 on both real-world and synthetic datasets.
The results showed that the quantum hardware was able to significantly improve the solution quality compared to the classical heuristic for small-scale problem instances. Motivated by this, the researchers then designed a quantum-inspired classical heuristic based on simulated annealing that achieved extremely good results on all the problem instances, essentially solving the optimization problem sufficiently well for the considered industrial requirements.
Critical Analysis
The paper provides a promising demonstration of how quantum computing can outperform classical methods on certain optimization problems, even with the current limitations of quantum hardware. However, the researchers acknowledge that the problem instances they considered were relatively small-scale, and it's unclear how the performance would scale to larger, more complex problems.
Additionally, the quantum-inspired classical heuristic they developed seems to be the most practical solution for real-world industrial use, rather than directly using the quantum hardware. This highlights the importance of developing hybrid quantum-classical algorithms that can leverage the strengths of both approaches.
Further research is needed to better understand the limitations and potential of quantum computing for optimization problems in materials science and other domains. Careful benchmarking and comparisons to state-of-the-art classical methods will be crucial for assessing the true value of quantum computing in these applications.
Conclusion
This research demonstrates the potential of quantum computing to outperform classical methods on certain optimization problems, particularly in the context of materials science and engineering. While the current quantum hardware is still limited, the insights gained from this work suggest that quantum-inspired classical algorithms may be a fruitful approach for solving complex optimization challenges in industry.
As quantum computing technology continues to evolve, this research highlights the importance of exploring the use of quantum annealers and other quantum computing approaches to tackle optimization problems that are difficult for classical computers. The findings could have far-reaching implications for a wide range of industries and applications.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
🛠️
Dynamic Optimization on Quantum Hardware: Feasibility for a Process Industry Use Case
Dennis Michael Nenno, Adrian Caspari
0
0
The quest for real-time dynamic optimization solutions in the process industry represents a formidable computational challenge, particularly within the realm of applications like model-predictive control, where rapid and reliable computations are critical. Conventional methods can struggle to surmount the complexities of such tasks. Quantum computing and quantum annealing emerge as textit{avant-garde} contenders to transcend conventional computational constraints. We convert a dynamic optimization problem, {characterized by an optimization problem with a system of differential-algebraic equations embedded}, into a Quadratic Unconstrained Binary Optimization problem, enabling quantum computational approaches. The empirical findings synthesized from classical methods, simulated annealing, quantum annealing via D-Wave's quantum annealer, and hybrid solver methodologies, illuminate the intricate landscape of computational prowess essential for tackling complex and high-dimensional dynamic optimization problems. Our findings suggest that while quantum annealing is a maturing technology that currently does not outperform state-of-the-art classical solvers, continuous improvements could eventually aid in increasing efficiency within the chemical process industry.
4/29/2024
Towards Robust Benchmarking of Quantum Optimization Algorithms
David Bucher, Nico Kraus, Jonas Blenninger, Michael Lachner, Jonas Stein, Claudia Linnhoff-Popien
0
0
Benchmarking the performance of quantum optimization algorithms is crucial for identifying utility for industry-relevant use cases. Benchmarking processes vary between optimization applications and depend on user-specified goals. The heuristic nature of quantum algorithms poses challenges, especially when comparing to classical counterparts. A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches. This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks. We discuss (1) application-specific algorithm choice, ensuring every solver is provided with the most fitting mathematical formulation of a problem; (2) the selection of benchmark data, including hard instances and real-world samples; (3) the choice of a suitable holistic figure of merit, like time-to-solution or solution quality within time constraints; and (4) equitable hyperparameter training to eliminate bias towards a particular method. The proposed guidelines are tested across three benchmarking scenarios, utilizing the Max-Cut (MC) and Travelling Salesperson Problem (TSP). The benchmarks employ classical mathematical algorithms, such as Branch-and-Cut (BNC) solvers, classical heuristics, Quantum Annealing (QA), and the Quantum Approximate Optimization Algorithm (QAOA).
5/14/2024
Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing
Jan-Nico Zaech, Martin Danelljan, Tolga Birdal, Luc Van Gool
0
0
Adiabatic quantum computing (AQC) is a promising approach for discrete and often NP-hard optimization problems. Current AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for many computer vision tasks. Despite requiring multiple measurements from the noisy AQC, current approaches only utilize the best measurement, discarding information contained in the remaining ones. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
5/2/2024
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem
Alessandro Gherardi, Alberto Leporati
0
0
Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.
6/13/2024