Reducing multiqubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The "deducreduc" method and its application to quantum factorization of numbers
Abstract
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 (circuitbased quantum computation). However, this number is still vastly smaller than RSA768 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 4qubit, 3qubit and 2qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4qubit interactions and 83% of the 3qubit interactions in the factorization of a 25digit 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 (constraintsatisfiability problem), psuedoboolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deductionreduction" 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 multiqubit (multivariable) terms as possible with deducreduc.
 Publication:

arXiv eprints
 Pub Date:
 August 2015
 arXiv:
 arXiv:1508.04816
 Bibcode:
 2015arXiv150804816T
 Keywords:

 Quantum Physics;
 Computer Science  Discrete Mathematics;
 Computer Science  Data Structures and Algorithms;
 Mathematics  Number Theory;
 05C50;
 11A41;
 11A51;
 11N35;
 11N36;
 11N80;
 11Y05;
 65K10;
 65P10;
 65Y20;
 68Q12;
 81P68;
 81P94;
 94A60;
 8108;
 B.2.4;
 B.8.2;
 C.1.3;
 C.1.m;
 F.2.1;
 F.2.3;
 F.4.1;
 G.1.0;
 G.1.3;
 G.1.5;
 G.1.6;
 G.2.0;
 G.2.1;
 I.1.2;
 I.6.4;
 C.4;
 E.3;
 G.0;
 J.2;
 K.2