|
|
 |
| |
|
|
|
A New Simple and Efficient Quantum Algorithm for Factoring Composite Integers |
|
|
|
PP: 35-39 |
|
|
|
doi:10.18576/qpl/070202
|
|
|
|
Author(s) |
|
|
|
Dhananjay P. Mehendale,
|
|
|
|
Abstract |
|
|
| We present a new simple and efficient quantum algorithm for factoring composite integers. The key step consists of making
use of the new exponentially fast search algorithm [1]. Let M = PQ, 0 < M < 2n, be a composite integer with two nearly equal prime
factors P,Q to be determined. We prepare register, say A = A1 ⊗A2, where A1 and A2 are sub-registers containing equally weighted
superposition of states |xi and |yi respectively such that 0 ≤ x, y ≤ 2n −1. Register A thus contains equally weighted superposition
of the tensor product states |xi|yi. We also prepare register B to keep the images of elements in register A produced under the action
of the function, f , f : A→B, defined as f (|xi|yi) = |xyi. The transformation, Uf , corresponding to the given fuction f is defined as
Uf : (|xi|yi)A(|0i)B →(|xi|yi)A(|xyi))B, which can also take superposition of states as input. Thus, register A is entangled with register
B through Uf . After building up quantum registers A and B we operate on register B a unitary operator, U, defined as U = åz |vihv|,
where 0 ≤ z ≤ 2n −1, and |vi = |00···0in|zi. The action of U will change the state in register B into the uniform superposition state
1 √2n å2n−1
z=0 |vi, so that that this state now becomes separable and the algorithm in [1] becomes applicable for searching a target state
present as a component state in this modified register B. We then perform the key step of applying [1] on register B for searching the
target state |ti = |00···0in|Mi, and amplify to the full extent the amplitude of this target state so that if we now partially measure the
register B it will almost always be found in this target state |ti = |00···0in|Mi. As a consequence of this the state in register A now
changes into the superposition state 1 √2
(|1i|Mi+|Pi|Qi+|Qi|Pi)+|Mi|1i). This new state in register A now clearly contains the
desired prime factorization which is easily revealed after further partial measurement done on any one of the sub-registers A1,A2. |
|
|
|
|
|
|
|
