선형 및 비선형 미분 방정식을 위한 향상된 양자 알고리즘

선형 및 비선형 미분 방정식을 위한 향상된 양자 알고리즘

타임 스탬프 : 2 년 2023 월 11 일 오전 28:XNUMX
선형 및 비선형 미분 방정식을 위한 향상된 양자 알고리즘 PlatoBlockchain Data Intelligence. 수직 검색. 일체 포함.

하리 크로비

Riverlane Research, 케임브리지, 매사추세츠

이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.

추상

비균질 선형 및 비선형 상미분 방정식(ODE)에 대한 이전 작업에 비해 실질적으로 일반화되고 개선된 양자 알고리즘을 제시합니다. 구체적으로 행렬 지수의 표준이 더 넓은 종류의 선형 및 비선형 ODE에 대한 응용 프로그램의 문을 여는 선형 ODE에 대한 양자 알고리즘의 실행 시간을 특성화하는 방법을 보여줍니다. Berry et al., (2017)에서는 선형 ODE의 특정 클래스에 대한 양자 알고리즘이 제공되며, 여기서 관련된 행렬은 대각화 가능해야 합니다. 여기에 제시된 선형 ODE에 대한 양자 알고리즘은 대각화할 수 없는 행렬의 여러 클래스로 확장됩니다. 여기의 알고리즘은 특정 클래스의 대각화 가능한 행렬에 대해 Berry et al., (2017)에서 파생된 범위보다 기하급수적으로 빠릅니다. 우리의 선형 ODE 알고리즘은 Carleman 선형화(Liu et al., (2021)에서 최근에 취한 접근법)를 사용하여 비선형 미분 방정식에 적용됩니다. 그 결과에 대한 개선은 두 배입니다. 첫째, 오류에 대한 기하급수적으로 더 나은 의존성을 얻습니다. 오류에 대한 이러한 종류의 로그 의존성은 Xue et al., (2021)에 의해 달성되었지만 동종 비선형 방정식에 대해서만 가능합니다. 둘째, 현재 알고리즘은 음의 로그 노름(대각화할 수 없는 행렬 포함)이 있는 경우 희박하고 가역적인 행렬(소산을 모델링하는)을 처리할 수 있는 반면 Liu et al., (2021) 및 Xue et al., (2021) ) 추가로 정규성이 필요합니다.

인기 요약

미분 방정식은 고에너지 물리학에서 유체 역학 및 플라즈마 물리학에 이르는 많은 물리 모델의 중요한 부분입니다. 솔루션에 비례하는 양자 상태를 생성하여 미분 방정식을 푸는 여러 양자 알고리즘이 있습니다. 그러나 이러한 양자 알고리즘은 특정 유형의 미분 방정식에만 적용할 수 있습니다. 특히 선형 ODE의 경우 선형 ODE를 인코딩하는 행렬 $A$에 정규성 또는 대각화 가능성과 같은 조건을 부과합니다. 이 작업은 훨씬 더 큰 종류의 선형 및 비선형 상미분 방정식에 적용할 수 있는 양자 알고리즘을 개발합니다. 우리는 대각화 가능성의 조건을 제거하고 미분 방정식의 안정성 이론에서 연구된 조건, 즉 행렬 $A$의 지수의 노름으로 대체합니다. 그런 다음 더 큰 종류의 비선형 미분 방정식에도 적용되는 양자 알고리즘을 제공하는 데 사용할 수 있습니다.

► BibTeX 데이터

► 참고 문헌

[1] DW Berry, AM Childs, A. Ostrander 및 G. Wang, "정밀도에 대한 의존도가 기하급수적으로 개선된 선형 미분 방정식을 위한 양자 알고리즘", Communications in Mathematical Physics, vol. 356, 아니오. 3, pp. 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, H. Ø. Kolden, HK Krovi, NF Loureiro, K. Trivisa 및 AM Childs, "소산 비선형 미분 방정식을 위한 효율적인 양자 알고리즘", 미국 국립 과학원 회보, vol. 118, 아니오. 35년 2021일. https:/ / doi.org/ 10.1073/ pnas.2026805118.
https : / /doi.org/ 10.1073 / pnas.2026805118

[3] C. Xue, Y.-C. 우, G.-P. Guo, "비선형 소산 상미분 방정식에 대한 양자 호모토피 섭동 방법", New Journal of Physics, vol. 23, p. 123035, 2021년 10.1088월. https:/ / doi.org/ 1367/ 2630-3/ acXNUMXeff.
https://doi.org/10.1088/1367-2630/ac3eff

[4] S. Lloyd, "범용 양자 시뮬레이터", Science, vol. 273, 아니오. 5278, pp. 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 및 BC Sanders, "희소한 Hamiltonians를 시뮬레이션하기 위한 효율적인 양자 알고리즘", Communications in Mathematical Physics, vol. 270, p. 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, "양자 신호 처리를 통한 최적의 해밀턴 시뮬레이션", Phys. Lett 목사, vol. 118, p. 010501, 2017년 10.1103월. https:/ / doi.org/ 118.010501/ PhysRevLett.XNUMX.
https : / /doi.org/10.1103/ PhysRevLett.118.010501

[7] GH Low 및 IL Chuang, "Qubitization에 의한 Hamiltonian 시뮬레이션," Quantum, vol. 3, p. 163, 2019년 10.22331월. https:/ / doi.org/ 2019/ q-07-12-163-XNUMX.
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 Hamiltonian Simulation," 제46회 Automata, Languages, and Programming에 관한 International Colloquium(ICALP 2019)(C. Baier, I. Chatzigiannakis, P. Flocchini 및 S. Leonardi, eds.), vol. 132 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 33:1–33:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. https:/ / doi.org/ 10.4230 /LIPIcs.ICALP.2019.33.
https : / /doi.org/10.4230/LIPIcs.ICALP.2019.33

[9] J. van Apeldoorn, A. Gilyén, S. Gribling 및 R. de Wolf, "Quantum SDP-Solvers: 더 나은 상한 및 하한 경계", Quantum, vol. 4, p. 230년 2020월 10.22331일. https:/ / doi.org/ 2020/ q-02-14-230-XNUMX.
https:/​/​doi.org/​10.22331/​q-2020-02-14-230

[10] A. Gilyén, Y. Su, GH Low 및 N. Wiebe, "양자 특이값 변환 및 그 이상: 양자 행렬 산술의 기하급수적 개선", 컴퓨팅 이론에 관한 제51회 연례 ACM SIGACT 심포지엄 절차, STOC 2019, ( 뉴욕, 뉴욕, 미국), p. 193–204, 컴퓨팅 기계 협회, 2019. https:/ / doi.org/ 10.1145/ 3313276.3316366.
https : / /doi.org/ 10.1145 / 3313276.3316366

[11] AW Harrow, A. Hassidim, S. Lloyd, "방정식의 선형 시스템을 위한 양자 알고리즘", Physical Review Letters, vol. 103, 아니오. 15, p. 150502, 2009. https:/ / doi.org/ 10.1103/ PhysRevLett.103.150502.
https : / /doi.org/10.1103/ PhysRevLett.103.150502

[12] DW Berry, “선형 미분방정식 풀이를 위한 고차원 양자 알고리즘,” Journal of Physics A: Mathematical and Theoretical, vol. 47, 아니. 10, p. 105301, 2014. https:/ / doi.org/ 10.1088/ 1751-8113/ 47/ 10/ 105301.
https:/​/​doi.org/​10.1088/​1751-8113/​47/​10/​105301

[13] AM 차일즈, J.-P. Liu 및 A. Ostrander, "편미분 방정식을 위한 고정밀 양자 알고리즘", Quantum, vol. 5, p. 574, 2021년 10.22331월. https:/ / doi.org/ 2021/ q-11-10-574-XNUMX.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574

[14] AM 차일즈 및 J.-P. Liu, "미분 방정식에 대한 양자 스펙트럼 방법", 수학 물리학에서의 커뮤니케이션, vol. 375, pp. 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, "비선형 미분 방정식을 위한 양자 알고리즘" 2020. https:/ / doi.org/ 10.48550/ arXiv.2011.06571.
https://​/​doi.org/​10.48550/​arXiv.2011.06571

[16] A. Ambainis, "선형 대수 문제를 위한 가변 시간 진폭 증폭 및 양자 알고리즘", 컴퓨터 과학의 이론적 측면에 관한 29회 국제 심포지엄(STACS 2012)(C. Dürr 및 T. Wilke, eds.), vol. 14 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 636–647, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. https:/ / doi.org/ 10.4230/ LIPIcs. STACS.2012.636.
https : / /doi.org/10.4230/LIPIcs.STACS.2012.636

[17] AM Childs, R. Kothari 및 RD Somma, "정밀도에 대한 의존도가 기하급수적으로 개선된 선형 방정식 시스템을 위한 양자 알고리즘", SIAM Journal on Computing, vol. 46, 아니. 6, 1920–1950, 2017. https:/ / doi.org/ 10.1137/ 16M1087072.
https : / //doi.org/10.1137/ 16M1087072

[18] Y. Subasi, RD Somma 및 D. Orsucci, "단열 양자 컴퓨팅에서 영감을 얻은 선형 방정식 시스템을 위한 양자 알고리즘" Phys. Lett 목사, vol. 122, p. 060504, 2 2019. https:/ / doi.org/ 10.1103/ PhysRevLett.122.060504.
https : / /doi.org/10.1103/ PhysRevLett.122.060504

[19] D. An 및 L. Lin, "시간 최적 단열 양자 컴퓨팅 및 양자 근사 최적화 알고리즘에 기반한 양자 선형 시스템 솔버", 양자 컴퓨팅의 ACM 트랜잭션, vol. 3, 3 2022. https:/ / doi.org/ 10.1145/ 3498331.
https : / /doi.org/ 10.1145 / 3498331

[20] L. Lin 및 Y. Tong, "양자 선형 시스템 해결에 적용한 최적의 다항식 기반 양자 고유 상태 필터링", Quantum, vol. 4, p. 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 및 DW Berry, "이산 단열 정리를 통한 최적 스케일링 양자 선형 시스템 솔버", PRX Quantum, vol. 3, p. 040303, 2022년 10.1103월. https:/ / doi.org/ 3.040303/ PRXQuantum.XNUMX.
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, "Vlasov 방정식을 위한 양자 알고리즘", Physical Review A, vol. 100, 아니. 6, p. 062315, 2019. https:/ / doi.org/ 10.1103/ PhysRevA.100.062315.
https : / /doi.org/10.1103/ PhysRevA.100.062315

[24] IY Dodin 및 EA Startsev, "플라즈마 시뮬레이션에 양자 컴퓨팅 적용", Physics of Plasmas, vol. 28, 아니. 9, p. 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, vol. 28, 아니. 6, p. 062305, 2021. https://doi.org/10.1063/5.0040313.
https : / /doi.org/ 10.1063 / 5.0040313

[26] I. Joseph, "비선형 고전 동역학의 양자 시뮬레이션에 대한 Koopman-von neumann 접근 방식", Phys. Res., vol. 2, p. 043102, 2020년 10.1103월. https:/ / doi.org/ 2.043102/ PhysRevResearch.XNUMX.
https : / /doi.org/10.1103/ PhysRevResearch.2.043102

[27] I. Novikau, EA Startsev 및 IY Dodin, "저온 플라즈마 파동 시뮬레이션을 위한 양자 신호 처리", Phys. A, vol. 105, p. 062444, 2022년 10.1103월. https:/ / doi.org/ 105.062444/ PhysRevA.XNUMX.
https : / /doi.org/10.1103/ PhysRevA.105.062444

[28] J. Hubisz, B. Sambasivam, J. Unmuth-Yockey, "열린 격자 장 이론을 위한 양자 알고리즘", Physical Review A, vol. 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, "시간 종속 선형 미분 방정식을 위한 시간 행진 기반 양자 솔버", 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 및 N. Wiebe, "$L^1$-norm 스케일링을 사용한 시간 종속 해밀턴 시뮬레이션", Quantum, vol. 4, p. 254, 2020년 10.22331월. https:/ / doi.org/ 2020/ q-04-20-254-XNUMX.
https:/​/​doi.org/​10.22331/​q-2020-04-20-254

[32] D. An, J.-P. Liu, D. Wang, Q. Zhao, "양자 미분 방정식 풀이 이론: 제한 및 빨리 감기," 2022. https:/ / doi.org/ 10.48550/ ARXIV.2211.05246.
https://​/​doi.org/​10.48550/​ARXIV.2211.05246

[33] W. Coppel, 미분 방정식의 안정성 및 점근적 동작. 히스 수학 논문, 히스, 1965.

[34] CF Van Loan, "매트릭스 지수에 대한 연구" 기술. 대표, 맨체스터 대학교, 2006.

[35] GG Dahlquist, "선형 다단계 방법의 특수 안정성 문제", BIT Numerical Mathematics, vol. 3, pp. 27–43, 1963년 10.1007월. https:/ / doi.org/ 01963532/ BFXNUMX.
https : / /doi.org/ 10.1007 / BF01963532

[36] L. Trefethen, M. Embree 및 M. Embree, Spectra 및 Pseudospectra: 비정규 행렬 및 연산자의 동작. 프린스턴 대학교 출판부, 2005. https:/ / doi.org/ 10.2307/ j.ctvzxx9kj.
https://doi.org/10.2307/j.ctvzxx9kj

[37] R. Bhatia, 매트릭스 분석. 수학 대학원 텍스트, 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 및 A. Zocco, "Viriato: 강력 자화 유체-운동 플라즈마 역학을 위한 푸리에-에르마이트 스펙트럼 코드", Computer Physics Communications, 권. 206, pp. 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. A, vol. 73, p. 054101, 2006년 10.1103월. https:/ / doi.org/ 73.054101/ PhysRevA.XNUMX.
https : / /doi.org/10.1103/ PhysRevA.73.054101

[40] B. Kågström, "행렬 지수에 대한 범위 및 섭동 범위", BIT Numerical Mathematics, vol. 17, pp. 39–57, 1977년 10.1007월. https:/ / doi.org/ 01932398/ BFXNUMX.
https : / /doi.org/ 10.1007 / BF01932398

[41] L. Elsner 및 M. Paardekooper, "행렬의 비정규성 측정", Linear Algebra and its Applications, vol. 92, pp. 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, 행렬의 기능: 이론 및 계산. 응용 수학의 다른 제목, 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 시리즈, 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 및 A. Tapp, "양자 진폭 증폭 및 추정", 양자 계산 및 정보(J. Samuel J. Lomonaco 및 HE Brandt, eds.), vol. 305, pp. 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, "Quantum algorithm for solve a quadratic nonlinear system of equations", 물리적 검토 A 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에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.

타임 스탬프 :

더보기 양자 저널