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] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", Quantum 7, 1031 (2023).

[4] Rahul Sarkar and Theodore J. Yoder, "Density theorems with applications in quantum signal processing", Journal of Computational and Applied Mathematics 430, 115243 (2023).

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

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

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

[8] Matthew Thibodeau and Bryan K. Clark, "Nearly-frustration-free ground state preparation", Quantum 7, 1084 (2023).

[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] I. Novikau, E. A. Startsev, and I. Y. Dodin, "Quantum signal processing for simulating cold plasma waves", Physical Review A 105 6, 062444 (2022).

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

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

[15] 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).

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

[17] 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).

[18] 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).

[19] I. Novikau, I.Y. Dodin, and E.A. Startsev, "Simulation of Linear Non-Hermitian Boundary-Value Problems with Quantum Singular-Value Transformation", Physical Review Applied 19 5, 054012 (2023).

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

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

[22] Nishchay Suri, Joseph Barreto, Stuart Hadfield, Nathan Wiebe, Filip Wudarski, and Jeffrey Marshall, "Two-Unitary Decomposition Algorithm and Open Quantum System Simulation", Quantum 7, 1002 (2023).

[23] 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).

[24] 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).

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

[26] 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).

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

[28] 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).

[29] 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).

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

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

[32] 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).

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

[34] 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).

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

[36] Youle Wang, Lei Zhang, Zhan Yu, and Xin Wang, "Quantum Phase Processing and its Applications in Estimating Phase and Entropies", arXiv:2209.14278, (2022).

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

[38] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).

[39] Lorenzo Laneve, "Quantum Signal Processing, Phase Extraction, and Proportional Sampling", arXiv:2303.11077, (2023).

[40] Lorenzo Laneve, "Robust black-box quantum-state preparation via quantum signal processing", arXiv:2305.04705, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 12:45:05) and SAO/NASA ADS (last updated successfully 2023-09-21 12:45:07). 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.