Quantum annealing (QA) is an optimization process in quantum computing similar to the probabilistic metaheuristic simulated annealing (SA). The QA process involves encoding an optimization problem into an energy landscape, which it then traverses in search for the point of minimal energy representing the global optimal state. In this thesis two different implementations of QA are examined, one run on a binary quadratic model (BQM) and one on a discrete quadratic model (DQM). These are then compared to their traditional counterpart: SA, in terms of performance and accuracy when solving the graph coloring problem (GCP). Regarding performance, the results illustrate how SA outperforms both QA implementations. However, it is apparent that these slower execution times are mostly due to various overhead costs that appear because of limited hardware. When only looking at the quantum annealing part of the process, it is about a hundred times faster than the SA process. When it comes to accuracy, both the DQM-implementation of QA and SA provided results of high quality, whereas the BQM-implementation performed notably worse, both by often not finding the optimal values and by sometimes returning invalid results. / Quantum annealing (QA) är en kvantbaserad optimeringsprocess som liknar den probabilistiska metaheuristiken simulated annealing (SA). QA går ut på att konvertera ett optimeringsproblem till ett energilandskap, som sedan navigeras för att hitta punkten med lägst energi, vilket då motsvarar den optimala lösningen på problemet. I denna uppsats undersöks två olika implementationer av QA: en som använder en binary quadratic model (BQM) och en som använder en discrete quadratic model (DQM). Dessa två implementationerna jämförs med deras traditionella motsvarighet: SA, utifrån både prestanda och korrekthet vid lösning av graffärgningsproblemet (GCP). När det gäller prestanda visar resultaten att SA är snabbare än båda QA implementationerna. Samtidigt är det tydligt att denna prestandaskillnad framförallt beror på diverse förberedelser innan exkueringen startar på kvantdatorn, vilka är krävande på grund av olika hårdvarubegränsningar. Om man endast betraktar kvantprocesserna visar vår studie att QA implementationerna är ungefär hundra gånger snabbare än SA. Gällande korrekthet gav både DQM-implementationen av QA och SA resultat av hög kvalitet medan BQM-implementationen presterade betydligt sämre. Den gjorde detta dels genom att inte skapa optimala resultat och genom att returnera otillåtna lösningar.

Phase transitions and their associated critical phenomena are of fundamental importance and play a crucial role in the development of statistical physics for both classical and quantum systems. Phase transitions embody diverse aspects of physics and also have numerous applications outside physics, e.g., in chemistry, biology, and combinatorial optimization problems in computer science. Many problems can be reduced to a system consisting of a large number of interacting agents, which under some circumstances (e.g., changes of external parameters) exhibit collective behavior; this type of scenario also underlies phase transitions. The theoretical understanding of equilibrium phase transitions was put on a solid footing with the establishment of the renormalization group. In contrast, non-equilibrium phase transition are relatively less understood and currently a very active research topic. One important milestone here is the Kibble-Zurek (KZ) mechanism, which provides a useful framework for describing a system with a transition point approached through a non-equilibrium quench process. I developed two efficient Monte Carlo techniques for studying phase transitions, one is for classical phase transition and the other is for quantum phase transitions, both are under the framework of KZ scaling. For classical phase transition, I develop a non-equilibrium quench (NEQ) simulation that can completely avoid the critical slowing down problem. For quantum phase transitions, I develop a new algorithm, named quasi-adiabatic quantum Monte Carlo (QAQMC) algorithm for studying quantum quenches. I demonstrate the utility of QAQMC quantum Ising model and obtain high-precision results at the transition point, in particular showing generalized dynamic scaling in the quantum system. To further extend the methods, I study more complex systems such as spin-glasses and random graphs. The techniques allow us to investigate the problems efficiently. From the classical perspective, using the NEQ approach I verify the universality class of the 3D Ising spin-glasses. I also investigate the random 3-regular graphs in terms of both classical and quantum phase transitions. I demonstrate that under this simulation scheme, one can extract information associated with the classical and quantum spin-glass transitions without any knowledge prior to the simulation.

Quantum annealing represents an essential milestone towards the goal of adiabatic quantum computing. In quantum annealing, the computation involves finding the ground state of a classical Ising-like Hamiltonian realized as interactions between qubits. Quantum fluctuations are introduced to allow the wavefunction of the qubits to explore the energy landscape, the hope being that the wavefunction finds a minimum energy configuration and possibly giving the result of the computation. While quantum annealing likely may not be as powerful as adiabatic quantum computing, it is possible that it may be better at optimization compared to analogous classical algorithms. In physical realizations of quantum annealing, there are still questions as to the role of quantum fluctuations in the operation of a device given the short coherence times of the individual qubits. These questions have consistently posed a serious theoretical challenge making it difficult to verify experimental results. Here we simplify the problem by considering a system of qubits with ferromagnetic interactions, modeling the decoherence effects as classical noise in the transverse-field of each qubit. We compare the calculations to data collected from a system of manufactured qubits produced by D-wave Systems by performing a finite-size scaling analysis that captures the competition between quantum fluctuations of the transverse-field and bit-flip errors from the noise. We argue that on time-scales larger than the single-qubit decoherence time, the device produces the expected quantum fluctuations for the many-body system. Using this finite-size scaling, one can diagnose sources of noise in the system. Hopefully, in the near future, these devices will not only be realizing coherent quantum annealing but will likely be useful as another example of synthetic quantum matter.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第23731号 / 理博第4821号 / 新制||理||1689(附属図書館) / 京都大学大学院理学研究科化学専攻 / (主査)教授 谷村 吉隆, 教授 林 重彦, 教授 渡邊 一也 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Quantum annealing is expected to be a powerful generic algorithm for solving hard combinatorial optimization problems faster than classical computers. Finding the solution to a combinatorial optimization problem is equivalent to finding the ground state of an Ising Hamiltonian. In today's quantum annealers the spins of the Ising Hamiltonian are mapped to superconducting qubits. On the other hand, dissipation processes degrade the success probability of finding the solution. In this thesis we set out to explore a newly proposed architecture for a noise-resilient quantum annealer that instead maps the Ising spins to continuous variable quantum states of light encoded in the field quadratures of a two-photon pumped Kerr- nonlinear resonator based on the proposal by Puri et al. (2017). In this thesis we study the Wigner negativity for this newly proposed architecture and evaluate its performance based on the negativity of the Wigner function. We do this by determining an experimental value to when the presence of losses become too detrimental, such that the Wigner function of the quantum state during the evolution within the anneal becomes positive for all times. Furthermore, we also demonstrate the capabilities of this continuous variable quantum annealer by simulating and finding the best solution of a small instance of the NP-complete subset sum problem and of the number partitioning problem.

Mapping of earth resources, environmental monitoring, and many other systems require high-resolution wide-area imaging. Since images often have to be captured at night or in inclement weather conditions, a capability is provided by Synthetic Aperture Radar (SAR). SAR systems exploit radar signal's long-range propagation and utilize digital electronics to process complex information, all of which enables high-resolution imagery. This gives SAR systems advantages over optical imaging systems, since, unlike optical imaging, SAR is effective at any time of day and in any weather conditions. Moreover, advanced technology called Interferometric Synthetic Aperture Radar (InSAR), has the potential to apply phase information from SAR images and to measure ground surface deformation. However, given the current state of technology, the quality of InSAR data can be distorted by several factors, such as image co-registration, interferogram generation, phase unwrapping, and geocoding. Image co-registration aligns two or more images so that the same pixel in each image corresponds to the same point of the target scene. Super-Resolution (SR), on the other hand, is the process of generating high-resolution (HR) images from a low-resolution (LR) one. SR influences the co-registration quality and therefore could potentially be used to enhance later stages of SAR image processing. Our research resulted in two major contributions towards the enhancement of SAR processing. The first one is a new learning-based SR model that can be applied with SAR, and similar applications. A second major contribution is utilizing the devised model for improving SAR co-registration and InSAR interferogram generation, together with methods for evaluating the quality of the resulting images. In the case of phase unwrapping, the process of recovering unambiguous phase values from a two-dimensional array of phase values known only modulo $2\pi$ rad, our research produced a third major contribution. This third major contribution is the finding that quantum annealers can resolve problems associated with phase unwrapping. Even though other potential solutions to this problem do currently exist - based on network programming for example - network programming techniques do not scale well to larger images. We were able to formulate the phase unwrapping problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. Since quantum annealers are limited in the number of qubits they can process, currently available quantum annealers do not have the capacity to process large SAR images. To resolve this limitation, we developed a novel method of recursively partitioning the image, then recursively unwrapping each partition, until the whole image becomes unwrapped. We tested our new approach with various software-based QUBO solvers and various images, both synthetic and real. We also experimented with a D-Wave Systems quantum annealer, the first and only commercial supplier of quantum annealers, and we developed an embedding method to map the problem to the D-Wave 2000Q_6, which improved the result images significantly. With our method, we were able to achieve high-quality solutions, comparable to state-of-the-art phase-unwrapping solvers. / Graduate

Quantum computing has emerged as a new field that may have the potential to revolutionize the landscape of information processing and computational power, although physically constructing quantum hardware has proven difficult,and quantum computers in the current Noisy Intermediate Scale Quantum (NISQ) era are error prone and limited in the number of qubits they contain.A sub-field within quantum algorithms research which holds potential for the NISQ era, and which has seen increasing activity in recent years, is quantum machine learning, where researchers apply approaches from classical machine learning to quantum computing algorithms and explore the interplay between the two. This master thesis investigates feature selection and autoencoding algorithms for quantum computers. Our review of the prior art led us to focus on contributing to three sub-problems: A) Embedded feature selection on quantum annealers, B) short depth quantum autoencoder circuits, and C)embedded compressed feature representation for quantum classifier circuits.For problem A, we demonstrate a working example by converting ridge regression to the Quadratic Unconstrained Binary Optimization (QUBO) problem formalism native to quantum annealers, and solving it on a simulated backend. For problem B we develop a novel quantum convolutional autoencoder architecture and successfully run simulation experiments to study its performance.For problem C, we choose a classifier quantum circuit ansatz based on theoretical considerations from the prior art, and experimentally study it in parallel with a classical benchmark method for the same classification task,then show a method from embedding compressed feature representation onto that quantum circuit. / Kvantberäkning är ett framväxande område som potentiellt kan revolutionera informationsbehandling och beräkningskraft. Dock är praktisk konstruktion av kvantdatorer svårt, och nuvarande kvantdatorer i den s.k. NISQ-eran lider av fel och begränsningar i antal kvantbitar de kan hantera. Ett lovande delområde inom kvantalgoritmer är kvantmaskininlärning, där forskare tillämpar klassiska maskininlärningsmetoder på kvantalgoritmer och utforskar samspelet mellande två områdena.. Denna avhandling fokuserar på kvantalgoritmer för funktionsval,och datakompression (i form av s.k. “autoencoders”). Vi undersöker tre delproblem: A) Inbäddat funktionsval på en kvantannealer, B) autoencoder-kvantkretsar för datakompression, och C) inbyggt funktionsval för kvantkretsar för klassificering. För problem A demonstrerar vi ett fungerande exempel genom att omvandla ridge regression till problemformuleringen "Quadratic Unconstrained Binary Optimization"(QUBO) som är nativ för kvantannealers,och löser det på en simulerad backend. För problem B utvecklar vi en ny konvolutionerande autoencoder-kvantkrets-arkitektur och utför simuleringsexperimentför att studera dess prestanda. För problem C väljer vi en kvantkrets-ansats för klassificering baserad på teoretiska överväganden från tidigare forskning och studerar den experimentellt parallellt med en klassisk benchmark-metod församma klassificeringsuppgift, samt visar en metod för inbyggt funktionsval (i form av datakompression) i denna kvantkrets.

Quantum computing is a form of computation that exploits quantum mechanical phenomena for information processing, with promising applications (among others) in optimization and machine learning. Indeed, quantum machine learning is currently one of the most popular directions of research in quantum computing, offering solutions with an at-least-theoretical advantage compared to the classical counterparts. Nevertheless, the quantum devices available in the current Noisy Intermediate-Scale Quantum (NISQ) era are limited in the number of qubits and significantly affected by noise. An interesting alternative to the current prototypes of general-purpose quantum devices is represented by quantum annealers, specific-purpose quantum machines implementing the heuristic search for solving optimization problems known as quantum annealing. However, despite the higher number of qubits, the current quantum annealers are characterised by very sparse topologies. These practical issues have led to the development of hybrid classical-quantum schemes, aiming at leveraging the strengths of both paradigms while circumventing some of the limitations of the available devices. In this thesis, several hybrid classical-quantum algorithms for optimization and machine learning are introduced and/or empirically assessed, as the empirical evaluation is a fundamental part of algorithmic research. The quantum computing models taken into account are both quantum annealing and circuit-based universal quantum computing. The results obtained have shown the effectiveness of most of the proposed approaches.