Top

Quantum Information Processing

Published in:

01-03-2017

Quantum Fourier transform in computational basis

Authors: S. S. Zhou, T. Loke, J. A. Izaac, J. B. Wang

Published in: Quantum Information Processing | Issue 3/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The quantum Fourier transform, with exponential speed-up compared to the classical fast Fourier transform, has played an important role in quantum computation as a vital part of many quantum algorithms (most prominently, Shor’s factoring algorithm). However, situations arise where it is not sufficient to encode the Fourier coefficients within the quantum amplitudes, for example in the implementation of control operations that depend on Fourier coefficients. In this paper, we detail a new quantum scheme to encode Fourier coefficients in the computational basis, with fidelity \(1 - \delta \) and digit accuracy \(\epsilon \) for each Fourier coefficient. Its time complexity depends polynomially on \(\log (N)\), where N is the problem size, and linearly on \(1/\delta \) and \(1/\epsilon \). We also discuss an application of potential practical importance, namely the simulation of circulant Hamiltonians.

previous article Generalized quantum counting algorithm for non-uniform amplitude distribution

next article Limitations on post-processing assisted quantum programming

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

\(\left| y_k - {\tilde{y}}_k \right| < \epsilon \), where \({\tilde{y}}_k\) is the truncated value of \(y_k\) with accuracy \(\epsilon = 2^{-p_0}\).

\(\left| \left\langle {\Psi ^{\text {final}}}\right| \left( \frac{1}{\sqrt{N}} \sum _{k=0}^{N-1} \left| {k}\right\rangle \left| {{\tilde{y}}_k}\right\rangle \right) \right| \ge 1 - \delta \), where \(\left| {\Psi ^{\text {final}}}\right\rangle \) is the state obtained through the QFTC algorithm.

\(\Vert \hbox {e}^{-iCt} - \widetilde{\hbox {e}^{-iCt}}\Vert \le \delta \), where \(\widetilde{\hbox {e}^{-iCt}}\) represents the operator that is actually performed by this algorithm.

Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484 (1997)MathSciNetCrossRefMATH

Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A Math. Phys. Eng. Sci. 400, 97 (1985). doi:10.1098/rspa.1985.0070 ADSMathSciNetCrossRefMATH

Bergland, G.: A guided tour of the fast Fourier transform. IEEE Spectr. 6, 41 (1969)ADSCrossRef

Cleve, R., Watrous, J.: Fast parallel circuits for the quantum Fourier transform. In: 41st Annual Symposium on Foundations of Computer Science Proceedings, pp. 526–536 (2000)

Kitaev, A.Y.: Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph/9511026 (1995)

Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) Automata, languages and programming No. 1443 in Lecture Notes in Computer Science, pp. 820–831. Springer, Berlin (1998)

Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002)MathSciNetCrossRefMATH

Benenti, G., Strini, G.: Quantum simulation of the single-particle Schrödinger equation. Am. J. Phys. 76, 657 (2008)ADSCrossRef

Kassal, I., Jordan, S.P., Love, P.J., Mohseni, M., Aspuru-Guzik, A.: Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proc. Natl. Acad. Sci. 105(48), 18681 (2008)ADSCrossRef

10.

Szkopek, T., Roychowdhury, V., Yablonovitch, E., Abrams, D.S.: Eigenvalue estimation of differential operators with a quantum algorithm. Phys. Rev. A 72, 062318 (2005)ADSCrossRef

11.

Hales, L., Hallgren, S.: An improved quantum Fourier transform algorithm and applications. In: 41st Annual Symposium on Foundations of Computer Science Proceedings, pp. 515–525 (2000)

12.

Schützhold, R.: Pattern recognition on a quantum computer. Phys. Rev. A 67, 062311 (2003)ADSMathSciNetCrossRef

13.

van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36, 763 (2006)MathSciNetCrossRefMATH

14.

Jordan, S.P.: Fast quantum algorithm for numerical gradient estimation. Phys. Rev. Lett. 95, 050501 (2005)ADSCrossRef

15.

Qiang, X., Loke, T., Montanaro, A., Aungskunsiri, K., Zhou, X., O’Brien, J.L., Wang, J.B., Matthews, J.C.F.: Efficient quantum walk on a quantum processor. arXiv:1510.08657 [quant-ph] (2015)

16.

Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)ADSMathSciNetCrossRef

17.

Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411 (2013)

18.

Rebentrost, P., Mohseni, M., Lloyd, S.: Quantum support vector machine for big data classification. Phys. Rev. Lett. 113(13), 130503 (2014)ADSCrossRef

19.

Giovannetti, V., Lloyd, S., Maccone, L.: Architectures for a quantum random access memory. Phys. Rev. A 78(5), 052310 (2008)ADSCrossRefMATH

20.

Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph/0208112 (2002)

21.

Kaye, P., Mosca, M.: Quantum networks for generating arbitrary quantum states. arXiv:quant-ph/0407102 (2004)

22.

Soklakov, A.N., Schack, R.: Efficient state preparation for a register of quantum bits. Phys. Rev. A 73, 012307 (2006)ADSCrossRef

23.

Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001)ADSCrossRef

24.

Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge University Press, Cambridge (2010)CrossRefMATH

25.

Ramos, G.U.: Roundoff error analysis of the fast Fourier transform. Math. Comput. 25(116), 757–768 (1971)MathSciNetCrossRef

26.

Tasche, M., Zeuner, H.: Worst and average case roundoff error analysis for FFT. BIT Numer. Math. 41(3), 563–581 (2001)MathSciNetCrossRefMATH

27.

Bell, R.: Introductory Fourier transform spectroscopy. Elsevier, Amsterdam (2012)

28.

Delanty, M., Steel, M.: Discretely-observable continuous time quantum walks on Moöbius strips and other exotic structures in 3D integrated photonics. Phys. Rev. A 86, 043821 (2012)ADSCrossRef

29.

Yoneda, T., Sung, Y.M., Lim, J.M., Kim, D., Osuka, A.: PdII complexes of [44]- and [46] Decaphyrins: the largest Hückel aromatic and antiaromatic, and Möbius aromatic macrocycles. Angew. Chem. Int. Ed. Engl. 53, 13169 (2014)CrossRef

30.

Olson, B.J., Shaw, S.W., Shi, C., Pierre, C., Parker, R.G.: Circulant matrices and their application to vibration analysis. Appl. Mech. Rev. 66, 040803 (2014)ADSCrossRef

31.

Cheng, B., Fan, J., Jia, X., Jia, J.: Parallel construction of independent spanning trees and an application in diagnosis on mobius cubes. J. Supercomput. 65, 1279 (2013)CrossRef

32.

Golub, G.H., Van Loan, C.F.: Matrix computations, vol. 3. JHU Press, Baltimore (2012)MATH

33.

Mülken, O., Blumen, A.: Continuous-time quantum walks: models for coherent transport on complex networks. Phys. Rep. 502, 37 (2011)ADSMathSciNetCrossRef

34.

Childs, A.M.: Quantum information processing in continuous time. Ph.D. thesis, Massachusetts Institute of Technology (2004)

35.

Childs, A.M., Kothari, R.: Limitations on the simulation of non-sparse hamiltonians. arXiv preprint arXiv:0908.4398 (2009)

36.

Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv:quant-ph/0410184 (2004)

37.

Draper, T.G., Kutin, S.A., Rains, E.M., Svore, K.M.: A logarithmic-depth quantum carry-lookahead adder. Quantum Info. Comput. 6, 351–369 (2006)MathSciNetMATH

38.

Álvarez-Sánchez, J.J., Álvarez-Bravo, J.V., Nieto, L.M.: A quantum architecture for multiplying signed integers. J. Phys. Conf. Ser. 128, 012013 (2008)CrossRef

39.

Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54, 147 (1996)ADSMathSciNetCrossRef

40.

Draper, T.G.: Addition on a quantum computer. arXiv:quant-ph/0008033 (2000)

41.

Ruiz-Perez, L., Garcia-Escartin, J.C.: Quantum arithmetic with the quantum Fourier transform. arXiv:1411.5949 [quant-ph] (2014)

42.

Maynard, C.M., Pius, E.: A quantum multiply-accumulator. Quantum Inf. Process. 13(5), 1127 (2013). doi:10.1007/s11128-013-0715-5 ADSMathSciNetCrossRefMATH

43.

Maynard, C.M., Pius, E.: Integer arithmetic with hybrid quantum-classical circuits. arXiv:1304.4069 (2013)

44.

Pavlidis, A., Gizopoulos, D.: Fast quantum modular exponentiation architecture for Shor’s factoring algorithm. Quantum Info. Comput. 14(7&8), 649–682 (2014)MathSciNet

45.

Kline, M.: Calculus: an intuitive and physical approach. Courier Corporation, North Chelmsford (1998)

Title: Quantum Fourier transform in computational basis
Authors: S. S. Zhou
T. Loke
J. A. Izaac
J. B. Wang
Publication date: 01-03-2017
Publisher: Springer US
Published in: Quantum Information Processing / Issue 3/2017
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-017-1515-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2017

Quantum correlations in a family of bipartite separable qubit states

Evolution prediction from tomography

Generation of concatenated Greenberger–Horne–Zeilinger-type entangled coherent state based on linear optics

Dynamic quantum secret sharing by using d-dimensional GHZ state

Limitations on post-processing assisted quantum programming

Transferring multiqubit entanglement onto memory qubits in a decoherence-free subspace