1브리스톨 대학교 수학과. n.linden@bristol.ac.uk
2QuSoft, CWI 및 네덜란드 암스테르담 대학. rdewolf@cwi.nl
이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.
추상
양자 푸리에 변환(Quantum Fourier Transform, QFT)은 위상 추정과 같은 더 큰 계산 내에서 일반적으로 서브루틴으로 사용되는 양자 컴퓨팅의 핵심 프리미티브입니다. 따라서 QFT에 입력되는 상태를 거의 제어할 수 없습니다. 따라서 좋은 QFT를 구현하려면 임의의 입력 상태에서 잘 수행되어야 한다고 생각할 수 있습니다. QFT 구현의 이 최악의 경우 올바른 동작을 $Verifying$하는 것은 일반적으로 기하급수적으로 어려워(큐비트 수에서) 이 검증이 유용한 크기의 시스템에서 실제로 불가능할 것이라는 우려를 제기합니다. 이 백서에서 우리는 사실 위상 추정, 주기 찾기 및 진폭 추정과 같은 주요 작업에 대해 좋은 $worst$-$case$ 성능을 달성하기 위해 QFT의 좋은 $average$-$case$ 성능만 있으면 된다는 것을 보여줍니다. . 또한 우리는 QFT의 필수 평균 사례 동작을 검증하기 위한 매우 효율적인 절차를 제공합니다.
인기 요약
► BibTeX 데이터
► 참고 문헌
[1] 스콧 아론슨과 패트릭 랄. 양자 근사 계산, 단순화. 알고리즘의 단순성에 관한 제3차 심포지엄(SOSA) 절차, 24–32페이지, 2020. arXiv:1908.10846.
https : / /doi.org/ 10.1137 / 1.9781611976014.5
arXiv : 1908.10846
[2] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. 양자 컴퓨팅의 강점과 약점. SIAM Journal on Computing, 26(5):1510–1523, 1997. quant-ph/ 9701001.
https : / /doi.org/ 10.1137 / S0097539796300933
arXiv : 퀀트 -PH / 9701001
[3] Gilles Brassard, Peter Høyer, Michele Mosca 및 Alain Tapp. 양자 진폭 증폭 및 추정. Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series의 305권, 53–74페이지. 2002. quant-ph/0005055.
https : / /doi.org/10.1090/conm/305/05215
arXiv : 퀀트 -PH / 0005055
[4] Chi-Fang Chen과 Fernando GSL Brandão. Trotter 오류에 대한 집중. arXiv:2111.05324, 9년 2021월 XNUMX일.
https:///doi.org/10.48550/arXiv.2111.05324
arXiv : 2111.05324
[5] 리차드 클레브, 아르투르 에커트, 키아라 마키아벨로, 미셸 모스카. 양자 알고리즘을 재검토했습니다. 런던 왕립 학회 회보, A454권, 339–354쪽, 1998년. quant-ph/ 9708016.
https : / /doi.org/ 10.1098 / rspa.1998.0164
arXiv : 퀀트 -PH / 9708016
[6] 돈 코퍼스미스. 양자 인수분해에 유용한 근사 푸리에 변환입니다. IBM 연구 보고서 번호 RC19642, quant-ph/ 0201067, 1994.
https:///doi.org/10.48550/arXiv.quant-ph/0201067
arXiv : 퀀트 -PH / 0201067
[7] 마커스 다 실바, 올리버 랜든-추기경, 데이비드 풀린. 단층 촬영 없이 양자 장치의 실제 특성화. Physical Review Letters, 107:210404, 2011. arXiv:1104.3835.
https : / /doi.org/10.1103/ PhysRevLett.107.210404
arXiv : 1104.3835
[8] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, Elham Kashefi. 양자 인증 및 벤치마킹. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
https://doi.org/10.1038/s42254-020-0186-4
arXiv : 1910.06343
[9] Steven T. Flammia와 Yi-Kai Liu. 소수의 Pauli 측정에서 직접 충실도 추정. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.
https : / /doi.org/10.1103/ PhysRevLett.106.230501
arXiv : 1104.4695
[10] András Gilyén, Srinivasan Arunachalam 및 Nathan Wiebe. 더 빠른 양자 기울기 계산을 통해 양자 최적화 알고리즘을 최적화합니다. 30th ACM-SIAM SODA 회보, 페이지 1425–1444, 2019. arXiv:1711.00465.
https : / /doi.org/ 10.1137 / 1.9781611975482.87
arXiv : 1711.00465
[11] 러브 K. 그로버. 데이터베이스 검색을 위한 빠른 양자 역학 알고리즘입니다. 28차 ACM STOC 회보, 212-219페이지, 1996. quant-ph/ 9605043.
https : / /doi.org/ 10.1145 / 237814.237866
arXiv : 퀀트 -PH / 9605043
[12] András Gilyén, Yuan Su, Guang Hao Low 및 Nathan Wiebe. 양자 특이값 변환 및 그 이상: 양자 행렬 산술의 기하급수적 개선. 51st ACM STOC 절차, 193–204, 2019. arXiv:1806.01838.
https : / /doi.org/ 10.1145 / 3313276.3316366
arXiv : 1806.01838
[13] 스티븐 P. 조던. 수치 기울기 추정을 위한 빠른 양자 알고리즘. Physical Review Letters, 95:050501, 2005. quant-ph/ 0405146.
https : / /doi.org/10.1103/ PhysRevLett.95.050501
arXiv : 퀀트 -PH / 0405146
[14] 알렉세이 유. Kitaev. 양자 측정 및 Abelian 안정기 문제. quant-ph/9511026, 12년 1995월 XNUMX일.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
arXiv : 퀀트 -PH / 9511026
[15] 노아 린든과 로널드 드 울프. 양자 회로에서 적은 수의 큰 오류를 경량으로 감지합니다. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv : 2009.08840
[16] 우르밀라 마하데프. 양자 계산의 고전적 검증. 59차 IEEE FOCS 절차, 259–267페이지, 2018. arXiv:1804.01082.
https : / /doi.org/10.1109/FOCS.2018.00033
arXiv : 1804.01082
[17] John M. Martyn, Zane M. Rossi, Andrew K. Tan 및 Isaac L. Chuang. 양자 알고리즘의 대통합. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https : / / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] 마이클 A. 닐슨과 아이작 L. 추앙. 양자 계산 및 양자 정보. 캠브리지 대학 출판부, 2000.
https : / /doi.org/ 10.1017 / CBO9780511976667
[19] 패트릭 랄. 위상, 에너지 및 진폭 추정을 위한 더 빠른 일관된 양자 알고리즘. 양자, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv : 2103.09717
[20] 피터 W. 쇼어. 양자 컴퓨터에서 소인수 분해 및 이산 대수를 위한 다항 시간 알고리즘. SIAM Journal on Computing, 26(5):1484–1509, 1997. FOCS'94의 이전 버전. quant-ph/ 9508027.
https : / /doi.org/ 10.1137 / S0097539795293172
arXiv : 퀀트 -PH / 9508027
[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. 무작위 입력을 사용한 해밀턴 시뮬레이션. arXiv:2111.04773, 8년 2021월 XNUMX일.
https:///doi.org/10.48550/arXiv.2111.04773
arXiv : 2111.04773
인용
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén 및 Giacomo Nannicini, "국가 준비 단위를 사용한 양자 단층 촬영", arXiv : 2207.08800.
위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2022-12-08 04:24:57). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.
On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2022-12-08 04:24:56).
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.
