Omejitve pristopa Macaulayeve matrike za uporabo algoritma HHL za reševanje multivariatnih polinomskih sistemov

Omejitve pristopa Macaulayeve matrike za uporabo algoritma HHL za reševanje multivariatnih polinomskih sistemov

Časovni žig: 26. julij 2023 6
Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Jintai Ding1Vlad Gheorghiu2, András Gilyén3, Sean Hallgren4in Jianqiang Li4

1Univerza v Cincinnatiju, OH, ZDA
2Inštitut za kvantno računalništvo / Oddelek za kombinatoriko in optimizacijo, Univerza Waterloo, ON, Kanada
3Inštitut za kvantne informacije in snov, Caltech, Pasadena, CA, ZDA
4Oddelek za računalništvo in tehniko, Pennsylvania State University, PA, ZDA

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Nedavno Chen in Gao [15] je predlagal nov kvantni algoritem za reševanje Boolovega polinomskega sistema, ki ga je motivirala kriptoanaliza nekaterih postkvantnih kriptosistemov. Ključna ideja njihovega pristopa je uporaba algoritma kvantnega linearnega sistema (QLS) za Macaulayev linearni sistem nad $mathbb{C}$, ki je izpeljan iz Boolovega polinomskega sistema. Učinkovitost njihovega algoritma je odvisna od števila pogojev Macaulayeve matrike. V tem prispevku podajamo močno spodnjo mejo števila pogoja kot funkcije Hammingove uteži logične rešitve in pokažemo, da v mnogih (če ne v vseh) primerih algoritem izčrpnega iskanja, ki temelji na Groverju, prekaša njihov algoritem. Nato izboljšamo algoritem Chena in Gaa z uvedbo Boolovega Macaulayevega linearnega sistema nad $mathbb{C}$ z redukcijo prvotnega Macaulayevega linearnega sistema. Ta izboljšani algoritem bi lahko potencialno znatno presegel algoritem surove sile, ko je Hammingova utež rešitve logaritemska glede na število logičnih spremenljivk.
Poleg tega nudimo preprost in bolj elementaren dokaz pravilnosti za naš izboljšani algoritem z uporabo redukcije z uporabo metode afinega zgoščevanja Valiant-Vazirani, rezultat pa tudi razširimo na polinomske sisteme nad $mathbb{F}_q$, s čimer izboljšamo poznejše delo Chena , Gao in Yuan navajata ChenGao2018. Predlagamo tudi nov pristop za ekstrakcijo rešitve Boolovega polinomskega sistema s posplošitvijo problema kvantnega zbiralnika kuponov [2].

[Vgrajeni vsebina]

► BibTeX podatki

► Reference

[1] Scott Aaronson. Preberite drobni tisk. Fizika narave Nat. Phys. , 11(4):291–293, 2015.
https: / / doi.org/ 10.1038 / nphys3272

[2] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis in Ronald de Wolf. Zbiralec kuponov Quantum. V zborniku 15. konference o teoriji kvantnega računalništva, komunikacije in kriptografije (TQC) TQC, strani 10:1–10:17, 2020. arXiv: 2002.07688.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
arXiv: 2002.07688

[3] Gwénolé Ars, Jean-Charles Faugere, Hideki Imai, Mitsuru Kawazoe in Makoto Sugita. Primerjava med XL in Gröbnerjevimi algoritmi. Na mednarodni konferenci o teoriji in uporabi kriptologije in informacijske varnosti, strani 338–353. Springer, 2004.
https:/​/​doi.org/​10.1007/​978-3-540-30539-2_24

[4] Andris Ambainis. Ojačitev variabilne časovne amplitude in kvantni algoritmi za probleme linearne algebre. V zborniku 29. simpozija o teoretičnih vidikih računalništva (STACS) STACS, strani 636–647, 2012. arXiv: 1010.4458.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
arXiv: 1010.4458

[5] Eric R Anschuetz, Jonathan P Olson, Alán Aspuru-Guzik in Yudong Cao. Variacijsko kvantno faktoring. arXiv: 1808.08927, 2018.
https:/​/​doi.org/​10.1007/​978-3-030-14082-3_7
arXiv: 1808.08927

[6] Bruno Buchberger idr. Gröbner računanje temelji na trikotništvu Macaulayevih matrik. V 50. obletnici baz Gröbner, strani 25–33. Mathematical Society of Japan, 2018.
https://​/​doi.org/​10.2969/​aspm/​07710025

[7] Kim Batselier. Ogrodje numerične linearne algebre za reševanje problemov z multivariatnimi polinomi. Doktorska disertacija, KU Leuven (Leuven, Belgija), 2013.
https://​/​doi.org/​10.13140/​RG.2.1.3137.9608

[8] Michel Boyer, Gilles Brassard, Peter Høyer in Alain Tapp. Ozke meje kvantnega iskanja. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/9605034.
<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
arXiv: kvant-ph / 9605034

[9] Magali Bardet, Jean-Charles Faugère, Bruno Salvy in Pierre-Jean Spaenlehauer. O kompleksnosti reševanja kvadratnih logičnih sistemov. Journal of Complexity, 29(1):53–75, 2013.
https://​/​doi.org/​10.1016/​j.jco.2012.07.001

[10] Andreas Björklund, Petteri Kaski in Ryan Williams. Reševanje sistemov polinomskih enačb nad GF(2) s samoreduciranjem s paritetnim štetjem. V zborniku 46. mednarodnega kolokvija o avtomatih, jezikih in programiranju (ICALP) ICALP, 2019.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.26

[11] Christopher JC Burges. Faktoring kot optimizacija. Microsoft Research MSR-TR-200, 2002.

[12] Ethan Bernstein in Umesh Vazirani. Teorija kvantne kompleksnosti. SIAM Journal on computing, 26(5):1411–1473, 1997.
https: / / doi.org/ 10.1137 / S0097539796300921

[13] Daniel J Bernstein in Bo-Yin Yang. Asimptotično hitrejši kvantni algoritmi za reševanje multivariantnih kvadratnih enačb. Na mednarodni konferenci o postkvantni kriptografiji, strani 487–506. Springer, 2018.
https:/​/​doi.org/​10.1007/​978-3-319-79063-3_23

[14] Alessio Caminata in Elisa Gorla. Reševanje multivariantnih polinomskih sistemov in invariant iz komutativne algebre. arXiv: 1706.06319, 2017.
https:/​/​doi.org/​10.1007/​978-3-030-68869-1_1
arXiv: 1706.06319

[15] Yu-Ao Chen in Xiao-Shan Gao. Kvantni algoritem za reševanje logičnih enačb in kvantni algebraični napad na kriptosisteme. Journal of Systems Science and Complexity, 2021. arXiv: 1712.06239.
https:/​/​doi.org/​10.1007/​s11424-020-0028-6
arXiv: 1712.06239

[16] Shantanav Chakraborty, András Gilyén in Stacey Jeffery. Moč blokovno kodiranih matričnih moči: izboljšane regresijske tehnike prek hitrejše Hamiltonove simulacije. V zborniku 46. mednarodnega kolokvija o avtomatih, jezikih in programiranju (ICALP) ICALP, strani 33:1–33:14, 2019. arXiv: 1804.01973.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33
arXiv: 1804.01973

[17] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang in Chunhao Wang. Sublinearni matrični aritmetični okvir nizkega ranga na osnovi vzorčenja za dekvantizacijo kvantnega strojnega učenja. V zborniku 52. simpozija ACM o teoriji računalništva (STOC) STOC, stran 387–400, 2020. arXiv: 1910.06151.
https: / / doi.org/ 10.1145 / 3357713.3384314
arXiv: 1910.06151

[18] Yu-Ao Chen, Xiao-Shan Gao in Chun-Ming Yuan. Kvantni algoritem za optimizacijo in reševanje polinomskega sistema nad končnim poljem in uporaba v kriptoanalizi, 2018. arXiv: 1802.03856.
arXiv: 1802.03856

[19] B David Clader, Bryan C Jacobs in Chad R Sprouse. Algoritem predkondicioniranega kvantnega linearnega sistema. Pisma fizičnega pregleda, 110 (25): 250504, 2013.
https: / / doi.org/ 10.1103 / PhysRevLett.110.250504

[20] Nicolas Courtois, Alexander Klimov, Jacques Patarin in Adi Shamir. Učinkoviti algoritmi za reševanje preddefiniranih sistemov multivariantnih polinomskih enačb. Na mednarodni konferenci o teoriji in aplikacijah kriptografskih tehnik, strani 392–407. Springer, 2000 (Razširjena različica od 24. avgusta 2004. http://​/​www.minrank.org/​xlfull.pdf).
https:/​/​doi.org/​10.1007/​3-540-45539-6_27
http://​/​www.minrank.org/​xlfull.pdf)

[21] Andrew M. Childs, Robin Kothari in Rolando D. Somma. Kvantni algoritem za sisteme linearnih enačb z eksponentno izboljšano odvisnostjo od natančnosti. SIAM Journal on Computing SIAM J. Comp., 46(6):1920–1950, 2017. arXiv: 1511.02306.
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306

[22] Claus Diem. XL-algoritem in domneva iz komutativne algebre. Na mednarodni konferenci o teoriji in uporabi kriptologije in informacijske varnosti, strani 323–337. Springer, 2004.
https:/​/​doi.org/​10.1007/​978-3-540-30539-2_23

[23] Jintai Ding in Dieter Schmidt. Rešitev stopnje in stopnje regularnosti za polinomske sisteme nad končnimi polji. V Teoriji števil in kriptografiji, strani 34–49. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-42001-6_4

[24] Jean-Charles Faugere, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi in Ludovic Perret. Hiter kvantni algoritem za reševanje multivariantnih kvadratnih enačb. arXiv: 1712.07211, 2017.
arXiv: 1712.07211

[25] András Gilyén, Yuan Su, Guang Hao Low in Nathan Wiebe. Kvantna singularna transformacija vrednosti in več: Eksponentne izboljšave za aritmetiko kvantne matrike [polna različica], 2018. arXiv: 1806.01838.
arXiv: 1806.01838

[26] András Gilyén, Yuan Su, Guang Hao Low in Nathan Wiebe. Kvantna transformacija singularne vrednosti in več: Eksponentne izboljšave za kvantno matrično aritmetiko. V zborniku 51. simpozija ACM o teoriji računalništva (STOC) STOC, strani 193–204, 2019. arXiv: 1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838

[27] Aram W. Harrow, Avinatan Hassidim in Seth Lloyd. Kvantni algoritem za linearne sisteme enačb. Physical Review Letters Phys. Rev. Lett., 103(15):150502, 2009. arXiv: 0811.3171.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171

[28] Stasis Jukna. Ekstremna kombinatorika – z aplikacijami v računalništvu (2. izdaja). Besedila iz teoretičnega računalništva. Springer, 2011.
https:/​/​doi.org/​10.1007/​978-3-642-17364-6

[29] Iordanis Kerenidis in Anupam Prakash. Kvantni priporočilni sistemi. V zborniku 8. konference o inovacijah v teoretični računalniški znanosti (ITCS) ITCS, strani 49:1–49:21, 2017. arXiv: 1603.08675.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv: 1603.08675

[30] Lin Lin in Yu Tong. Optimalno filtriranje kvantnih lastnih stanj na osnovi polinoma z uporabo pri reševanju kvantnih linearnih sistemov. Quantum Quant., 4:361, 2020. arXiv: 1910.14596.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361
arXiv: 1910.14596

[31] Ludovic Perret. Bases de Gröbner en Cryptographie Post-Quantique. Doktorska disertacija, UPMC-Paris 6 Sorbonne Universités, 2016.

[32] Herbert Robbins. Opomba k Stirlingovi formuli. Ameriški matematični mesečnik, 62(1):26–29, 1955.
https: / / doi.org/ 10.2307 / 2308012

[33] Izvorna koda Mathematica je na voljo tudi v Woflram Notebook Archive: https://​/​notebookarchive.org/​2022-02-1ec5yyv, 2022.
https://​/​notebookarchive.org/​2022-02-1ec5yyv

[34] Yiğit Subaşı, Rolando D. Somma in Davide Orsucci. Kvantni algoritmi za sisteme linearnih enačb po navdihu adiabatnega kvantnega računalništva. Physical Review Letters Phys. Rev. Lett., 122(6):060504, 2019. arXiv: 1805.10549.
https: / / doi.org/ 10.1103 / PhysRevLett.122.060504
arXiv: 1805.10549

[35] Changpeng Shao in Hua Xiang. Kvantni cirkulantni predkondicioner za linearni sistem enačb. Physical Review A, 98(6):062321, 2018.
https: / / doi.org/ 10.1103 / PhysRevA.98.062321

[36] Yu Tong, Dong An, Nathan Wiebe in Lin Lin. Hitra inverzija, predkondicionirani reševalci kvantnih linearnih sistemov in hitro vrednotenje matričnih funkcij. arXiv: 2008.13295, 2020.
https: / / doi.org/ 10.1103 / PhysRevA.104.032422
arXiv: 2008.13295

[37] Leslie G. Valiant in Vijay V. Vazirani. NP je tako enostaven kot odkrivanje edinstvenih rešitev. Theoretical Computer Science Theor. Računalništvo. Sci., 47:85–93, 1986. Prejšnja različica v STOC'85.
https:/​/​doi.org/​10.1016/​0304-3975(86)90135-0

[38] Ronald de Wolf. Kvantno računalništvo: zapiski predavanj, 2019. arXiv: 1907.09415.
arXiv: 1907.09415

[39] Manuela Wiesinger-Widi. Gröbnerjeve baze in posplošene silvestrove matrike. Doktorska disertacija, Univerza Johannes Kepler Linz, Avstrija, 2015.
https: / / doi.org/ 10.1145 / 2016567.2016594

Navedel

Pridobitve ni bilo mogoče Crossref citirani podatki med zadnjim poskusom 2023-07-26 10:46:19: ni bilo mogoče pridobiti navajanih podatkov za 10.22331 / q-2023-07-26-1069 od podjetja Crossref. To je normalno, če je bil DOI registriran pred kratkim. Na SAO / NASA ADS ni bilo najdenih podatkov o navajanju del (zadnji poskus 2023-07-26 10:46:19).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal