On efficient quantum block encoding of pseudo-differential operators

Haoya Li1, Hongkang Ni2, and Lexing Ying1,2

1Department of Mathematics, Stanford University, Stanford, CA 94305
2Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA 94305

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


Block encoding lies at the core of many existing quantum algorithms. Meanwhile, efficient and explicit block encodings of dense operators are commonly acknowledged as a challenging problem. This paper presents a comprehensive study of the block encoding of a rich family of dense operators: the pseudo-differential operators (PDOs). First, a block encoding scheme for generic PDOs is developed. Then we propose a more efficient scheme for PDOs with a separable structure. Finally, we demonstrate an explicit and efficient block encoding algorithm for PDOs with a dimension-wise fully separable structure. Complexity analysis is provided for all block encoding algorithms presented. The application of theoretical results is illustrated with worked examples, including the representation of variable coefficient elliptic operators and the computation of the inverse of elliptic operators without invoking quantum linear system algorithms (QLSAs).

Block encoding lies at the core of many existing quantum algorithms. Meanwhile, efficient and explicit block encodings of dense operators are commonly acknowledged as a challenging problem. This paper presents a comprehensive study of the block encoding of a rich family of dense operators: the pseudo-differential operators (PDOs). We develop novel block-encoding schemes for three types of PDOs with different structures. In addition to a thorough complexity analysis, we provide explicit examples where different PDOs are represented with the proposed block-encoding schemes.

► BibTeX data

► References

[1] D. An and L. Lin. Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm. ACM Transactions on Quantum Computing, 3: 1–28, 2022. 10.1145/​3498331.

[2] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Physical review letters, 114: 090502, 2015. 10.1103/​PhysRevLett.114.090502.

[3] G. Beylkin and L. Monzón. On approximation of functions by exponential sums. Applied and Computational Harmonic Analysis, 19: 17–48, 2005. 10.1016/​j.acha.2005.01.003.

[4] D. Camps and R. Van Beeumen. Fable: Fast approximate quantum circuits for block-encodings. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 104–113. IEEE, 2022. 10.1109/​QCE53715.2022.00029.

[5] D. Camps, L. Lin, R. Van Beeumen, and C. Yang. Explicit quantum circuits for block encodings of certain sparse matrice. arXiv preprint arXiv:2203.10236, 2022. 10.48550/​arXiv.2203.10236.

[6] Y. Cao, A. Papageorgiou, I. Petras, J. Traub, and S. Kais. Quantum algorithm and circuit design solving the poisson equation. New Journal of Physics, 15 (1): 013021, 2013. 10.1088/​1367-2630/​15/​1/​013021.

[7] G. Castelazo, Q. T. Nguyen, G. De Palma, D. Englund, S. Lloyd, and B. T. Kiani. Quantum algorithms for group convolution, cross-correlation, and equivariant transformations. Physical Review A, 106: 032402, 2022. 10.1103/​PhysRevA.106.032402.

[8] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint arXiv:2003.02831, 2020. 10.48550/​arXiv.2003.02831.

[9] 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. 10.1137/​16M1087072.

[10] A. M. Childs, J.-P. Liu, and A. Ostrander. High-precision quantum algorithms for partial differential equations. Quantum, 5: 574, 2021. 10.22331/​q-2021-11-10-574.

[11] D. Coppersmith. An approximate fourier transform useful in quantum factoring. arXiv preprint quant-ph/​0201067, 2002. 10.48550/​arXiv.quant-ph/​0201067.

[12] P. C. Costa, S. Jordan, and A. Ostrander. Quantum algorithm for simulating the wave equation. Physical Review A, 99: 012323, 2019. 10.1103/​PhysRevA.99.012323.

[13] P. C. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3: 040303, 2022. 10.1103/​PRXQuantum.3.040303.

[14] A. J. da Silva and D. K. Park. Linear-depth quantum circuits for multiqubit controlled gates. Physical Review A, 106: 042602, 2022. 10.1103/​PhysRevA.106.042602.

[15] L. Demanet and L. Ying. Discrete symbol calculus. SIAM review, 53: 71–104, 2011. 10.1137/​080731311.

[16] Y. Dong, X. Meng, K. B. Whaley, and L. Lin. Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 103: 042419, 2021. 10.1103/​PhysRevA.103.042419.

[17] Y. Dong, L. Lin, H. Ni, and J. Wang. Infinite quantum signal processing. arXiv preprint arXiv:2209.10162, 2022. 10.48550/​arXiv.2209.10162.

[18] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019. 10.1145/​3313276.3316366.

[19] L. Grover and T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/​0208112, 2002. 10.48550/​arXiv.quant-ph/​0208112.

[20] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3: 190, 2019. 10.22331/​q-2019-10-07-190.

[21] A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103: 150502, 2009. 10.1103/​PhysRevLett.103.150502.

[22] A. Y. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52: 1191, 1997. 10.1070/​RM1997v052n06ABEH002155.

[23] A. Y. Kitaev, A. Shen, M. N. Vyalyi, and M. N. Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002. 10.1090/​gsm/​047.

[24] L. Lin and Y. Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4: 361, 2020. 10.22331/​q-2020-11-11-361.

[25] G. H. Low and I. L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical review letters, 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501.

[26] A. Mahasinghe and J. Wang. Efficient quantum circuits for toeplitz and hankel matrices. Journal of Physics A: Mathematical and Theoretical, 49: 275301, 2016. 10.1088/​1751-8113/​49/​27/​275301.

[27] S. McArdle, A. Gilyén, and M. Berta. Quantum state preparation without coherent arithmetic. arXiv preprint arXiv:2210.14892, 2022. 10.48550/​arXiv.2210.14892.

[28] A. Montanaro and S. Pallister. Quantum algorithms and the finite element method. Physical Review A, 93: 032324, 2016. 10.1103/​PhysRevA.93.032324.

[29] Y. Nam, Y. Su, and D. Maslov. Approximate quantum fourier transform with o (n log (n)) t gates. NPJ Quantum Information, 6: 26, 2020. 10.1038/​s41534-020-0257-5.

[30] Q. T. Nguyen, B. T. Kiani, and S. Lloyd. Quantum algorithm for dense and full-rank kernels using hierarchical matrices. Quantum, 6: 876, 2022. 10.22331/​q-2022-12-13-876.

[31] M. A. Nielsen and I. Chuang. Quantum computation and quantum information. American Association of Physics Teachers, 2002. 10.1119/​1.1463744.

[32] E. G. Rieffel and W. H. Polak. Quantum computing: A gentle introduction. MIT Press, 2011. 10.1063/​PT.3.1442.

[33] S. Sachdeva, N. K. Vishnoi, et al. Faster algorithms via approximation theory. Foundations and Trends in Theoretical Computer Science, 9: 125–210, 2014. 10.1561/​0400000065.

[34] E. M. Stein and T. S. Murphy. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 3. Princeton University Press, 1993. ISBN 9780691032160. URL https:/​/​press.princeton.edu/​books/​hardcover/​9780691032160/​harmonic-analysis-pms-43-volume-43.

[35] Y. Tong, D. An, N. Wiebe, and L. Lin. Fast inversion, preconditioned quantum linear system solvers, fast green's-function computation, and fast evaluation of matrix functions. Physical Review A, 104, 2021. 10.1103/​PhysRevA.104.032422.

[36] R. Vale, T. M. D. Azevedo, I. Araújo, I. F. Araujo, and A. J. da Silva. Decomposition of multi-controlled special unitary single-qubit gates. arXiv preprint arXiv:2302.06377, 2023. 10.48550/​arXiv.2302.06377.

[37] M. W. Wong. An Introduction to Pseudo-Differential Operators. World Scientific, 1999. 10.1142/​4047.

[38] L. Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6: 842, 2022. 10.22331/​q-2022-10-20-842.

Cited by

[1] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, and Mikel Sanz, "Efficient quantum amplitude encoding of polynomial functions", Quantum 8, 1297 (2024).

[2] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yiğit Subaşı, "Efficient quantum linear solver algorithm with detailed running costs", arXiv:2305.11352, (2023).

[3] David Jennings, Matteo Lostaglio, Robert B. Lowrie, Sam Pallister, and Andrew T. Sornborger, "The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts", arXiv:2309.07881, (2023).

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