arXiv:1508.07190

Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 2: The "split-reduc" method and its application to quantum determination of Ramsey numbers

Emile Okada, Richard Tanburn, Nikesh S. Dattani

Published Aug 28, 2015• 0 citations

Abstract

Quantum annealing has recently been used to determine the Ramsey numbers R(m,2) for 3 < m < 9 and R(3,3) [Bian et al. (2013) PRL 111, 130505]. This was greatly celebrated as the largest experimental implementation of an adiabatic evolution algorithm to that date. However, in that computation, more than 66% of the qubits used were auxiliary qubits, so the sizes of the Ramsey number Hamiltonians used were tremendously smaller than the full 128-qubit capacity of the device used. The reason these auxiliary qubits were needed was because the best quantum annealing devices at the time (and still now) cannot implement multi-qubit interactions beyond 2-qubit interactions, and they are also limited in their capacity for 2-qubit interactions. We present a method which allows the full qubit capacity of a quantum annealing device to be used, by reducing multi-qubit and 2-qubit interactions. With our method, the device used in the 2013 Ramsey number quantum computation could have determined R(16,2) and R(4,3) with under 10 minutes of runtime.

DOI: 10.48550/arxiv.1508.07190

Related papers

Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The "deduc-reduc" method and its application to quantum factorization of numbers

Richard Tanburn, Emile Okada, Nike Dattani

Adiabatic quantum computing has recently been used to factor 56153 [Dattani & Bryans, arXiv:1411.6758] at room temperature, which is orders of magnitude larger than any number attempted yet using Shor's algorithm (circuit-based quantum computation). However, this number is still vastly smaller than RSA-768 which is the largest number factored thus far on a classical computer. We address a major issue arising in the scaling of adiabatic quantum factorization to much larger numbers. Namely, the existence of many 4-qubit, 3-qubit and 2-qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4-qubit interactions and 83% of the 3-qubit interactions in the factorization of a 25-digit number with almost no effort, without adding any auxiliary qubits. Our method is not limited to quantum factoring. Its importance extends to the wider field of discrete optimization. Any CSP (constraint-satisfiability problem), psuedo-boolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deduction-reduction" method which we introduce in this paper. We provide an open source code which takes in a Hamiltonian (or a discrete discrete function which needs to be optimized), and returns a Hamiltonian that has the same unique ground state(s), no new auxiliary variables, and as few multi-qubit (multi-variable) terms as possible with deduc-reduc.

arXiv:1508.04816Aug 19, 20158 citations

Experimental determination of Ramsey numbers with quantum annealing

Zhengbing Bian, Fabián A. Chudak, William G. Macready +2 more

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. It has found applications in mathematics, theoretical computer science, information theory, and classical error correcting codes. Ramsey numbers mark the threshold at which order first appears and are notoriously difficult to calculate due to their explosive rate of growth. Recently, a quantum algorithm has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm based on quantum annealing and show that it correctly determines the Ramsey numbers R(3, 3) and R(m, 2) for 4 ≤ m ≤ 8. The R(8, 2) computation used 84 qubits of which 28 were computational qubits. This computation is the largest experimental implementation of a scientifically meaningful quantum algorithm that has been done to date.

Jan 9, 201212 citations

Experimental Determination of Ramsey Numbers

Zhengbing Bian, Fabián A. Chudak, William G. Macready +2 more

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth. Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(m,2) for 4≤m≤8. The R(8,2) computation used 84 qubits of which 28 were computational qubits. This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.

arXiv:1201.1842Physical Review LettersSep 25, 201397 citations

Putting “Quantumness” to the Test

Graeme Smith, John A. Smolin

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures.Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth.Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers Rðm; nÞ.Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers Rð3; 3Þ and Rðm; 2Þ for 4 m 8.The Rð8; 2Þ computation used 84 qubits of which 28 were computational qubits.This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.

PhysicsSep 25, 201315 citations

Analog-Digital Quantum Computing with Quantum Annealing Processors

Rahul Deshpande, Majid Kheirkhah, Chris Rich +12 more

Quantum annealing processors typically control qubits in unison, attenuating quantum fluctuations uniformly until the applied system Hamiltonian is diagonal in the computational basis. This simplifies control requirements, allowing annealing QPUs to scale to much larger sizes than gate-based systems, but constraining the class of available operations. Here we expand the class by performing analog-digital quantum computing in a highly-multiplexed, superconducting quantum annealing processor. This involves evolution under a fixed many-body Hamiltonian that, in the weak-coupling regime, is well-described by an effective XY model, together with arbitrary-basis initialization and measurement via auxiliary qubits. Operationally, this is equivalent to implementing single-qubit gates at the beginning and end of an analog quantum evolution. We demonstrate this capability with several foundational applications: single-qubit and two-qubit coherent oscillations with varying initialization and measurement bases, a multi-qubit quantum walk with fermionic dispersion in line with theory, and Anderson localization in a disordered chain. These experiments open the door to a wide range of new possibilities in quantum computation and simulation, greatly expanding the applications of commercially available quantum annealing processors.

quant-pharXiv:2603.15534Mar 17, 20260 citations

Finite-size scaling in quantum annealing with decoherence

Phillip Weinberg

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.

Jan 1, 20200 citations