Quantum computer in reverse gear

Martin Lanthaler (left) and Wolfgang Lechner (right) from the Department of Theoretical Physics at the University of Innsbruck.
Credit: ParityQC

Reversible logic gates designed for large scale integer factorization.

Large numbers can only be factorized with a great deal of computational effort. Physicists at the University of Innsbruck, Austria, led by Wolfgang Lechner are now providing a blueprint for a new type of quantum computer to solve the factorization problem, which is a cornerstone of modern cryptography.

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, 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. If this were possible, however, it would be feasible to factorize large numbers, i.e. divide them into their factors, which is an important pillar of cryptography.

Martin Lanthaler, Ben Niehoff and Wolfgang Lechner from the Department of Theoretical Physics at the University of Innsbruck and the quantum spin-off ParityQC have now developed exactly this inversion of algorithms with the help of quantum computers. 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.”

Superposition of all possible results

„The core of our work is the encoding of the basic building blocks of the multiplier circuit, specifically AND gates, half and full adders with the parity architecture as the ground state problem on an ensemble of interacting spins,” says Martin Lanthaler. The coding allows the entire circuit to be built from repeating subsystems that can be arranged on a two-dimensional grid. By stringing several of these subsystems together, larger problem instances can be realized. Instead of the classical brute force method, where all possible factors are tested, quantum methods can speed up the search process: To find the ground state, and thus solve an optimization problem, it is not necessary to search the whole energy landscape, but deeper valleys can be reached by “tunneling”.

The current research work provides a blueprint for a new type of quantum computer to solve the factorization problem, which is a cornerstone of modern cryptography. This blueprint is based on the parity architecture developed at the University of Innsbruck and can be implemented on all current quantum computing platforms.

The results were recently published in Nature Communications Physics. Financial support for the research was provided by the Austrian Science Fund FWF, the European Union and the Austrian Research Promotion Agency FFG, among others.

Wissenschaftliche Ansprechpartner:

Wolfgang Lechner
Department of Theoretical Physics
University of Innsbruck
+43 512 507 52232
Wolfgang.Lechner@uibk.ac.at
https://www.uibk.ac.at/th-physik/quantum-optimization/

Originalpublikation:

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

Weitere Informationen:

https://www.uibk.ac.at/en/newsroom/2022/new-form-of-universal-quantum-computers/ – New form of uni­ver­sal quan­tum com­put­ers

Media Contact

Dr. Christian Flatz Büro für Öffentlichkeitsarbeit
Universität Innsbruck

All latest news from the category: Information Technology

Here you can find a summary of innovations in the fields of information and data processing and up-to-date developments on IT equipment and hardware.

This area covers topics such as IT services, IT architectures, IT management and telecommunications.

Back to home

Comments (0)

Write a comment

Newest articles

Lighting up the future

New multidisciplinary research from the University of St Andrews could lead to more efficient televisions, computer screens and lighting. Researchers at the Organic Semiconductor Centre in the School of Physics and…

Researchers crack sugarcane’s complex genetic code

Sweet success: Scientists created a highly accurate reference genome for one of the most important modern crops and found a rare example of how genes confer disease resistance in plants….

Evolution of the most powerful ocean current on Earth

The Antarctic Circumpolar Current plays an important part in global overturning circulation, the exchange of heat and CO2 between the ocean and atmosphere, and the stability of Antarctica’s ice sheets….

Partners & Sponsors