Clifford 회로는 $textsf{RP}=textsf{NP}$인 경우에만 PAC를 올바르게 학습할 수 있습니다.

플라톤에 의해 재발행

팔로워 : 0

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

이 논문이 흥미 롭거나 토론하고 싶습니까? 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 데이터

@article{Liang2023cliffordcircuitscan, doi = {10.22331/q-2023-06-07-1036}, url = {https://doi.org/10.22331/q-2023-06-07-1036}, 제목 = {Clifford { C}회로는 {$textsf{RP}=textsf{NP}$}}, 저자 = {Liang, Daniel}, 저널 = {{Quantum}}인 경우에만 {P}제대로 {PAC} {L}획득할 수 있습니다. , issn = {2521-327X}, 게시자 = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, 볼륨 = {7}, 페이지 = {1036}, 월 = 2023월, 연도 = {XNUMX} }

► 참고 문헌

[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] JB Altepeter, D. Branning, E. Jeffrey, TC Wei, PG Kwiat, RT Thew, JL O'Brien, MA Nielsen 및 AG 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과 Ronald de Wolf. 학습 알고리즘의 최적 양자 샘플 복잡성. Ryan O'Donnell, 편집자, 제32회 전산 복잡성 회의(CCC 2017), Leibniz International Proceedings in Informatics(LIPIcs) 79권, 페이지 25:1–25:31, Dagstuhl, 독일, 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와 Shai Shalev-Shwartz. dnf 학습에 대한 복잡성 이론적 한계. In Vitaly Feldman, Alexander Rakhlin 및 Ohad Shamir, 편집자, 학습 이론에 관한 29차 연례 회의, 기계 학습 연구 절차 49권, 페이지 815–830, Columbia University, New York, New York, USA, 23년 26월 2016–49일 .PMLR. URL https:/ / proceedings.mlr.press/ v16/ danielyXNUMX.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. 강의 9: 학습의 어려움. 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. CS6781에 대한 강의 노트 – 기계 학습의 이론적 기초.
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] 마이클 카리토노프. 분포별 학습의 암호화 경도. 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] 라이언 오도넬과 존 라이트. 효율적인 양자 단층 촬영. 컴퓨팅 이론에 관한 16차 연례 ACM 심포지엄 절차, STOC '899, 페이지 912–2016, 뉴욕, 뉴욕, 미국, 9781450341325년. 컴퓨팅 기계 협회. ISBN 10.1145. 2897518.2897544/ XNUMX.
https : / /doi.org/ 10.1145 / 2897518.2897544

[42] 라이언 오도넬과 존 라이트. 효율적인 양자 단층 촬영 ii. 컴퓨팅 이론에 관한 제49회 연례 ACM SIGACT 심포지엄 절차, STOC 2017, 페이지 962–974, 뉴욕, 뉴욕, 미국, 2017. 컴퓨팅 기계 협회. 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