# Product Decomposition of Periodic Functions in Quantum Signal Processing

Jeongwan Haah

Microsoft Quantum and Microsoft Research, Redmond, Washington, USA

### 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.

### ► 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] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, and Matthias Troyer, "Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm", Quantum 4, 287 (2020).

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

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

[5] Guang Hao Low and Isaac L. Chuang, "Hamiltonian Simulation by Qubitization", arXiv:1610.06546.

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2020-07-14 08:08:49) and SAO/NASA ADS (last updated successfully 2020-07-14 08:08:50). The list may be incomplete as not all publishers provide suitable and complete citation data.