Forbedret kvanteforespørgselskompleksitet på nemmere input

Genudgivet af Platon

Abonnenter: 0

Noel T. Anderson¹, Jay-U Chung¹, Shelby Kimmel¹, Da-Yeon Koh²og Xiaohan Ye^1,3

¹Middlebury College, Middlebury, VT, USA
²Williams College, Williamstown, MA, USA
³Brown University, Providence, RI, USA

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Quantum span programalgoritmer til funktionsevaluering har nogle gange reduceret forespørgselskompleksitet, når de loves, at inputtet har en bestemt struktur. Vi designer en modificeret spændvidde-programalgoritme for at vise, at disse forbedringer fortsætter, selv uden et løfte på forhånd, og vi udvider denne tilgang til det mere generelle problem med statskonvertering. Som en applikation beviser vi eksponentielle og superpolynomielle kvantefordele i gennemsnitlig forespørgselskompleksitet for adskillige søgeproblemer, og generaliserer Montanaros Search with Advice [Montanaro, TQC 2010].

Forbedret kvanteforespørgselskompleksitet på lettere input PlatoBlockchain Data Intelligence. Lodret søgning. Ai.

Udvalgt billede: Beslutningstræ bruges til at oprette en af vores algoritmer.

Populært resumé

Vi forventer, at kvantealgoritmer, ligesom klassiske algoritmer, skal køre hurtigere på lettere input. For eksempel, hvis du søger efter en vare i en uordnet liste, og der er mange kopier af den vare, ville vi forvente, at kvantealgoritmen skulle køre hurtigere i denne situation sammenlignet med, hvis der kun er én markeret vare, selv uden at vide det antallet af målelementer før tid. For problemet med søgning er det faktisk kendt, hvordan man får en sådan fordel ved lettere input. At generalisere denne idé til problemer ud over søgning er imidlertid udfordrende, når der ikke er en oplagt måde at markere, når beregningen har kørt længe nok. Vi modificerer flere populære algoritmiske rammer i forespørgselsmodellen for at skabe flag, der advarer os om, hvorvidt beregningen har kørt længe nok, hvilket giver os mulighed for at afslutte algoritmen tidligt på lettere input uden at vide på forhånd, om instansen er let eller svær. Som en applikation, givet en fordeling af både lette og hårde input til et problem, kan vi analysere den gennemsnitlige forespørgselskompleksitet. Vi viser, at visse distributioner af input til søgeproblemer giver store gennemsnitlige kvanteforespørgselsfordele i forhold til klassiske algoritmer.

► BibTeX-data

@article{Anderson2024improvedquantum, doi = {10.22331/q-2024-04-08-1309}, url = {https://doi.org/10.22331/q-2024-04-08-1309}, title = {Forbedret {Q}uantum {Q} meget {C}kompleksitet på {E}lettere {I}nputs}, forfatter = {Anderson, Noel T. og Chung, Jay-U og Kimmel, Shelby og Koh, Da-Yeon og Ye, Xiaohan}, journal = {{Quantum}}, issn = {2521-327X}, udgiver = {{Verein zur F{“{o}}rderung des Open Access Publizierens in the Quantenwissenschaften}}, volumen = {8}, sider = {1309}, måned = apr, år = {2024} }

► Referencer

[1] Andris Ambainis og Ronald de Wolf. Gennemsnitlig-case kvanteforespørgselskompleksitet. 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] Dorit Aharonov. Kvanteberegning. Annual Reviews of Computational Physics VI, side 259-346, 1999. doi:10.1142/9789812815569_0007.
https:///doi.org/10.1142/9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer og Alain Tapp. Snævre grænser for kvantesøgning. 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 -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

[4] Aleksandrs Belovs. Spænd programmer til funktioner med konstant størrelse 1-certifikater: Udvidet abstrakt. I Proceedings of the Fourty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, side 77-84, 2012. doi:10.1145/2213977.2213985.
https:///doi.org/10.1145/2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca og Alain Tapp. Kvanteamplitudeforstærkning og estimering. I Quantum computation and information, bind 305 af Contemp. Math., side 53-74. Amer. Matematik. Soc., Providence, RI, 2002. doi:10.1090/conm/305/05215.
https:///doi.org/10.1090/conm/305/05215

[6] Gilles Brassard, Peter Høyer og Alain Tapp. Kvantetælling. I Automata, Languages and Programming, side 820–831, 1998. doi:10.1007/BFb0055105.
https://doi.org/10.1007/BFb0055105

[7] Aleksandrs Belovs og Ben W. Reichardt. Span-programmer og kvantealgoritmer til st-forbindelse og klodetektion. Lecture Notes in Computer Science, 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] Aleksandrs Belovs og Ansis Rosmanis. Stram nedre kvantegrænse for omtrentlig optælling med kvantetilstande. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi og Leila Taghavi. Quantum speedup baseret på klassiske beslutningstræer. Quantum, 4:241, 2020. doi:10.22331/q-2020-03-02-241.
https://doi.org/10.22331/q-2020-03-02-241

[10] Aleksandrs Belovs og Duyal Yolcu. Enkeltbillet til las vegas og kvantemodstanderen. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello og Michele Mosca. Kvantealgoritmer revideret. Proceedings fra Royal Society of London. Serie A: Mathematical, Physical and Engineering Sciences, 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 og Alvaro Piedrafita. Span-programmer og kvantetidskompleksitet. I 45th International Symposium on Mathematical Foundations of Computer Science (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] Chris Cade, Ashley Montanaro og Aleksandrs Belovs. Tids- og rumeffektive kvantealgoritmer til detektering af cyklusser og test af todelthed. Quantum Information & Computation, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel og R. Teal Witter. Anvendelser af kvantealgoritmen for st-forbindelse. I 14. konference om teorien om kvanteberegning, kommunikation og kryptografi (TQC 2019), side 6:1–6:14, 2019. doi:10.4230/LIPIcs.TQC.2019.6.
https:///doi.org/10.4230/LIPIcs.TQC.2019.6

[15] Dmitry Grinko, Julien Gacon, Christa Zoufal og Stefan Woerner. Iterativ kvanteamplitudeestimering. npj Quantum Information, 7(1):52, Mar 2021. doi:10.1038/s41534-021-00379-1.
https://doi.org/10.1038/s41534-021-00379-1

[16] Kærlighed K. Grover. Kvantemekanik hjælper med at søge efter en nål i en høstak. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/PhysRevLett.79.325.
https:///doi.org/10.1103/PhysRevLett.79.325

[17] Wassily Hoeffding. Sandsynlighedsuligheder for summer af afgrænsede stokastiske variable. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.
https:///doi.org/10.1080/01621459.1963.10500830

[18] Tsuyoshi Ito og Stacey Jeffery. Omtrentlig spændvidde programmer. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/s00453-018-0527-1.
https://doi.org/10.1007/s00453-018-0527-1

[19] Michael Jarret, Stacey Jeffery, Shelby Kimmel og Alvaro Piedrafita. Kvantealgoritmer til forbindelse og relaterede problemer. I 26th Annual European Symposium on Algorithms (ESA 2018), side 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. Kvantemålinger og Abelian Stabilizer Problem. 1995. arXiv:quant-ph/9511026.
arXiv:quant-ph/9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek og Mario Szegedy. Kvanteforespørgselskompleksitet af statskonvertering. I 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, side 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 og Miklos Santha. Søg via Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/090745854.
https:///doi.org/10.1137/090745854

[23] Ashley Montanaro. Kvantesøgning med råd. I Konference om kvanteberegning, kommunikation og kryptografi, side 77-93. Springer, 2010. doi:10.1007/978-3-642-18073-6_7.
https://doi.org/10.1007/978-3-642-18073-6_7

[24] Ben W. Reichardt. Spændende programmer og kvanteforespørgselskompleksitet: Den generelle modstandsgrænse er næsten stram for hver boolesk funktion. 50th Annual IEEE Symposium on Foundations of Computer Science, side 544–551, 2009. doi:10.1109/FOCS.2009.55.
https:///doi.org/10.1109/FOCS.2009.55

[25] Ben W. Reichardt. Refleksioner for kvanteforespørgselsalgoritmer. I Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, side 560-569. 2011. doi:10.1137/1.9781611973082.44.
https:///doi.org/10.1137/1.9781611973082.44

[26] Leila Taghavi. Forenklet kvantealgoritme til orakelidentifikationsproblemet. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/s42484-022-00080-2.
https://doi.org/10.1007/s42484-022-00080-2

Citeret af

[1] Stacey Jeffery, Shelby Kimmel og Alvaro Piedrafita, "Quantum Algorithm for Path-Edge Sampling", arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel og R. Teal Witter, "Robust and Space-Efficient Dual Adversary Quantum Query Algorithms", arXiv: 2306.15040, (2023).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-04-11 15:45:18). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-04-11 15:45:17).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

SEO Powered Content & PR Distribution. Bliv forstærket i dag.
PlatoData.Network Vertical Generative Ai. Styrk dig selv. Adgang her.
PlatoAiStream. Web3 intelligens. Viden forstærket. Adgang her.
PlatoESG. Kulstof, CleanTech, Energi, Miljø, Solenergi, Affaldshåndtering. Adgang her.
PlatoHealth. Bioteknologiske og kliniske forsøgs intelligens. Adgang her.
Kilde: https://quantum-journal.org/papers/q-2024-04-08-1309/

Tidsstempel: April 8, 2024

Tidsstempel: Mar 30, 2023

Genudgivet af Platon

Parallel kvantealgoritme til Hamilton-simulering

Motorer til forudsigelig arbejdsudvinding fra hukommelsesfulde kvante stokastiske processer

Ingen signalering begrænser kvanteberegning med ubestemt kausal struktur

Ortonormale baser for ekstrem kvantetilstand

Sammensat sikker enhedsuafhængig kryptering med certificeret sletning

Opnåelse af kvantefeltteoriens grænse i langt fra ligevægt kvantelinkmodeller

Gennemsnitlig feltstudie af 2D kvasipartikelkondensatdannelse ved tilstedeværelse af stærkt henfald

Komplet udvidelse: den ikke-signalerende analog af kvanteoprensning

Kvantenøglefordelingsrater fra semidefinite programmering

Praktisk tilfældighedsforstærkning og privatisering med implementeringer på kvantecomputere

Om os

Vertikal søgning & Ai

perron

Stay Connected

Konto