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.

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

► 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] Joran van Apeldoorn and András Gilyén, "Quantum algorithms for zero-sum games", arXiv:1904.03180.

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

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

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

[5] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, and Matthias Troyer, "Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm", arXiv:1910.01659.

The above citations are from SAO/NASA ADS (last updated 2019-10-15 00:44:12). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-10-15 00:44:10).