Research PapersNo Access

QUANTUM PHASE ESTIMATION WITH AN ARBITRARY NUMBER OF QUBITS

CHEN-FU CHIANG

Département de Physique, Université de Sherbrooke Sherbrooke, Québec, Canada J1K 2R1S, Canada

https://doi.org/10.1142/S0219749913500081Cited by:2 (Source: Crossref)

Abstract

Due to the great difficulty in scalability, quantum computers are limited in the number of qubits during the early stages of the quantum computing regime. In addition to the required qubits for storing the corresponding eigenvector, suppose we have additional k qubits available. Given such a constraint k, we propose an approach for the phase estimation for an eigenphase of exactly n-bit precision. This approach adopts the standard recursive circuit for quantum Fourier transform (QFT) in [R. Cleve and J. Watrous, Fast parallel circuits for quantum fourier transform, Proc. 41st Annual Symp. on Foundations of Computer Science (2000), pp. 526–536.] and adopts classical bits to implement such a task. Our algorithm has the complexity of O(n log k), instead of O(n²) in the conventional QFT, in terms of the total invocation of rotation gates. We also design a scheme to implement the factorization algorithm by using k available qubits via either the continued fractions approach or the simultaneous Diophantine approximation.

Keywords:

References

S. Hallgren , Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem , Proc. 34th ACM Symp. on Theory of Computing ( 2002 ) . Google Scholar
P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, Proc. FOCS (1994) pp. 124–134. Google Scholar
P. Shor , SIAM J. Comput. 26 , 1484 ( 1997 ) . Crossref, Web of Science, Google Scholar
M. Szegedy, Quantum speed-up of Markov chain based algorithms, Proc. 45th Annual IEEE Sympo. on Foundations of Computer Science (2004) pp. 32–41. Google Scholar
P. Wocjan et al. , Phys. Rev. 80 , 022340 ( 2009 ) . Crossref, Web of Science, Google Scholar
R. Cleve and J. Watrous, Fast parallel circuits for quantum fourier transform, Annual Symp. Foundations of Computer Sciences (2000) pp. 526–536. Google Scholar
A. Kitaev , A. Shen and M. Vyalyi , Classical and Quantum Computation , Graduate Studies in Mathematics 47 ( American Mathematical Society , 2002 ) . Crossref, Google Scholar
M. Nielsen and I. Chuang , Quantum Computation and Quantum Information ( Cambridge University Press , 2000 ) . Google Scholar
H. Ahmedi and C. Chiang , Quantum Inform. Comput. 12 , ( 2012 ) . Google Scholar
D. Cheung, Improved bounds for the approximate QFT, Proc. Winter Int. Symp. Information and Communication Technologies (WISICT) (2004) pp. 1–6. Google Scholar
S. Parker and M. Plenio , Phys. Rev. Lett. 85 , 3049 ( 2000 ) . Crossref, Web of Science, Google Scholar
J. Seifert, Using fewer qubits in Shor's factorization algorithm via simultaneous diophantine approximation, Proc. Conf. Topics in Cryptology (2001) pp. 319–327. Google Scholar
A. Schönhage and V. Straßen , Computing 7 , 281 ( 1971 ) . Crossref, Web of Science, Google Scholar
R. Griffiths and C. Niu , Phys. Rev. Lett. 76 , 3228 ( 1996 ) . Crossref, Web of Science, Google Scholar
T. Kleinjung et al., Factorization of a 768-bit RSA modulus, International Association for Cryptologic Research, Retrieved 2010-08-09 . Google Scholar
J. Lagarias , SIAM J. Comput. 14 , 196 ( 1985 ) . Crossref, Web of Science, Google Scholar