A factorisation algorithm in Adiabatic Quantum Computation

被引:2
作者
Kieu, Tien D. [1 ]
机构
[1] Swinburne Univ Technol, Ctr Quantum & Opt Sci, Hawthorn, Vic, Australia
来源
JOURNAL OF PHYSICS COMMUNICATIONS | 2019年 / 3卷 / 02期
关键词
Adiabatic Quantum Computation; Quantum Algorithms; factorisation problem;
D O I
10.1088/2399-6528/ab060d
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
The problem of factorising positive integer N into two integer factors x and y is first reformulated as an optimisation problem over the positive integer domain of either of the Diophantine polynomials Q(N)(x, y) = N-2(N- xy)(2) + x(x - y)(2) or R-N(x, y) = N-2(N-xy)(2) + (x - y)(2) + x, of each of which the optimal solution is unique x <= root N <= y, and x = 1 if and only if N is prime. An algorithm in the context of Adiabatic Quantum Computation is then proposed for the general factorisation problem.
引用
收藏
页数:6
相关论文
共 9 条
[1]  
[Anonymous], 1966, QUANTUM MECH
[2]  
[Anonymous], 2000, ARXIVQUANTPH0007071
[3]   Integer polynomial optimization in fixed dimension [J].
De Loera, JA ;
Hemmecke, R ;
Köppe, M ;
Weismantel, R .
MATHEMATICS OF OPERATIONS RESEARCH, 2006, 31 (01) :147-153
[4]   A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem [J].
Farhi, E ;
Goldstone, J ;
Gutmann, S ;
Lapan, J ;
Lundgren, A ;
Preda, D .
SCIENCE, 2001, 292 (5516) :472-476
[5]  
Jiang S, 2018, ARXIV180402733QUANTP
[6]  
Kieu T. D, 2017, ARXIV170200603QUANTP
[7]  
Kieu TD, 2018, ARXIV180107859QUANTP, DOI [10.1007/s11128-019-2206-9, DOI 10.1007/S11128-019-2206-9]
[8]  
RIVEST RL, 1978, COMMUN ACM, V21, P120, DOI [10.1145/359340.359342, 10.1145/357980.358017]
[9]  
Shor P. W., 1994, P 35 ANN S FDN COMP