Quantum Algorithms: Application Perspective

Introduction

In recent years, quantum computing has become an area of high interest for both the academia and the industry. Although some companies such as IBM and Microsoft have made available quantum devices of up to 16 qubits and with varying qubit layouts, the era of quantum computing that would involve a number of qubits that facilitates useful and scalable quantum applications lies still well ahead. Once quantum computers become physically possible and economically viable, though, it is believed that they will be able to outperform classical devices, both in terms of the required space as well as time, by utilizing such quantum mechanical phenomena as superposition, entanglement and, equally importantly, destructive and constructive interference. It is clear however that quantum computers will not solve computationally unsolvable problems such as the halting problem. They might though be useful for certain problems for which classical algorithms are currently unable to provide efficient solutions.

The potential for quantum computing to become an important discipline was realized in 1994 with the emergence of Shor’s algorithms for integer factorization and discrete logarithms (Shor, 1994). Shor’s were the first quantum algorithms that offered a promise of a direct commercial usage especially in the field of cryptography. In 1996 quantum search algorithm (Grover) was proposed, which thanks to its simplicity proved to be applicable as a subroutine in many other quantum algorithms, such as quantum counting (Brassard, Høyer and Tapp, 1998) or protein structure prediction (Wong and Chang, 2020). While Shor’s algorithms have applications in asymmetric cryptography, Grover’s algorithm can be used to tackle symmetric keys.

The possibility of a practical development of quantum computers was given a boost with the publication by Arute et al. (2019) of their results of boson-sampling (Aaronson and Arkhipov, 2013) experiments on a noisy 53-qubit quantum device. These experiments are widely held as the first successful attempt at demonstrating that quantum mechanical computing methods might indeed be faster than classical ones for certain problems, despite the fact that no practical problem was solved by these experiments.

Quantum computing is intended to improve the computational performance of hard problems. As cryptographic algorithms are designed around assumptions of computational hardness of such problems as large prime number factorization, lattice problems such as lwe (learning with errors) (Regev, 2009), or that, more generally, P¹NP. Quantum algorithms other than Shor’s and Grover’s might as well prove useful in handling information security issues.

The discorvery of the three quantum algorithms mentioned above has led to the development of the field of post-quantum cryptography (Bhatia and Zheng, 2020). It seeks to counteract against the potential threat of currently unbreakable classical codes being eventually broken by the quantum technology. Within the post-quantum cryptographic research, it is believed that certain lattice-based cryptographic optimization schemes will be insurmountable by quantum-mechanical methods (Peikert, 2016), (Bhatia and Kumar, 2019).