Fetching the paper…

Reading the bibliography…

2018

Product Decomposition of Periodic Functions in Quantum Signal Processing

Haah, Jeongwan

Original
PDF
Post on X

Understand

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.

Product Decomposition of Periodic Functions in Quantum Signal Processing · Around

Built on

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions (National Bureau of Standards, 1964)
1964
Earlier work this paper cites.
G. U. Ramos, “Roundoff error analysis of the fast fourier transform,” Mathematics of Computation 25
1971
Earlier work this paper cites.
A. Shamir, “Factoring numbers in O ⁡ ( log ⁡ n ) O(\log n) arithmetic steps,” Information Processing Letters 8
1979
Earlier work this paper cites.
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
1979
Earlier work this paper cites.
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
1994
Earlier work this paper cites.
V. Y. Pan, “Optimal and nearly optimal algorithms for approximating polynomial zeros,” Computers & Mathematics with Applications 31
1996
Earlier work this paper cites.
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
1996
Earlier work this paper cites.
D. E. Knuth, The Art of Computer Programming , 3rd ed., Vol. 2 (Addison-Wesley, 1998)
1998
Earlier work this paper cites.

Similar

J. Qian and C. A. Wang, “How much precision is needed to compare two sums of square roots of integers?” Information Processing Letters 100
2006
Cited alongside, same era.
A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for solving linear systems of equations,” Phys. Rev. Lett. 15
Original
2009
Cited alongside, same era.
Q. Cheng, X. Meng, C. Sun, and J. Chen, “Bounding the sum of square roots via lattice reduction,” Math. Comp. 79
Original
2010
Cited alongside, same era.
A. M. Childs, “On the relationship between continuous- and discrete-time quantum walk,” Commun. Math. Phys. 294
Original
2010
Cited alongside, same era.
A. M. Childs and N. Wiebe, “Hamiltonian simulation using linear combinations of unitary operations,” Quantum Information and Computation 12

Then

G. H. Low, T. J. Yoder, and I. L. Chuang, “Methodology of resonant equiangular composite quantum gates,” Phys. Rev. X 6
Original
2016
Later among the works it cites.
G. H. Low and I. L. Chuang, “Optimal Hamiltonian simulation by quantum signal processing,” Phys. Rev. Lett. 118
Original
2017
Later among the works it cites.
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
Original
2017
Later among the works it cites.
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
Original
2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2012

Cited alongside, same era.

D. W. Berry and A. M. Childs, “Black-box hamiltonian simulation and unitary implementation,” Quantum Information and Computation 12

2012

Cited alongside, same era.

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

2014

Cited alongside, same era.

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

2015

Cited alongside, same era.

G. H. Low and I. L. Chuang, “Hamiltonian simulation by uniform spectral amplification,” arXiv:1707.05391

Cited in the paper.

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

2018

Closest in time.

G. H. Low and I. L. Chuang, “Hamiltonian simulation by Qubitization,” Quantum 3

Original

2019

Closest in time.

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

2019

Closest in time.

D. Harvey and J. van der Hoeven, “Faster integer multiplication using short lattice vectors,” Open Book Series 2

2019

Closest in time.