User:Fawly/sandbox/shor
Procedure
[edit]The problem that we are trying to solve is, given a composite number , to find a non-trivial divisor of (a divisor strictly between and ). Before attempting to find such a divisor, if there's any doubt whether is composite or prime, one can use relatively quick primality-testing algorithms to verify that is indeed composite, although this is not a part of Shor's algorithm.
Shor's algorithm consists of two parts:
- A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
- A quantum algorithm to solve the order-finding problem.
The aim of the algorithm is to find a non-trivial square root of modulo that is different from and , because then
for a non-zero integer that gives us two distinct non-trivial divisors and of . This idea is similar to other factoring algorithms, such as the quadratic sieve, and a more detailed explanation can be found in the Explanation section below. Before starting the algorithm, it is imperative to check to be odd (otherwise is a divisor) and not to be any power of an integer (otherwise that integer is a divisor), so as to guarantee the existence of a non-trivial square root of modulo .
In turn, finding such a is reduced to finding an element as a parameter in an integer function, such that the function has an even period with a certain additional property (as explained below, it is required that the condition of Step 6 of the classical part does not hold). The quantum algorithm is used for finding the period of randomly chosen elements , as this is a difficult problem on a classical computer.
Classical part
[edit]- Pick a random number .
- Compute , the greatest common divisor of and . This may be done using the Euclidean algorithm.
- If , then is a nontrivial factor of , so we are done.
- Otherwise, use the quantum period-finding subroutine (below) to find , which denotes the period of the following function:
- If is odd, then go back to step 1.
- If , then go back to step 1.
- Otherwise, both or are nontrivial factors of , so we are done.
For example: Given , , and , we have , where and . For that is a product of two distinct primes, and , , which for is , and divides .
Quantum part: period-finding subroutine
[edit]![]() | This section may be too technical for most readers to understand.(February 2014) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6b/Shor%27s_algorithm.svg/450px-Shor%27s_algorithm.svg.png)
The quantum circuits used for this algorithm are custom designed for each choice of and each choice of the random used in . Given , find such that , which implies that . The input and output qubit registers need to hold superpositions of values from to , and so have qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least different values of that produce the same , even as the period approaches .
Proceed as follows:
- Initialize the registers to
where denotes the tensor product.
This initial state is a superposition of states, and is easily obtained by generating independent qubits, each a superposition of and states. We can accomplish this by initializing the qubits to the zero-position, and then applying the Hadamard gate in parallel to each of the qubits, where . - Construct as a quantum function and apply it to the above state, to obtain
- Apply the inverse quantum Fourier transform to the input register. This transform (operating on a superposition of states) uses a -th root of unity such as to distribute the amplitude of any given state equally among all of the states, and to do so in a different way for each different . We thus obtain
- be a -th root of unity,
- be the period of ,
- be the smallest of the for which (we have ), and
- write
- indexes these , running from to , so that .
- Perform a measurement. We obtain some outcome in the input register and some outcome in the output register. As is periodic, the probability of measuring some state is given by
- Since is close to some integer , the known value is close to the unknown value . Performing [classical] continued fraction expansion on allows us to find approximations of it that satisfy two conditions:
Given these multiple conditions (and assuming is irreducible), is very likely to be the appropriate period , or at least a factor of it.
- .
- .
- Check (classically) if . If so, then we are done.
- Otherwise, (classically) obtain more candidates for by using multiples of , or by using other with near . If any candidate works, then we are done.
- Otherwise, try again starting from step 1 of this subroutine.
Explanation of the algorithm
[edit]The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function and may be implemented classically. The second part finds the period using the quantum Fourier transform and is responsible for the quantum speedup.
Non-trivial square root of 1
[edit]Shor's algorithm hinges on finding a non-trivial square root of modulo ; That is, a solution to
where .
If such exists, we claim that is a proper factor of , i.e., . In fact, if , then divides , so that , which goes against the construction of . If, on the other hand, , then by Bézout's identity, there are integers such that
Multiplying both sides by , we obtain
As divides , we find that divides , so that , again contradicting the construction of .
Therefore, is the required proper factor of . Similarly, it can be proven that is also a proper factor of .
For such a non-trivial square root of modulo to exist, notice that , and for any power of an odd prime , there is no non-trivial square root of modulo : For any either or has to be a multiple of .
Therefore, for Shor's algorithm to work, we need to be odd (otherwise is a divisor) and not to be any power of an odd prime (otherwise that prime is a divisor). We can check that there are no integer roots for , and if is not a power of any integer, it is not a power of any odd prime. Here, the upper bound for the integer that we need to check is determined by , since for to be odd, cannot be . This check, however, cannot rule out that may be an odd prime itself, which can only be ruled out by primality-testing algorithms.
Given that is odd and not any power of an odd prime, based on the fundamental theorem of arithmetic, we may assume that is the product of two coprime integers greater than ( and ). From the four combinations of choosing plus sign and minus sign in the integer equations , based on the Chinese remainder theorem and , there are at least four distinct square roots of modulo , and therefore at least two distinct non-trivial square roots exist. In fact, they are the solutions to and .
Obtaining factors from period
[edit]The integers less than and coprime with form the multiplicative group of integers modulo , which is a finite abelian group . The size of this group is given by . By the end of step 3, we have an integer in this group. As the group is finite, must have a finite order , which is the smallest positive integer such that
This is the order of the finite cyclic subgroup ⟨a⟩ of the group , which is the smallest positive integer for which . Since and are coprime, by Euler's totient theorem, must exist, and divides , where denotes Euler's totient function.
Therefore, divides (also written ). Suppose that we are able to obtain and that it is even. (If is odd, then by step 5, we have to restart the algorithm with a different random number ) Now is a square root of modulo that is different from . This is because is the order of modulo , so , or else the order of in this group would be . If , then by step 6, we have to restart the algorithm with a different random number .
Eventually, we must hit an of order in such that . This is because such a is a square root of modulo other than and , whose existence is guaranteed by the Chinese remainder theorem, as the odd number is not a prime power.
Finding the period
[edit]Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously.
Physicists call this behavior a "superposition" of states. To compute the period of a function , we evaluate the function at all points simultaneously.
Quantum physics does not allow us to access all this information directly, however. A measurement will yield only one of all possible values, destroying all others. If not for the no-cloning theorem, we could first measure without measuring , and then make a few copies of the resulting state (which is a superposition of states all having the same ). Measuring on these states would provide different values which give the same , leading to the period. Because we cannot make exact copies of a quantum state, this method does not work. Therefore, we have to carefully transform the superposition to another state that will return the correct answer with high probability. This is achieved by the quantum Fourier transform.
Shor thus had to solve three "implementation" problems. All of them had to be implemented "fast", which means that they can be implemented with a number of quantum gates that is polynomial in .
- Create a superposition of states. This can be done by applying Hadamard gates to all qubits in the input register. Another approach would be to use the quantum Fourier transform (see below).
- Implement the function as a quantum transform. To achieve this, Shor used repeated squaring for his modular exponentiation transformation. It is important to note that this step is more difficult to implement than the quantum Fourier transform, in that it requires ancillary qubits and substantially more gates to accomplish.
- Perform a quantum Fourier transform. By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with ) that uses just gates.[2]
After all these transformations, a measurement will yield an approximation to the period . For simplicity assume that there is a such that is an integer. Then the probability to measure is . To see this, we notice that then
for all integers . Therefore, the sum whose square gives us the probability to measure will be , as takes roughly values and thus the probability is . There are possible values of such that is an integer, and also possibilities for , so the probabilities sum to .
The period-finding routine can be considered a variation of the more general quantum phase estimation algorithm to determine the eigenvalue of a unitary corresponding to an eigenvector. In the case of the period-finding routine used in Shor's Algorithm, the unitary in question is modular multiplication by the chosen base mod . While the computational basis is not an eigenvector of this unitary, it is a uniform superposition of its eigenvectors and thus the measurement will give the eigenvalue's phase for one of the eigenvectors. Since not all such phases can be used to extract the period, the retries of the subroutine may be necessary. [3]
The bottleneck
[edit]The runtime bottleneck of Shor's algorithm is quantum modular exponentiation, which is by far slower than the quantum Fourier transform and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with reversible gates, starting with ripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations.[4][5] Reversible circuits typically use on the order of gates for qubits. Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits owing to high constants.
Discrete logarithms
[edit]Given a group with order and generator , suppose we know that , for some , and we wish to compute , which is the discrete logarithm: . Consider the abelian group , where each factor corresponds to modular addition of values. Now, consider the function
This gives us an abelian hidden subgroup problem, as corresponds to a group homomorphism. The kernel corresponds to the multiples of . So, if we can find the kernel, we can find . A quantum algorithm for solving this problem exists. This algorithm is, like the factor-finding algorithm, due to Peter Shor and both are implemented by creating a superposition through using Hadamard gates, followed by implementing as a quantum transform, followed finally by a quantum Fourier transform.[3] Due to this, the quantum algorithm for computing the discrete logarithm is also occasionally referred to as "Shor's Algorithm."
The order-finding problem can also be viewed as a hidden subgroup problem.[3] To see this, consider the group of integers under addition, and for a given such that: , the function
For any finite abelian group G, a quantum algorithm exists for solving the hidden subgroup for G in polynomial time.[3]
See also
[edit]- GEECM, a factorization algorithm said to be "often much faster than Shor's"[6]
- Grover's algorithm
- Peter Shor
References
[edit]- ^ Qiskit authors. "Qiskit Textbook: Quantum Phase Estimation". IBM. Retrieved 7 November 2020.
- ^ Shor 1999, p. 14
- ^ a b c d Nielsen, Michael A.; Chuang, Isaac L. (9 December 2010). Quantum Computation and Quantum Information (PDF) (7th ed.). Cambridge University Press. ISBN 978-1-107-00217-3. Retrieved 24 April 2022.
- ^ Markov, Igor L.; Saeedi, Mehdi (2012). "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation". Quantum Information and Computation. 12 (5–6): 361–394. arXiv:1202.6614. Bibcode:2012arXiv1202.6614M. doi:10.26421/QIC12.5-6-1. S2CID 16595181.
- ^ Markov, Igor L.; Saeedi, Mehdi (2013). "Faster Quantum Number Factoring via Circuit Synthesis". Phys. Rev. A. 87 (1): 012310. arXiv:1301.3210. Bibcode:2013PhRvA..87a2310M. doi:10.1103/PhysRevA.87.012310. S2CID 2246117.
- ^ Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "Post-quantum RSA" (PDF). International Workshop on Post-Quantum Cryptography. Lecture Notes in Computer Science. 10346: 311–329. doi:10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9. Archived (PDF) from the original on 2017-04-20.
Further reading
[edit]![]() | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (September 2010) |
- Nielsen, Michael A. & Chuang, Isaac L. (2010), Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, ISBN 9781107002173.
- Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 0-19-857049-X
- "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented in one of the comments. Scott Aaronson suggests the following 12 references as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
- Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode:1999SIAMR..41..303S, doi:10.1137/S0036144598347011. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
- Quantum Computing and Shor's Algorithm, Matthew Hayward's Quantum Algorithms Page, 2005-02-17, imsa.edu, LaTeX2HTML version of the original LaTeX document, also available as PDF or postscript document.
- Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
- Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294–2, dated 4 Oct 2004, 7 page postscript document.
- Chapter 6 Quantum Computation, 91 page postscript document, Caltech, Preskill, PH229.
- Quantum computation: a tutorial by Samuel L. Braunstein.
- The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
- III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481–681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
- Lavor, C.; Manssur, L. R. U.; Portugal, R. (2003). "Shor's Algorithm for Factoring Large Integers". arXiv:quant-ph/0303175.
- Lomonaco, Jr (2000). "Shor's Quantum Factoring Algorithm". arXiv:quant-ph/0010034. This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
- Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Sanjeev Arora and Boaz Barak, Princeton University. Published as Chapter 10 Quantum Computation of Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4
- A Step Toward Quantum Computing: Entangling 10 Billion Particles, from "Discover Magazine", Dated January 19, 2011.
- Josef Gruska - Quantum Computing Challenges also in Mathematics unlimited: 2001 and beyond, Editors Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5
External links
[edit]- Version 1.0.0 of libquantum: contains a C language implementation of Shor's algorithm with their simulated quantum computer library, but the width variable in shor.c should be set to 1 to improve the runtime complexity.
- PBS Infinite Series created two videos explaining the math behind Shor's algorithm, "How to Break Cryptography" and "Hacking at Quantum Speed with Shor's Algorithm".