Click here to flash read.
arXiv:2404.16450v1 Announce Type: cross
Abstract: In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in $(\mathbb{Z}/N\mathbb{Z})^{\times}$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
Click here to read this post out
ID: 823534; Unique Viewers: 0
Unique Voters: 0
Total Votes: 0
Votes:
Latest Change: April 26, 2024, 7:32 a.m.
Changes:
Dictionaries:
Words:
Spaces:
Views: 9
CC:
No creative common's license
No creative common's license
Comments: