A quantum computer is a device that performs operations according to the rules of quantum theory. There are various types of quantum computers of which nowadays the two most important ones considered for practical realization are the circuit-model quantum computer and the quantum annealer. Practical realizations of circuit-model quantum computers are currently limited in size to about ten qubits while quantum annealers with more than 2000 qubits are commercially available.
Quantum annealing is a paradigm to solve combinatorial optimization problems, featuring a discrete search space with many local minima, by a process using quantum fluctuations. We analyze the problem solving capability of a D-Wave 2X quantum annealer with more than 1000 qubits by comparing its performance with that of a simulated ideal quantum annealer. The ideal quantum annealer is modeled as a zero-temperature quantum system of interacting spin-1/2 particles and its dynamics is emulated by solving the time-dependent Schrödinger equation.
We study 2-satisfiability (2-SAT) problems with 8, 12 and 18 variables (or Ising spins in the physics language) that have a unique ground state, a small energy gap between the ground state and the first-excited state and a highly degenerate first-excited state. We report about a comparison of the frequencies for finding the ground state, as obtained with the D-Wave 2X and the simulated ideal quantum annealer. Our analysis indicates that the D-Wave 2X processor does not perform "ideal" quantum annealing and that more research is necessary to investigate the effects of e.g. temperature, imperfections etc.