Quantum computers are known to be qualitatively more powerful than classical computers, but so far only a small number of different algorithms have been discovered that actually use this potential. It would therefore be highly desirable to develop other types of quantum algorithms that widen the range of possible applications. Here we propose an efficient and exact quantum algorithm for finding the square-free part of a large integer - a problem for which no efficient classical algorithm exists. The algorithm relies on properties of Gauss sums and uses the quantum Fourier transform. We give an explicit quantum network for the algorithm. Our algorithm introduces new concepts and methods that have not been used in quantum information processing so far and may be applicable to a wider class of problems.Quantum computers are known to be qualitatively more powerful than classical computers, but so far only a small number of different algorithms have been discovered that actually use this potential. It would therefore be highly desirable to develop other types of quantum algorithms that widen the range of possible applications. Here we propose an efficient and exact quantum algorithm for finding the square-free part of a large integer - a problem for which no efficient classical algorithm exists. The algorithm relies on properties of Gauss sums and uses the quantum Fourier transform. We give an explicit quantum network for the algorithm. Our algorithm introduces new concepts and methods that have not been used in quantum information processing so far and may be applicable to a wider class of problems.

Scientific ReportsFeb 10, 201228 citations

Efficient Quantum Algorithms for Estimating Gauss Sums

Wim van Dam, G. Seroussi

We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.

arXiv:quant-ph/0207131Jul 23, 200238 citations

Quantum Fourier Transform and Related Algorithms

Santanu Pattanayak

In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.

Apress eBooksJan 1, 20210 citations

Quantum multiplication algorithm based on the convolution theorem

Mehdi Ramezani, Morteza Nikaeen, Farnaz Farman +2 more

The problem of efficient multiplication of large numbers has been a long-standing challenge in classical computation and has been extensively studied for centuries. It appears that the existing classical algorithms are close to their theoretical limit and offer little room for further enhancement. However, with the advent of quantum computers and the need for quantum algorithms that can perform multiplication on quantum hardware, a new paradigm emerges. In this paper, inspired by the convolution theorem and quantum amplitude amplification paradigm we propose a quantum algorithm for integer multiplication with time complexity of $O(\sqrt{n}{log}^{2}n)$ which outperforms the best-known classical algorithm, the Harvey algorithm with time complexity of $O(nlogn)$ . Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers, making it a versatile choice for a wide range of integer multiplication tasks. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.The problem of efficient multiplication of large numbers has been a long-standing challenge in classical computation and has been extensively studied for centuries. It appears that the existing classical algorithms are close to their theoretical limit and offer little room for further enhancement. However, with the advent of quantum computers and the need for quantum algorithms that can perform multiplication on quantum hardware, a new paradigm emerges. In this paper, inspired by the convolution theorem and quantum amplitude amplification paradigm we propose a quantum algorithm for integer multiplication with time complexity of $O(\sqrt{n}{log}^{2}n)$ which outperforms the best-known classical algorithm, the Harvey algorithm with time complexity of $O(nlogn)$. Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers, making it a versatile choice for a wide range of integer multiplication tasks. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.

arXiv:2306.08473Physical Review ANov 6, 20238 citations

Factoring Gaussian Integers: A Quantum Algorithm

Mingwei Wu

In this paper, we developed a quantum algorithm for factoring Gaussian integers based on Shor's Algorithm. It is one of the problems that are intractable for classical computers but are manageable for quantum computers. An efficient quantum algorithm for factoring is influential in the application of cryptography because a large portion of the current cryptographic schemes rely on the assumption that factoring is difficult. We also discuss potential generalizations of our algorithm to other algebraic integers.In this paper, we developed a quantum algorithm for factoring Gaussian integers based on Shor's Algorithm. It is one of the problems that are intractable for classical computers but are manageable for quantum computers. An efficient quantum algorithm for factoring is influential in the application of cryptography because a large portion of the current cryptographic schemes rely on the assumption that factoring is difficult. We also discuss potential generalizations of our algorithm to other algebraic integers.

2021 2nd International Conference on Electronics, Communications and Information Technology (CECIT)Dec 1, 20211 citation

Quantum probabilistic subroutines and problems in number theory

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.

arXiv:quant-ph/9907020Physical Review AAug 18, 200011 citations

O(\sqrt{n}{log}^{2}n)

which outperforms the best-known classical algorithm, the Harvey algorithm with time complexity of

O(nlogn)

. Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers, making it a versatile choice for a wide range of integer multiplication tasks. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.