Shor algorithm
The Shor algorithm is an algorithm from the mathematical branch of number theory that uses quantum computer science . It calculates a nontrivial divisor of a composite number on a quantum computer and thus belongs to the class of factorization methods .
The Shor algorithm cannot yet be used for practically relevant tasks, since up to now (as of 2020) there are no sufficiently large and low-error quantum computers available. A number of binary digits (i. E., ) To factor, a quantum computer requires a quantum register , the size of at least grows linearly with the number of binary digits. Shor's original algorithm requires 3n qubits , the best known variant manages with 2n + 3 qubits. These numbers apply to an ideal (error-free) quantum computer. In practice it is necessary to use quantum error correction methods. Then by a (large, but constant in n ) factor M more physical qubits are required, where M depends very strongly on the error rate and the error correction code used. It is estimated that 10 to 100 million qubits are required for a 2048-bit number (in the absence of errors it would only be a few thousand). For example, a research group at the US company IBM used a quantum computer with seven qubits in 2001 to break down the number 15 into the factors 5 and 3.
The Shor algorithm is very important for cryptography because it finds a nontrivial divisor essentially faster than classical algorithms : While these require subexponential, but significantly higher than polynomial runtime , the Shor algorithm only has polynomial runtime . This represents a danger, for example, for the RSA cryptosystems that are often used for encrypted data transmission , the security of which is based precisely on the assumption that there is no factoring method with a polynomial runtime.
The algorithm was published in 1994 by Peter Shor , who was then employed by AT&T Bell Laboratories . The work is entitled Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer . This also describes a second algorithm for calculating the discrete logarithm , which is also referred to as the Shor algorithm. In general, however, this term is used for the factorization procedure.
properties
The Shor algorithm is a probabilistic algorithm . In some cases, depending on the number of repetitions, it leads to no result; the algorithm thus belongs to the class of Monte Carlo algorithms .
- Input: A composite number .
- Output: A non-trivial factor of .
- Runtime: gate operations.
procedure
The basic idea is that factorization can be reduced to determining the order . This determination can be carried out effectively with the aid of the quantum Fourier transform . The algorithm is therefore often divided into a classic part to reduce the problem and a quantum part that efficiently solves the remaining problem .
Classic part
- Pick a number with .
- Find the , (e.g. using the Euclidean algorithm ). If the result is not 1, return this as the solution and terminate. Otherwise go to the next step.
- Determine with the help of the quantum part (see below) the order of in the prime residue class group (the smallest such that ). Step 2 made sure that one exists.
- Start again at 1 if:
- is odd, or
- .
- Give back as a solution.
Solution in the last step
Consider the product ( ) * ( ) = . After step 3 we know that: that does not apply: (step 4) and that does not apply: (step 3, since the smallest number with is and applies), from which it follows that contains nontrivial factors of ; the Euclidean algorithm for calculating the supplies these divisors in polynomial time.
Number of iterations for the part invention
The probability of obtaining a factor by randomly choosing is at least , where the number of mutually different prime factors is (not equal to 2). If, for example, is composed of only two prime factors, one gets a solution with a probability of 1/2 per run, so the probability of failure after steps is only .
Quantum part
- Determine as a power of 2 with .
- Initialize the first quantum register (input register) with the superposition (see qubit ) of all states ( is a number smaller than ). This results in the state: .
- Initialize the second register (output register) with the superposition of the states . The result is the state: .
- Leads to the first register the quantum Fourier transformation through, wherein: so that we have: .
- Take a measurement (read the contents of the registers). The probability of the state with given by: . For this the relationship or applies , so that we can write: This discrete function has characteristic maxima for values of a variable that satisfy the relationship through amplification . It can be shown that for the given relationships of and there is at most one such value for fixed . This can be used to calculate if and are relatively prime. (The probability for this case is at least or , that is, we get with a high probability after repetitions.)
- Return the calculated value if it is actually the order of , otherwise repeat the experiment.
literature
- M. Homeister: Understanding Quantum Computing . 5th edition. Springer Vieweg, Wiesbaden 2018, ISBN 978-3-658-22883-5 , p. 223 ff.
- B. Lenze: Mathematics and Quantum Computing . Logos Verlag, Berlin 2020, second edition, ISBN 978-3-832-54716-5 , pp. 89ff.
- RJ Lipton, KW Regan: Quantum Algorithms via Linear Algebra: A Primer . MIT Press, Cambridge MA 2014, ISBN 978-0-262-02839-4 , pp. 97 ff.
- MA Nielsen, IL Chuang: Quantum Computation and Quantum Information . Cambridge University Press, Cambridge MA 2010, ISBN 978-1-107-00217-3 , p. 234 ff.
- W. Scherer: Mathematics of quantum informatics . Springer-Verlag, Berlin / Heidelberg 2016, ISBN 978-3-662-49079-2 , p. 206 ff.
- CP Williams: Explorations in Quantum Computing . Springer-Verlag, London 2011, second edition, ISBN 978-1-846-28886-9 , pp. 272 ff.
- IBM's Test Tube Quantum Computer Makes History; First Demonstration Of Shor's Historic Factoring Algorithm - ScienceDaily, December 20, 2001
Individual evidence
- ↑ ^{a } ^{b} Craig Gidney, Martin Ekerå: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits . May 23, 2019, Tables 1 and 2 , arxiv : 1905.09749 (English).
- ↑ Lieven MK Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang: Experimental realization of an order-finding algorithm with an NMR quantum computer. In: Nature , 414/2001, pp. 883-887, doi: 10.1038 / 414883a
- ↑ Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing , 26/1997, pp. 1484–1509, arxiv : quant-ph / 9508027