Abstract : Quantum annealing is a general strategy for solving difficult optimization problems with the aid of quantum adiabatic evolution [1, 2]. Both analytical and numerical evidence suggests that under idealized, closed system conditions, quantum annealing can outperform classical thermalization-based algorithms such as simulated annealing [3, 4]. Do engineered quantum annealing devices effectively perform classical thermalization when coupled to a decohering thermal environment? To address this we establish, using superconducting flux qubits with programmable spin-spin couplings, an experimental signature which is consistent with quantum annealing, and at the same time inconsistent with classical thermalization, in spite of a decoherence timescale which is orders of magnitude shorter than the adiabatic evolution time. This suggests that programmable quantum devices, scalable with current superconducting technology, implement quantum annealing with a surprising robustness against noise and imperfections.
Abstract : Quantum annealing is a general strategy for solving difficult optimization problems with the aid of quantum adiabatic evolution [1, 2]. Both analytical and numerical evidence suggests that under idealized, closed system conditions, quantum annealing can outperform classical thermalization-based algorithms such as simulated annealing [3, 4]. Do engineered quantum annealing devices effectively perform classical thermalization when coupled to a decohering thermal environment? To address this we establish, using superconducting flux qubits with programmable spin-spin couplings, an experimental signature which is consistent with quantum annealing, and at the same time inconsistent with classical thermalization, in spite of a decoherence timescale which is orders of magnitude shorter than the adiabatic evolution time. This suggests that programmable quantum devices, scalable with current superconducting technology, implement quantum annealing with a surprising robustness against noise and imperfections.
A circuit consisting of a network of coupled compound Josephson junction rf-SQUID flux qubits has been used to implement an adiabatic quantum optimization algorithm. It is shown that detailed knowledge of the magnitude of the persistent current as a function of annealing parameters is key to implementation of the algorithm on this particular type of hardware. Experimental results contrasting two annealing protocols, one with and one without active compensation for the growth of the qubit persistent current during annealing, are presented in order to illustrate this point.
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 field of quantum information has been a fast growing field of research in the last few decades. The reason for this development is the potentially immense power of quantum computers, capable of solving hard problems in a fraction of the time it would take a classical computer. Quantum annealers are a type of quantum computer that seek to solve computational problems by finding the ground state of a quantum system. This type of quantum computer has been implemented on a large scale using superconducting flux quantum bits, but the computational power is limited. One potential improvement to help in this context is the implementation of multi-body interactions between quantum bits. Many-body interactions would be useful in allowing quantum annealers to solve more complex problems that are relevant in various areas of quantum information and science and implementing quantum error correction. \n \nWe present a superconducting device that implements a strong and tunable in sign and magnitude three-body interaction between superconducting flux quantum bits. The circuit design proposed has vanishing two-body interactions and robustness against noise and parameter variations. This circuit behaves as an ideal computational basis ZZZ coupler in a simulated three-qubit quantum annealing experiment. These properties are confirmed by calculations based on the Born-Oppenheimer approximation, a two-level spin model for the coupling circuit, and full numerical diagonalization. \n \nThe proposed circuit is based on already available technology and therefore could be readily implemented in the next generation of quantum annealing hardware. This work will be relevant for advanced quantum annealing protocols and future developments of high-order many-body interactions in quantum computers and simulators.
Finding the global minimum in a rugged potential landscape is a computationally hard task, often equivalent to relevant optimization problems. Annealing strategies, either classical or quantum, explore the configuration space by evolving the system under the influence of thermal or quantum fluctuations. The thermal annealing dynamics can rapidly freeze the system into a low-energy configuration, and it can be simulated well on a classical computer, but it easily gets stuck in local minima. Quantum annealing, on the other hand, can be guaranteed to find the true ground state and can be implemented in modern quantum simulators; however, quantum adiabatic schemes become prohibitively slow in the presence of quasidegeneracies. Here, we propose a strategy which combines ideas from simulated annealing and quantum annealing. In such a hybrid algorithm, the outcome of a quantum simulator is processed on a classical device. While the quantum simulator explores the configuration space by repeatedly applying quantum fluctuations and performing projective measurements, the classical computer evaluates each configuration and enforces a lowering of the energy. We have simulated this algorithm for small instances of the random energy model, showing that it potentially outperforms both simulated thermal annealing and adiabatic quantum annealing. It becomes most efficient for problems involving many quasidegenerate ground states.
Quantum annealing can potentially be used to find better solutions to hard optimization problems faster than purely classical hardware. To take full advantage of quantum effects such as tunneling, a physical annealer should be comprised of qubits with a sufficient degree of quantum coherence. In addition, to encode useful problems, an annealer should provide a dense physical connectivity graph between qubits. Towards these goals, we develop superconducting ``fluxmon'' flux qubits suitable for high-connectivity quantum annealing without the use of performance-degrading lossy dielectrics. We carry out in-depth studies of noise and dissipation, and of qubit-qubit coupling in the strongly nonlinear regime. We perform the first frequency-resolved measurements extracting both the quantum and classical parts of the 1/f flux noise intrinsic to superconducting devices, and observe the classical-to-quantum crossover of the noise. We also identify atomic hydrogen as a magnetic dissipation source. We then implement tunable inter-qubit coupling compatible with high connectivity, and provide direct spectroscopic measurements of ultra-strong coupling between qubits. Finally, we use our system to explore quantum annealing faster than the system thermalization time, a previously unaccessed regime.
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.