Quantum Algorithm for Prime Factorization with High Probability

FU Xiang-qun; BAO Wan-su; ZHOU Chun; ZHONG Pu-cha

您当前的位置：

首页 >

文章列表页 >

Quantum Algorithm for Prime Factorization with High Probability

更新时间：2025-07-16

- Quantum Algorithm for Prime Factorization with High Probability
- Acta Electronica Sinica Vol. 39, Issue 1, Pages: 35-39(2011)
- 作者机构：
  
  解放军信息工程大学电子技术学院,河南,郑州,450004
- 作者简介：
- 基金信息：
- DOI：
  CLC： TN301.6
- Published：2011
- 稿件说明：
移动端阅览
FU Xiang-qun, BAO Wan-su, ZHOU Chun, et al. Quantum Algorithm for Prime Factorization with High Probability[J]. Acta Electronica Sinica, 2011, 39(1): 35-39.
DOI：

FU Xiang-qun, BAO Wan-su, ZHOU Chun, et al. Quantum Algorithm for Prime Factorization with High Probability[J]. Acta Electronica Sinica, 2011, 39(1): 35-39. DOI：

摘要

本文基于量子Fourier变换给出了一个新的整数分解量子算法

通过利用多次量子Fourier变换和变量代换

使得

变成相位因子(r是从模N整数环中所选元素的阶)

进而可使非零的非目标态的几率幅变为零

算法成功的概率大于3/4

高于Shor整数分解量子算法

且不再依赖于

的大小(Shor算法成功的概率依赖于

的大小)

同时还将新算法的资源消耗情况与Shor算法进行了对比.

Abstract

In this paper

based on the quantum Fourier transform

we give a new quantum algorithm for prime factorization.The algorithm turns

to be phase factor under repeated application of Fourier transform and variate transform

where

is the order of a selective element in the ring of integers modulo

.Furthermore the amplitude of the non-target states except zero state is modified to be 0.Our algorithm's success probability

which is more than 3/4 and higher than Shor's algorithm

doesn't depend on the size of

other than Shor's algorithm.Meanwhile

we present a comparison of the required resource between the new algorithm and Shor's algorithm.

关键词

Keywords

references

Views

1609

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem

Convergence Characteristics of Multi-scale Quantum Harmonic Oscillator Algorithm

Analysis of a Public-Key Cryptograph Based on Multi-Discrete Logarithm Problems

Related Author

BAO Wan-su

SONG Zhen

ZHONG Pu-cha

FU Xiang-qun

WANG Peng

HUANG Yan

YUAN Ya-nan

DU Zheng

Related Institution

Yueyang Army Subarea of Hunan ProvinceYueyangHunan 414000China

Institute of Electronic Technologythe PLA Information Engineering UniversityZhengzhouHenan 450004China

Yueyang Army Subarea of Hunan Province

Parallel Computing Laboratory, Chengdu University of Information Technology

Parallel Computing Laboratory Chengdu University of Information Technology Chengdu Sichuan China

⁰