Βελτιωμένοι κβαντικοί αλγόριθμοι για γραμμικές και μη γραμμικές διαφορικές εξισώσεις

Βελτιωμένοι κβαντικοί αλγόριθμοι για γραμμικές και μη γραμμικές διαφορικές εξισώσεις

Βελτιωμένοι κβαντικοί αλγόριθμοι για γραμμικές και μη γραμμικές διαφορικές εξισώσεις PlatoBlockchain Data Intelligence. Κάθετη αναζήτηση. Ολα συμπεριλαμβάνονται.

Χάρη Κρόβη

Riverlane Research, Cambridge, MA

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Παρουσιάζουμε ουσιαστικά γενικευμένους και βελτιωμένους κβαντικούς αλγόριθμους σε σχέση με προηγούμενη εργασία για ανομοιογενείς γραμμικές και μη γραμμικές συνήθεις διαφορικές εξισώσεις (ODE). Συγκεκριμένα, δείχνουμε πώς ο κανόνας της εκθετικής μήτρας χαρακτηρίζει τον χρόνο εκτέλεσης των κβαντικών αλγορίθμων για γραμμικούς ODE που ανοίγουν την πόρτα σε μια εφαρμογή σε μια ευρύτερη κατηγορία γραμμικών και μη γραμμικών ODE. Στο Berry et al., (2017), δίνεται ένας κβαντικός αλγόριθμος για μια συγκεκριμένη κατηγορία γραμμικών ODE, όπου ο σχετικός πίνακας πρέπει να είναι διαγωνιοποιήσιμος. Ο κβαντικός αλγόριθμος για γραμμικούς ODE που παρουσιάζονται εδώ επεκτείνεται σε πολλές κατηγορίες μη διαγωνοποιήσιμων πινάκων. Ο αλγόριθμος εδώ είναι επίσης εκθετικά ταχύτερος από τα όρια που προκύπτουν στο Berry et al., (2017) για ορισμένες κατηγορίες διαγωνοποιήσιμων πινάκων. Ο γραμμικός αλγόριθμός μας ODE εφαρμόζεται στη συνέχεια σε μη γραμμικές διαφορικές εξισώσεις χρησιμοποιώντας τη γραμμικοποίηση Carleman (μια προσέγγιση που υιοθετήθηκε πρόσφατα από εμάς στο Liu et al., (2021)). Η βελτίωση σε σχέση με αυτό το αποτέλεσμα είναι διπλή. Πρώτον, λαμβάνουμε μια εκθετικά καλύτερη εξάρτηση από το σφάλμα. Αυτό το είδος λογαριθμικής εξάρτησης από το σφάλμα έχει επίσης επιτευχθεί από τους Xue et al., (2021), αλλά μόνο για ομοιογενείς μη γραμμικές εξισώσεις. Δεύτερον, ο παρών αλγόριθμος μπορεί να χειριστεί οποιονδήποτε αραιό, αντιστρέψιμο πίνακα (που μοντελοποιεί τη διάχυση) εάν έχει αρνητικό log-norm (συμπεριλαμβανομένων μη διαγωνισίμων πινάκων), ενώ οι Liu et al., (2021) και Xue et al., (2021) απαιτούν επιπλέον κανονικότητα.

Οι διαφορικές εξισώσεις αποτελούν σημαντικό μέρος πολλών μοντέλων φυσικής από τη φυσική υψηλής ενέργειας έως τη δυναμική των ρευστών και τη φυσική του πλάσματος. Υπάρχουν αρκετοί κβαντικοί αλγόριθμοι που λύνουν διαφορικές εξισώσεις παράγοντας μια κβαντική κατάσταση ανάλογη της λύσης. Αυτοί οι κβαντικοί αλγόριθμοι, ωστόσο, είναι εφαρμόσιμοι μόνο σε ορισμένους τύπους διαφορικών εξισώσεων. Συγκεκριμένα, για γραμμικά ODE, επιβάλλουν συνθήκες όπως η κανονικότητα ή η δυνατότητα διαγωνιοποίησης στον πίνακα $A$ που κωδικοποιεί το γραμμικό ODE. Αυτή η εργασία αναπτύσσει κβαντικούς αλγόριθμους που μπορούν να εφαρμοστούν σε μια σημαντικά μεγαλύτερη κατηγορία γραμμικών και μη γραμμικών συνηθισμένων διαφορικών εξισώσεων. Αφαιρούμε την συνθήκη της διαγωνισιμότητας και την αντικαθιστούμε με μια που έχει μελετηθεί στη θεωρία της σταθερότητας των διαφορικών εξισώσεων, δηλαδή τον κανόνα της εκθετικής του πίνακα $A$. Αυτό μπορεί στη συνέχεια να χρησιμοποιηθεί για να δώσει έναν κβαντικό αλγόριθμο που ισχύει και για μεγαλύτερη κατηγορία μη γραμμικών διαφορικών εξισώσεων.

► Δεδομένα BibTeX

► Αναφορές

[1] DW Berry, AM Childs, A. Ostrander, and G. Wang, «Κβαντικός αλγόριθμος για γραμμικές διαφορικές εξισώσεις με εκθετικά βελτιωμένη εξάρτηση από την ακρίβεια», Communications in Mathematical Physics, τόμ. 356, αρ. 3, σελ. 1057–1081, 2017. https://​/​doi.org/​10.1007/​s00220-017-3002-y.
https: / / doi.org/ 10.1007 / s00220-017-3002-y

[2] J.-P. Liu, Η. Ø. Kolden, HK Krovi, NF Loureiro, K. Trivisa, and AM Childs, «Efficient quantum algorithm for dissipative nonlinear differential equations», Proceedings of the National Academy of Sciences, τομ. 118, αρ. 35, 2021. https://doi.org/​10.1073/​pnas.2026805118.
https: / / doi.org/ 10.1073 / pnas.2026805118

[3] C. Xue, Y.-C. Wu και G.-P. Guo, «Μέθοδος διαταραχής κβαντικής ομοτοπίας για μη γραμμικές συνήθεις διαφορικές εξισώσεις διασποράς», New Journal of Physics, τομ. 23, σελ. 123035, Δεκέμβριος 2021. https://​/​doi.org/​10.1088/​1367-2630/​ac3eff.
https://doi.org/​10.1088/​1367-2630/​ac3eff

[4] S. Lloyd, «Universal quantum simulators», Science, τομ. 273, αρ. 5278, σελ. 1073–1078, 1996. https://doi.org/​10.1126/​science.273.5278.1073.
https: / / doi.org/ 10.1126 / science.273.5278.1073

[5] DW Berry, G. Ahokas, R. Cleve, and BC Sanders, “Efficient quantum algorithms for simulating sparse Hamiltonians”, Communications in Mathematical Physics, τομ. 270, σελ. 359–371, 2007. https://doi.org/​10.1007/​s00220-006-0150-x.
https: / / doi.org/ 10.1007 / s00220-006-0150-x

[6] GH Low και IL Chuang, «Βέλτιστη προσομοίωση χαμιλτονίου με επεξεργασία κβαντικού σήματος», Φυσ. Rev. Lett., τόμ. 118, σελ. 010501, Ιαν 2017. https://doi.org/​10.1103/​PhysRevLett.118.010501.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[7] GH Low και IL Chuang, «Hamiltonian Simulation by Qubitization», Quantum, τομ. 3, σελ. 163, Ιούλιος 2019. https://doi.org/​10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[8] S. Chakraborty, A. Gilyén και S. Jeffery, «The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster S Hamiltonian Simulation», στο 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019,P.Chienniic,C. i, eds.), τόμ. 132 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Γερμανία), σελ. 33:1–33:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. https:/​/​doi.org/​10.4230
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33

[9] J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf, «Quantum SDP-Solvers: Better upper and bottom bounds», Quantum, τομ. 4, σελ. 230, Φεβ. 2020. https://doi.org/​10.22331/​q-2020-02-14-230.
https:/​/​doi.org/​10.22331/​q-2020-02-14-230

[10] A. Gilyén, Y. Su, GH Low, και N. Wiebe, «Quantum singular value transformation and above: Exponential βελτιώσεις για την αριθμητική του κβαντικού πίνακα», στο Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOCNew USA, 2019, USA, pNY. 193–204, Association for Computing Machinery, 2019. https://​/​doi.org/​10.1145/​3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366

[11] AW Harrow, A. Hassidim και S. Lloyd, «Quantum algorithm for linear systems of equations», Physical Review Letters, τομ. 103, αρ. 15, σελ. 150502, 2009. https://doi.org/​10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[12] DW Berry, “High-order quantum algorithm for solving linear differential equations”, Journal of Physics A: Mathematical and Theoretical, τομ. 47, αρ. 10, σελ. 105301, 2014. https://doi.org/​10.1088/​1751-8113/​47/​10/​105301.
https:/​/​doi.org/​10.1088/​1751-8113/​47/​10/​105301

[13] AM Childs, J.-P. Liu, and A. Ostrander, «High-precision quantum algorithms for partial differential equations», Quantum, τόμ. 5, σελ. 574, Νοέμβριος 2021. https://doi.org/​10.22331/​q-2021-11-10-574.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574

[14] AM Childs και J.-P. Liu, "Quantum φασματικές μέθοδοι για διαφορικές εξισώσεις", Communications in Mathematical Physics, τομ. 375, σελ. 1427–1457, 2020. https://doi.org/​10.1007/​s00220-020-03699-z.
https: / / doi.org/ 10.1007 / s00220-020-03699-z

[15] S. Lloyd, G. De Palma, C. Gokler, B. Kiani, Z.-W. Liu, M. Marvian, F. Tennie και T. Palmer, «Quantum algorithm for nonlinear differial equations», 2020. https://doi.org/​10.48550/​arXiv.2011.06571.
https://doi.org/​10.48550/​arXiv.2011.06571

[16] A. Ambainis, “Variable time amplitude amplification and quantum algorithms for linear algebra Problems”, στο 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) (C. Dürr and T. Wilke, eds.), τομ. 14 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Γερμανία), σελ. 636–647, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. https:/​/​doi.org/​10.4230CS2012.636.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636

[17] AM Childs, R. Kothari και RD Somma, «Κβαντικός αλγόριθμος για συστήματα γραμμικών εξισώσεων με εκθετικά βελτιωμένη εξάρτηση από την ακρίβεια», SIAM Journal on Computing, τόμ. 46, αρ. 6, σελ. 1920–1950, 2017. https://​/​doi.org/​10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[18] Y. Subasi, RD Somma και D. Orsucci, «Κβαντικοί αλγόριθμοι για συστήματα γραμμικών εξισώσεων εμπνευσμένων από αδιαβατικό κβαντικό υπολογισμό», Φυσ. Rev. Lett., τόμ. 122, σελ. 060504, 2 2019. https://​/​doi.org/​10.1103/​PhysRevLett.122.060504.
https: / / doi.org/ 10.1103 / PhysRevLett.122.060504

[19] 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, 3 2022. https://doi.org/​10.1145/​3498331.
https: / / doi.org/ 10.1145 / 3498331

[20] L. Lin and Y. Tong, “Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems”, Quantum, τόμ. 4, σελ. 361, 11 2020. https://doi.org/​10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[21] PC Costa, D. An, YR Sanders, Y. Su, R. Babbush, and DW Berry, «Optimal scaling quantum linear-systems solver via discrete adiabatic theorem», PRX Quantum, τομ. 3, σελ. 040303, Οκτώβριος 2022. https://​/​doi.org/​10.1103/​PRXQuantum.3.040303.
https: / / doi.org/ 10.1103 / PRXQuantum.3.040303

[22] SK Leyton και TJ Osborne, «Ένας κβαντικός αλγόριθμος για την επίλυση μη γραμμικών διαφορικών εξισώσεων», 2008. https://doi.org/​10.48550/​arXiv.0812.4423.
https://doi.org/​10.48550/​arXiv.0812.4423

[23] A. Engel, G. Smith και SE Parker, «Quantum algorithm for the Vlasov equation», Physical Review A, vol. 100, αρ. 6, σελ. 062315, 2019. https://doi.org/​10.1103/​PhysRevA.100.062315.
https: / / doi.org/ 10.1103 / PhysRevA.100.062315

[24] IY Dodin και EA Startsev, «On applications of quantum computing to plasma simulations», Physics of Plasmas, τομ. 28, αρ. 9, σελ. 092101, 2021. https://doi.org/​10.1063/​5.0056974.
https: / / doi.org/ 10.1063 / 5.0056974

[25] A. Engel, G. Smith και SE Parker, «Γραμμική ενσωμάτωση μη γραμμικών δυναμικών συστημάτων και προοπτικές για αποδοτικούς κβαντικούς αλγόριθμους», Physics of Plasmas, τομ. 28, αρ. 6, σελ. 062305, 2021. https://doi.org/​10.1063/​5.0040313.
https: / / doi.org/ 10.1063 / 5.0040313

[26] Ι. Τζόζεφ, «Προσέγγιση Koopman–von Neumann στην κβαντική προσομοίωση μη γραμμικής κλασικής δυναμικής», Phys. Rev. Res., τόμ. 2, σελ. 043102, Οκτώβριος 2020. https://​/​doi.org/​10.1103/​PhysRevResearch.2.043102.
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043102

[27] I. Novikau, EA Startsev και IY Dodin, «Quantum signal processing for simulating cold plasma waves», Phys. Rev. A, τομ. 105, σελ. 062444, Ιουν 2022. https://​/​doi.org/​10.1103/​PhysRevA.105.062444.
https: / / doi.org/ 10.1103 / PhysRevA.105.062444

[28] J. Hubisz, B. Sambasivam και J. Unmuth-Yockey, «Quantum algorithms for open lattice field theory», Physical Review A, τομ. 104, 11 2021. https://doi.org/​10.1103/​physreva.104.052420.
https: / / doi.org/ 10.1103 / physreva.104.052420

[29] D. An, D. Fang, S. Jordan, J.-P. Liu, GH Low και J. Wang, «Αποτελεσματικός κβαντικός αλγόριθμος για μη γραμμικές εξισώσεις αντίδρασης-διάχυσης και εκτίμηση ενέργειας», 2022. https://doi.org/​10.48550/​arXiv.2205.01141.
https://doi.org/​10.48550/​arXiv.2205.01141

[30] D. Fang, L. Lin και Y. Tong, «Time-marching based quantum solvers for time-dependent linear differial equations», 2022. https://doi.org/​10.48550/​arXiv.2208.06941.
https://doi.org/​10.48550/​arXiv.2208.06941

[31] DW Berry, AM Childs, Y. Su, X. Wang, and N. Wiebe, «Time-dependent Hamiltonian simulation with $L^1$-norm scaling», Quantum, vol. 4, σελ. 254, Απρ. 2020. https://doi.org/​10.22331/​q-2020-04-20-254.
https:/​/​doi.org/​10.22331/​q-2020-04-20-254

[32] D. An, J.-P. Liu, D. Wang και Q. Zhao, «A theory of quantum differential equation solvers: limitations and fast-forwarding», 2022. https://doi.org/​10.48550/​ARXIV.2211.05246.
https://doi.org/​10.48550/​ARXIV.2211.05246

[33] W. Coppel, Stability and Asymptotic Behavior of Differential Equations. Μαθηματικές μονογραφίες Heath, Heath, 1965.

[34] CF Van Loan, «Μια μελέτη της εκθετικής μήτρας», τεχν. rep., University of Manchester, 2006.

[35] GG Dahlquist, «Ένα ειδικό πρόβλημα σταθερότητας για γραμμικές μεθόδους πολλαπλών βημάτων», BIT Numerical Mathematics, τομ. 3, σελ. 27–43, Μάρτιος 1963. https://doi.org/​10.1007/​BF01963532.
https: / / doi.org/ 10.1007 / BF01963532

[36] L. Trefethen, M. Embree και M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, 2005. https://doi.org/​10.2307/​j.ctvzxx9kj.
https://doi.org/​10.2307/​j.ctvzxx9kj

[37] R. Bhatia, Matrix Analysis. Graduate Texts in Mathematics, Springer New York, 1996. https://​/​doi.org/​10.1007/​978-1-4612-0653-8.
https:/​/​doi.org/​10.1007/​978-1-4612-0653-8

[38] NF Loureiro, W. Dorland, L. Fazendeiro, A. Kanekar, A. Mallet, MS Vilelas, and A. Zocco, «Viriato: A Fourier–Hermite φασματικός κώδικας για ισχυρά μαγνητισμένη ρευστοκινητική δυναμική πλάσματος», Computer Physics Communications, τομ. 206, σελ. 45–63, 2016. https://doi.org/​10.1016/​j.cpc.2016.05.004.
https: / / doi.org/ 10.1016 / j.cpc.2016.05.004

[39] RA Bertlmann, W. Grimus, και BC Hiesmayr, «Διατύπωση ανοιχτού κβαντικού συστήματος σωματιδιακής διάσπασης», Phys. Rev. A, τομ. 73, σελ. 054101, Μάιος 2006. https://doi.org/​10.1103/​PhysRevA.73.054101.
https: / / doi.org/ 10.1103 / PhysRevA.73.054101

[40] B. Kågström, «Όρια και όρια διαταραχής για τον εκθετικό πίνακα», BIT Numerical Mathematics, τόμ. 17, σελ. 39–57, Μάρτιος 1977. https://doi.org/​10.1007/​BF01932398.
https: / / doi.org/ 10.1007 / BF01932398

[41] L. Elsner and M. Paardekooper, «On μέτρα της μη κανονικότητας των πινάκων», Linear Algebra and its Applications, τομ. 92, σελ. 107–123, 1987. https://​/​doi.org/​10.1016/​0024-3795(87)90253-9.
https:/​/​doi.org/​10.1016/​0024-3795(87)90253-9

[42] N. Higham, Functions of Matrices: Theory and Computation. Other Titles in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 2008. https:/​/​doi.org/​10.1137/​1.9780898717778.
https: / / doi.org/ 10.1137 / 1.9780898717778

[43] E. Hairer, S. Nørsett και G. Wanner, Επίλυση συνηθισμένων διαφορικών εξισώσεων I: Μη σκληρά προβλήματα. Springer Series in Computational Mathematics, Springer Berlin Heidelberg, 2008. https://doi.org/​10.1007/​978-3-540-78862-1.
https:/​/​doi.org/​10.1007/​978-3-540-78862-1

[44] MM Gilles Brassard, Peter Høyer and A. Tapp, «Quantum amplitude amplification and estimation», στο Quantum Computation and Information (J. Samuel J. Lomonaco and HE Brandt, eds.), τομ. 305, σελ. 53–74, Σύγχρονα Μαθηματικά, 2002. https://​/​doi.org/​10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

Αναφέρεται από

[1] Cheng Xue, Xiao-Fan Xu, Yu-Chun Wu και Guo-Ping Guo, «Κβαντικός αλγόριθμος για την επίλυση ενός τετραγωνικού μη γραμμικού συστήματος εξισώσεων», Physical Review Α 106 3, 032427 (2022).

[2] Dong An, Di Fang, Stephen Jordan, Jin-Peng Liu, Guang Hao Low και Jiasu Wang, «Αποτελεσματικός κβαντικός αλγόριθμος για μη γραμμικές εξισώσεις αντίδρασης-διάχυσης και εκτίμηση ενέργειας», arXiv: 2205.01141, (2022).

[3] Dominic W. Berry και Pedro CS Costa, «Κβαντικός αλγόριθμος για χρονικά εξαρτώμενες διαφορικές εξισώσεις με χρήση σειράς Dyson», arXiv: 2212.03544, (2022).

[4] Koichi Miyamoto και Hiroshi Ueda, «Εξαγωγή μιας συνάρτησης κωδικοποιημένης σε πλάτη μιας κβαντικής κατάστασης από δίκτυο τανυστών και ορθογώνια επέκταση συνάρτησης», arXiv: 2208.14623, (2022).

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2023-02-03 04:56:43). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2023-02-03 04:56:41).

Σφραγίδα ώρας:

Περισσότερα από Quantum Journal