Täiustatud kvantpäringu keerukus lihtsamatel sisenditel

Taasavaldanud Platon

järgijaid: 0

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

¹Middlebury kolledž, Middlebury, VT, USA
²Williamsi kolledž, Williamstown, MA, USA
³Browni ülikool, Providence, RI, USA

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Funktsioonide hindamise kvantulatusega programmialgoritmid on mõnikord vähendanud päringu keerukust, kui lubatakse, et sisendil on teatud struktuur. Kavandame muudetud ulatusprogrammi algoritmi, et näidata, et need täiustused püsivad isegi ilma lubaduseta enne tähtaega, ja laiendame seda lähenemisviisi olekute teisendamise üldisemale probleemile. Rakendusena tõestame mitme otsinguprobleemi puhul eksponentsiaalseid ja superpolünoomilisi kvanteelisi keskmise päringu keerukuses, üldistades Montanaro otsingu koos nõuannetega [Montanaro, TQC 2010].

Esiletõstetud pilt: ühe meie algoritmi loomiseks kasutatud otsustuspuu.

Populaarne kokkuvõte

Eeldame, et kvantalgoritmid, nagu klassikalised algoritmid, peaksid lihtsamate sisendite korral kiiremini töötama. Näiteks kui otsite üksust järjestamata loendist ja sellest üksusest on palju koopiaid, siis eeldame, et kvantalgoritm peaks selles olukorras töötama kiiremini võrreldes sellega, kui märgitud üksus on ainult üks, isegi teadmata. sihtüksuste arv enne tähtaega. Tõepoolest, otsinguprobleemi jaoks on teada, kuidas saada selline eelis lihtsamate sisendite korral. Selle idee üldistamine probleemidele väljaspool otsingut on aga keeruline, kui pole selget viisi märgistada, kui arvutus on kestnud piisavalt kaua. Muudame päringumudelis mitut populaarset algoritmiraamistikku, et luua lippe, mis hoiatavad meid, kas arvutus on piisavalt kaua kestnud, võimaldades meil lihtsamate sisendite puhul varakult algoritmi lõpetada, teadmata ette, kas eksemplar on lihtne või raske. Rakendusena saame analüüsida keskmist päringu keerukust, võttes arvesse probleemi nii lihtsate kui ka raskete sisendite jaotust. Näitame, et teatud otsinguprobleemide sisendite jaotused annavad suuri keskmisi kvantpäringu eeliseid võrreldes klassikaliste algoritmidega.

► BibTeX-i andmed

@article{Anderson2024improvedquantum, doi = {10.22331/q-2024-04-08-1309}, url = {https://doi.org/10.22331/q-2024-04-08-1309}, title = {Parem {Q}uantum {Q}query {C}keerukus {E}lihtsamatel {I}sisenditel}, autor = {Anderson, Noel T. ja Chung, Jay-U ja Kimmel, Shelby ja Koh, Da-Yeon ja Ye, Xiaohan}, ajakiri = {{Kvant}}, issn = {2521-327X}, väljaandja = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, helitugevus = {8}, lehekülge = {1309}, kuu = aprill, aasta = {2024} }

► Viited

[1] Andris Ambainis ja Ronald de Wolf. Kvantpäringu keskmine keerukus. 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. Kvantarvutus. Annual Reviews of Computational Physics VI, lk 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. Kitsad piirid kvantotsingul. 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. Konstantse suurusega 1-sertifikaatidega funktsioonide ulatusprogrammid: Laiendatud kokkuvõte. Väljaandes Proceedings of the Forty-12th Annual ACM Symposium on Theory of Computing, STOC '77, lk 84–2012, 10.1145. doi:2213977.2213985/XNUMX.
https:///doi.org/10.1145/2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca ja Alain Tapp. Kvantamplituudi võimendamine ja hindamine. Kvantarvutus ja teave, Contemp. köide 305. Math., lk 53–74. Amer. matemaatika. 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. Kvantloendus. Väljaandes Automata, Languages and Programming, lk 820–831, 1998. doi:10.1007/BFb0055105.
https:///doi.org/10.1007/BFb0055105

[7] Aleksandrs Belovs ja Ben W. Reichardt. Võrdlusprogrammid ja kvantalgoritmid st-ühenduvuse ja küüniste tuvastamiseks. 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. Range kvant-alumine piir kvantolekutega ligikaudseks loendamiseks. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi ja Leila Taghavi. Klassikalistel otsustuspuudel põhinev kvantkiirendus. 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. Ühe suuna pilet Las Vegasesse ja kvantvaenlasesse. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello ja Michele Mosca. Vaadati uuesti läbi kvantalgoritmid. Londoni Kuningliku Seltsi toimetised. A-seeria: 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 programmid ja kvantaja keerukus. 45. rahvusvahelisel arvutiteaduse matemaatiliste aluste sümpoosionil (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. Aja- ja ruumitõhusad kvantalgoritmid tsüklite tuvastamiseks ja kaheosalisuse testimiseks. Quantum Information & Computation, 18(1-2):18-50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel ja R. Teal Witter. Kvant-algoritmi rakendused st-ühenduvuse jaoks. 14. kvantarvutuse, kommunikatsiooni ja krüptograafia teooria konverentsil (TQC 2019), lk 6:1–6:14, 2019. doi:10.4230/LIPIcs.TQC.2019.6.
https:///doi.org/10.4230/LIPIcs.TQC.2019.6

[15] Dmitri Grinko, Julien Gacon, Christa Zoufal ja Stefan Woerner. Iteratiivne kvantamplituudi hindamine. npj Quantum Information, 7(1):52, märts 2021. doi: 10.1038/s41534-021-00379-1.
https://doi.org/10.1038/s41534-021-00379-1

[16] Lov K. Grover. Kvantmehaanika aitab heinakuhjast nõela otsida. 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. Piiratud juhuslike suuruste summade tõenäosusvõrratused. 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. Ligikaudsed ulatusprogrammid. 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. Ühenduvuse ja sellega seotud probleemide kvantalgoritmid. 26th Annual European Symposium on Algorithms (ESA 2018), lk 49:1–49:13, 2018. doi:10.4230/LIPIcs.ESA.2018.49.
https:///doi.org/10.4230/LIPIcs.ESA.2018.49

[20] Aleksei Y. Kitajev. Kvantmõõtmised ja Abeli stabilisaatori probleem. 1995. arXiv:quant-ph/9511026.
arXiv:quant-ph/9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek ja Mario Szegedy. Kvantpäringu olekute teisendamise keerukus. Aastal 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, lk 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. Otsige Quantum Walki kaudu. SIAM Journal on Computing, 40(1):142–164, 2011. doi: 10.1137/090745854.
https:///doi.org/10.1137/090745854

[23] Ashley Montanaro. Kvantotsing nõuannetega. Kvantarvutuse, kommunikatsiooni ja krüptograafia konverentsil lk 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. Laiendatud programmid ja kvantpäringu keerukus: üldine vastase piirang on iga tõeväärtusfunktsiooni jaoks peaaegu tihe. 50. iga-aastane IEEE sümpoosion arvutiteaduse aluste kohta, lk 544–551, 2009. doi:10.1109/FOCS.2009.55.
https:///doi.org/10.1109/FOCS.2009.55

[25] Ben W. Reichardt. Peegeldused kvantpäringu algoritmide jaoks. 2011. aasta ACM-SIAM-i iga-aastase diskreetsete algoritmide sümpoosioni toimetistes Proceedings, lk 560–569. 2011. doi: 10.1137/1.9781611973082.44.
https:///doi.org/10.1137/1.9781611973082.44

[26] Leila Taghavi. Oraakli tuvastamise probleemi lihtsustatud kvantalgoritm. Quantum Machine Intelligence, 4(2):19, 2022. doi: 10.1007/s42484-022-00080-2.
https://doi.org/10.1007/s42484-022-00080-2

Viidatud

[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, "Tõhusad ja ruumisäästlikud topeltvastase kvantpäringu algoritmid", arXiv: 2306.15040, (2023).

Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2024-04-10 15:41:33). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.

On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2024-04-10 15:41:32).

See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.

SEO-põhise sisu ja PR-levi. Võimenduge juba täna.
PlatoData.Network Vertikaalne generatiivne Ai. Jõustage ennast. Juurdepääs siia.
PlatoAiStream. Web3 luure. Täiustatud teadmised. Juurdepääs siia.
PlatoESG. Süsinik, CleanTech, Energia, Keskkond päikeseenergia, Jäätmekäitluse. Juurdepääs siia.
PlatoTervis. Biotehnoloogia ja kliiniliste uuringute luureandmed. Juurdepääs siia.
Allikas: https://quantum-journal.org/papers/q-2024-04-08-1309/

Ajatempel: Aprill 8, 2024

Ajatempel: Aprill 30, 2024

Kiraalne ülijuhtivus legeeritud kolmnurkvõrega Fermi-Hubbardi mudelis kahes mõõtmes

Allikaklaster:

Quantum Journal

Allikasõlm: 2179530

Ajatempel: Juuli 20, 2023

Taasavaldanud Platon

Sidusus ja kontekstuaalsus Mach-Zehnderi interferomeetris

Kvantmärgid digitaalallkirjade jaoks

Täiustatud proovi keerukuse alampiir (täpsusega) kvantolekutomograafia jaoks

Kvantoptimaalne juhtimine poolautomaatse diferentseerimise kaudu

Täiustatud lähendusalgoritm kvantmaksimaalse lõikamise jaoks kolmnurgavabadel graafikutel

Skaleeritav ja kiire tehisnärvivõrgu sündroomi dekooder pinnakoodide jaoks

Kvantkoodi lokaalne tõenäosuslik dekodeerimine

Kvantahela silumine ja tundlikkuse analüüs kohalike inversioonide kaudu

Kvantahelate simuleerimine puutensorvõrkude abil

Kvantkanalite lähendamine täiesti positiivsete kaartide abil väikese Krausi auastmega

Kiraalne ülijuhtivus legeeritud kolmnurkvõrega Fermi-Hubbardi mudelis kahes mõõtmes

Meist

Vertikaalne otsing ja Ai

Platvorm

Püsi ühenduses

konto