Abstract
Quantum computers are physical devices that exploit the laws of quantum mechanics to perform calculations, in principle, substantially faster than classical computers. In the last years, we have witnessed a rapid advance in the practical realization of quantum computers and the coveted affirmation of the so-called “quantum advantage”. In other words, the demonstration that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time. Remarkably, some of the hard problems that have been demonstrated to empower the quantum advantage, are at the base of the current and wide-used protocols for key distribution. This means that the security of today’s cryptography will potentially be broken, in the next future, by the upcoming quantum machines.
Introduction: computational hardness
Modern cryptography, including the well-based cryptographical protocols for key distribution, are all designed around special classes of mathematical problems, which are considered computationally “hard” to be solved. The hypothesis of computational hardness dictates that a particular problem cannot be solved efficiently, by means of today’s technologies and computational resources. Here, the expression “efficiently” means “in a reasonable amount of time”, which of course depends on the specific situation and security requirements. The amount of time needed for solving a problem (i.e., finding an output result given some input parameter) is a quantity that can be easily evaluated from the size of the input parameter. Usually, the larger the input size, the larger the amount of time required for the solution of the problem. However, if the resolution time is an exponential function of the input size, then even a relatively small input would require several billions of years for the problem to be solved. Consequently, the problems requiring an exponential time to be sorted out, by making use of current technologies and algorithms, are considered computationally “hard”.
As an example, the best-known public-key cryptosystem RSA, relies on the high computational complexity of the prime factorization of a given integer number. The solution to this problem requires an exponential time for the already-known algorithm, therefore, with the recommended public-key size of 1024, 2048, and 3072 bits, the RSA cryptosystem is considered secure, by assuming that a potential enemy is supported by the typical resources and computational power of nowadays. However, this is an assumption based on the current experience, since there is no mathematical evidence that the problem cannot be broken in principle, for instance with a different algorithm not yet discovered.
The potential of quantum computers
Alongside developments in the field of classical computers, the imminent advent of quantum computers poses an additional and real threat to the security of current cryptosystems. Quantum computing exploits the properties of quantum systems, properly prepared as qubits, to perform calculations. In particular, the non-classical phenomena of superposition and entanglement are employed to build quantum logic gates and circuits. Differently from the classical bit, which only exists as 0 level or 1 level, a qubit is a quantum state described by the generic combination of the two levels, and such combination has the property of coherence, which is an inherent feature of quantum superposition. Such property of the qubits allows for the design of new kind of algorithms, that can efficiently perform tasks believed to be hard for classical computers (read our article here on the Second Quantum Revolution)
One of the most famous quantum algorithms is the Shor’s algorithm, able to factorize large numbers efficiently, i.e., with a polynomial time instead of an exponential time. Introduced in 1994, the Shor’s algorithms caused the “big bang” of quantum computation, as its application can break the current cryptographic standards, such as RSA, with the catastrophic effect of rendering the widespread key distribution methods completely insecure.
The development of large-scale quantum computer for real-world applications is practically challenging, due to the necessity of controlling, individually, a multitude of quantum systems, while protecting them from a noisy environment and decoherence. To address this problem, many physical systems, each one with its strengths and limitations, are under investigation. Here we briefly sum up the most promising ones.
State of the art and current platforms for quantum computers
Single atoms are among the quantum particles that can be practically exploited in the building of a quantum computer. Specifically, ionized atoms are easily controllable and can be individually confined thanks to the use of electrical traps. A quantum computer is then built upon a linear string of trapped ions, with logic gates and circuits operations that are obtained by means of microwave or laser fields. Up to now, quantum algorithms have been performed on strings of seven ions, whereas longer chains of up to 32 ions and 2D crystals of up to 300 ions have been employed for quantum states engineering or simulation.
Another category of quantum computers is built upon superconducting electronic circuits, cooled down below a few milli-Kelvin degrees. More specifically, the quantum systems addressed are microscopic wires of superconductor separated by some insulating barrier, where the current flows via the quantum tunneling effect. In 2019, a 53-qubit programmable superconducting processor has been employed by Google to carry out a computational task that is outside the reach of present-day classical computer, thus proving, for the first time in an experiment, the quantum supremacy.
Finally, a third family of quantum computers exploits photons and non-classical states of light. Quantum gates and operations are performed with optical tools and devices, such as beam splitters and interferometers. In 2022, quantum computing start-up Xanadu, in Toronto, demonstrated for the first time a fully programmable photonic quantum computer able to display quantum advantage. The device, named Borealis, has been proven to operate with 216 qubits.
Just to give an idea of the potential of the new quantum technology arising, it has been demonstrated that Borealis takes just 36 microseconds to perform a task that would take a classical supercomputer several thousand years to complete, even with state-of-the-art algorithms.
As for the Shor’s algorithm for factorization speed-up, it has been successfully demonstrated in laboratory experiments, even though it has been tested with only small integers so far (in 2012, a superconducting quantum processor has successfully factorized the number 21). Nonetheless, with the continuous advance in technology and the increasing reliability of techniques for long-term manipulation of the qubits, we can reasonably expect that the next generation of quantum computers will successfully demonstrate the quantum advantage for many other tasks, including factorization.
Bibliography
Peter W. Shor. “Algorithms for quantum computation: discrete logarithms and factoring”. In Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press (1994).
Lucero, E., Barends, R., Chen, Y. et al. “Computing prime factors with a Josephson phase qubit quantum processor”. Nature Phys 8, 719–723 (2012).
Arute, F., Arya, K., Babbush, R. et al. “Quantum supremacy using a programmable superconducting processor”. Nature 574, 505–510 (2019).
Madsen, L.S., Laudenbach, F., Askarani, M.F. et al. “Quantum computational advantage with a programmable photonic processor”. Nature 606, 75–81 (2022).
Authors
Claudia De Lazzari
Saverio Francesconi
Ilaria Vagniluca
