Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing

• URL: http://arxiv.org/abs/2307.14419v1
• Date: Wed, 26 Jul 2023 18:00:02 GMT
• Title: Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing
• Authors: Ant\'on Makarov, M\'arcio M. Taddei, Eneko Osaba, Giacomo Franceschetto, Esther Villar-Rodriguez, Izaskun Oregi
• Abstract summary: Satellite image acquisition scheduling is a problem that is omnipresent in the earth observation field. We present two QUBO formulations for the problem, using different approaches to handle the non-trivial constraints. We also provide practical guidelines on the size limits of problem instances that can be realistically solved on current quantum computers.
• Score: 0.786197460675312
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Satellite image acquisition scheduling is a problem that is omnipresent in the earth observation field; its goal is to find the optimal subset of images to be taken during a given orbit pass under a set of constraints. This problem, which can be modeled via combinatorial optimization, has been dealt with many times by the artificial intelligence and operations research communities. However, despite its inherent interest, it has been scarcely studied through the quantum computing paradigm. Taking this situation as motivation, we present in this paper two QUBO formulations for the problem, using different approaches to handle the non-trivial constraints. We compare the formulations experimentally over 20 problem instances using three quantum annealers currently available from D-Wave, as well as one of its hybrid solvers. Fourteen of the tested instances have been obtained from the well-known SPOT5 benchmark, while the remaining six have been generated ad-hoc for this study. Our results show that the formulation and the ancilla handling technique is crucial to solve the problem successfully. Finally, we also provide practical guidelines on the size limits of problem instances that can be realistically solved on current quantum computers.

Related papers

• Quantum Algorithms for Drone Mission Planning [0.0]
  Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. We investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods.
  arXiv  Detail & Related papers  (2024-09-27T10:58:25Z)
• Quantum Optimization Methods for Satellite Mission Planning [0.3252295747842729]
  The ever-growing amount of satellites in orbit underscores the need to operate them efficiently. 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.
  arXiv  Detail & Related papers  (2024-04-08T13:36:29Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. 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.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
  arXiv  Detail & Related papers  (2023-06-07T12:19:22Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Analyzing the behaviour of D'WAVE quantum annealer: fine-tuning parameterization and tests with restrictive Hamiltonian formulations [1.035593890158457]
  D'WAVE Systems' quantum-annealer can be use to solve optimization problems by translating them into an energy minimization problem. This study is focused on providing useful insights and information into the behaviour of the quantum-annealer when addressing real-world optimization problems.
  arXiv  Detail & Related papers  (2022-07-01T07:54:26Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Quantum Annealing Approaches to the Phase-Unwrapping Problem in Synthetic-Aperture Radar Imaging [0.32622301272834525]
  We explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real.
  arXiv  Detail & Related papers  (2020-10-01T07:04:02Z)
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer [0.35232085374661287]
  We compare state-of-the-art classical optimisation methods to a D-Wave 2000Q quantum annealer for the planning of Earth observation missions. We find that the solution quality of the quantum annealer is comparable to the method used operationally for small problem instances, but degrades rapidly due to the limited precision of the quantum annealer.
  arXiv  Detail & Related papers  (2020-06-17T08:55:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.