|
|
 |
| |
|
|
|
A New Simple Quantum Algorithm for Finding Two Prime Factors of a Composite Integer |
|
|
|
PP: 9-13 |
|
|
|
doi:10.18576/qpl/090102
|
|
|
|
Author(s) |
|
|
|
Dhananjay P. Mehendale,
|
|
|
|
Abstract |
|
|
| We present a new simple quantum algorithm for factoring composite integers assuming that we can successfully perform the
non-unitary operation of projecting certain quantum state by some quantum dynamics in a reasonably less time. Let M be a “known”
composite integer with two nearly equal “unknown” prime factors P,Q. Thus, M = PQ, 0 < M < 2
n − 1. 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 ≤ 2
n −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 f, f : A → B, defined as f(|xi|yi) = |xyi, where xy is the product
of x and y. The unitary transformation, Uf
, corresponding to 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, we get a “sum” state through operating Uf
, namely, |Ψ1i = 1
2
n ∑
2
n−1
x=0 ∑
2
n−1
y=0
(|xi|yi)A(|xyi)B
and thus register A gets entangled with register B through Uf
. We then operate V = I ⊗U, on |Ψ1i where I is Identity operator
operating on register A and U = ∑
2
n−1
z=0
|zihz|, operating on register B, leading to V|Ψ1i = |Ψ2i. We further operate a non-unitary
operator W = I ⊗ |MihM| on |Ψ2i producing |Ψ3i = W|Ψ2i where |MihM| operating on register B is projector in the direction of a
“known” computational basis state |Mi. After the action of unitary operator V if we can perform the “successful” action of the nonunitary operator W by some quantum dynamics in reasonably less time then we will arrive at the following required quantum state:
|Φi = 1
2
(|1i|Mi+|Pi|Qi+|Qi|Pi)+|Mi|1i)A(|Mi)B. The desired prime factors will then be revealed through partial measurement of
any of the sub-registers A1,A2.
|
|
|
|
|
|
|
|
