Details

Autor(en) / Beteiligte

• Weng-Long Chang
• Mang Feng

Titel

Fast Quantum Algorithms of Solving an Instance of Quadratic Congruence on a Quantum Computer

Ist Teil von

• 2012 Fifth International Symposium on Parallel Architectures, Algorithms and Programming, 2012, p.295-302

Ort / Verlag

IEEE

Erscheinungsjahr

2012

Quelle

IEEE Xplore

Beschreibungen/Notizen

• It is assumed that P is the product of two prime numbers q 1 and q 2 . If there is an integer 0 <; M <; P such that M 2 = C (mod P), i.e., the congruence has a solution, then C is said to be a quadratic congruence (mod P). Quadratic congruence (mod P) is a NP-complete problem. If the value of C is equal to one, then four integer solutions for M 2 = 1 (mod P) are, respectively, b, P - b, 1 and P - 1, where 1 <; P - b <; (P / 2) and (P / 2) <; b <; P - 1. This is a special case of quadratic congruence (mod P). In this paper, it is shown that four integer solutions for M 2 = 1 (mod P) can be found by means of the proposed quantum algorithms with polynomial quantum gates, polynomial quantum bits and the successful probability that is the same as that of Shor's order-finding algorithm.