We present a quantum implementation of the Euclid algorithm for calculating the Greatest Common Divisor when one of the integers involved is a compound of two odd-valued primes. We discuss a possible application to the quantum factoring problem, for which modular exponentiation is no longer required, and the factors are revealed directly by measurements, although the method does not scale for large numbers in a favourable manner.
We present a quantum implementation of the Euclid algorithm for calculating the Greatest Common Divisor when one of the integers involved is a compound of two odd-valued primes. We discuss a possible application to the quantum factoring problem, for which modular exponentiation is no longer required, and the factors are revealed directly by measurements, although the method does not scale for large numbers in a favourable manner.
We present a quantum algorithm solving the greatest common divisor (GCD) problem. This quantum algorithm possesses similar computational complexity with classical algorithms, such as the well-known Euclidean algorithm for GCD. This algorithm is an application of the quantum algorithms for the hidden subgroup problems, the same as Shor factoring algorithm. Explicit quantum circuits realized by quantum gates for this quantum algorithm are provided. We also give a computer simulation of this quantum algorithm and present the expected outcomes for the corresponding quantum circuit.
Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer N is achieved in a number of steps equal to the number k of its prime factors, -- e.g., if N is the product of two primes, two quantum measurements are enough, regardless of the number of digits n of the number N. Since k is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.
Quantum computation has attracted much attention since it was shown by Shor and Grover the possibility to implement quantum algorithms able to realize, respectively, factoring and searching in a faster way than any other known classical algorithm. It is possible to use Grover algorithm, taking profit of its ability to find a specific value in a unordered database, to find, for example, the zero of a logical function; the minimal or maximal value in a database or to recognize if an odd number is prime or not. Here we show quantum algorithms to solve those cited mathematical problems. The solution requires the use of a quantum bit string comparator being used as oracle. This quantum circuit compares two quantum states and identifies if they are equal or, otherwise, which of them is the largest. Moreover, we also show the quantum bit string comparator allow us to implement conditional statements in quantum computation, a fundamental structure for designing of 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.
The content of this poster is a description of the implementation of two well-known quantum integer factorization methods and, in addition, a proposal of a new, third way along with some examples of its use. For all three methods, the measured results of their circuits will be shown.The first method is Shor's algorithm, where a quantum circuit is used only to find the period of a specially assembled modular exponentiating function. The rest of the algorithm is preprocessing and postprocessing that can be done on a classical computer, so one could say that this is a hybrid algorithm. New results of the successful factorization of the number 119, performed by this algorithm on a real 7-qubit quantum computer, will be presented. It is worth mentioning here that the highest number successfully factorized by this algorithm on a real quantum computer so far was 35.The second method is variational quantum factorization (VQF). In this method, preprocessing builds a system of equations based on the classical binary multiplication procedure of two numbers, resulting in a factorized number. This system of equations is then used to form a Hamiltonian in such a way that its ground state corresponds to the solution of this equation system. Only now the hybrid quantum optimization comes into play to iteratively find this ground state. The advantage over Shor's algorithm is that this method does not require a fault-tolerant quantum computer, but on the other hand it approaches the solution iteratively using a classical computer, which reduces the potential quantum advantage.The new, third method employs Grover's search algorithm in an unusual way to create a quantum factorization circuit. A key part of this approach is the quantum implementation of a multiplying oracle. The main advantage of this method over the previous ones is that it can be used to assemble a relatively simple universal factorization circuit. Moreover, there is almost no preprocessing and postprocessing required. This method is still under development, but this poster will present the first results.
Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.