Shors Algorithm Using Efficient Approximate Quantum Fourier Transform

Oonishi Kento, Kunihiro Noboru

Shors Algorithm Using Efficient Approximate Quantum Fourier Transform

説明

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 T gates of the original. Moreover, it requires one-fourth of the T-depth of the original. Finally, a T-scheduling method for running the circuit with the smallest KQ (where K is the number of logical qubits and Q is the circuit depth) is presented.

収録刊行物

IEEE Transactions on Quantum Engineering

IEEE Transactions on Quantum Engineering 4 3102016-, 2023-09-25

Institute of Electrical and Electronics Engineers