IEEE Transactions on Quantum Engineering · 2023 · 15 citations · 28 references
ComputingComputer ScienceAlgorithmsCryptographyQuantum ComputingQuantum AlgorithmsQuantum CircuitsQuantum ComputationQuantum CryptographyQuantum Fourier TransformApproximate Quantum Fourier TransformDiscrete Logarithm AlgorithmsDiscrete Logarithm ProblemPolynomial Time ComplexityPolynomial-time AlgorithmsQuantum Circuit Implementations Of Fourier TransformShor's AlgorithmShor's Factoring Algorithm
Shor's algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor's algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform is proposed, and it is applied to Rines and Chuang's implementation. The proposed implementation requires one-third the number of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> gates of the original. Moreover, it requires one-fourth the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> -depth of the original. Finally, a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> -scheduling method for running the circuit with the smallest KQ is presented.
28
Algorithms for quantum computation: discrete logarithms and factoring
Peter W. Shor · 2002 · 8.5K citations
Computing, Computer Science, Physics +12
Quantum supremacy using a programmable superconducting processor
Nature · 2019 · 7K citations · Full text
Computing, Computer Science, Physics +14
Neal Koblitz · Mathematics of Computation · 1987 · 984 citations
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Quantum · 2021 · 660 citations · Full text
Computing, Computer Science, Physics +17