The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Although solutions to this problem exist based on network programming, these techniques do not scale well to larger sized images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved on a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant, with one constant per subimage. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. This basic idea is extended to several passes, where each pass results in an image which is subsequently decomposed to yet another set of subproblems until the resulting image can be accommodated by the annealer at hand. Additionally, we explore improvements to the method by decomposing the original image into overlapping subimages and ignoring the results on the overlapped (marginal) pixels. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real. Additionally, we experiment using D-wave systems’ quantum annealer, the D-wave 2000Q_6 and developed an embedding method which, for our problem, yielded improved results. Our method resulted in high quality solutions, comparable to state-of-the-art phase-unwrapping solvers.
The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Although solutions to this problem exist based on network programming, these techniques do not scale well to larger sized images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved on a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant, with one constant per subimage. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. This basic idea is extended to several passes, where each pass results in an image which is subsequently decomposed to yet another set of subproblems until the resulting image can be accommodated by the annealer at hand. Additionally, we explore improvements to the method by decomposing the original image into overlapping subimages and ignoring the results on the overlapped (marginal) pixels. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real. Additionally, we experiment using D-wave systems’ quantum annealer, the D-wave 2000Q_6 and developed an embedding method which, for our problem, yielded improved results. Our method resulted in high quality solutions, comparable to state-of-the-art phase-unwrapping solvers.
The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Although solutions to this problem exist based on network programming, these techniques do not scale well to larger-sized images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant, with one constant per sub-image. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real. Additionally, we experiment using D-Wave Systems's quantum annealer, the D-Wave 2000Q. The software-based solvers obtain high-quality solutions comparable to state-of-the-art phase-unwrapping solvers. We are currently working on optimally mapping the problem onto the restricted topology of the quantum annealer to improve the quality of the solution.
The focus of this work is to 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 on a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. In this work, we present a margin-based extension of the approach discussed above. We also present its performance under a variety of QUBO solvers including DWave’s 2000Q 6.
Quantum computers and algorithms are advancing rapidly, showing promise in tackling complex computational challenges. However, current quantum annealers are limited in handling large-scale problems due to their limited size and inherent noise. As a near-term solution, hybrid computing has emerged, harnessing the strengths of classical and quantum computing together. The phase unwrapping problem is a compu- tationally challenging task in interferometric synthetic aperture radar (In-SAR) image processing. In this study, we propose a hybrid approach to address the phase unwrapping problem for images larger than what current quantum annealers can handle. We utilized D-Wave's hybrid workflow, followed by refinements to enhance its performance. Our approach involves decomposing images and solving the resulting sub-images usingD- Wave's Constrained Quadratic Model (CQM), and then combining them. We assume that the obtained labels of sub-images are within an additive factor of the true labels. To determine these additive factors, we allow sub-images to overlap and use the labels of overlapping sectors for additive factor determination. Another phase of D- Wave's CQM is used for obtaining these shift factors. This enhanced CQM method results in improved outcomes compared to applying CQM to the entire image. Moreover, the proposed method enables unwrapping images larger than those that CQM can handle.
Phase unwrapping is the reconstruction of a phase given its values mod 2π. Phase unwrapping is an important image processing technique used in synthetic aperture radar interferometry, in the context of height estimation and ground deformation. By formulating the phase unwrapping problem as a global minimization problem,Lpnorm techniques form the backbone of many established phase unwrapping algorithms. TheL0norm is commonly agreed to produce the best unwrapping solutions, but the necessary brute-force calculations are infeasible for the phase unwrapping of SAR interferograms. Developments in variational quantum algorithms suggest computational advantages, when compared to classical approaches, for a multitude of applications. We therefore investigate the application of quantum algorithms to the phase unwrapping problem and introduce and derive an approximateL0norm optimization solver utilizing the quantum approximate optimisation algorithm. This hybrid algorithm uses classical nonconvex parameter optimization to produce optimal parameters for a quantum circuit encoding theL0phase unwrapping. Subsequent execution of this quantum circuit allows for an estimate of the solution of the phase unwrapping problem with advantages compared to brute force approaches. We validate our approach for small topographies, by demonstrating improved results when compared to establishedL1optimization.
Quantum computers and algorithms are undergoing rapid development, offering promising solutions to complex computational problems. This study focuses on harnessing the potential of quantum annealing to address the challenging phase unwrapping problem. Specifically, we employed D-Wave’s quantum annealers, currently among the most powerful in existence. To effectively utilize these systems, it is crucial to embed the problem onto their underlying structure, the Pegasus graph in the case of the D-Wave Advantage system. A shorter chain-length in the embedding process generally correlates with improved results. In the course of this thesis, we devised an algorithm for efficiently embedding the phase unwrapping problem onto the D-Wave Advantage system. Our approach yielded promising results when compared to D-Wave’s automatic embeddings. Notably, our introduced embedding boasts the minimum chain-length and utilizes the native structure of the target graph. Additionally, we leveraged D-Wave’s hybrid workflow, combining classical and quantum computing capabilities, to tackle larger image problems. Refinements to the hybrid method were implemented, resulting in enhanced performance. Experimental evaluations were conducted on actual quantum annealers, demonstrating that our refined algorithms outperform those provided by D-Wave.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.