Clifford 회로는 $textsf{RP}=textsf{NP}$인 경우에만 적절하게 PAC 학습될 수 있습니다.

Clifford 회로는 $textsf{RP}=textsf{NP}$인 경우에만 적절하게 PAC 학습될 수 있습니다.

타임 스탬프 : 7 년 2023 월 6 일 07:XNUMX AM
소스 노드 : 2706854

다니엘 리앙

오스틴에 있는 텍사스 대학교 컴퓨터 공학과

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

추상

입력 상태, 측정 및 확률의 데이터 세트가 주어지면 양자 회로와 관련된 측정 확률을 효율적으로 예측할 수 있습니까? Caro와 Datta의 최근 작업 [19]는 정보 이론적 의미에서 PAC 학습 양자 회로 문제를 연구하여 계산 효율성에 대한 열린 질문을 남겼습니다. 특히, 효율적인 학습기가 가능했을 수 있는 회로의 후보 클래스 중 하나는 Clifford 회로였습니다. 이러한 회로에 의해 생성된 안정기 상태라고 하는 해당 상태 세트는 효율적으로 PAC 학습이 가능한 것으로 알려져 있기 때문입니다.44]. 여기서 우리는 부정적인 결과를 제공하여 $textsf{RP = NP}$가 아닌 한 1/ poly($n$) 오류가 있는 CNOT 회로의 적절한 학습이 고전 학습자에게 어렵다는 것을 보여주며 표준 복잡성 이론 하에서 강력한 학습자의 가능성을 배제합니다. 가정. Clifford 회로의 고전적인 아날로그 및 하위 집합으로서 이것은 당연히 Clifford 회로에 대한 경도 결과로 이어집니다. 또한 $textsf{RP = NP}$인 경우 CNOT 및 Clifford 회로에 대한 효율적인 적절한 학습 알고리즘이 존재함을 보여줍니다. 유사한 주장에 의해, 우리는 $textsf{NP ⊆ RQP}$인 경우에만 그러한 회로에 대한 효율적인 적절한 양자 학습기가 존재한다는 것을 발견했습니다. 부적절한 학습이나 $mathcal{O(1)}$ 오류에 대한 경도 문제는 향후 작업에 남겨둡니다.

► BibTeX 데이터

► 참고 문헌

[1] 스콧 애런슨. 양자 상태의 학습 가능성. 왕립 학회 회보 A: 수학, 물리 및 공학 과학, 463 (2088): 3089–3114, 2007. 10.1098/rspa.2007.0113.
https : / /doi.org/ 10.1098 / rspa.2007.0113

[2] 스콧 애런슨. 양자 상태의 그림자 단층 촬영. 컴퓨팅 이론에 관한 제50회 연례 ACM SIGACT 심포지엄 절차, STOC 2018, 페이지 325–338, 뉴욕, 뉴욕, 미국, 2018. 컴퓨팅 기계 협회. ISBN 9781450355599. 10.1145/ 3188745.3188802.
https : / /doi.org/ 10.1145 / 3188745.3188802

[3] Scott Aaronson과 Daniel Gottesman. 스태빌라이저 회로의 향상된 시뮬레이션. Physical Review A, 70(5): 052328, 2004. 10.1103/physreva.70.052328.
https : / /doi.org/10.1103/ physreva.70.052328

[4] J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O'Brien, M. A. Nielsen 및 A. G. White. Ancilla 보조 양자 프로세스 단층 촬영. 물리. Lett., 90: 193601, 2003년 10.1103월. 90.193601/​PhysRevLett.XNUMX.
https : / /doi.org/10.1103/ PhysRevLett.90.193601

[5] 마틴 앤서니와 피터 L. 바틀렛. 보간에서 함수 학습. 조합론, 확률 및 컴퓨팅, 9 (3): 213–225, 2000. 10.1017/ S0963548300004247.
https : / /doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam과 Ronald de Wolf. 게스트 칼럼: 양자 학습 이론에 대한 조사. ACM SIGACT 뉴스, 48(2): 41–67, 2017. 10.1145/3106700.3106710.
https : / /doi.org/ 10.1145 / 3106700.3106710

[7] Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/​LIPIcs.CCC.2017.25.
https : / /doi.org/10.4230/ LIPIcs.CCC.2017.25

[8] Srinivasan Arunachalam, Alex B Grilo 및 Henry Yuen. 양자 통계 쿼리 학습. arXiv 프리프린트 arXiv:2002.08240, 2020. https:/ / doi.org/ 10.48550/ arXiv.2002.08240.
https://​/​doi.org/​10.48550/​arXiv.2002.08240
arXiv : 2002.08240

[9] Srinivasan Arunachalam, Alex Bredariol Grilo 및 Aarthi Sundaram. 얕은 고전 회로 학습의 양자 경도. 컴퓨팅에 관한 SIAM 저널, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https : / //doi.org/10.1137/ 20M1344202

[10] Charles H. Bennett와 Gilles Brassard. 양자 암호화: 공개 키 배포 및 동전 던지기. 이론적 컴퓨터 과학, 560: 7–11, 2014년 0304월. ISSN 3975-10.1016. 2014.05.025/j.tcs.XNUMX.
https : / /doi.org/ 10.1016 / j.tcs.2014.05.025

[11] Charles H. Bennett 및 Stephen J. Wiesner. 아인슈타인-포돌스키-로젠 상태에서 69입자 및 2881입자 연산자를 통한 통신. 물리학 Lett., 2884: 1992–10.1103, 69.2881년 XNUMX월. XNUMX/PhysRevLett.XNUMX.
https : / /doi.org/10.1103/ PhysRevLett.69.2881

[12] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, William K. Wootters. 이중 클래식 및 아인슈타인-포돌스키-로젠 채널을 통해 알려지지 않은 양자 상태를 순간이동합니다. 물리학 Lett., 70: 1895–1899, 1993년 10.1103월. 70.1895/PhysRevLett.XNUMX.
https : / /doi.org/10.1103/ PhysRevLett.70.1895

[13] 에단 번스타인과 우메쉬 바지라니. 양자 복잡도 이론. 컴퓨팅에 관한 SIAM 저널, 26 (5): 1411–1473, 1997. 10.1137/ S0097539796300921.
https : / /doi.org/ 10.1137 / S0097539796300921

[14] 아브림 블룸. 학습의 전산 경도. http:/ / www.cs.cmu.edu/ avrim/ ML07/ lect1007.pdf, 2015. URL http:/ / www.cs.cmu.edu/ avrim/ ML07/ lect1007 .pdf. CS 10-806 기계 학습 및 데이터 과학의 기초에 대한 강의 노트.
http://www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] Avrim L. Blum 및 Ronald L. Rivest. 3노드 신경망 훈련은 np-완전합니다. 신경망, 5(1): 117–127, 1992. ISSN 0893-6080. https://doi.org/10.1016/ S0893-6080(05)80010-3.
https:/​/​doi.org/​10.1016/​S0893-6080(05)80010-3

[16] Anselm Blumer, A. Ehrenfeucht, David Haussler, Manfred K. Warmuth. 학습 가능성 및 vapnik-chervonenkis 차원. J. ACM, 36(4): 929–965, 1989년 0004월. ISSN 5411-10.1145. 76359.76371/XNUMX.
https : / /doi.org/ 10.1145 / 76359.76371

[17] Jonathan F Buss, Gudmund S Frandsen 및 Jeffrey O Shallit. 선형 대수학의 일부 문제의 계산 복잡성. 컴퓨터 및 시스템 과학 저널, 58(3): 572–596, 1999. ISSN 0022-0000. https://doi.org/10.1006/jcss.1998.1608.
https : / /doi.org/ 10.1006 / jcss.1998.1608

[18] 마티아스 C. 카로. 클래식 인스턴스 및 양자 레이블을 사용한 이진 분류. 양자 기계 지능, 3(1), 2021년 10.1007월. 42484/s021-00043-XNUMX-z.
https : / /doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro와 Ishaun Datta. 양자 회로의 의사 차원. 양자 기계 지능, 2(2), 2020년 2524월. ISSN 4914-10.1007. 42484/s020-00027-5-XNUMX.
https:/​/​doi.org/​10.1007/​s42484-020-00027-5

[20] Hao-Chung Cheng, Min-Hsiu Hsieh, Ping-Cheng Yeh. 알려지지 않은 양자 측정의 학습 가능성. 양자정보 Comput., 16 (7–8): 615–656, 2016년 1533월. ISSN 7146-10.26421. 16.7/QIC8-4-XNUMX.
https : / / doi.org/ 10.26421 / QIC16.7-8-4

[21] 아이작 L. 추앙과 MA 닐슨. 양자 블랙박스의 동역학을 실험적으로 결정하기 위한 처방. Journal of Modern Optics, 44(11-12): 2455–2467, 1997. 10.1080/ 09500349708231894.
https : / /doi.org/ 10.1080 / 09500349708231894

[22] 정개민과 린한수안. PAC 모델 및 대략적인 상태 판별 문제에서 양자 채널 학습을 위한 효율적인 알고리즘 샘플. In Min-Hsiu Hsieh, 편집자, 제16차 양자 계산 이론, 통신 및 암호학 회의(TQC 2021), Leibniz International Proceedings in Informatics(LIPIcs) 197권, 페이지 3:1–3:22, Dagstuhl, 독일, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-198-6. 10.4230/LIPIcs.TQC.2021.3.
https : / //doi.org/10.4230/LIPIcs.TQC.2021.3

[23] Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf's. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 815–830, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR. URL https:/​/​proceedings.mlr.press/​v49/​daniely16.html.
https://proceedings.mlr.press/v49/daniely16.html

[24] Steven T Flammia, David Gross, Yi-Kai Liu, Jens Eisert. 압축 감지를 통한 양자 단층 촬영: 오류 범위, 샘플 복잡성 및 효율적인 추정기. New Journal of Physics, 14 (9): 095022, 2012년 10.1088월. 1367/ 2630-14/ 9/ 095022/ XNUMX.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​9/​095022

[25] 폴 W. 골드버그와 마크 R. 제럼. 실수로 매개변수화된 개념 클래스의 vapnik-chervonenkis 차원 경계. 기계 학습, 18: 131–148, 1995. 10.1007/BF00993408.
https : / /doi.org/ 10.1007 / BF00993408

[26] 다니엘 고테스만. 안정기 코드 및 양자 오류 수정, 1997.

[27] 다니엘 고테스만. 양자 컴퓨터의 하이젠베르크 표현, 1998.

[28] Venkatesan Guruswami와 Prasad Raghavendra. 노이즈가 있는 하프스페이스 학습의 경도. 컴퓨팅에 관한 SIAM 저널, 39(2): 742–765, 2009. 10.1137/070685798.
https : / /doi.org/ 10.1137 / 070685798

[29] 하정완, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, Nengkun Yu. 양자 상태의 샘플 최적 단층 촬영. 정보 이론에 관한 IEEE 거래, 1-1페이지, 2017. ISSN 1557-9654. 10.1109/tit.2017.2719044.
https : / /doi.org/10.1109/ tit.2017.2719044

[30] Nika Haghtalab. Lecture 9: Hardness of Learning. https:/​/​www.cs.cornell.edu/​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf, 2020. URL https:/​/​www.cs.cornell.edu/​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf. Lecture notes for CS6781 - Theoretical Foundations of Machine Learning.
https:/ / www.cs.cornell.edu/ courses/ cs6781/ 2020sp/ lectures/ 09-hardness1.pdf

[31] Hsin-Yuan Huang, Richard Kueng, John Preskill. 극소수의 측정에서 양자 시스템의 많은 속성을 예측합니다. 자연 물리학, 2020년 10.1038월. 41567/s020-0932-7-XNUMX.
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[32] 조나단 카츠. 복잡성 이론 강의 노트 3. https:/ / www.cs.umd.edu/ jkatz/ complexity/ f11/ lecture3.pdf, 2011. URL https:/ / www.cs.umd. edu/jkatz/complexity/f11/lecture3.pdf. CS 652 강의 노트 - 복잡성 이론.
https:/ / www.cs.umd.edu/ ~jkatz/ complexity/ f11/ lecture3.pdf

[33] Michael Kharitonov. Cryptographic hardness of distribution-specific learning. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, page 372–381, New York, NY, USA, 1993. Association for Computing Machinery. ISBN 0897915917. 10.1145/​167088.167197.
https : / /doi.org/ 10.1145 / 167088.167197

[34] J. Kleinberg 및 E. Tardos. 알고리즘 설계. 피어슨 교육, 2022. ISBN 9780132131087. URL https:// / books.google.com/ books?id=GORecgAACAAJ.
https://books.google.com/books?id=GORecgAACAAJ

[35] 아담 클리반스. PAC 학습 모델. https:/ / www.cs.utexas.edu/ klivans/ f06lec2.pdf, 2005. URL https:/ / www.cs.utexas.edu/ klivans/ f06lec2.pdf. CS 395T 전산 학습 이론에 대한 강의 노트.
https://www.cs.utexas.edu/~klivans/f06lec2.pdf

[36] 로버트 코닉과 존 A. 스몰린. 임의의 클리포드 그룹 요소를 효율적으로 선택하는 방법. Journal of Mathematical Physics, 55 (12): 122202, 2014년 1089월. ISSN 7658-10.1063. 1.4903507/XNUMX.
https : / /doi.org/ 10.1063 / 1.4903507

[37] 리처드 쿠엥과 데이비드 그로스. Qubit 스태빌라이저 상태는 복잡한 투영 3-디자인, 2015년입니다.

[38] 라이 칭이와 쳉 하오충. 일부 t 게이트의 양자 회로 학습. 정보 이론에 관한 IEEE 거래, 1-1페이지, 2022. 10.1109/ TIT.2022.3151760.
https : / //doi.org/10.1109/TIT.2022.3151760

[39] 리차드 A. 로우. Clifford 그룹을 위한 학습 및 테스트 알고리즘. 물리학 A, 80: 052314, 2009년 10.1103월. 80.052314/PhysRevA.XNUMX.
https : / /doi.org/10.1103/ PhysRevA.80.052314

[40] 애슐리 몬타나로. 2017년 Bell 샘플링을 통한 안정기 상태 학습.

[41] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1145/​2897518.2897544.
https : / /doi.org/ 10.1145 / 2897518.2897544

[42] Ryan O'Donnell and John Wright. Efficient quantum tomography ii. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 962–974, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345286. 10.1145/​3055399.3055454.
https : / /doi.org/ 10.1145 / 3055399.3055454

[43] Yihui Quek, Srinivasan Arunachalam, John A Smolin. 개인 학습은 양자 안정성을 의미합니다. M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang 및 J. Wortman Vaughan, 편집자, Advances in Neural Information Processing Systems, 34권, 20503-20515페이지. Curran Associates, Inc., 2021. URL https:/ / proceedings.neurips.cc/ paper/ 2021/ file/ abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] 안드레아 로케토. 안정기 상태는 PAC에서 효율적으로 학습할 수 있습니다. 양자 정보 및 계산, 18(7-8): 541–552, 2018. 10.26421/qic18.7-8-1.
https : / / doi.org/ 10.26421 / qic18.7-8-1

[45] 피터 W. 쇼어. 양자 컴퓨터에서 소인수 분해 및 이산 대수를 위한 다항 시간 알고리즘. SIAM Review, 41(2): 303–332, 1999. 10.1137/S0036144598347011.
https : / /doi.org/ 10.1137 / S0036144598347011

[46] 다니엘 R. 사이먼. 양자 컴퓨팅의 힘. 컴퓨팅에 관한 SIAM 저널, 26 (5): 1474–1483, 1997. 10.1137/ S0097539796298637.
https : / /doi.org/ 10.1137 / S0097539796298637

[47] 레슬리 G 발리언트. 학습 가능한 이론. ACM 통신, 27(11): 1134–1142, 1984. 10.1145/1968.1972.
https : / /doi.org/ 10.1145 / 1968.1972

[48] Ewout Van Den Berg. 무작위 Clifford 연산자를 샘플링하는 간단한 방법입니다. 2021년 QCE(Quantum Computing and Engineering)에 관한 IEEE 국제 컨퍼런스, 54–59페이지, 2021. 10.1109/ QCE52317.2021.00021.
https : / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] 미투나 요가나단. 고전적 시뮬레이션 가능성이 효율적인 상태 학습 가능성을 의미하는 조건, 2019.

[50] 주황준. Multiqubit Clifford 그룹은 단일 3-디자인입니다. 물리학 A, 96: 062336, 2017년 10.1103월. 96.062336/PhysRevA.XNUMX.
https : / /doi.org/10.1103/ PhysRevA.96.062336

인용

[1] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, "Learning efficient decoders for quasi-chaotic quantum scramblers", arXiv : 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt 및 Theodore J. Yoder, "양자 위상 상태 학습을 위한 최적의 알고리즘", arXiv : 2208.07851, (2022).

[3] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", arXiv : 2305.20069, (2023).

위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2023-06-07 22:21:42). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.

On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2023-06-07 22:21:40).

이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.

타임 스탬프 :

더보기 양자 저널