Generatiivinen tiedustelu

Kvantti

Parannettu kvanttikyselyn monimutkaisuus helpommilla syötteillä

Jälleen julkaissut Platon
Jälleen julkaissut Platon

Treffi:

Luettu: 0

Noel T. Anderson1, Jay-U Chung1, Shelby Kimmel1, Da-Yeon Koh2, ja Xiaohan Ye1,3

1Middlebury College, Middlebury, VT, Yhdysvallat
2Williams College, Williamstown, MA, Yhdysvallat
3Brownin yliopisto, Providence, RI, Yhdysvallat

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Kvanttialueen ohjelman algoritmeilla funktion arvioinnissa on joskus vähemmän kyselyn monimutkaisuutta, kun lupaan, että syötteellä on tietty rakenne. Suunnittelemme muokatun span ohjelma-algoritmin osoittamaan, että nämä parannukset jatkuvat jopa ilman lupausta etukäteen, ja laajennamme tätä lähestymistapaa yleisempään tilanmuunnosongelmaan. Sovelluksena todistamme eksponentiaalisia ja superpolynomisia kvanttietuja keskimääräisessä kyselyn monimutkaisessa useissa hakuongelmissa yleistämällä Montanaron hakua neuvoilla [Montanaro, TQC 2010].

Suositeltu kuva: Päätöspuu, jota käytettiin yhden algoritmimme luomiseen.

Suosittu yhteenveto

Odotamme, että kvanttialgoritmien, kuten klassisten algoritmien, pitäisi toimia nopeammin helpommilla tuloilla. Jos esimerkiksi etsit kohdetta järjestämättömästä luettelosta ja siitä on useita kopioita, oletamme, että kvanttialgoritmin pitäisi toimia nopeammin tässä tilanteessa verrattuna tilanteeseen, jossa on vain yksi merkitty kohde, vaikka sitä tietäisikin. kohdetuotteiden määrä etukäteen. Itse asiassa hakuongelman osalta tiedetään, kuinka saada tällainen etu helpommilla syötteillä. Tämän idean yleistäminen haun ulkopuolisiin ongelmiin on kuitenkin haastavaa, kun ei ole ilmeistä tapaa ilmoittaa, kun laskenta on kestänyt tarpeeksi kauan. Muokkaamme useita suosittuja algoritmikehystä kyselymallissa luodaksemme lippuja, jotka varoittavat, onko laskenta ollut käynnissä tarpeeksi kauan, jolloin voimme lopettaa algoritmin varhaisessa vaiheessa helpommissa syötteissä tietämättä etukäteen, onko ilmentymä helppo vai vaikea. Sovelluksena voimme analysoida kyselyn keskimääräistä monimutkaisuutta, kun otetaan huomioon ongelman helpon ja vaikean syötteen jakautuminen. Osoitamme, että tietyt hakuongelmien syötteiden jakaumat tuottavat suuria keskimääräisiä kvanttikyselyetuja klassisiin algoritmeihin verrattuna.

► BibTeX-tiedot

► Viitteet

[1] Andris Ambainis ja Ronald de Wolf. Tapausten keskimääräinen kvanttikyselyn monimutkaisuus. 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. Kvanttilaskenta. Annual Reviews of Computational Physics VI, sivut 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer ja Alain Tapp. Kvanttihaun tiukat rajat. 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. Span-ohjelmat funktioille, joissa on vakiokokoinen 1-sertifikaatti: Laajennettu abstrakti. Teoksessa Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, sivut 77–84, 2012. doi: 10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / +2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca ja Alain Tapp. Kvanttiamplitudin vahvistus ja estimointi. Teoksessa Quantum computation and information, osa 305 Contemp. Math., sivut 53–74. Amer. Matematiikka. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

[6] Gilles Brassard, Peter Høyer ja Alain Tapp. Kvanttilaskenta. Teoksessa Automata, Languages ​​and Programming, sivut 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs ja Ben W. Reichardt. Span-ohjelmat ja kvanttialgoritmit st-liitettävyyden ja kynsien havaitsemiseen. 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 ja Ansis Rosmanis. Tiukka kvanttialaraja kvanttitilojen likimääräiseen laskemiseen. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi ja Leila Taghavi. Klassisiin päätöspuihin perustuva kvanttinopeus. 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 ja Duyal Yolcu. Yhdensuuntainen lippu las vegasiin ja kvanttivastustajaan. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello ja Michele Mosca. Kvanttialgoritmit tarkasteltiin uudelleen. Proceedings of the Royal Society of London. A-sarja: 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 ja Alvaro Piedrafita. Span-ohjelmat ja kvanttiajan monimutkaisuus. 45. kansainvälisessä symposiumissa tietojenkäsittelytieteen matemaattisista perusteista (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 ja Aleksandrs Belovs. Aika- ja tilatehokkaat kvanttialgoritmit syklien havaitsemiseen ja kaksiosaisuuden testaamiseen. Quantum Information & Computation, 18(1-2):18-50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel ja R. Teal Witter. Kvanttialgoritmin sovellukset st-yhteydelle. 14. konferenssissa kvanttilaskennan, viestinnän ja kryptografian teoriasta (TQC 2019), sivut 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 ja Stefan Woerner. Iteratiivinen kvanttiamplitudin estimointi. npj Quantum Information, 7(1):52, maaliskuu 2021. doi: 10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Lov K. Grover. Kvanttimekaniikka auttaa etsimään neulaa heinäsuovasta. 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. Todennäköisyysepäyhtälöt rajallisten satunnaismuuttujien summille. 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 ja Stacey Jeffery. Likimääräiset jänneohjelmat. 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 ja Alvaro Piedrafita. Kvanttialgoritmit yhteyksille ja niihin liittyville ongelmille. 26th Annual European Symposium on Algorithms (ESA 2018), sivut 49:1–49:13, 2018. doi:10.4230/LIPIcs.ESA.2018.49.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2018.49

[20] Aleksei Y. Kitaev. Kvanttimittaukset ja Abelin stabilisaattoriongelma. 1995. arXiv:quant-ph/​9511026.
arXiv: kvant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek ja Mario Szegedy. Kvanttikyselyn tilan muuntamisen monimutkaisuus. Vuonna 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, sivut 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 ja Miklos Santha. Hae Quantum Walkin kautta. SIAM Journal on Computing, 40(1):142–164, 2011. doi: 10.1137/​090745854.
https: / / doi.org/ 10.1137 / +090745854

[23] Ashley Montanaro. Kvanttihaku neuvoineen. Kvanttilaskentaa, viestintää ja kryptografiaa käsittelevässä konferenssissa, sivut 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. Span-ohjelmat ja kvanttikyselyn monimutkaisuus: Yleinen vastustajaraja on lähes tiukka jokaiselle boolen funktiolle. 50th Annual IEEE Symposium on Foundations of Computer Science, sivut 544–551, 2009. doi: 10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Heijastuksia kvanttikyselyalgoritmeille. Julkaisussa Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, sivut 560–569. 2011. doi: 10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / +1.9781611973082.44

[26] Leila Taghavi. Yksinkertaistettu kvanttialgoritmi oraakkelin tunnistusongelmaan. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Viitattu

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

[2] Michael Czekanski, Shelby Kimmel ja R. Teal Witter, "Järkeät ja avaruustehokkaat kaksoisvastustajien kvanttikyselyalgoritmit", arXiv: 2306.15040, (2023).

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2024-04-08 15:35:29). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

Ei voitu noutaa Crossref siteeratut tiedot viimeisen yrityksen aikana 2024-04-08 15:35:27: Ei voitu noutaa viittauksia 10.22331 / q-2024-04-08-1309 mainittuihin tietoihin Crossrefiltä. Tämä on normaalia, jos DOI rekisteröitiin äskettäin.

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

spot_img

Uusin älykkyys

spot_img

Tekijänoikeus @ 2024 Plato Technologies Inc.