양자에서 영감을 받은 영구 ID

플라톤에 의해 재발행

팔로워 : 0

¹퀀텀 정보 및 물질 연구소, 캘리포니아 기술 연구소, 패서 디나, CA 91125, 미국
²컴퓨터 과학, Tufts University, Medford, MA 02155, USA

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

추상

퍼머넌트는 복잡도 이론과 조합론 모두에 중추적입니다. 양자 컴퓨팅에서 퍼머넌트는 Boson 샘플링 모델과 같은 선형 광학 계산의 출력 진폭 표현에 나타납니다. 이 연결을 활용하여 우리는 기존의 많은 신원과 새롭고 놀라운 영구 신원에 대해 양자에서 영감을 얻은 증명을 제공합니다. 특히, 우리는 이 정리의 새로운 일반화에 대한 증명뿐만 아니라 MacMahon 마스터 정리의 양자에서 영감을 받은 증명을 제공합니다. 이 정리의 이전 증명은 완전히 다른 아이디어를 사용했습니다. 순전히 조합 응용 프로그램을 넘어, 우리의 결과는 입력 고양이 상태를 사용하여 선형 광학 양자 계산의 정확하고 대략적인 샘플링의 고전적인 경도를 보여줍니다.

주요 이미지: 양자에서 영감을 받은 증명은 고양이 상태 입력(DALL.E를 사용하여 생성된 추상 묘사)을 사용한 양자 계산에 대한 새로운 복잡성 결과로 이어집니다.

► BibTeX 데이터

@article{Chabaud2022Quantuminspired, doi = {10.22331/q-2022-12-19-877}, URL = {https://doi.org/10.22331/q-2022-12-19-877}, title = {양자에서 영감을 받은 영구 아이덴티티}, 작성자 = {Chabaud, Ulysse 및 Deshpande, Abhinav 및 Mehraban, Saeed}, 저널 = {{Quantum}}, issn = {2521-327X}, 게시자 = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, 볼륨 = {6}, 페이지 = {877}, 월 = 2022월, 연도 = {XNUMX} }

► 참고 문헌

[1] H. Minc, "Permanents,", vol. 6. 케임브리지 대학 출판부, 1984.
https : / /doi.org/ 10.1017 / CBO9781107340688

[2] JK Percus, "조합 방법", vol. 4. Springer 과학 및 비즈니스 미디어, 2012.
https://doi.org/10.1007/978-1-4612-6404-0

[3] LG 발리언트, “영구 계산의 복잡성,” Theoretical Computer Science 8, 189–201(1979).
https://doi.org/10.1016/0304-3975(79)90044-6

[4] ER Caianiello, "양자장 이론에 관하여 - I: Feynman 그래프를 사용하지 않고 전기역학에서 다이슨 방정식의 명시적 해법", Il Nuovo Cimento(1943-1954) 10, 1634–1652(1953).
https : / /doi.org/ 10.1007 / BF02781659

[5] S. Scheel, "선형 광 네트워크의 영구 장치," quant-ph/ 0406127.
arXiv : 퀀트 -PH / 0406127

[6] S. Aaronson 및 A. Arkhipov, "선형 광학의 계산 복잡성", 계산 이론 9, 143(2013), arXiv:1011.3245.
https : / /doi.org/ 10.1145 / 1993636.1993682
arXiv : arXiv : 1011.3245

[7] S. Aaronson, "영구 물질이 # P-hard라는 선형 광학적 증명", 왕립 학회 회보 A: 수학, 물리 및 공학 과학 467, 3393–3405(2011).
https : / /doi.org/ 10.1098 / rspa.2011.0232

[8] S. Rahimi-Keshari, AP Lund 및 TC Ralph, "Quantum optics는 계산 복잡성 이론에 대해 무엇을 말할 수 있습니까?" Physical review letter 114, 060501(2015).
https : / /doi.org/10.1103/ PhysRevLett.114.060501

[9] D. Grier 및 L. Schaeffer, "선형 광학을 사용하여 영구에 대한 새로운 경도 결과", arXiv:1610.04670.
arXiv : arXiv : 1610.04670

[10] PP Rohde, DW Berry, KR Motes 및 JP Dowling, "다차원 적분 클래스의 $#$P-경도에 대한 양자 광학 인수", arXiv:1607.04960.
arXiv : arXiv : 1607.04960

[11] L. Chakhmakhchyan, NJ Cerf 및 R. Garcia-Patron, "양의 준정부호 행렬의 영구성을 추정하기 위한 양자에서 영감을 받은 알고리즘", Physical Review A 96, 022329(2017).
https : / /doi.org/10.1103/ PhysRevA.96.022329

[12] A. Meiburg, "긍정적인 준확정 영구 및 양자 상태 단층 촬영의 근사 불가능성" arXiv:2111.03142.
arXiv : arXiv : 2111.03142

[13] PA MacMahon, "조합 분석, 볼륨 I 및 II,", vol. 137. 미국 수학회, 2001.

[14] I. Good, "MacMahon의 '마스터 정리'를 통한 일부 '이항'정체성 증명", Cambridge Philosophical Society의 Mathematical Proceedings, vol. 58, pp. 161–162, 캠브리지 대학 출판부. 1962.
https : / /doi.org/ 10.1017 / S030500410003632X

[15] L. Carlitz, "MacMahon의 마스터 정리 적용", SIAM Journal on Applied Mathematics 26, 431–436(1974).
https : / /doi.org/ 10.1137 / 0126040

[16] L. Carlitz, "MacMahon의 마스터 정리와 관련된 일부 확장 및 회선 공식", SIAM Journal on Mathematical Analysis 8, 320–336(1977).
https : / /doi.org/ 10.1137 / 0508023

[17] HJ Ryser, "조합 수학,", vol. 14. 미국 수학회, 1963.

[18] K. Balasubramanian, 조합론 및 행렬의 대각선. PhD 논문, Indian Statistical Institute-Kolkata, 1980.

[19] ET Bax, 계산 문제를 위한 유한 차분 알고리즘. 1998년 California Institute of Technology 박사 논문.

[20] DG Glynn, "정사각 행렬의 영속", European Journal of Combinatorics 31, 1887–1891 (2010).
https : / / doi.org/ 10.1016 / j.ejc.2010.01.010

[21] PP Rohde, KR Motes, PA Knott, J. Fitzsimons, WJ Munro 및 JP Dowling, "선형 광학으로 일반화된 고양이 상태를 샘플링하는 것이 어렵다는 추측에 대한 증거", Physical Review A 91, 012342(2015).
https : / /doi.org/10.1103/ PhysRevA.91.012342

[22] C. Weedbrook, S. Pirandola, R. García-Patrón, NJ Cerf, TC Ralph, JH Shapiro 및 S. Lloyd, "Gaussian quantum information,"Reviews of Modern Physics 84, 621 (2012).
https : / /doi.org/10.1103/ RevModPhys.84.621

[23] A. Leverrier, "$SU(p, q)$ 일관된 상태 및 Gaussian de Finetti 정리," Journal of Mathematical Physics 59, 042202 (2018).
https : / /doi.org/ 10.1063 / 1.5007334

[24] T. Jiang 및 Y. Ma, "무작위 직교 행렬과 독립 법선 사이의 거리", arXiv:1704.05205.
arXiv : arXiv : 1704.05205

[25] AC Dixon, "이항 정리에 의한 특정 확장에서 계수의 세제곱의 합", 수학 메신저 20, 79–80(1891).

[26] I. Good, "MacMahon의 '마스터 정리'에 대한 간략한 증명", Cambridge Philosophical Society의 Mathematical Proceedings, vol. 58, pp. 160–160, 캠브리지 대학 출판부. 1962.
https : / /doi.org/ 10.1017 / S0305004100036318

[27] S. Garoufalidis, TT Lê 및 D. Zeilberger, "양자 MacMahon 마스터 정리", 국립 과학 아카데미 회보 103, 13928–13931(2006).
https : / /doi.org/ 10.1073 / pnas.0606003103

[28] M. Konvalinka 및 I. Pak, "MacMahon Master Theorem의 비가환적 확장", Advances in Mathematics 216, 29–61(2007).
https : / / doi.org/ 10.1016 / j.aim.2007.05.020

[29] MP Tuite, "MacMahon Master Theorem의 일부 일반화", Journal of Combinatorial Theory, Series A 120, 92–101 (2013).
https : / /doi.org/ 10.1016 / j.jcta.2012.07.007

[30] VV Kocharovsky, VV Kocharovsky 및 SV Tarasov, "하프니안 마스터 정리", 선형 대수학 및 응용 144–161(2022).
https : / /doi.org/ 10.1016 / j.laa.2022.06.021

[31] WY Chen, H. Galbraith 및 J. Louck, "각운동량 이론, 기본 미적분 및 조합론", Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8

[32] BM Terhal 및 DP DiVincenzo, "비상 호작용-페르미온 양자 회로의 고전 시뮬레이션", Physical Review A 65, 032325 (2002).
https : / /doi.org/10.1103/ PhysRevA.65.032325

[33] V. Shchesnovich, "멀티포트 장치의 다광자 실험을 위한 부분 비구별성 이론", Physical Review A 91, 013844(2015).
https : / /doi.org/10.1103/ PhysRevA.91.013844

[34] D. Spivak, MY Niu, BC Sanders 및 H. de Guise, "페르미온 및 보존의 일반화된 간섭", Physical Review Research 4, 023013(2022).
https : / /doi.org/10.1103/ PhysRevResearch.4.023013

[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin 및 M. Hafezi, "일반화된 보손에 대한 보손 샘플링", arXiv:2204.08389.
https : / /doi.org/10.1103/ PhysRevResearch.4.043096
arXiv : arXiv : 2204.08389

[36] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix 및 B. Valiron, "LO$_text{v}$-Calculus: 선형 광학 양자 회로를 위한 그래픽 언어", arXiv:2204.11787.
https : / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv : arXiv : 2204.11787

[37] G. De Felice 및 B. Coecke, "스트링 다이어그램을 통한 양자 선형 광학", arXiv:2204.12985.
arXiv : arXiv : 2204.12985

[38] B. Peropadre, GG Guerreschi, J. Huh, A. Aspuru-Guzik, "마이크로파 보손 샘플링 제안", Physical review letter 117, 140505 (2016).
https : / /doi.org/10.1103/ PhysRevLett.117.140505

[39] S. Girvin, "서킷 qed의 슈뢰딩거 고양이 상태", arXiv:1710.03179.
arXiv : arXiv : 1710.03179

[40] X. 구, AF Kockum, A. Miranowicz, Y.-x. Liu 및 F. Nori, "초전도 양자 회로를 사용한 마이크로파 포토닉스", Physics Reports 718, 1–102(2017).
https : / //doi.org/ 10.1016 / j.physrep.2017.10.002

[41] J. Huh, "매트릭스 영구 컴퓨팅을 위한 빠른 양자 알고리즘", arXiv:2205.01328.
arXiv : arXiv : 2205.01328

[42] S. Aaronson 및 T. Hance, "영구를 위한 Gurvits의 근사 알고리즘 일반화 및 비랜덤화", Quantum Info. 컴퓨팅 14, 541–559(2014).
https : / / doi.org/ 10.26421 / QIC14.7-8-1

[43] S. Chin and J. Huh, "보손 샘플링의 일반화된 동시성", 과학 보고서 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5

[44] M.-H. Yung, X. Gao, J. Huh, "선형 광학에서 보손 샘플링과 그 계산적 함의에 대한 보편적 경계", National science review 6, 719–729 (2019).
https://doi.org/ 10.1093/ nsr/ nwz048

[45] VS Shchesnovich, "구분할 수 없는 보손의 양자 간섭에서 샘플링의 고전적 복잡성에 관하여", 양자 정보 국제 저널 18, 2050044(2020).
https : / /doi.org/ 10.1142 / S0219749920500446

[46] DM Jackson, "시퀀스에 대한 특정 열거 문제의 통일", Journal of Combinatorial Theory, Series A 22, 92–96(1977).
https://doi.org/10.1016/0097-3165(77)90066-8

[47] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins 및 CJ Villas-Boas, "양자 정보 처리 및 양자 감지를 위한 두 가지 모드 압착 상태의 중첩", Physical Review A 103, 062405(2021).
https : / /doi.org/10.1103/ PhysRevA.103.062405

[48] AP Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, JL O'Brien 및 TC Ralph, "가우시안 상태에서 샘플링한 보손" 물리적 검토 편지 113, 100502(2014).
https : / /doi.org/10.1103/ PhysRevLett.113.100502

[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde 및 JP Dowling, "임의의 광자 추가 또는 광자 빼기 압착 상태 샘플링은 보손 샘플링과 동일한 복잡성 클래스에 있습니다." Physical Review A 91, 022317(2015).
https : / /doi.org/10.1103/ PhysRevA.91.022317

[50] CS Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn 및 I. Jex, "Gaussian boson sampling,"Physical review letters 119, 170501 (2017).
https : / /doi.org/10.1103/ PhysRevLett.119.170501

[51] A. Lund, S. Rahimi-Keshari 및 T. Ralph, "가우스 연속 변수 측정을 사용한 정확한 보손 샘플링", Physical Review A 96, 022301(2017).
https : / /doi.org/10.1103/ PhysRevA.96.022301

[52] L. Chakhmakhchyan 및 NJ Cerf, "가우스 측정을 사용한 Boson 샘플링", Physical Review A 96, 032326(2017).
https : / /doi.org/10.1103/ PhysRevA.96.032326

[53] U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi 및 G. Ferrini, "광자 추가 또는 광자 빼기 압착 상태의 연속 변수 샘플링", Physical Review A 96, 062307( 2017).
https : / /doi.org/10.1103/ PhysRevA.96.062307

[54] N. Quesada, JM Arrazola 및 N. Killoran, "임계값 검출기를 사용한 가우시안 보손 샘플링", Physical Review A 98, 062322(2018).
https : / /doi.org/10.1103/ PhysRevA.98.062322

[55] A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert, et al., “높은 양자 컴퓨팅 이점 -차원 Gaussian boson 샘플링,” Science Advances 8, 7894(2022).
https://doi.org/10.1126/sciadv.abi7894