Product Decomposition of Periodic Functions in Quantum Signal Processing

Jeongwan Haah

Microsoft Quantum and Microsoft Research, Redmond, Washington, USA

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


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

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

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

[3] G. H. Low and I. L. Chuang, ``Hamiltonian simulation by Qubitization,'' Quantum 3, 163 (2019), 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.

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

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

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

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

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

[10] A. Shamir, ``Factoring numbers in $O(\log n)$ arithmetic steps,'' Information Processing Letters 8, 28–31 (1979).

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

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

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

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

[15] V. Y. Pan, ``Optimal and nearly optimal algorithms for approximating polynomial zeros,'' Computers & Mathematics with Applications 31, 97 – 138 (1996).

[16] G. U. Ramos, ``Roundoff error analysis of the fast fourier transform,'' Mathematics of Computation 25, 757–768 (1971).

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

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

[20] A. M. Childs, ``On the relationship between continuous- and discrete-time quantum walk,'' Commun. Math. Phys. 294, 581–603 (2010), 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.

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

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

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

Cited by

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

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

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

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

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

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

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

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

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

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

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

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

[13] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", arXiv:2103.09717.

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-23 06:34:50) and SAO/NASA ADS (last updated successfully 2021-04-23 06:34:51). The list may be incomplete as not all publishers provide suitable and complete citation data.