기본 양자 서브루틴: 표시된 여러 요소 찾기 및 숫자 합산

기본 양자 서브루틴: 표시된 여러 요소 찾기 및 숫자 합산

타임 스탬프 : 14 년 2024 월 9 일 오전 40시 XNUMX 분
기본 양자 서브루틴: 표시된 여러 요소 찾기 및 숫자 합산 PlatoBlockchain Data Intelligence. 수직 검색. 일체 포함.

조란 반 아펠 도른1, 샌더 그리블링2및 해롤드 뉴보어3

1IViR 및 QuSoft, 네덜란드 암스테르담 대학교
2네덜란드 틸뷔르흐 소재 틸뷔르흐 대학교 계량경제학 및 운영 연구학과
3Korteweg–de Vries 수학 및 QuSoft 연구소, 네덜란드 암스테르담 대학교, 독일 보훔 루르 대학교 컴퓨터 과학 학부, 덴마크 코펜하겐 대학교 수리과학과

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

추상

우리는 최적의 양자 쿼리 수 $O(sqrt{N k})$를 사용하고 게이트 복잡성의 다대수 오버헤드만 사용하여 $N$ 크기 목록에서 $k$로 표시된 모든 요소를 ​​찾는 방법을 보여줍니다. 하나는 작은 양자 메모리를 가지고 있습니다. 이전 알고리즘은 게이트 복잡도에서 $k$ 요소의 오버헤드를 발생시키거나 쿼리 복잡도에 추가 요소 $log(k)$를 발생시켰습니다.
그런 다음 다음에 대한 양자 쿼리 액세스가 주어지면 $s = sum_{i=1}^N v_i$의 곱셈 $delta$ 근사를 찾는 문제를 고려합니다. 여기서 $v=(v_i)는 [0,1]^N$입니다. $v$의 이진 설명입니다. $O(sqrt{N log(1/rho) / delta})$ 양자 쿼리($rho$에 대한 가벼운 가정 하에서)를 사용하여 최소 $1-rho$ 확률로 그렇게 하는 알고리즘을 제공합니다. 이는 진폭 추정의 간단한 적용에 비해 $1/delta$ 및 $log(1/rho)$에 대한 의존성을 1차적으로 향상시킵니다. 개선된 $log(XNUMX/rho)$ 의존성을 얻기 위해 첫 번째 결과를 사용합니다.

► BibTeX 데이터

► 참고 문헌

[1] 스리니바산 아루나찰람(Srinivasan Arunachalam)과 로날드 드 울프(Ronald de Wolf). 양자 검색에서 게이트 수를 최적화합니다. 양자 정보. Comput., 17(3-4):251–261, 2017. doi:10.26421/qic17.3-4.
https : / /doi.org/ 10.26421 / qic17.3-4

[2] 호세 A. 아델(José A. Adell)과 P. 조드라(P. Jodrá). 정확한 Kolmogorov 및 일부 친숙한 이산 분포 간의 전체 변동 거리. 불평등 및 적용 저널, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https:/​/​doi.org/​10.1155/​JIA/​2006/​64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter 및 Ronald de Wolf. 행렬 스케일링 및 행렬 균형을 위한 양자 알고리즘. 제48회 오토마타, 언어 및 프로그래밍에 관한 국제 콜로키움(ICALP'21) 진행, 198권, 페이지 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.ICALP.2021.110.
https : / /doi.org/10.4230/LIPIcs.ICALP.2021.110
arXiv : 2011.12823

[4] 스콧 아론슨과 패트릭 Rall. 양자 근사 계산이 단순화되었습니다. 알고리즘의 단순성에 관한 심포지엄, 24년 32~2020페이지. doi:10.1137/​1.9781611976014.5.
https : / /doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer 및 Alain Tapp. 양자 검색의 경계가 엄격합니다. Fortschritte der Physik, 46(4–5):493–505, 1998. Physcomp'96의 이전 버전. arXiv:퀀트-ph/​9605034.
arXiv : 퀀트 -PH / 9605034

[6] 해리 버먼(Harry Buhrman), 리처드 클리브(Richard Cleve), 로날드 드 울프(Ronald de Wolf), 크리스토프 잘카(Christof Zalka). 작은 오류 및 오류가 없는 양자 알고리즘의 한계입니다. 컴퓨터 과학 기초에 관한 제40회 연례 심포지엄(FOCS'99), 358~368페이지. IEEE 컴퓨터 학회, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca 및 Alain Tapp. 양자 진폭 증폭 및 추정. 양자 계산 및 양자 정보: 밀레니엄 볼륨, 현대 수학 305권, 53~74페이지. 미국수학회, 2002. doi:10.1002/(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[8] 리처드 브렌트와 폴 짐머만. 현대 컴퓨터 산술, 18권. 케임브리지 대학 출판부, 2010.

[9] 란 카네티, 가이 이븐, 오데드 골드라이히. 평균을 추정하기 위한 샘플링 알고리즘의 하한입니다. 정보 처리 서한, 53(1):17–25, 1995년 10.1016월. doi:0020/0190-94(00171)XNUMX-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini 및 Leonard Wossnig. 양자 기계 학습: 고전적인 관점. 왕립학회보 A: 수학, 물리 및 공학 과학, 474(2209):20170551, 2018년 10.1098월. doi:2017.0551/​rspa.XNUMX.
https : / /doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest 및 Clifford Stein. 알고리즘 소개. MIT Press, 4판, 2022.

[12] P. Diaconis 및 D. Freedman. 유한한 교환 가능 시퀀스. The Annals of Probability, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https : / //www.jstor.org/stable/ 2242823

[13] 크리스토프 뒤어(Christoph Dürr)와 피터 회이어(Peter Høyer). 최소값을 찾기 위한 양자 알고리즘, 1996. doi:10.48550/arXiv.Quant-ph/9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv : 퀀트 -PH / 9607014

[14] 크리스토프 뒤어(Christoph Dürr), 마크 하일리그만(Mark Heiligman), 피터 회이어(Peter Høyer), 메흐디 말라(Mehdi Mhalla). 일부 그래프 문제의 양자 쿼리 복잡성. SIAM 컴퓨팅 저널, 35(6):1310–1328, 2006년 10.1137월. doi:050644719/​XNUMX.
https : / /doi.org/ 10.1137 / 050644719

[15] 폴 다검, 리차드 카프, 마이클 루비, 셸던 로스. 몬테카를로 추정을 위한 최적 알고리즘. SIAM 컴퓨팅 저널, 29(5):1484–1496, 2000년 10.1137월. doi:0097539797315306/​SXNUMX.
https : / /doi.org/ 10.1137 / S0097539797315306

[16] 비토리오 지오반네티, 세스 로이드, 로렌조 맥코네. 양자 랜덤 액세스 메모리. 실제 검토 편지, 100(16), 2008년 10.1103월. doi:100.160501/physrevlett.XNUMX.
https : / //doi.org/10.1103/ physrevlett.100.160501

[17] 샌더 그리블링(Sander Ggribling)과 해롤드 뉴보어(Harold Nieuwboer). 매트릭스 스케일링에 대한 양자 하한 및 상한이 개선되었습니다. 컴퓨터 과학의 이론적 측면에 관한 제39차 국제 심포지엄(STACS'22) 진행, 219권, 페이지 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/LIPIcs.STACS.2022.35.
https : / /doi.org/10.4230/LIPIcs.STACS.2022.35
arXiv : 2109.15282

[18] 마트 드 그라프(Mart de Graaf)와 로날드 드 울프(Ronald de Wolf). 야오 원리의 양자 버전에 대하여. 컴퓨터 과학의 이론적 측면에 관한 19차 심포지엄(STACS'02), 컴퓨터 과학 강의 노트 2285권, 347~358페이지, 베를린, 하이델베르그, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] 러브 K. 그로버. 데이터베이스 검색을 위한 빠른 양자 역학 알고리즘입니다. 제38차 연례 ACM 컴퓨팅 이론 심포지엄(STOC'96) 진행, 페이지 212–219, 1996. arXiv:퀀트-ph/​9605043, doi:10.1145/​237814.237866.
https : / /doi.org/ 10.1145 / 237814.237866
arXiv : 퀀트 -PH / 9605043

[20] 러브 K. 그로버. 양자 원격 계산, 1997. Bell Labs 기술 각서 ITD97-31630F. doi:10.48550/arXiv.Quant-ph/9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv : 퀀트 -PH / 9704012

[21] 러브 K. 그로버. 빠른 양자 역학 알고리즘을 위한 프레임워크입니다. 컴퓨팅 이론에 관한 제98회 연례 ACM 심포지엄(STOC'53) 진행, 페이지 62–1998, 9711043. arXiv:퀀트-ph/​10.1145, doi:276698.276712/​XNUMX.
https : / /doi.org/ 10.1145 / 276698.276712
arXiv : 퀀트 -PH / 9711043

[22] 야신 하무디. 양자 하위 가우스 평균 추정기. 제29차 연례 유럽 알고리즘 심포지엄(ESA 2021), 라이프니츠 국제 정보학 회보(LIPIcs) 204권, 페이지 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https : / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] 스반테 얀슨. 기하 및 지수 변수의 합계에 대한 꼬리 경계입니다. 통계 및 확률 편지, 135:1–6, 2018. doi:10.1016/j.spl.2017.11.017.
https:/​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] 도널드 어빈 크누스. 컴퓨터 프로그래밍 기술, 2권. Addison-Wesley, 1998판, 312994415. URL: https://​/​www.worldcat.org/​oclc/​XNUMX.
https://​/​www.worldcat.org/​oclc/​312994415

[25] 로빈 코타리와 라이언 오도넬. 소스 코드가 있을 때 평균 추정 또는 양자 몬테카를로 방법. 이산 알고리즘에 관한 2023년 연례 ACM-SIAM 심포지엄(SODA'23) 진행, 페이지 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https : / /dodo.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen과 Isaac L. Chuang. 양자 계산 및 양자 정보. 케임브리지 대학 출판부, 2002.

[27] Ashwin Nayak과 펠릭스 우. 중앙값 및 관련 통계를 근사화하는 양자 쿼리 복잡성입니다. 제31회 연례 ACM SIGACT 컴퓨팅 이론 심포지엄(STOC'99) 진행, 페이지 384–393, 1999. arXiv:퀀트-ph/​9804066, doi:10.1145/​301250.301349.
https : / /doi.org/ 10.1145 / 301250.301349
arXiv : 퀀트 -PH / 9804066

[28] B. 루스. 포아송 이항 분포에 대한 이항 근사: Krawtchouk 확장. 확률 이론 및 그 응용, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https:/ / doi.org/ 10.1137/ S0040585X9797821X

[29] 로버트 M. 영. 75.9 오일러 상수. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https : / /doi.org/ 10.2307 / 3620251

인용

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

타임 스탬프 :

더보기 양자 저널