On quantum computational algorithms

Dong Ruan, Gui‐Lu Long, Shi-Jie WEI +1 more

Quantum computing exploits quantum mechanical properties to perform computations. It enables quantum parallelism and provides much more powerful data processing capabilities than classical computers. With a quantum computer, one can exponentially accelerate quantum system simulation and accelerate some important classical algorithms. Traditional quantum algorithms use unitary evolution to process information. A quantum computing process is the product of a series of unitary operators. In 1994, Shor invented a quantum prime factorization algorithm that exponentially accelerates the factorization of an integer. In 1996, Grover proposed a quantum search algorithm that accelerates the search of an unsorted database using square-root steps. Afterwards, the development of quantum algorithms slowed down, leading to a subsequent query by Shor in 2003 regarding why no more significant quantum algorithms have been found. Since 2009, many important new quantum algorithms have been proposed, such as a quantum algorithm for solving linear equations with the capability of exponential acceleration, a quantum algorithm for sparse Hamiltonian simulation using linear combinations of unitary operators, and a novel algorithm for Hamiltonian simulation, which provides exponential improvements in precision. In this paper, we first describe the basic principles of quantum computation. We then describe the Shor algorithm and Grover/Long search algorithm. These quantum algorithms are the general quantum algorithms that use unitary operations in their computational processes. Next, we introduce the basic principles of duality quantum computing, which was proposed in 2002. In contrast to traditional quantum computing, duality quantum computing allows the use of linear combinations of unitary operators in the computation process, meaning the multiplication, division, addition, and subtraction of unitary operators are all possible in duality quantum computing. Thus, duality quantum computing provides more flexibility for constructing quantum algorithms and the techniques used in classical algorithm design can be directly used to construct quantum algorithms. We then review recent work regarding newer quantum algorithms that enable the linear combination of unitary operators, which are actually duality quantum algorithms. Additionally, a duality quantum simulation algorithm for open quantum systems is introduced. This algorithm not only reduces computational complexity, but also improves accuracy exponentially. Finally, a summary and the future prospects of quantum algorithms are provided.

Jamie Smith, Michele Mosca

Shinil Cho

Mariko Sasakura, Kenichi Iwata

Quantum computers are the first computers based on a different paradigm since the establishment of classical computers. Quantum algorithms that run on quantum computers are created based on a fundamentally different way of thinking than algorithms that run on classical computers. Therefore, visualisation to support the understanding of quantum algorithms needs to be different from visualisation to support the understanding of conventional algorithms. In this paper, the differences between quantum algorithms and conventional algorithms are discussed from the perspective of visualisation.

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Seyed M. Hosseini, Hossein Pilaram

One of the most crucial measures to maintain data security is the use of cryptography schemes and digital signatures built upon cryptographic algorithms. The resistance of cryptographic algorithms against conventional attacks is guaranteed by the computational difficulties and the immense amount of computation required to them. In the last decade, with the advances in quantum computing technology and the realization of quantum computers, which have higher computational power compared to conventional computers and can execute special kinds of algorithms (i.e., quantum algorithms), the security of many existing cryptographic algorithms has been questioned. The reason is that by using quantum computers and executing specific quantum algorithms through them, the computational difficulties of conventional cryptographic algorithms can be reduced, which makes it possible to overcome and break them in a relatively short period of time. Therefore, researchers began efforts to find new quantum-resistant cryptographic algorithms that would be impossible to break, even using quantum computers, in a short time. Such algorithms are called post-quantum cryptographic algorithms. In this article, we provide a comprehensive review of the challenges and vulnerabilities of different kinds of conventional cryptographic algorithms against quantum computers. Afterward, we review the latest cryptographic algorithms and standards that have been proposed to confront the threats posed by quantum computers. We present the classification of post-quantum cryptographic algorithms and digital signatures based on their technical specifications, provide examples of each category, and outline the strengths and weaknesses of each category.