Global AI and Data Science

 View Only
Expand all | Collapse all

About Prime Factorization by Quantum Computer

  • 1.  About Prime Factorization by Quantum Computer

    Posted Fri March 31, 2023 03:26 AM

    I often hear that quantum computing can be used to prime factorize large composite numbers, making it easier to break cryptography that was considered secure . What properties of quantum computing algorithms make them suitable for prime factorization of large composite numbers?

    I have an image that quantum computing algorithms explore multiple possibilities at the same time and gradually bring the correct answer to the surface. 
    If this image I have is correct, I can understand that quantum computers are suitable for problem such as the traveling salesman problem , searching mazes Etc... Why do I think so? It is because that these problems can be reduced to the problem of searching a huge binary tree. So we can take advantage of the quantum computer's characteristic to search multiple branches at the same time in the process of finding the correct leaf while tracing the branches.

    In prime factorization of large numbers, does the algorithm perform something like dividing a given integer a by integers from 2 to √a in parallel?



    ------------------------------
    Ken Iida
    Ken.Iida@kyndryl.com
    NagoyaJapan
    ------------------------------


  • 2.  RE: About Prime Factorization by Quantum Computer

    Posted Mon April 03, 2023 02:10 AM

    Veritasium has an very interesting video on the subject: https://www.youtube.com/watch?v=-UrdExQW0cs



    ------------------------------
    Lennart Jonsson
    ------------------------------



  • 3.  RE: About Prime Factorization by Quantum Computer

    Posted Fri April 07, 2023 02:14 AM
    Edited by Ken Iida Fri April 07, 2023 02:16 AM

    I have read various articles explaining Shor's algorithm, but it seems that many of them have omitted the explanation that the 0th power of every integer  is 1. I think it's good that this Youtube article emphasizes this point in an easy-to-understand manner.



    ------------------------------
    Ken Iida
    Ken.Iida@kyndryl.com
    NagoyaJapan
    ------------------------------



  • 4.  RE: About Prime Factorization by Quantum Computer

    Posted Mon April 03, 2023 02:38 AM
    Edited by Diego Cardalliaguet Mon April 03, 2023 04:38 AM

    Hello Ken,
    Your image is not fully correct. There are no multiple possibilities calculations at the same time. Entanglement is a collective state for quantum particles (with particle read in a broad sense: protons, electrons, photons  and other species in the quantum world) where the state of a quantum variable is correlated among them all. In that situation you can manipulate the collective set of particles and induce states, it is at this stage where quantum computers do the calculations.
    Entanglement is a delicate state and you can lose it very easily with external interference with your system of particles. After manipulating the state of your collective, most of the times you need to measure to understand what happened. This very act of measuring breaks the state and, what you get as outcome are the probabilities of each of the members of the collective to be in one state. All these relations are established and manipulated using Linear Algebra and operators that, for dimensions 2 and 3 can be represented by matrices, and by tensors in higher dimensions (there are other formulations but Linear Algebra is quite familiar for many people).
    Now, let's go to the factorization problem. 

    The standard algorithm for quantum factorization is Shor's algorithm. You can find a technical description in here. What it does is a substitution of the complex problem of factorization by a less-complex-but-yet-complex problem of period finding in moddular division. I won't explain here how it works but how entanglement is used. 
    A technique called Phase Kickback is used to induce states in from one (or several) qubits to another (or several) qubit. A unitary operator (linear algebra) is built that implements modular multiplication. It is used to measure the quantum phase of several of these unitary operations that leads to measure the period of modular multiplication and then it's possible to perform classical operations to obtain the factors.

    All this is to explain that each of the complex problems (as of today) will require specific algorithms for quantum calculations and, that entanglement is not a magic wand to be generally used to solve many problems. The difficulty of having proper algorithms for complex problems is to understand how to implement useful entanglements to solve problems and provide them with meaning.
    Very probably this explanation would need some corrections but I believe it contains the basical ideas to understand how it works.



    ------------------------------
    Diego Cardalliaguet
    Europe GEO Technical Sales
    IBM
    ------------------------------



  • 5.  RE: About Prime Factorization by Quantum Computer

    Posted Mon April 03, 2023 03:31 AM

    I understand as follows, is it correct?

    (1)For prime factorization, once I find the period of a function like the one below, I can follow the procedure to get the answer.
         f(x) = a^x  mod  m
    (2)One of the areas of expertise of quantum computers is the Fourier transform.
    (3)A Fourier transform is used to find the period of this function, thus taking advantage of quantum computers.





    ------------------------------
    Ken Iida
    Ken.Iida@kyndryl.com
    NagoyaJapan
    ------------------------------



  • 6.  RE: About Prime Factorization by Quantum Computer

    Posted Mon April 03, 2023 03:59 AM

    You understand it well:

    https://www.math.mcgill.ca/darmon/courses/12-13/nt/projects/Fangxi-Lin.pdf

    Regards, 
    D.



    ------------------------------
    Diego Cardalliaguet
    Europe, Middle East and Africa GEO Technical Sales
    IBM
    ------------------------------



  • 7.  RE: About Prime Factorization by Quantum Computer

    Posted Tue April 04, 2023 02:34 AM

    This thread of yesterday remembered me about this article that is quite enlightening about entanglement. I hope that you'll enjoy it.



    ------------------------------
    Diego Cardalliaguet
    Europe, Middle East and Africa GEO Technical Sales
    IBM
    ------------------------------



  • 8.  RE: About Prime Factorization by Quantum Computer

    Posted Wed April 05, 2023 12:08 AM
    Edited by Ken Iida Wed April 05, 2023 04:00 AM

     this article  is very interesting.
    The parables using shapes, colors and good and evil were very easy to understand. I think that the mysterious part of quantum mechanics is well explained in this article.



    ------------------------------
    Ken Iida
    Ken.Iida@kyndryl.com
    NagoyaJapan
    ------------------------------



  • 9.  RE: About Prime Factorization by Quantum Computer

    IBM Champion
    Posted Wed June 21, 2023 06:39 AM

    Well, the properties of quantum computing algorithms that make them suitable for prime factorization of large composite numbers are:

    • Quantum superposition: Quantum computers can store information in a superposition of states, which means that they can represent multiple possibilities at the same time. This is essential for prime factorization, because it allows the computer to try all possible factors of a number simultaneously.
    • Quantum entanglement: Quantum entanglement allows quantum computers to share information between different qubits. This is important for prime factorization, because it allows the computer to communicate the results of its calculations to other qubits, which can then be used to further the factorization process.
    • Quantum parallelism: Quantum parallelism is the ability of quantum computers to perform multiple calculations simultaneously. This is essential for prime factorization, because it allows the computer to factor a number much faster than a classical computer.

    Your image of quantum computing algorithms exploring multiple possibilities at the same time is true. This is the basis of quantum algorithms for many different problems, including prime factorization. But in the case of prime factorization, the algorithm does not divide a given integer a by integers from 2 to √a in parallel. Instead, it uses quantum superposition to try all possible factors of a at the same time. This allows the computer to factor a number much faster than a classical computer, which would have to try each possible factor individually.

    And to be specific, the algorithm used for prime factorization is called Shor's algorithm. 

    I hope this gives you a clear idea !



    ------------------------------
    Youssef Sbai Idrissi
    Software Engineer
    ------------------------------



  • 10.  RE: About Prime Factorization by Quantum Computer

    Posted Fri June 23, 2023 02:20 PM

    Your understanding of quantum computing algorithms exploring multiple possibilities simultaneously is correct. One of the fundamental properties of quantum computing that enables efficient prime factorization is called quantum superposition. In classical computing, you would indeed need to perform divisions sequentially by testing each potential factor. However, quantum computing algorithms, such as Shor's algorithm, leverage superposition and a phenomenon called quantum parallelism to perform computations on multiple inputs simultaneously.

    Shor's algorithm, specifically designed for prime factorization, utilizes quantum parallelism to evaluate the function f(x) = a^x mod N, where N is the number to be factored and a is a randomly chosen base. By applying quantum techniques, the algorithm can evaluate this function for a range of values simultaneously, exploring multiple potential factors in parallel.

    Moreover, quantum algorithms can also exploit another crucial quantum property known as entanglement. This property allows qubits (quantum bits) to become correlated in such a way that the state of one qubit depends on the state of another, even if they are physically separated. Shor's algorithm employs entanglement to extract information about the periodicity of the function f(x), which leads to the discovery of the prime factors.

    Therefore, through the combined use of superposition and entanglement, quantum algorithms like Shor's can efficiently determine the prime factors of large composite numbers. This capability poses a significant challenge to certain cryptographic systems that rely on the computational difficulty of factorization for their security.



    ------------------------------
    Robert Collins
    ------------------------------