더 쉬운 입력에 대한 향상된 양자 쿼리 복잡성

더 쉬운 입력에 대한 향상된 양자 쿼리 복잡성

타임 스탬프 : 8 년 2024 월 11 일 오전 29:XNUMX

노엘 T. 앤더슨1, 정재우1, 셸비 킴멜1, 고다연2, 그리고 예샤오한1,3

1미들버리 칼리지, 미들베리, 버몬트, 미국
2윌리엄스 칼리지, 윌리엄스타운, 매사추세츠, 미국
3브라운 대학교, 프로비던스, RI, 미국

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

추상

함수 평가를 위한 양자 범위 프로그램 알고리즘은 입력이 특정 구조를 갖는다고 약속할 때 쿼리 복잡성을 줄이는 경우가 있습니다. 우리는 미리 약속하지 않아도 이러한 개선 사항이 지속된다는 것을 보여주기 위해 수정된 범위 프로그램 알고리즘을 설계하고 이 접근 방식을 상태 변환의 보다 일반적인 문제로 확장합니다. 응용 프로그램으로서 우리는 Montanaro의 Search with Advice [Montanaro, TQC 2010]를 일반화하여 여러 검색 문제에 대한 평균 쿼리 복잡성에서 지수 및 초다항식 양자 이점을 증명합니다.

PlatoBlockchain 데이터 인텔리전스를 더 쉽게 입력하여 양자 쿼리 복잡성을 개선했습니다. 수직 검색. 일체 포함.

주요 이미지: 알고리즘 중 하나를 생성하는 데 사용된 의사결정 트리.

인기 요약

우리는 클래식 알고리즘과 마찬가지로 양자 알고리즘이 더 쉬운 입력에서 더 빠르게 실행될 것으로 기대합니다. 예를 들어, 순서가 지정되지 않은 목록에서 항목을 검색하고 해당 항목의 복사본이 많이 있는 경우 표시된 항목이 하나만 있는 경우에 비해 이 상황에서 양자 알고리즘이 더 빠르게 실행되어야 한다고 예상할 수 있습니다. 사전에 대상 항목의 수. 실제로 검색 문제의 경우 더 쉬운 입력으로 이러한 이점을 얻는 방법이 알려져 있습니다. 그러나 계산이 충분히 오랫동안 실행되었을 때 플래그를 지정하는 명확한 방법이 없는 경우 이 아이디어를 검색 이외의 문제로 일반화하는 것은 어렵습니다. 우리는 쿼리 모델에서 몇 가지 널리 사용되는 알고리즘 프레임워크를 수정하여 계산이 충분히 오랫동안 실행되었는지 여부를 알려주는 플래그를 생성하여 인스턴스가 쉬운지 어려운지 미리 알지 못한 채 더 쉬운 입력에서 알고리즘을 조기에 종료할 수 있도록 합니다. 애플리케이션으로서 문제에 대한 쉬운 입력과 어려운 입력의 분포가 주어지면 평균 쿼리 복잡성을 분석할 수 있습니다. 우리는 검색 문제에 대한 특정 입력 분포가 기존 알고리즘에 비해 큰 평균 양자 쿼리 이점을 제공한다는 것을 보여줍니다.

► BibTeX 데이터

► 참고 문헌

[1] 안드리스 암바이니스(Andris Ambainis)와 로날드 드 울프(Ronald de Wolf). 평균 사례 양자 쿼리 복잡성. Journal of Physics A: Mathematical and General, 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] 도릿 아하로노프. 양자 계산. 전산물리학 연례 리뷰 VI, 페이지 259-346, 1999. doi:10.1142/​9789812815569_0007.
https : / /dodo.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer 및 Alain Tapp. 양자 검색의 엄격한 경계. Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -피.
<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

[4] 알렉산드르 벨로프스. 일정한 크기의 1-인증서를 갖는 기능을 위한 스팬 프로그램: 확장된 초록. 컴퓨팅 이론에 관한 제12차 연례 ACM 심포지엄 진행 과정, STOC '77, 페이지 84–2012, 10.1145. doi:2213977.2213985/​XNUMX.
https : / /doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca 및 Alain Tapp. 양자 진폭 증폭 및 추정. 양자 계산 및 정보, Contemp 305권. 수학, 53~74페이지. 아메르. 수학. Soc., 프로비던스, RI, 2002. doi:10.1090/​conm/​305/​05215.
https : / /doi.org/10.1090/conm/305/05215

[6] Gilles Brassard, Peter Høyer, Alain Tapp. 양자 계산. Automata, 언어 및 프로그래밍, 페이지 820–831, 1998. doi:10.1007/​BFb0055105.
https : / //doi.org/ 10.1007 / BFb0055105

[7] 알렉산드르 벨로프스(Aleksandrs Belovs)와 벤 W. 레이차드(Ben W. Reichardt). st-connectivity 및 클로 감지를 위한 스팬 프로그램 및 양자 알고리즘. 컴퓨터 과학 강의 노트, 7501 LNCS:193–204, 2012. doi:10.1007/978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] 알렉산드르 벨로프스와 안시스 로스마니스. 양자 상태를 이용한 대략적인 계산을 위한 엄격한 양자 하한. 2020.arXiv:2002.06879.
arXiv : 2002.06879

[9] 살만 베이지(Salman Beigi)와 레일라 타가비(Leila Taghavi). 고전적인 의사 결정 트리를 기반으로 한 양자 속도 향상. 양자, 4:241, 2020. doi:10.22331/q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] 알렉산드르 벨로프스와 듀얄 욜쿠. 라스베가스와 양자 대적에게 가는 편도 티켓입니다. 2023.arXiv:2301.02003.
arXiv : 2301.02003

[11] 리처드. 클리브, 아르투르. 에케르트, 키아라 마키아벨로, 미셸 모스카. 양자 알고리즘이 재검토되었습니다. 런던 왕립학회의 회보. 시리즈 A: 수학, 물리 및 공학 과학, 454(1969):339–354, 1998. doi:10.1098/rspa.1998.0164.
https : / /doi.org/ 10.1098 / rspa.1998.0164

[12] Arjan Cornelissen, Stacey Jeffery, Maris Ozols 및 Alvaro Piedrafita. 범위 프로그램 및 양자 시간 복잡성. 제45회 컴퓨터 과학의 수학적 기초에 관한 국제 심포지엄(MFCS 2020)에서. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https : / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.26

[13] 크리스 케이드, 애슐리 몬타나로, 알렉산드르 벨로브스. 주기를 감지하고 이분성을 테스트하기 위한 시간 및 공간 효율적인 양자 알고리즘입니다. 양자 정보 및 계산, 18(1-2):18–50, 2018.

[14] 카이 드로렌조(Kai DeLorenzo), 셸비 킴멜(Shelby Kimmel), R. 틸 위터(R. Teal Witter). st-Connectivity를 위한 양자 알고리즘의 응용. 양자 컴퓨팅, 통신 및 암호화 이론에 관한 제14차 컨퍼런스(TQC 2019), 페이지 6:1–6:14, 2019. doi:10.4230/LIPIcs.TQC.2019.6.
https : / //doi.org/10.4230/LIPIcs.TQC.2019.6

[15] 드미트리 그린코, 줄리앙 가콘, 크리스타 주팔, 스테판 워너. 반복적 양자 진폭 추정. npj Quantum Information, 7(1):52, 2021년 10.1038월. doi:41534/​s021-00379-1-XNUMX.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] 러브 K. 그로버. 양자 역학은 건초 더미에서 바늘을 찾는 데 도움이 됩니다. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https : / /doi.org/10.1103/ PhysRevLett.79.325

[17] 바실리 회프딩. 유계확률변수의 합에 대한 확률 불평등. 미국 통계 협회 저널, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https : / /doi.org/ 10.1080 / 01621459.1963.10500830

[18] 이토 츠요시와 스테이시 제프리. 대략적인 스팬 프로그램. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] 마이클 자렛, 스테이시 제프리, 셸비 킴멜, 알바로 피에드라피타. 연결성 및 관련 문제에 대한 양자 알고리즘. 제26회 알고리즘에 관한 연례 유럽 심포지엄(ESA 2018), 페이지 49:1–49:13, 2018. doi:10.4230/LIPIcs.ESA.2018.49.
https : / / doi.org/ 10.4230 / LIPIcs.ESA.2018.49

[20] Alexei Y. Kitaev. 양자 측정 및 Abelian Stabilizer 문제. 1995. arXiv:퀀트-ph/9511026.
arXiv : 퀀트 -PH / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek 및 Mario Szegedy. 상태 변환의 양자 쿼리 복잡성. 2011년 컴퓨터 과학 기초에 관한 IEEE 52차 연례 심포지엄, 344~353페이지, 2011. doi:10.1109/FOCS.2011.75.
https : / /doi.org/10.1109/FOCS.2011.75

[22] 프레데릭 마그니에즈(Frédéric Magniez), 애쉬윈 나약(Ashwin Nayak), 제레미 롤랜드(Jérémie Roland), 미클로스 산타(Miklos Santha). Quantum Walk를 통해 검색하세요. SIAM 컴퓨팅 저널, 40(1):142–164, 2011. doi:10.1137/​090745854.
https : / /doi.org/ 10.1137 / 090745854

[23] 애슐리 몬타나로. 조언을 통한 양자 검색. 양자 계산, 통신 및 암호화에 관한 회의, 77~93페이지. 스프링거, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] 벤 W. 레이차트. 범위 프로그램 및 양자 쿼리 복잡성: 모든 부울 함수에 대한 일반적인 적대 경계는 거의 단단합니다. 컴퓨터 과학 기초에 관한 제50회 연례 IEEE 심포지엄, 544~551페이지, 2009. doi:10.1109/FOCS.2009.55.
https : / /doi.org/10.1109/FOCS.2009.55

[25] 벤 W. 레이차트. 양자 쿼리 알고리즘에 대한 반영. 이산 알고리즘에 관한 2011년 연례 ACM-SIAM 심포지엄 진행, 진행, 페이지 560-569. 2011. doi:10.1137/​1.9781611973082.44.
https : / /doi.org/ 10.1137 / 1.9781611973082.44

[26] 레일라 타가비. 오라클 식별 문제에 대한 단순화된 양자 알고리즘입니다. 양자 기계 지능, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

인용

[1] Stacey Jeffery, Shelby Kimmel 및 Alvaro Piedrafita, “경로 가장자리 샘플링을 위한 양자 알고리즘”, arXiv : 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel 및 R. Teal Witter, "강력하고 공간 효율적인 이중 적 양자 쿼리 알고리즘", arXiv : 2306.15040, (2023).

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

On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2024-04-11 15:45:17).

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

타임 스탬프 :

더보기 양자 저널