Abstract NP-hard optimization problems scale very rapidly with problem size, becoming unsolvable with brute force methods, even with supercomputing resources. Typically, such problems have been approximated with heuristics. However, these methods still take a long time and are not guaranteed to find an optimal solution. Quantum computing offers the possibility of producing significant speed-up and improved solution quality. Current quantum annealing (QA) devices are designed to solve difficult optimization problems, but they are limited by hardware size and qubit connectivity restrictions. We present a novel heterogeneous computing stack that combines QA and classical machine learning, allowing the use of QA on problems larger than the hardware limits of the quantum device. These results represent experiments on a real-world problem represented by the weighted k -clique problem. Through this experiment, we provide insight into the state of quantum machine learning.
Abstract NP-hard optimization problems scale very rapidly with problem size, becoming unsolvable with brute force methods, even with supercomputing resources. Typically, such problems have been approximated with heuristics. However, these methods still take a long time and are not guaranteed to find an optimal solution. Quantum computing offers the possibility of producing significant speed-up and improved solution quality. Current quantum annealing (QA) devices are designed to solve difficult optimization problems, but they are limited by hardware size and qubit connectivity restrictions. We present a novel heterogeneous computing stack that combines QA and classical machine learning, allowing the use of QA on problems larger than the hardware limits of the quantum device. These results represent experiments on a real-world problem represented by the weighted k -clique problem. Through this experiment, we provide insight into the state of quantum machine learning.
Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. In this paper, we study how to use quantum computing to solve BP problems. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. Therefore, we propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.
Satellite communication (SatCom) systems play a vital role in providing global connectivity and enable a wide range of applications, including Internet of Things (IoT) connectivity for remote areas, such as forests and oceans. Two crucial resource allocation challenges in SatCom are beam placement (BP) and frequency assignment (FA) problems, which involve the clique covering (CC) and graph coloring (GC) problems, respectively. Conventional solutions for these problems incur excessive computational cost, which is intractable for classical computers. A promising approach is to formulate these problems using the Ising model, construct their Hamiltonians, and then solve them efficiently by a quantum computer. However, the current quantum computers have very limited hardware and can only handle rather small inputs. To overcome this limitation, we propose a hybrid-quantum-classical-computational pipeline where an efficient hamiltonian reduction method is the key for solving large CC/GC instances. Through experiments on real quantum computers, our reduction method outperforms commercial solutions, allowing quantum annealers to handle significantly larger BP/FA instances while maintaining high probability to achieve feasible solutions and near-optimal performance. Although the inherent hardness of the CC/GC problems cannot be overcome by quantum computing, our research contributes to the early exploration of quantum computing in the context of the complex optimization problems in SatCom systems, particularly in the realm of IoT connectivity for remote areas.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
Summary Recent progress in geophysics can be attributed to developments in heterogeneous HPC architectures, with one of the next major leaps being forecasted to be due to quantum computers. It is, however, very difficult to find the right combination of hardware, algorithms and a use-case. This is especially true for applications which have to be simultaneously: relevant and operating at scales where problems become difficult to solve using classical means. Maximizing stack-power for improved near surface characterization and velocity model building, an NP-hard combinatorial optimization problem, appears to naturally fit a particular type of quantum computing known as quantum annealing. We present the quantum-native formulation of this problem. Furthermore, in order to improve the probability of success we embed it in a hybrid classical-quantum workflow. We present the results on controlled experiments run using a 5000-qubit machine and discuss the impact of different classical to quantum problem re-formulations.
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size---opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
Satellite mission planning for Earth observation satellites is a combinatorial optimization problem that consists of selecting the optimal subset of imaging requests, subject to constraints, to be fulfilled during an orbit pass of a satellite. The ever-growing amount of satellites in orbit underscores the need to operate them efficiently, which requires solving many instances of the problem in short periods of time. However, current classical algorithms often fail to find the global optimum or take too long to execute. Here, we approach the problem from a quantum computing point of view, which offers a promising alternative that could lead to significant improvements in solution quality or execution speed in the future. To this end, we study a planning problem with a variety of intricate constraints and discuss methods to encode them for quantum computers. Additionally, we experimentally assess the performance of quantum annealing and the quantum approximate optimization algorithm on a realistic and diverse dataset. Our results identify key aspects like graph connectivity and constraint structure that influence the performance of the methods. We explore the limits of today’s quantum algorithms and hardware, providing bounds on the problems that can be currently solved successfully and showing how the solution degrades as the complexity grows. This work aims to serve as a baseline for further research in the field and establish realistic expectations on current quantum optimization capabilities.