Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán Lượng Tử và Kinh điển trong Giải Phương Trình Nhiệt
Tóm tắt
Máy tính lượng tử được dự đoán sẽ vượt trội hơn máy tính cổ điển trong việc giải các phương trình vi phân từng phần, có thể lên đến mức độ gia tăng theo hàm số mũ. Trong bài báo này, chúng tôi xem xét một phương trình vi phân từng phần điển hình—phương trình nhiệt trong một vùng hình chữ nhật—và so sánh chi tiết độ phức tạp của mười thuật toán cổ điển và lượng tử để giải nó, theo nghĩa là tính toán xấp xỉ lượng nhiệt trong một vùng nhất định. Chúng tôi phát hiện rằng, đối với không gian có chiều
$$d \ge 2$$
, có một sự gia tăng tốc độ lượng tử tối đa là bình phương theo nghĩa độ sai lệch cho phép
$$\epsilon $$
khi sử dụng phương pháp dựa trên việc áp dụng đánh giá biên độ vào một cuộc đi bộ ngẫu nhiên cổ điển được tăng tốc. Tuy nhiên, một phương pháp thay thế dựa trên thuật toán lượng tử cho các phương trình tuyến tính không bao giờ nhanh hơn các thuật toán cổ điển tốt nhất.
Từ khóa
#máy tính lượng tử #thuật toán cổ điển #phương trình nhiệt #phương trình vi phân từng phần #tốc độ lượng tửTài liệu tham khảo
Harrow, A., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 15, 150502 (2009). arXiv:0811.3171
Leyton, S., Osborne, T.: A quantum algorithm to solve nonlinear differential equations (2008). arXiv:0812.4423
Clader, B., Jacobs, B., Sprouse, C.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110, 250504 (2013). arXiv:1301.2340
Berry, D.: High-order quantum algorithm for solving linear differential equations. J. Phys. A: Math. Gen. 47, 105301 (2014). arXiv:1010.2745
Berry, D., Childs, A., Ostrander, A., Wang, G.: Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Commun. Math. Phys. 356, 1057 (2017). arXiv:1701.03684
Arrazola, J., Kalajdzievski, T., Weedbrook, C., Lloyd, S.: Quantum algorithm for nonhomogeneous linear partial differential equations. Phys. Rev. A 100, 032306 (2019). arXiv:1809.02622
Childs, A., Liu, J.-P.: Quantum spectral methods for differential equations. Commun. Math. Phys. (2020). arXiv:1901.00961
Lubasch, M., Joo, J., Moinier, P., Kiffner, M., Jaksch, D.: Variational quantum algorithms for nonlinear problems (2019). arXiv:1907.09032
Childs, A., Liu, J.-P., Ostrander, A.: High-precision quantum algorithms for partial differential equations (2020). arXiv:2002.07868
Xin, T., Wei, S., Cui, J., Xiao, J., Arrazola, I., Lamata, L., Kong, X., Lu, D., Solano, E., Long, G.: Quantum algorithm for solving linear differential equations: theory and experiment. Phys. Rev. A 101 (2020). arXiv:1807.04553
Cao, Y., Papageorgiou, A., Petras, I., Traub, J., Kais, S.: Quantum algorithm and circuit design solving the Poisson equation. New J. Phys. 15, 013021 (2013). arXiv:1207.2485
Scherer, A., Valiron, B., Mau, S.-C., Alexander, S., van den Berg, E., Chapuran, T.: Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target. Quantum Inf. Process. 16, 1 (2017). arXiv:1505.06552
Wang, S., Wang, Z., Li, W., Fan, L., Wei, Z., Gu, Y.: Quantum fast Poisson solver: the algorithm and modular circuit design (2019). arXiv:1910.09756
Costa, P., Jordan, S., Ostrander, A.: Quantum algorithm for simulating the wave equation. Phys. Rev. A 99 (2019). arXiv:1711.05394
Montanaro, A., Pallister, S.: Quantum algorithms and the finite element method. Phys. Rev. A 93, 032324 (2016). arXiv:1512.05903
Carslaw, H.S., Jaeger, J.C.: Conduction of Heat in Solids. Clarendon Press, Oxford (1959)
Wilmott, P., Howson, S., Howison, S., Dewynne, J., et al.: The Mathematics of Financial Derivatives: A Student Introduction. Cambridge University Press, Cambridge (1995)
Perona, P., Malik, J.: Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 629 (1990)
Ore, O.: On functions with bounded derivatives. Trans. Am. Math. Soc. 43, 321 (1938)
Lawler, G.: Random Walk and the Heat Equation. American Mathematical Society, Providence (2010)
Kac, M.: Random walk and the theory of Brownian motion. Am. Math. Mon. 54, 369 (1947)
King, G.: Monte-Carlo method for solving diffusion problems. Ind. Eng. Chem. 43, 2475 (1951)
Cliffe, K., Giles, M., Scheichl, R., Teckentrup, A.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14, 3 (2011)
Giles, M.: Multilevel Monte Carlo path simulation. Oper. Res. 56, 607 (2008)
Chakraborty, S., Gilyén, A., Jeffery, S.: The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In: Proceedings of 46th International Colloquium on Automata, Languages, and Programming, pp. 33:1–33:14 (2019). arXiv:1804.01973
Apers, S., Sarlette, A.: Quantum fast-forwarding: Markov chains and graph property testing (2018). arXiv:1804.02321
Gilyén, A., Su, Y., Low, G., Wiebe, N.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In: Proceedings of 51st Annual ACM Symposium Theory of Computing, pp. 193–204 (2019). arXiv:1806.01838
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information: A Millennium 305, 53 (2002). arXiv:quant-ph/0005055
Iserles, A.: A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press, Cambridge (2009)
LeVeque, R.: Finite Difference Methods for Ordinary and Partial Differential Equations. SIAM, Philadelphia (2007)
Trefethen, L.: Finite difference and spectral methods for ordinary and partial differential equations (1996). http://people.maths.ox.ac.uk/trefethen/pdetext.html
Shewchuk, J.: An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMU-CS-TR-94-125 (Carnegie Mellon University, 1994). http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.ps
Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)
Kachitvichyanukul, V., Schmeiser, B.: Binomial random variate generation. Commun. ACM 31, 216 (1988)
Devroye, L.: Non-uniform Random Variate Generation. Springer-Verlag, New York (1986)
Childs, A., Kothari, R., Somma, R.: Quantum linear systems algorithm with exponentially improved dependence on precision. SIAM J. Comput. 46, 1920 (2017). arXiv:1511.02306
Zalka, C.: Simulating quantum systems on a quantum computer. Proc. R. Soc. A Math. Phys. Eng. Sci. 454, 313 (1998) https://doi.org/10.1098/rspa.1998.0162
Long, G.-L, Sun, Y.: Efficient scheme for initializing a quantum register with an arbitrary superposed state. Phys. Rev. A 64 (2001). arXiv:quant-ph/0104030
Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions (2002). arXiv:quant-ph/0208112
Kaye, P., Mosca, M.: Quantum networks for generating arbitrary quantum states (2004). arXiv:quant-ph/0407102
Sanders, Y.R., Low, G.H., Scherer, A., Berry, D.W.: Black-box quantum state preparation without arithmetic. Phys. Rev. Lett. 122, 020502 (2019). https://doi.org/10.1103/PhysRevLett.122.020502, arXiv:1807.03206
Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comput. Syst. Sci. 62, 376 (2001). (quant-ph/9812012)
Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12, 449 (1992)
Bauer, W.: The Monte Carlo method. J. Soc. Ind. Appl. Math. 6, 438 (1958)
Chia, N.-H., Gilyén, A., Li, T., Lin, H.-H., Tang, E., Wang, C.: Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning (2019). arXiv:1910.06151
Diaconis, P.: Group representations in probability and statistics (Institute of Mathematical Statistics, 1988)