Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. [1] [2] It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms. [3] On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. [4] Another concern is that noise in quantum circuits may undermine results, [5] requiring additional qubits for quantum error correction.
Shor proposed multiple similar algorithms for solving the factoring problem, the discrete logarithm problem, and the period-finding problem. "Shor's algorithm" usually refers to the factoring algorithm, but may refer to any of the three algorithms. The discrete logarithm algorithm and the factoring algorithm are instances of the period-finding algorithm, and all three are instances of the hidden subgroup problem.
On a quantum computer, to factor an integer , Shor's algorithm runs in polynomial time, meaning the time taken is polynomial in . [6] It takes quantum gates of order using fast multiplication, [7] or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven, [8] thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP . This is significantly faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: . [9]
If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as
RSA is based on the assumption that factoring large integers is computationally intractable. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography.
Given the high error rates of contemporary quantum computers and too few qubits to use quantum error correction, laboratory demonstrations obtain correct results only in a fraction of attempts.
In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored into , using an NMR implementation of a quantum computer with seven qubits. [11] After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits. [12] [13] In 2012, the factorization of was performed with solid-state qubits. [14] Later, in 2012, the factorization of was achieved. [15] In 2016, the factorization of was performed again using trapped-ion qubits with a recycling technique. [16] In 2019, an attempt was made to factor the number using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors. [17] However, all these demonstrations have compiled the algorithm by making use of prior knowledge of the answer, and some have even oversimplified the algorithm in a way that makes it equivalent to coin flipping. [18] Furthermore, attempts using quantum computers with other algorithms have been made. [19] However, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms. [20]
Theoretical analyses of Shor's algorithm assume a quantum computer free of noise and errors. However, near-term practical implementations will have to deal with such undesired phenomena (when more qubits are available, Quantum error correction can help). In 2023, Jin-Yi Cai showed that in the presence of noise, Shor's algorithm fails asymptotically almost surely for large semiprimes that are products of two primes in OEIS sequenceA073024. [5] These primes have the property that has a prime factor larger than , and have a positive density in the set of all primes. Hence error-correction will be needed to be able to factor all numbers with Shor's algorithm.
The problem that we are trying to solve is: given an odd composite number , find its integer factors .
To achieve this, Shor's algorithm consists of two parts:
A complete factoring algorithm is possible if we're able to efficiently factor arbitrary into just two integers and greater than 1, since if either or are not prime then the factoring algorithm can in turn be run on those until only primes remain.
A basic observation is that, using Euclid's algorithm, we can always compute the GCD between two integers efficiently. In particular, this means we can check efficiently whether is even, in which case 2 is trivially a factor. Let us thus assume that is odd for the remainder of this discussion. Afterwards, we can use efficient classical algorithms to check if is a prime power. [21] For prime powers, efficient classical factorization algorithms exist, [22] hence the rest of the quantum algorithm may assume that is not a prime power.
If those easy cases do not produce a nontrivial factor of , the algorithm proceeds to handle the remaining case. We pick a random integer . A possible nontrivial divisor of can be found by computing , which can be done classically and efficiently using the Euclidean algorithm. If this produces a nontrivial factor (meaning ), the algorithm is finished, and the other nontrivial factor is . If a nontrivial factor was not identified, then that means that and the choice of are coprime, so is contained in the multiplicative group of integers modulo , having a multiplicative inverse modulo . Thus, has a multiplicative order modulo , meaning
and is the smallest positive integer satisfying this congruence.
The quantum subroutine finds . It can be seen from the congruence that divides , written . This can be factored using difference of squares: Since we have factored the expression in this way, the algorithm doesn't work for odd (because must be an integer), meaning the algorithm would have to restart with a new . Hereafter we can therefore assume is even. It cannot be the case that , since this would imply , which would contradictorily imply that would be the order of , which was already . At this point, it may or may not be the case that . If it is not true that , then that means we are able to find a nontrivial factor of . We computeIf , then that means was true, and a nontrivial factor of cannot be achieved from , and the algorithm must restart with a new . Otherwise, we have found a nontrivial factor of , with the other being , and the algorithm is finished. For this step, it is also equivalent to compute ; it will produce a nontrivial factor if is nontrivial, and will not if it's trivial (where ).
The algorithm restated shortly follows: let be odd, and not a prime power. We want to output two nontrivial factors of .
It has been shown that this will be likely to succeed after a few runs. [2] In practice, a single call to the quantum order-finding subroutine is enough to completely factor with very high probability of success if one uses a more advanced reduction. [23]
The goal of the quantum subroutine of Shor's algorithm is, given coprime integers and , to find the order of modulo , which is the smallest positive integer such that . To achieve this, Shor's algorithm uses a quantum circuit involving two registers. The second register uses qubits, where is the smallest integer such that , i.e., . The size of the first register determines how accurate of an approximation the circuit produces. It can be shown that using qubits gives sufficient accuracy to find . The exact quantum circuit depends on the parameters and , which define the problem. The following description of the algorithm uses bra–ket notation to denote quantum states, and to denote the tensor product, rather than logical AND.
The algorithm consists of two main steps:
The connection with quantum phase estimation was not discussed in the original formulation of Shor's algorithm, [2] but was later proposed by Kitaev. [24]
In general the quantum phase estimation algorithm, for any unitary and eigenstate such that , sends input states to output states close to , where is an integer close to . In other words, it sends each eigenstate of to a state close to the associated eigenvalue. For the purposes of quantum order-finding, we employ this strategy using the unitary defined by the actionThe action of on states with is not crucial to the functioning of the algorithm, but needs to be included to ensure the overall transformation is a well-defined quantum gate. Implementing the circuit for quantum phase estimation with requires being able to efficiently implement the gates . This can be accomplished via modular exponentiation, which is the slowest part of the algorithm. The gate thus defined satisfies , which immediately implies that its eigenvalues are the -th roots of unity . Furthermore, each eigenvalue has an eigenvector of the form , and these eigenvectors are such that
where the last identity follows from the geometric series formula, which implies .
Using quantum phase estimation on an input state would then return the integer with high probability. More precisely, the quantum phase estimation circuit sends to such that the resulting probability distribution is peaked around , with . This probability can be made arbitrarily close to 1 using extra qubits.
Applying the above reasoning to the input , quantum phase estimation thus results in the evolutionMeasuring the first register, we now have a balanced probability to find each , each one giving an integer approximation to , which can be divided by to get a decimal approximation for .
Then, we apply the continued fractions algorithm to find integers and , where gives the best fraction approximation for the approximation measured from the circuit, for and coprime and . The number of qubits in the first register, , which determines the accuracy of the approximation, guarantees thatgiven the best approximation from the superposition of was measured [2] (which can be made arbitrarily likely by using extra bits and truncating the output). However, while and are coprime, it may be the case that and are not coprime. Because of that, and may have lost some factors that were in and . This can be remedied by rerunning the quantum order-finding subroutine an arbitrary number of times, to produce a list of fraction approximationswhere is the number of times the subroutine was run. Each will have different factors taken out of it because the circuit will (likely) have measured multiple different possible values of . To recover the actual value, we can take the least common multiple of each :The least common multiple will be the order of the original integer with high probability. In practice, a single run of the quantum order-finding subroutine is in general enough if more advanced post-processing is used. [25]
Phase estimation requires choosing the size of the first register to determine the accuracy of the algorithm, and for the quantum subroutine of Shor's algorithm, qubits is sufficient to guarantee that the optimal bitstring measured from phase estimation (meaning the where is the most accurate approximation of the phase from phase estimation) will allow the actual value of to be recovered.
Each before measurement in Shor's algorithm represents a superposition of integers approximating . Let represent the most optimal integer in . The following theorem guarantees that the continued fractions algorithm will recover from :
Theorem — If and are bit integers, and then the continued fractions algorithm run on will recover both and .
[3] As is the optimal bitstring from phase estimation, is accurate to by bits. Thus,which implies that the continued fractions algorithm will recover and (or with their greatest common divisor taken out).
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. [26] [27] 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.
Shor's algorithms for the discrete log and the order finding problems are instances of an algorithm solving the period finding problem.[ citation needed ]. All three are instances of the hidden subgroup problem.
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, where 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 , a quantum algorithm exists for solving the hidden subgroup for in polynomial time. [3]
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. Theoretically a large-scale quantum computer could break widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is largely experimental and impractical, with several obstacles to useful applications.
In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two spin states can also be measured as horizontal and vertical linear polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of multiple states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.
The Hadamard transform is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on 2m real numbers.
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems such as factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's algorithms for factoring and finding discrete logarithms in quantum computing are instances of the hidden subgroup problem for finite abelian groups, while the other problems correspond to finite groups that are not abelian.
The time-evolving block decimation (TEBD) algorithm is a numerical scheme used to simulate one-dimensional quantum many-body systems, characterized by at most nearest-neighbour interactions. It is dubbed Time-evolving Block Decimation because it dynamically identifies the relevant low-dimensional Hilbert subspaces of an exponentially larger original Hilbert space. The algorithm, based on the Matrix Product States formalism, is highly efficient when the amount of entanglement in the system is limited, a requirement fulfilled by a large class of quantum many-body systems in one dimension.
BB84 is a quantum key distribution scheme developed by Charles Bennett and Gilles Brassard in 1984. It is the first quantum cryptography protocol. The protocol is provably secure assuming a perfect implementation, relying on two conditions: (1) the quantum property that information gain is only possible at the expense of disturbing the signal if the two states one is trying to distinguish are not orthogonal ; and (2) the existence of an authenticated public classical channel. It is usually explained as a method of securely communicating a private key from one party to another for use in one-time pad encryption. The proof of BB84 depends on a perfect implementation. Side channel attacks exist, taking advantage of non-quantum sources of information. Since this information is non-quantum, it can be intercepted without measuring or cloning quantum particles.
The one-way quantum computer, also known as measurement-based quantum computer (MBQC), is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.
Amplitude amplification is a technique in quantum computing which generalizes the idea behind Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and independently rediscovered by Lov Grover in 1998.
In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. The algorithm was initially introduced by Alexei Kitaev in 1995.
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith. With small modifications to the QFT, it can also be used for performing fast integer arithmetic operations such as addition and multiplication.
Algorithmic cooling is an algorithmic method for transferring heat from some qubits to others or outside the system and into the environment, which results in a cooling effect. This method uses regular quantum operations on ensembles of qubits, and it can be shown that it can succeed beyond Shannon's bound on data compression. The phenomenon is a result of the connection between thermodynamics and information theory.
The Harrow–Hassidim–Lloyd algorithm or HHL algorithm is a quantum algorithm for numerically solving a system of linear equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.
Quantum image processing (QIMP) is using quantum computing or quantum information processing to create and work with quantum images.
The swap test is a procedure in quantum computation that is used to check how much two quantum states differ, appearing first in the work of Barenco et al. and later rediscovered by Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. It appears commonly in quantum machine learning, and is a circuit used for proofs-of-concept in implementations of quantum computers.
The One Clean Qubit model of computation is performed an qubit system with one pure state and maximally mixed states. This model was motivated by highly mixed states that are prevalent in Nuclear magnetic resonance quantum computers. It's described by the density matrix , where is the identity matrix. In computational complexity theory, DQC1; also known as the Deterministic quantum computation with one clean qubit is the class of decision problems solvable by a one clean qubit machine in polynomial time, upon measuring the first qubit, with an error probability of at most 1/poly(n) for all instances.
In quantum computing, the variational quantum eigensolver (VQE) is a quantum algorithm for quantum chemistry, quantum simulations and optimization problems. It is a hybrid algorithm that uses both classical computers and quantum computers to find the ground state of a given physical system. Given a guess or ansatz, the quantum processor calculates the expectation value of the system with respect to an observable, often the Hamiltonian, and a classical optimizer is used to improve the guess. The algorithm is based on the variational method of quantum mechanics.
In quantum computing, phase kickback refers to the fact that controlled operations have effects on their controls, in addition to on their targets, and that these effects correspond to phasing operations. The phase of one qubit is effectively transferred to another qubit during a controlled operation, creating entanglement and computational advantages that enable various popular quantum algorithms and protocols.