Product Decomposition of Periodic Functions in Quantum Signal Processing

Jeongwan Haah

doi:10.22331/q-2019-10-07-190

Product Decomposition of Periodic Functions in Quantum Signal Processing

Microsoft Quantum and Microsoft Research, Redmond, Washington, USA

Published:	2019-10-07, volume 3, page 190
Eprint:	arXiv:1806.10236v4
Doi:	https://doi.org/10.22331/q-2019-10-07-190
Citation:	Quantum 3, 190 (2019).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We consider an algorithm to approximate complex-valued periodic functions $f(e^{i\theta})$ as a matrix element of a product of $SU(2)$-valued functions, which underlies so-called quantum signal processing. We prove that the algorithm runs in time $\mathcal O(N^3 \mathrm{polylog}(N/\epsilon))$ under the random-access memory model of computation where $N$ is the degree of the polynomial that approximates $f$ with accuracy $\epsilon$; previous efficiency claim assumed a strong arithmetic model of computation and lacked numerical stability analysis.

► BibTeX data

@article{Haah2019product,
  doi = {10.22331/q-2019-10-07-190},
  url = {https://doi.org/10.22331/q-2019-10-07-190},
  title = {Product {D}ecomposition of {P}eriodic {F}unctions in {Q}uantum {S}ignal {P}rocessing},
  author = {Haah, Jeongwan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {190},
  month = oct,
  year = {2019}
}

► References

[1] G. H. Low and I. L. Chuang, ``Optimal Hamiltonian simulation by quantum signal processing,'' Phys. Rev. Lett. 118, 010501 (2017), arXiv:1606.02685.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685

[2] G. H. Low, T. J. Yoder, and I. L. Chuang, ``Methodology of resonant equiangular composite quantum gates,'' Phys. Rev. X 6, 041067 (2016), arXiv:1603.03996.
https://doi.org/10.1103/PhysRevX.6.041067
arXiv:1603.03996

[3] G. H. Low and I. L. Chuang, ``Hamiltonian simulation by Qubitization,'' Quantum 3, 163 (2019), arXiv:1610.06546.
https://doi.org/10.22331/q-2019-07-12-163
arXiv:1610.06546

[4] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics,'' in STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019) pp. 193–204, arXiv:1806.01838.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838

[5] A. M. Childs and N. Wiebe, ``Hamiltonian simulation using linear combinations of unitary operations,'' Quantum Information and Computation 12, 901–924 (2012), arXiv:1202.5822.
arXiv:1202.5822

[6] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, ``Exponential improvement in precision for simulating sparse Hamiltonians,'' in Proceedings of the 46th ACM Symposium on Theory of Computing (STOC) (2014) pp. 283–292, arXiv:1312.1414.
https://doi.org/10.1145/2591796.2591854
arXiv:1312.1414

[7] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, ``Toward the first quantum simulation with quantum speedup,'' Proceedings of the National Academy of Sciences 115, 9456–9461 (2018), arXiv:1711.10980.
https://doi.org/10.1073/pnas.1801723115
arXiv:1711.10980

[8] J. Haah, M. Hastings, R. Kothari, and G. H. Low, ``Quantum algorithm for simulating real time evolution of lattice hamiltonians,'' in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018) pp. 350–360.
https://doi.org/10.1109/FOCS.2018.00041

[9] A. W. Harrow, A. Hassidim, and S. Lloyd, ``Quantum algorithm for solving linear systems of equations,'' Phys. Rev. Lett. 15, 150502 (2009), arXiv:0811.3171.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171

[10] A. Shamir, ``Factoring numbers in $O(\log n)$ arithmetic steps,'' Information Processing Letters 8, 28–31 (1979).
https://doi.org/10.1016/0020-0190(79)90087-5

[11] A. Schönhage, ``On the power of random access machines,'' in Automata, Languages and Programming. ICALP 1979. Lecture Notes in Computer Science,, Vol. 71, edited by M. H.A. (Springer, Berlin, Heidelberg, 1979) pp. 520–529.
https://doi.org/10.1007/3-540-09510-1_42

[12] J. Qian and C. A. Wang, ``How much precision is needed to compare two sums of square roots of integers?'' Information Processing Letters 100, 194 – 198 (2006).
https://doi.org/10.1016/j.ipl.2006.05.002

[13] Q. Cheng, X. Meng, C. Sun, and J. Chen, ``Bounding the sum of square roots via lattice reduction,'' Math. Comp. 79, 1109–1122 (2010), arXiv:0905.4487.
https://doi.org/10.1090/S0025-5718-09-02304-7
arXiv:0905.4487

[14] G. H. Low and I. L. Chuang, ``Hamiltonian simulation by uniform spectral amplification,'' arXiv:1707.05391.
arXiv:1707.05391

[15] V. Y. Pan, ``Optimal and nearly optimal algorithms for approximating polynomial zeros,'' Computers & Mathematics with Applications 31, 97 – 138 (1996).
https://doi.org/10.1016/0898-1221(96)00080-6

[16] G. U. Ramos, ``Roundoff error analysis of the fast fourier transform,'' Mathematics of Computation 25, 757–768 (1971).
https://doi.org/10.2307/2004342

[17] D. Harvey and J. van der Hoeven, ``Faster integer multiplication using short lattice vectors,'' Open Book Series 2, 293–310 (2019), arXiv:1802.07932.
https://doi.org/10.2140/obs.2019.2.293
arXiv:1802.07932

[18] D. E. Knuth, The Art of Computer Programming, 3rd ed., Vol. 2 (Addison-Wesley, 1998).

[19] D. W. Berry, A. M. Childs, and R. Kothari, ``Hamiltonian simulation with nearly optimal dependence on all parameters,'' in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015) pp. 792–809, arXiv:1501.01715.
https://doi.org/10.1109/FOCS.2015.54
arXiv:1501.01715

[20] A. M. Childs, ``On the relationship between continuous- and discrete-time quantum walk,'' Commun. Math. Phys. 294, 581–603 (2010), arXiv:0810.0312.
https://doi.org/10.1007/s00220-009-0930-1
arXiv:0810.0312

[21] D. W. Berry and A. M. Childs, ``Black-box hamiltonian simulation and unitary implementation,'' Quantum Information and Computation 12 (2012), arXiv:0910.4157.
arXiv:0910.4157

[22] J. P. Boyd, ``The rate of convergence of fourier coefficients for entire functions of infinite order with application to the weideman-cloot sinh-mapping for pseudospectral computations on an infinite interval,'' Journal of Computational Physics 110, 360 – 372 (1994).
https://doi.org/10.1006/jcph.1994.1032

[23] M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions (National Bureau of Standards, 1964).

[24] A. M. Childs, R. Kothari, and R. D. Somma, ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision,'' SIAM Journal on Computing 46, 1920–1950 (2017), arXiv:1511.02306.
https://doi.org/10.1137/16M1087072
arXiv:1511.02306

[25] L. K. Grover, ``A fast quantum mechanical algorithm for database search,'' in Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC) (1996) pp. 212–219, arXiv:quant-ph/9605043.
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043

Cited by

[1] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low, "Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians", SIAM Journal on Computing FOCS18-250 (2021).

[2] Lexing Ying, "Stable factorization for phase factors of quantum signal processing", Quantum 6, 842 (2022).

[3] Yulong Dong and Lin Lin, "Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark", Physical Review A 103 6, 062412 (2021).

[4] Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry, "Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem", PRX Quantum 3 4, 040303 (2022).

[5] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe, "Hybridized Methods for Quantum Simulation in the Interaction Picture", Quantum 6, 780 (2022).

[6] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).

[7] Zane M. Rossi and Isaac L. Chuang, "Quantum hypothesis testing with group structure", Physical Review A 104 1, 012425 (2021).

[8] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).

[9] Jiasu Wang, Yulong Dong, and Lin Lin, "On the energy landscape of symmetric quantum signal processing", Quantum 6, 850 (2022).

[10] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).

[11] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 193 (2019) ISBN:9781450367059.

[12] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin, "Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions", Physical Review A 104 3, 032422 (2021).

[13] Yulong Dong, Lin Lin, and Yu Tong, "Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices", PRX Quantum 3 4, 040305 (2022).

[14] I. Novikau, E. A. Startsev, and I. Y. Dodin, "Quantum signal processing for simulating cold plasma waves", Physical Review A 105 6, 062444 (2022).

[15] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, and Matthias Troyer, "Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm", Quantum 4, 287 (2020).

[16] Lin Lin and Yu Tong, "Near-optimal ground state preparation", Quantum 4, 372 (2020).

[17] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).

[18] Koen Groenland, Freek Witteveen, Kareljan Schoutens, and Rene Gerritsma, "Signal processing techniques for efficient compilation of controlled rotations in trapped ions", New Journal of Physics 22 6, 063006 (2020).

[19] Lin Lin and Yu Tong, "Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems", Quantum 4, 361 (2020).

[20] S S Gayathri, R. Kumar, and Samiappan Dhanalakshmi, "Efficient Floating-point Division Quantum Circuit using Newton-Raphson Division", Journal of Physics: Conference Series 2335 1, 012058 (2022).

[21] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J. Yoder, and Sarah Sheldon, "Quantum advantage for computations with limited space", Nature Physics 17 8, 894 (2021).

[22] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin, "Efficient phase-factor evaluation in quantum signal processing", Physical Review A 103 4, 042419 (2021).

[23] Guang Hao Low and Isaac L. Chuang, "Hamiltonian Simulation by Qubitization", Quantum 3, 163 (2019).

[24] Zoe Holmes, Gopikrishnan Muraleedharan, Rolando D. Somma, Yigit Subasi, and Burak Şahinoğlu, "Quantum algorithms from fluctuation theorems: Thermal-state preparation", Quantum 6, 825 (2022).

[25] Guang Hao Low and Isaac L. Chuang, "Hamiltonian Simulation by Qubitization", arXiv:1610.06546, (2016).

[26] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, "Grand Unification of Quantum Algorithms", PRX Quantum 2 4, 040203 (2021).

[27] Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov, "Locality and Digital Quantum Simulation of Power-Law Interactions", Physical Review X 9 3, 031006 (2019).

[28] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low, "Quantum algorithm for simulating real time evolution of lattice Hamiltonians", arXiv:1801.03922, (2018).

[29] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy, "Finding Angles for Quantum Signal Processing with Machine Precision", arXiv:2003.02831, (2020).

[30] Xin Wang, Youle Wang, Zhan Yu, and Lei Zhang, "Quantum Phase Processing: Transform and Extract Eigen-Information of Quantum Systems", arXiv:2209.14278, (2022).

[31] Joran van Apeldoorn and András Gilyén, "Quantum algorithms for zero-sum games", arXiv:1904.03180, (2019).

[32] Guang Hao Low, "Hamiltonian simulation with nearly optimal dependence on spectral norm", arXiv:1807.03967, (2018).

[33] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", arXiv:2208.06941, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-03-22 11:50:20) and SAO/NASA ADS (last updated successfully 2023-03-22 11:50:21). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.