Limitations Of The Macaulay Matrix Approach For Using The HHL Algorithm To Solve Multivariate Polynomial Systems

Újra kiadta Platón

Követő: 0

Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Jintai Ding¹, Vlad Gheorghiu², Gilyén András³, Sean Hallgren⁴és Jianqiang Li⁴

¹Cincinnati Egyetem, OH, USA
²Institute for Quantum Computing / Kombinatorika és Optimalizálás Tanszék, Waterloo Egyetem, ON, Kanada
³Institute for Quantum Information and Matter, Caltech, Pasadena CA, USA
⁴Számítástechnikai és Mérnöki Tanszék, Pennsylvania Állami Egyetem, PA, USA

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

Nemrég Chen és Gao [15] új kvantum-algoritmust javasolt a Boole-féle polinomiális rendszerek megoldására, amelyet néhány posztkvantum kriptorendszer kriptoanalízise motivált. Megközelítésük alapötlete az, hogy egy Quantum Linear System (QLS) algoritmust alkalmazzanak egy Macaulay lineáris rendszerre $mathbb{C}$ felett, amely a Boole-féle polinomrendszerből származik. Algoritmusuk hatékonysága a Macaulay-mátrix feltételszámától függ. Ebben a cikkben egy erős alsó korlátot adunk meg a feltételszámnak a Boole-féle megoldás Hamming-súlyának függvényében, és megmutatjuk, hogy sok (ha nem minden) esetben egy Grover-alapú kimerítő keresési algoritmus jobban teljesít, mint az algoritmusa. Ezután javítjuk Chen és Gao algoritmusát a Boole-féle Macaulay lineáris rendszer bevezetésével $mathbb{C}$ helyett az eredeti Macaulay lineáris rendszer csökkentésével. Ez a továbbfejlesztett algoritmus potenciálisan jelentősen felülmúlhatja a brute-force algoritmust, ha a megoldás Hamming-súlya logaritmikus a Boole-változók számában.
Továbbá egyszerű és elemibb bizonyítékot adunk továbbfejlesztett algoritmusunk helyességére a Valiant-Vazirani affin kivonatolási módszert alkalmazó redukcióval, valamint kiterjesztjük az eredményt a $mathbb{F}_q$ feletti polinomiális rendszerekre, javítva Chen későbbi munkáját. , Gao és Yuan idézi ChenGao2018. Javasolunk egy új megközelítést a Boole-féle polinomiális rendszer megoldásának kinyerésére a kvantumszelvény-gyűjtő probléma általánosításán keresztül.2].

[Beágyazott tartalmat]

► BibTeX adatok

@cikk{Ding2023limitationsof, doi = {10.22331/q-2023-07-26-1069}, url = {https://doi.org/10.22331/q-2023-07-26-1069}, title = {A korlátozások az {M}acaulay mátrix megközelítés a {HHL} algoritmus használatához többváltozós polinomrendszerek megoldására}, szerző = {Ding, Jintai és Gheorghiu, Vlad és Gily{'{e}}n, Andr{'{a}} és Hallgren, Sean és Li, Jianqiang}, folyóirat = {{Quantum}}, issn = {2521-327X}, kiadó = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, kötet = {7}, oldalak = {1069}, hónap = júl, év = {2023} }

► Referenciák

[1] Scott Aaronson. Olvassa el az apró betűs részt. Természetfizika 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 és Ronald de Wolf. Kvantum kupongyűjtő. In Proceedings of the 15. Conference on the Theory of Quantum Computation, Communication és Cryptography (TQC) TQC, 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 és Makoto Sugita. XL és Gröbner bázisalgoritmusok összehasonlítása. In International Conference on the Theory and Application of Cryptology and Information Security, 338–353. oldal. Springer, 2004.
https://doi.org/10.1007/978-3-540-30539-2_24

[4] Andris Ambainis. Változó idő amplitúdójú erősítés és kvantum algoritmusok lineáris algebrai problémákhoz. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS) STACS, 636–647. oldal, 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 és Yudong Cao. Variációs kvantumfaktoring. arXiv: 1808.08927, 2018.
https://doi.org/10.1007/978-3-030-14082-3_7
arXiv: 1808.08927

[6] Bruno Buchberger et al. Gröbner a számítást Macaulay-mátrixok háromszögesítésével alapozza meg. In A Gröbner-bázisok 50. évfordulója, 25–33. Japán Matematikai Társaság, 2018.
https:///doi.org/10.2969/aspm/07710025

[7] Kim Batselier. Numerikus lineáris algebrai keretrendszer többváltozós polinomokkal kapcsolatos problémák megoldására. PhD értekezés, KU Leuven (Leuven, Belgium), 2013.
https:///doi.org/10.13140/RG.2.1.3137.9608

[8] Michel Boyer, Gilles Brassard, Peter Høyer és Alain Tapp. Szoros korlátok a kvantumkeresésben. 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:quant-ph/9605034

[9] Magali Bardet, Jean-Charles Faugère, Bruno Salvy és Pierre-Jean Spaenlehauer. A másodfokú logikai rendszerek megoldásának bonyolultságáról. Journal of Complexity, 29(1):53–75, 2013.
https:///doi.org/10.1016/j.jco.2012.07.001

[10] Andreas Björklund, Petteri Kaski és Ryan Williams. Polinomiális egyenletrendszerek megoldása GF(2) felett paritásszámláló önredukálással. In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP) ICALP, 2019.
https:///doi.org/10.4230/LIPIcs.ICALP.2019.26

[11] Christopher JC Burges. A faktorálás mint optimalizálás. Microsoft Research MSR-TR-200, 2002.

[12] Ethan Bernstein és Umesh Vazirani. Kvantumkomplexitás elmélet. SIAM Journal on computing, 26(5):1411–1473, 1997.
https:///doi.org/10.1137/S0097539796300921

[13] Daniel J Bernstein és Bo-Yin Yang. Aszimptotikusan gyorsabb kvantumalgoritmusok többváltozós másodfokú egyenletek megoldására. In International Conference on Post-Quantum Cryptography, 487–506. oldal. Springer, 2018.
https://doi.org/10.1007/978-3-319-79063-3_23

[14] Alessio Caminata és Elisa Gorla. Többváltozós polinomrendszerek és invariáns megoldása kommutatív algebrából. arXiv: 1706.06319, 2017.
https://doi.org/10.1007/978-3-030-68869-1_1
arXiv: 1706.06319

[15] Yu-Ao Chen és Xiao-Shan Gao. Kvantum algoritmus Boole-egyenletek megoldásához és kriptorendszerek elleni kvantum-algebrai támadásokhoz. 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, and Stacey Jeffery. A blokkkódolt mátrixhatványok ereje: Továbbfejlesztett regressziós technikák gyorsabb Hamilton-szimulációval. In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP) ICALP, 33:1–33:14, 2019. arXiv: 1804.01973.
https:///doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv: 1804.01973

[17] Nai-Hui Chia, Gilyén András, Tongyang Li, Han-Hsuan Lin, Ewin Tang és Chunhao Wang. Mintavételen alapuló szublineáris alacsony rangú mátrix aritmetikai keretrendszer a kvantumgépi tanulás dekvantálásához. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC) STOC, 387–400. oldal, 2020. arXiv: 1910.06151.
https:///doi.org/10.1145/3357713.3384314
arXiv: 1910.06151

[18] Yu-Ao Chen, Xiao-Shan Gao és Chun-Ming Yuan. Kvantumalgoritmus optimalizáláshoz és polinomrendszerek megoldásához véges mezőn és kriptoanalízisben való alkalmazáshoz, 2018. arXiv: 1802.03856.
arXiv: 1802.03856

[19] B David Clader, Bryan C Jacobs és Chad R Sprouse. Előfeltételezett kvantumlineáris rendszer algoritmus. Fizikai felülvizsgálati levelek, 110(25):250504, 2013.
https:///doi.org/10.1103/PhysRevLett.110.250504

[20] Nicolas Courtois, Alexander Klimov, Jacques Patarin és Adi Shamir. Hatékony algoritmusok túldefiniált többváltozós polinomiális egyenletrendszerek megoldására. A kriptográfiai technikák elméletével és alkalmazásaival foglalkozó nemzetközi konferencia 392–407. oldalain. Springer, 2000 (24. augusztus 2004-i kiterjesztett verzió. 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 és Rolando D. Somma. Kvantumalgoritmus lineáris egyenletrendszerekhez, exponenciálisan javított pontosságfüggőséggel. 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. Az XL-algoritmus és a kommutatív algebrából származó sejtés. In International Conference on the Theory and Application of Cryptology and Information Security, 323–337. oldal. Springer, 2004.
https://doi.org/10.1007/978-3-540-30539-2_23

[23] Jintai Ding és Dieter Schmidt. Fokozat és szabályossági fok megoldása polinomiális rendszerekre véges mezők felett. In Számelmélet és kriptográfia, 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 és Ludovic Perret. Gyors kvantum algoritmus többváltozós másodfokú egyenletek megoldására. arXiv: 1712.07211, 2017.
arXiv: 1712.07211

[25] Gilyén András, Yuan Su, Guang Hao Low és Nathan Wiebe. Kvantum szinguláris érték transzformáció és azon túl: Exponenciális fejlesztések a kvantummátrix aritmetikához [teljes verzió], 2018. arXiv: 1806.01838.
arXiv: 1806.01838

[26] Gilyén András, Yuan Su, Guang Hao Low és Nathan Wiebe. Kvantum szinguláris érték transzformáció és azon túl: Exponenciális fejlesztések a kvantummátrix aritmetikában. In Proceedings of the 51. ACM Symposium on the Theory of Computing (STOC) STOC, 193–204. oldal, 2019. arXiv: 1806.01838.
https:///doi.org/10.1145/3313276.3316366
arXiv: 1806.01838

[27] Aram W. Harrow, Avinatan Hassidim és Seth Lloyd. Kvantumalgoritmus lineáris egyenletrendszerekhez. 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] Stasys Jukna. Extremális kombinatorika – Alkalmazásokkal a számítástechnikában (2. kiadás). Szövegek az elméleti számítástechnikában. Springer, 2011.
https://doi.org/10.1007/978-3-642-17364-6

[29] Iordanis Kerenidis és Anupam Prakash. Kvantum ajánló rendszerek. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS) ITCS, 49:1–49:21, 2017. arXiv: 1603.08675.
https:///doi.org/10.4230/LIPIcs.ITCS.2017.49
arXiv: 1603.08675

[30] Lin Lin és Yu Tong. Optimális polinom alapú kvantum-sajátállapot-szűrés kvantumlineáris rendszerek megoldására. 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 és Cryptographie Post-Quantique. PhD értekezés, UPMC-Paris 6 Sorbonne Universités, 2016.

[32] Herbert Robbins. Egy megjegyzés Stirling képletéhez. The American Mathematical Monthly, 62(1):26–29, 1955.
https:///doi.org/10.2307/2308012

[33] A Mathematica forráskódja a Woflram Notebook Archívumban is elérhető: https:///notebookarchive.org/2022-02-1ec5yyv, 2022.
https:///notebookarchive.org/2022-02-1ec5yyv

[34] Yiğit Subaşı, Rolando D. Somma és Davide Orsucci. Kvantumalgoritmusok lineáris egyenletrendszerekhez, amelyeket az adiabatikus kvantumszámítás ihletett. 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 és Hua Xiang. Kvantumcirkulációs előfeltétele lineáris egyenletrendszerhez. Fizikai Szemle A, 98(6):062321, 2018.
https:///doi.org/10.1103/PhysRevA.98.062321

[36] Yu Tong, Dong An, Nathan Wiebe és Lin Lin. Gyors inverzió, előre kondicionált kvantumlineáris rendszermegoldók és mátrixfüggvények gyors kiértékelése. arXiv: 2008.13295, 2020.
https:///doi.org/10.1103/PhysRevA.104.032422
arXiv: 2008.13295

[37] Leslie G. Valiant és Vijay V. Vazirani. Az NP olyan egyszerű, mint egyedi megoldások észlelése. Elméleti számítástechnika elmélet. Comput. Sci., 47:85–93, 1986. Korábbi változat: STOC'85.
https://doi.org/10.1016/0304-3975(86)90135-0

[38] Ronald de Wolf. Kvantumszámítás: Előadási jegyzetek, 2019. arXiv: 1907.09415.
arXiv: 1907.09415

[39] Manuela Wiesinger-Widi. Gröbner-bázisok és általánosított szilvesztermátrixok. PhD értekezés, Johannes Kepler Egyetem Linz, Ausztria, 2015.
https:///doi.org/10.1145/2016567.2016594

Idézi

Nem sikerült lekérni Az adatok által hivatkozott kereszthivatkozás utolsó próbálkozáskor 2023-07-26 10:46:19: Nem sikerült lekérni a 10.22331/q-2023-07-26-1069 hivatkozás által hivatkozott adatokat a Crossref-től. Ez normális, ha a DOI-t nemrég regisztrálták. Tovább SAO/NASA HIRDETÉSEK művekre hivatkozó adat nem található (utolsó próbálkozás 2023-07-26 10:46:19).

Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.

SEO által támogatott tartalom és PR terjesztés. Erősödjön még ma.
PlatoData.Network Vertical Generative Ai. Erősítse meg magát. Hozzáférés itt.
PlatoAiStream. Web3 Intelligence. Felerősített tudás. Hozzáférés itt.
PlatoESG. Autóipar / elektromos járművek, Carbon, CleanTech, Energia, Környezet, Nap, Hulladékgazdálkodás. Hozzáférés itt.
BlockOffsets. A környezetvédelmi ellentételezési tulajdon korszerűsítése. Hozzáférés itt.
Forrás: https://quantum-journal.org/papers/q-2023-07-26-1069/

Időbélyeg: Július 26, 2023

Időbélyeg: 8. november 2023.

A Macaulay-mátrix megközelítés korlátai a HHL algoritmus használatához többváltozós polinomrendszerek megoldására

Újra kiadta Platón

Absztrakt

► BibTeX adatok

► Referenciák

Idézi

Még több Quantum Journal

A kvantummérés minimális idejének behatárolása

Variációs kvantum algoritmusok jellemzése szabad fermionok segítségével

Kétegységes dekompozíciós algoritmus és nyílt kvantumrendszer szimuláció

Kísérleti kommunikáció kvantumcsatornák szuperpozíciójával

A mozgás és sugárzás kvantum-rabi interferometriája

Kvantum aláírások nemlineáris gravitációs hullámokban

Összefonódás tisztítása kvantum LDPC kódokkal és iteratív dekódolással

Stabilizátor formalizmus operátori algebra kvantum hibajavításhoz

Hamilton-kvantumok alapállapotainak megtanulása kernel módszerekkel

Shuttling szekvenciák automatizált generálása lineáris szegmentált ioncsapda kvantumszámítógéphez

Rólunk

Vertical Search & Ai

Emelvény

Maradjon kapcsolatban

Fiók