Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImage Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a comparison study of state-of-the-art classical optimisation methods to a D-Wave 2000Q quantum annealer for the planning of Earth observation missions. The problem is to acquire high value images while obeying the attitude manoeuvring constraint of the satellite. In order to investigate close to real-world problems, we created benchmark problems by simulating realistic scenarios. Our results show that a tuned quantum annealing approach can run faster than a classical exact solver for some of the problem instances. Moreover, we find that the solution quality of the quantum annealer is comparable to the heuristic method used operationally for small problem instances, but degrades rapidly due to the limited precision of the quantum annealer.
rate research
Read More
Optimal flight gate assignment is a highly relevant optimization problem from airport management. Among others, an important goal is the minimization of the total transit time of the passengers. The corresponding objective function is quadratic in the binary decision variables encoding the flight-to-gate assignment. Hence, it is a quadratic assignment problem being hard to solve in general. In this work we investigate the solvability of this problem with a D-Wave quantum annealer. These machines are optimizers for quadratic unconstrained optimization problems (QUBO). Therefore the flight gate assignment problem seems to be well suited for these machines. We use real world data from a mid-sized German airport as well as simulation based data to extract typical instances small enough to be amenable to the D-Wave machine. In order to mitigate precision problems, we employ bin packing on the passenger numbers to reduce the precision requirements of the extracted instances. We find that, for the instances we investigated, the bin packing has little effect on the solution quality. Hence, we were able to solve small problem instances extracted from real data with the D-Wave 2000Q quantum annealer.
We perform an in-depth comparison of quantum annealing with several classical optimisation techniques, namely thermal annealing, Nelder-Mead, and gradient descent. We begin with a direct study of the 2D Ising model on a quantum annealer, and compare its properties directly with those of the thermal 2D Ising model. These properties include an Ising-like phase transition that can be induced by either a change in quantum-ness of the theory, or by a scaling the Ising couplings up or down. This behaviour is in accord with what is expected from the physical understanding of the quantum system. We then go on to demonstrate the efficacy of the quantum annealer at minimising several increasingly hard two dimensional potentials. For all the potentials we find the general behaviour that Nelder-Mead and gradient descent methods are very susceptible to becoming trapped in false minima, while the thermal anneal method is somewhat better at discovering the true minimum. However, and despite current limitations on its size, the quantum annealer performs a minimisation very markedly better than any of these classical techniques. A quantum anneal can be designed so that the system almost never gets trapped in a false minimum, and rapidly and successfully minimises the potentials.
We investigate the occurrence of the phenomenon of many-body localization (MBL) on a D-Wave 2000Q programmable quantum annealer. We study a spin-1/2 transverse-field Ising model defined on a Chimera connectivity graph, with random exchange interactions and random longitudinal fields. On this system we experimentally observe a transition from an ergodic phase to an MBL phase. We first theoretically show that the MBL transition is induced by a critical disorder strength for individual energy eigenstates in a Chimera cell, which follows from the analysis of the mean half-system block entanglement, as measured by the von Neumann entropy. We show the existence of an area law for the block entanglement over energy eigenstates for the MBL phase, which stands in contrast with an extensive volume scaling in the ergodic phase. The identification of the MBL critical point is performed via the measurement of the maximum variance of the mean block entanglement over the disorder ensemble as a function of the disorder strength. Our results for the energy density phase diagram also show the existence of a many-body mobility edge in the energy spectrum. The time-independent disordered Ising Hamiltonian is then experimentally realized by applying the reverse annealing technique allied with a pause-quench protocol on the D-Wave device. We then characterize the MBL critical point through magnetization measurements at the end of the annealing dynamics, obtaining results compatible with our theoretical predictions for the MBL transition.
The application in cryptography of quantum algorithms for prime factorization fostered the interest in quantum computing. However, quantum computers, and particularly quantum annealers, can also be helpful to construct secure cryptographic keys. Indeed, finding robust Boolean functions for cryptography is an important problem in sequence ciphers, block ciphers, and hash functions, among others. Due to the super-exponential size $mathcal{O}(2^{2^n})$ of the associated space, finding $n$-variable Boolean functions with global cryptographic constraints is computationally hard. This problem has already been addressed employing generic low-connected incoherent D-Wave quantum annealers. However, the limited connectivity of the Chimera graph, together with the exponential growth in the complexity of the Boolean function design problem, limit the problem scalability. Here, we propose a special-purpose coherent quantum annealing architecture with three couplers per qubit, designed to optimally encode the bent function design problem. A coherent quantum annealer with this tree-type architecture has the potential to solve the $8$-variable bent function design problem, which is classically unsolved, with only $127$ physical qubits and $126$ couplers. This paves the way to reach useful quantum supremacy within the framework of quantum annealing for cryptographic purposes.
The Earth observation satellites (EOSs) are specially designed to collect images according to user requirements. The agile EOSs (AEOS), with stronger attitude maneuverability, greatly improve the observation capability, while increasing the complexity in scheduling. We address a multiple AEOSs scheduling with multiple observations for the first time}, where the objective function aims to maximize the entire observation profit over a fixed horizon. The profit attained by multiple observations for each target is nonlinear to the number of observations. We model the multiple AEOSs scheduling as a specific interval scheduling problem with each satellite orbit respected as machine. Then A column generation based framework is developed to solve this problem, in which we deal with the pricing problems with a label-setting algorithm. Extensive simulations are conducted on the basis of a Chinas AEOS constellation, and the results indicate the optimality gap is less than 3% on average, which validates the performance of the scheduling solution obtained by the proposed framework. We also compare the framework in the conventional EOS scheduling.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
