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.
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.
Quantum annealing aims at solving combinatorial optimization problems mapped to Ising interactions between quantum spins. Here, with the objective of developing a noise-resilient annealer, we propose a paradigm for quantum annealing with a scalable network of two-photon-driven Kerr-nonlinear resonators. Each resonator encodes an Ising spin in a robust degenerate subspace formed by two coherent states of opposite phases. A fully connected optimization problem is mapped to local fields driving the resonators, which are connected with only local four-body interactions. We describe an adiabatic annealing protocol in this system and analyse its performance in the presence of photon loss. Numerical simulations indicate substantial resilience to this noise channel, leading to a high success probability for quantum annealing. Finally, we propose a realistic circuit QED implementation of this promising platform for implementing a large-scale quantum Ising machine.
Quantum phenomena have the potential to speed up the solution of hard optimization problems. For example, quantum annealing, based on the quantum tunneling effect, has recently been shown to scale exponentially better with system size than classical simulated annealing. However, current realizations of quantum annealers with superconducting qubits face two major challenges. First, the connectivity between the qubits is limited, excluding many optimization problems from a direct implementation. Second, decoherence degrades the success probability of the optimization. We address both of these shortcomings and propose an architecture in which the qubits are robustly encoded in continuous variable degrees of freedom. By leveraging the phenomenon of flux quantization, all-to-all connectivity with sufficient tunability to implement many relevant optimization problems is obtained without overhead. Furthermore, we demonstrate the robustness of this architecture by simulating the optimal solution of a small instance of the nondeterministic polynomial-time hard (NP-hard) and fully connected number partitioning problem in the presence of dissipation.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
The application of quantum annealing to the optimization of continuous-variable functions is a relatively unexplored area of research. We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. After domain-wall encoding to map a continuous variable to discrete Ising variables, we first benchmark the performance of the real hardware, the D-Wave 2000Q, against several state-of-the-art classical optimization algorithms designed for continuous-variable problems to find that the D-Wave 2000Q matches the classical algorithms in a limited domain of computation time. Beyond this domain, classical global optimization algorithms outperform the quantum device. Next we examine several optimization algorithms that are applicable to the Ising formulation of the problem, such as the time-evolving block decimation (TEBD) to simulate ideal coherent quantum annealing, simulated annealing, simulated quantum annealing, and spin-vector Monte Carlo. The data show that TEBD's coherent quantum annealing achieves far better results than the other approaches, demonstrating the effectiveness of coherent tunneling. From these two types of benchmarks, we conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms if thermal noise and other imperfections are sufficiently suppressed and the device operates coherently, as demonstrated in recent short-time quantum simulations.
A pivotal task for quantum computing is to speed up the solution of problems that are both classically intractable and practically valuable. Among these, combinatorial optimization problems have attracted tremendous attention due to their broad applicability and natural fitness to Ising Hamiltonians. Here we propose a quantum-sampling strategy, on the basis of which we design an algorithm to accelerate the solution of the ground states of the Ising model, a class of Nondeterministic Polynomial time (NP)-hard problems in combinatorial optimization. The algorithm employs a shallow-circuit quantum-sampling subroutine to navigate the energy landscape. Using up to 104 superconducting qubits, we experimentally demonstrate that this algorithm outputs favorable solutions compared with even a highly optimized classical simulated-annealing algorithm, and we illustrate the path toward quantum speedup based on the time-to-solution metric relative to simulated annealing under serial execution. Our results indicate a promising alternative to classical heuristics for combinatorial optimization, for which quantum advantage may become possible on near-term superconducting quantum processors.