Newswise — Modern computers rely on microprocessors that perform gates, such as the AND gate which adds two bits. These gates are irreversible, making it impossible for algorithms to run in reverse. According to Wolfgang Lechner, a theoretical physics professor at the University of Innsbruck, the multiplication 22=4 cannot be reversed, as 4 could also result from 14 or 4*1. If computers could run in reverse, it would enable the factorization of large numbers, which is a crucial component of cryptography.
Martin Lanthaler, Ben Niehoff, and Wolfgang Lechner, all from the Department of Theoretical Physics at the University of Innsbruck and the quantum spin-off ParityQC, have successfully created an algorithmic inversion through the use of quantum computers. The team began with a classical logic circuit that multiplied two numbers, and through quantum optimization methods, they were able to encode the circuit's logic within the ground states of a quantum system. This allowed for both multiplication and factorization to be solved as ground-state problems, despite being built from irreversible operations. Martin Lanthaler further explains that the logic of the circuit can be translated into quantum mechanics, opening up new possibilities for solving problems that were once deemed impossible with classical computers.
Superposition of all possible results
According to Martin Lanthaler, the fundamental aspect of their work involves encoding the essential components of the multiplier circuit, such as AND gates, half and full adders, with the use of the parity architecture as the ground state problem on a collection of interacting spins. This coding enables the construction of the entire circuit using repeating subsystems that can be organized on a two-dimensional grid. Multiple subsystems can be strung together to tackle larger problem instances. Rather than relying on the classical brute force method, where all possible factors are tested, quantum methods can accelerate the search process. In order to discover the ground state and solve an optimization problem, it is not necessary to survey the entire energy landscape. Instead, "tunneling" can be used to access deeper valleys, resulting in a more efficient and faster search.
The research work described provides a model for a novel quantum computer capable of tackling the factorization problem, a key aspect of modern cryptography. This blueprint utilizes the parity architecture, which was created at the University of Innsbruck, and is compatible with all contemporary quantum computing platforms.
The team's findings were recently published in the journal Nature Communications Physics. Financial backing for the research was given by a variety of organizations, including the Austrian Science Fund FWF, the European Union, and the Austrian Research Promotion Agency FFG, among others.
Publication: Scalable set of reversible parity gates for integer factorization. Martin Lanthaler, Benjamin E. Niehoff & Wolfgang Lechner. Nature Communications Physics 6, 73 (2023) DOI: https://doi.org/10.1038/s42005-023-01191-3
RSS