1물리학과, ETH 취리히, 스위스
2이론 연구 연구소, ETH 취리히, 스위스
이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.
추상
양자성 증명은 전통적인 검증자가 신뢰할 수 없는 증명자의 $textit{quantum Advantage}$를 효율적으로 인증할 수 있는 일종의 도전-응답 프로토콜입니다. 즉, 양자 증명자는 검증자의 문제에 올바르게 대답하고 수락될 수 있는 반면, 모든 다항 시간 고전 증명자는 그럴듯한 계산 가정을 기반으로 높은 확률로 거부됩니다. 검증자의 문제에 답하기 위해 기존 양자 증명은 일반적으로 양자 증명자가 다항식 크기 양자 회로와 측정의 조합을 수행하도록 요구합니다.
이 백서에서는 증명자가 로그 깊이 고전 계산과 함께 $textit{상수 깊이 양자 회로}$(및 측정)만 수행하면 되는 두 가지 양자성 구조 증명을 제공합니다. 첫 번째 구성은 기존의 모든 양자 증명을 일정한 양자 깊이 버전으로 변환할 수 있는 일반 컴파일러입니다. 우리의 두 번째 구성은 $textit{반올림을 통한 학습}$ 문제를 기반으로 하며 일반 구성보다 더 짧은 깊이와 더 적은 큐비트를 요구하는 회로를 생성합니다. 또한 두 번째 구조는 잡음에 대한 견고성도 어느 정도 갖추고 있습니다.
► BibTeX 데이터
► 참고 문헌
[1] 스콧 아론슨과 알렉스 아르키포프. 선형 광학의 계산 복잡성. 컴퓨팅 이론에 관한 제333회 연례 ACM 심포지엄 절차, 342–2011페이지, XNUMX년.
https : / /doi.org/ 10.1145 / 1993636.1993682
[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell 등. 프로그래밍 가능한 초전도 프로세서를 사용한 양자 우위. 자연, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei 등 Qiskit: 양자 컴퓨팅을 위한 오픈 소스 프레임워크, 2021년.
[4] Sanjeev Arora와 Boaz Barak. 컴퓨팅 복잡성 : 현대적인 접근 방식. 케임브리지 대학 출판부, 2009.
[5] Scott Aaronson과 Lijie Chen. 양자 우위 실험의 복잡성-이론적 토대. 제32회 전산 복잡성 회의 진행, CCC '17, 1–67페이지, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] 스콧 애런슨과 샘 건. 스푸핑 선형 교차 엔트로피 벤치마킹의 고전적인 견고성. 컴퓨팅 이론, 16(11):1–8, 2020.
https : / /doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai 및 E. Kushilevitz. ${NC}^0$의 암호화. 컴퓨터 과학 기초에 관한 제45회 연례 IEEE 심포지엄, 166-175페이지, 2004년.
https : / /doi.org/10.1109/FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, Daniel Wichs. 반올림을 통한 학습, 재방문. In Advances in Cryptology – CRYPTO 2013, 페이지 57–74, 베를린, 하이델베르크, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] 데이비드 A 배링턴. 폭이 제한된 다항식 크기 분기 프로그램은 ${NC}^1$에 있는 언어를 정확히 인식합니다. 컴퓨터 및 시스템 과학 저널, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani 및 Thomas Vidick. 단일 양자 장치의 양자성과 인증 가능한 임의성에 대한 암호화 테스트입니다. 컴퓨터 과학 기초(FOCS)에 관한 2018년 IEEE 59차 연례 심포지엄, 320–331페이지. IEEE, 2018.
https : / /doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, Jeremy M. Sage. 갇힌 이온 양자 컴퓨팅: 진보와 도전. 응용 물리학 리뷰, 2019.
https : / /doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh Vazirani. 양자 랜덤 회로 샘플링의 복잡성과 검증. Nature Physics, 15(2):159–163, 2019년 XNUMX월.
https://doi.org/10.1038/s41567-018-0318-2
[13] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis 및 Hartmut Neven. 단기 장치에서 양자 우월성을 특성화합니다. 자연 물리학, 14(6):595–600, 2018.
https : / /doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani 및 Thomas Vidick. 간단한 양자 증명. 양자 계산, 통신 및 암호화 이론에 관한 15차 회의(TQC 2020), Leibniz International Proceedings in Informatics(LIPIcs) 158권, 페이지 8:1–8:14, Dagstuhl, 독일, 2020. Schloss Dagstuhl–Leibniz- Zentrum for Informatik.
https : / //doi.org/10.4230/LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert 및 Alon Rosen. 의사 난수 함수 및 격자. 암호화의 발전 – EUROCRYPT 2012, 719-737페이지. 스프링거 베를린 하이델베르크, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] John F Clauser, Michael A Horne, Abner Shimony, Richard A Holt. 로컬 숨겨진 변수 이론을 테스트하기 위해 제안된 실험. Physical Review Letters, 23(15):880, 1969.
https : / /doi.org/10.1103/ PhysRevLett.23.880
[17] 매튜 쿠드론, 잘렉스 스타크, 토마스 비딕. 시간에 대한 지역성 거래: 깊이가 낮은 회로에서 인증 가능한 임의성. 수학 물리학에서의 커뮤니케이션, 382(1):49–86, 2021.
https : / /doi.org/ 10.1007 / s00220-021-03963-w
[18] 리차드 클리브와 존 와트러스. 양자 푸리에 변환을 위한 빠른 병렬 회로. 컴퓨터 과학 기초에 관한 제41회 연례 심포지엄 절차, 526~536페이지. IEEE, 2000.
https : / /doi.org/10.1109/ SFCS.2000.892140
[19] 피에르 뒤자르트. Autour de la fonction qui compte le nombre de nombres 프리미어. 박사 논문, Université de Limoges, 1998.
https:/ / www.unilim.fr/ laco/ theses/ 1998/ T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis, Andrew N Cleland. 표면 코드: 실용적인 대규모 양자 계산을 향하여. Physical Review A, 86(3):032324, 2012.
https : / /doi.org/10.1103/ PhysRevA.86.032324
[21] 프랑수아 르 갈. 개인 서신, 2022.
[22] 크레이그 기드니와 마틴 에케로. 2048만 노이즈 큐비트를 사용하여 8시간 안에 20비트 RSA 정수를 인수분해하는 방법. 양자, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu와 Matty J Hoban. 얕은 회로 출력의 엔트로피를 추정하는 것은 어렵습니다. arXiv 프리프린트 arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv : 2002.12814
[24] 히라하라 슈이치와 프랑수아 르 갈. 작은 깊이의 양자 회로를 사용한 양자성 테스트. 컴퓨터 과학의 수학적 기초에 관한 46회 국제 심포지엄(MFCS 2021), Leibniz International Proceedings in Informatics(LIPIcs) 202권, 페이지 59:1–59:15, 독일 Dagstuhl, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https : / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] 아람 W 해로우와 애슐리 몬타나로. 양자 컴퓨팅 우위. 자연, 549(7671):203–209, 2017.
https : / /doi.org/ 10.1038 / nature23458
[26] Peter Høyer와 Robert Špalek. Quantum Fan-out은 강력합니다. 컴퓨팅 이론, 1(5):81–103, 2005.
https : / /doi.org/ 10.4086 / toc.2005.v001a005
[27] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Jianxin Chen. 양자 우위 회로의 고전적 시뮬레이션. arXiv 프리프린트 arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv : 2005.06787
[28] 그레고리 D. 카하나모쿠-메이어 양자 데이터 위조: 고전적으로 IQP 기반 양자 테스트를 물리칩니다. arXiv 프리프린트 arXiv:1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv : 1912.05547
[29] Gregory D. Kahanamoku-Meyer, 최순원, Umesh V. Vazirani, Norman Y. Yao. 전산 벨 테스트에서 고전적으로 검증 가능한 양자 이점. 자연 물리학, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert 및 Oded Regev. 이상적인 격자 및 링에 대한 오류로 학습합니다. 암호화 기술의 이론 및 응용에 관한 연례 국제 회의, 1-23페이지. 스프링거, 2010.
https : / /doi.org/ 10.1145 / 2535925
[31] 우르밀라 마하데프. 양자 계산의 고전적 검증. 컴퓨터 과학 기초(FOCS)에 관한 2018년 IEEE 59차 연례 심포지엄, 259–267페이지. IEEE, 2018.
https : / /doi.org/10.1109/FOCS.2018.00033
[32] Michael A Nielsen과 Isaac Chuang. 양자 계산 및 양자 정보, 2002.
[33] AS Popova와 AN Rubtsov. Gaussian Boson 샘플링을 위한 Quantum Advantage 임계값 크래킹. Quantum 2.0 컨퍼런스 및 전시회에서, 페이지 QW2A.15. Optica 출판 그룹, 2022.
https://doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] 존 프레스킬. NISQ 시대와 그 이후의 양자 컴퓨팅. 양자, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] 마이클 오 라빈. 소수성을 테스트하기 위한 확률적 알고리즘. 정수론 저널, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] 오데드 레게브. 격자에서 오류, 무작위 선형 코드 및 암호화로 학습합니다. ACM 저널(JACM), 56(6):1–40, 2009.
https : / /doi.org/ 10.1145 / 1568318.1568324
[37] 댄 셰퍼드와 마이클 J 브렘너. 일시적으로 구조화되지 않은 양자 계산. 왕립 학회 회보 A: 수학, 물리 및 공학 과학, 465(2105):1413–1439, 2009.
https : / /doi.org/ 10.1098 / rspa.2008.0443
[38] 피터 W 쇼어. 양자 계산을 위한 알고리즘: 이산 대수 및 인수 분해. 컴퓨터 과학 기초에 관한 절차 35차 연례 심포지엄, 124–134페이지. IEEE, 1994.
https : / /doi.org/10.1109/ SFCS.1994.365700
[39] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han , Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao , Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu 및 Jian-Wei Pan. 초전도 양자 프로세서를 사용한 강력한 양자 컴퓨팅 이점. 물리학 Lett., 127:180501, 2021.
https : / /doi.org/10.1103/ PhysRevLett.127.180501
[40] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, JS Chen, NC Pisenti, M Chmielewski, C Collins 등 11큐비트 양자 컴퓨터 벤치마킹. 네이처 커뮤니케이션, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] 지 웬딘. 초전도 회로를 이용한 양자 정보 처리: 리뷰. 물리학 발전에 관한 보고서, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal. 얕은 양자 회로와 무한한 팬인 얕은 고전 회로 사이의 기하급수적 분리. 컴퓨팅 이론에 관한 제51회 연례 ACM SIGACT 심포지엄 절차, 515–526페이지, 2019.
https : / /doi.org/ 10.1145 / 3313276.3316404
[43] 앤드류 치치 야오. 비밀을 생성하고 교환하는 방법. 컴퓨터 과학 기초에 관한 제27회 연례 심포지엄(sfcs 1986), 162–167페이지. IEEE, 1986.
https : / /doi.org/10.1109/ SFCS.1986.25
[44] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang , Wu Dachao, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu 및 Jian-Wei Pan. 60큐비트 24주기 무작위 회로 샘플링을 통한 양자 계산 이점. Science Bulletin, 67(3):240–245, 2022.
https : / /doi.org/ 10.1016 / j.scib.2021.10.017
[45] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. 야오, 마르코 세티나, 크리스토퍼 먼로. 고전적으로 검증 가능한 Quantum Advantage를 위한 대화형 프로토콜. arXiv 프리프린트 arXiv:2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv : 2112.05156
[46] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei- Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, Jian-Wei Pan. 광자를 사용한 양자 계산 이점. 과학, 370(6523):1460–1463, 2020.
https : / / doi.org/ 10.1126 / science.abe8770
인용
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath 및 Ruben Verresen, "유한 깊이 단위, 측정 및 피드포워드의 토폴로지 순서 계층", arXiv : 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch, Robert Koenig, "비-가중 애니온 조작을 위한 적응형 상수 깊이 회로", arXiv : 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina 및 Christopher Monroe, "고전적으로 검증 가능한 양자 이점을 위한 대화형 프로토콜", arXiv : 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo 및 Dmitriy Vassilyev, "선형 회귀 및 극단 집합 이론의 별별 키 동형 PRF", arXiv : 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, 최순원, Umesh V. Vazirani 및 Norman Y. Yao, "계산 벨 테스트에서 고전적으로 검증 가능한 양자 이점", 자연 물리학 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn 및 Avishay Tal, "양자 우위 실험에서 인증된 무작위성", arXiv : 2111.14846.
[7] Nai-Hui Chia 및 Shih-Han Hung, "양자 깊이의 고전적 검증", arXiv : 2205.04656.
[8] 미즈타니 아키히로, 다케우치 유키, 히로마사 료, 아이카와 유스케, 다니 세이이치로, "얽힌 마법 상태에 대한 전산 자가 테스트", 물리적 검토 A 106 1, L010601(2022).
[9] Yihui Quek, Mark M. Wilde 및 Eneet Kaur, "일정한 양자 깊이에서 다변량 추적 추정", arXiv : 2206.15405.
위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2022-09-21 12:16:02). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.
On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2022-09-21 12:16:00).
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.
