Papers

# Scalable set of reversible parity gates for integer factorization We are delighted to announce an important breakthrough in integer factorization by ParityQC co-CEO Wolfgang Lechner, Martin Lanthaler and Ben Niehoff. The paper outlining the research results was published in Nature Communications Physics. Read the press release below.

Innsbruck, May 4th 2023 Large numbers can only be factorized with a great deal of computational effort, unfeasible for today’s classical computers. Physicists at the University of Innsbruck led by Wolfgang Lechner are now providing a blueprint for a new type of quantum computer to solve the integer factorization problem, a pillar of modern cryptography at the basis of RSA encryption.

Today’s computers are based on microprocessors that execute so-called gates. A gate can, for example, be an AND operation, i.e. an operation that adds two bits. These gates, and thus computers as a whole, are irreversible. That is, algorithms cannot simply run backwards. “If you take the multiplication 2*2=4, you cannot simply run this operation in reverse, because 4 could be 2*2, but likewise 1*4 or 4*1,” explains Wolfgang Lechner, professor of theoretical physics at the University of Innsbruck and co-CEO of ParityQC. If this were possible, however, it would be feasible to factorize large numbers, i.e. to divide them into factors, which is a way of reversing the currently used method of cryptography, RSA.

Martin Lanthaler, Ben Niehoff and Wolfgang Lechner from the Department of Theoretical Physics at the University of Innsbruck have now developed exactly this inversion of algorithms with quantum computing, implementing the ParityQC Architecture. The starting point is a classical logic circuit, which multiplies two numbers. If two integers are entered as the input value, the circuit returns their product. Such a circuit is built from irreversible operations. “However, the logic of the circuit can be encoded within ground states of a quantum system,” explains Martin Lanthaler from Wolfgang Lechner’s team. “Thus, both multiplication and factorization can be understood as ground-state problems and solved using quantum optimization methods.”