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

Understand

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.