Limitazioni dell'approccio matriciale di Macaulay per l'utilizzo dell'algoritmo HHL per risolvere sistemi polinomiali multivariati

Limitazioni dell'approccio matriciale di Macaulay per l'utilizzo dell'algoritmo HHL per risolvere sistemi polinomiali multivariati

Timestamp: 26 luglio 2023 6:40
Limitazioni dell'approccio della matrice Macaulay per l'utilizzo dell'algoritmo HHL per risolvere sistemi polinomiali multivariati PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Jintai Ding1, Vlad Gheorghiu2, Andras Gilyén3, Sean Hallgren4e Jian Qiang Li4

1Università di Cincinnati, Ohio, USA
2Institute for Quantum Computing / Dipartimento di Combinatoria e Ottimizzazione, Università di Waterloo, ON, Canada
3Istituto per l'informazione quantistica e la materia, Caltech, Pasadena CA, USA
4Dipartimento di Informatica e Ingegneria, Pennsylvania State University, PA, USA

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Recentemente Chen e Gao [15] hanno proposto un nuovo algoritmo quantistico per la risoluzione di sistemi polinomiali booleani, motivato dalla crittanalisi di alcuni crittosistemi post-quantistici. L'idea chiave del loro approccio è applicare un algoritmo Quantum Linear System (QLS) a un sistema lineare di Macaulay su $mathbb{C}$, che è derivato dal sistema polinomiale booleano. L'efficienza del loro algoritmo dipende dal numero di condizione della matrice di Macaulay. In questo articolo, diamo un forte limite inferiore al numero della condizione in funzione del peso di Hamming della soluzione booleana e mostriamo che in molti (se non tutti) i casi un algoritmo di ricerca esaustiva basato su Grover supera il loro algoritmo. Quindi, miglioriamo l'algoritmo di Chen e Gao introducendo il sistema lineare booleano di Macaulay su $mathbb{C}$ riducendo il sistema lineare originale di Macaulay. Questo algoritmo migliorato potrebbe potenzialmente superare in modo significativo l'algoritmo di forza bruta, quando il peso di Hamming della soluzione è logaritmico nel numero di variabili booleane.
Inoltre, forniamo una semplice e più elementare prova di correttezza per il nostro algoritmo migliorato utilizzando una riduzione che impiega il metodo di hashing affine Valiant-Vazirani, ed estendiamo anche il risultato ai sistemi polinomiali su $mathbb{F}_q$ migliorando il successivo lavoro di Chen , Gao e Yuan citano ChenGao2018. Suggeriamo anche un nuovo approccio per estrarre la soluzione del sistema polinomiale booleano tramite una generalizzazione del problema del raccoglitore di coupon quantistici [2].

[Contenuto incorporato]

► dati BibTeX

► Riferimenti

, Scott Aaronson. Leggi la stampa fine. Natura Fisica Nat. Fis. , 11(4):291–293, 2015.
https: / / doi.org/ 10.1038 / nphys3272

, Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis e Ronald de Wolf. Collezionista di coupon quantistici. In Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC) TQC , pagine 10:1–10:17, 2020. arXiv: 2002.07688.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
arXiv: 2002.07688

, Gwénolé Ars, Jean-Charles Faugere, Hideki Imai, Mitsuru Kawazoe e Makoto Sugita. Confronto tra algoritmi di base XL e di Gröbner. In International Conference on the Theory and Application of Cryptology and Information Security, pagine 338–353. Primavera, 2004.
https:/​/​doi.org/​10.1007/​978-3-540-30539-2_24

, Andris Ambainis. Amplificazione di ampiezza a tempo variabile e algoritmi quantistici per problemi di algebra lineare. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS) STACS , pagine 636–647, 2012. arXiv: 1010.4458.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
arXiv: 1010.4458

, Eric R Anschuetz, Jonathan P Olson, Alán Aspuru-Guzik e Yudong Cao. Fattorizzazione quantistica variazionale. arXiv: 1808.08927, 2018.
https:/​/​doi.org/​10.1007/​978-3-030-14082-3_7
arXiv: 1808.08927

, Bruno Buchberger et al. Gröbner basa il calcolo triangolarizzando le matrici di Macaulay. In The 50th Anniversary of Gröbner Bases, pagine 25–33. Società matematica del Giappone, 2018.
https://​/​doi.org/​10.2969/​aspm/​07710025

, Kim Batselier. Un framework di algebra lineare numerica per risolvere problemi con polinomi multivariati. Tesi di dottorato, KU Leuven (Leuven, Belgio), 2013.
https://​/​doi.org/​10.13140/​RG.2.1.3137.9608

, Michel Boyer, Gilles Brassard, Peter Hoyer e Alain Tapp. Limiti stretti sulla ricerca quantistica. 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

, Magali Bardet, Jean-Charles Faugère, Bruno Salvy e Pierre-Jean Spaenlehauer. Sulla complessità della risoluzione di sistemi booleani quadratici. Journal of Complexity, 29(1):53–75, 2013.
https://​/​doi.org/​10.1016/​j.jco.2012.07.001

, Andreas Bjorklund, Petteri Kaski e Ryan Williams. Risolvere sistemi di equazioni polinomiali su GF(2) mediante un'autoriduzione che conta la parità. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) ICALP, 2019.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.26

, Christopher JC Burges. Factoring come ottimizzazione. Ricerca Microsoft MSR-TR-200, 2002.

, Ethan Bernstein e Umesh Vazirani. Teoria quantistica della complessità. SIAM Journal on computing, 26(5):1411–1473, 1997.
https: / / doi.org/ 10.1137 / S0097539796300921

, Daniel J Bernstein e Bo-Yin Yang. Algoritmi quantistici asintoticamente più veloci per risolvere equazioni quadratiche multivariate. In International Conference on Post-Quantum Cryptography, pagine 487–506. Primavera, 2018.
https:/​/​doi.org/​10.1007/​978-3-319-79063-3_23

, Alessio Caminata e Elisa Gorla. Risoluzione di sistemi polinomiali multivariati e un invariante dall'algebra commutativa. arXiv: 1706.06319, 2017.
https:/​/​doi.org/​10.1007/​978-3-030-68869-1_1
arXiv: 1706.06319

, Yu-Ao Chen e Xiao-Shan Gao. Algoritmo quantistico per la risoluzione di equazioni booleane e attacco algebrico quantistico ai crittosistemi. Journal of Systems Science and Complexity, 2021. arXiv: 1712.06239.
https:/​/​doi.org/​10.1007/​s11424-020-0028-6
arXiv: 1712.06239

, Shantanav Chakraborty, András Gilyén e Stacey Jeffery. Il potere dei poteri della matrice codificati a blocchi: tecniche di regressione migliorate tramite una simulazione hamiltoniana più veloce. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) ICALP, pagine 33:1–33:14, 2019. arXiv: 1804.01973.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33
arXiv: 1804.01973

, Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang e Chunhao Wang. Quadro aritmetico a matrice di basso rango sublineare basato sul campionamento per la dequantizzazione dell'apprendimento automatico quantistico. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC) STOC , pagina 387–400, 2020. arXiv: 1910.06151.
https: / / doi.org/ 10.1145 / 3357713.3384314 mila
arXiv: 1910.06151

, Yu-Ao Chen, Xiao-Shan Gao e Chun-Ming Yuan. Algoritmo quantistico per l'ottimizzazione e la risoluzione di sistemi polinomiali su campo finito e applicazione alla crittoanalisi, 2018. arXiv: 1802.03856.
arXiv: 1802.03856

, B David Clader, Bryan C Jacobs e Chad R Sprouse. Algoritmo del sistema quantistico lineare precondizionato. Lettere di revisione fisica, 110(25):250504, 2013.
https: / / doi.org/ 10.1103 / PhysRevLett.110.250504

, Nicolas Courtois, Alexander Klimov, Jacques Patarin e Adi Shamir. Algoritmi efficienti per risolvere sistemi sovradefiniti di equazioni polinomiali multivariate. In Conferenza internazionale sulla teoria e le applicazioni delle tecniche crittografiche, pagine 392–407. Springer, 2000 (versione estesa del 24 agosto 2004. http://​/​www.minrank.org/​xlfull.pdf).
https:/​/​doi.org/​10.1007/​3-540-45539-6_27
http://​/​www.minrank.org/​xlfull.pdf)

, Andrew M. Childs, Robin Kothari e Rolando D. Somma. Algoritmo quantistico per sistemi di equazioni lineari con dipendenza dalla precisione migliorata in modo esponenziale. SIAM Journal on Computing SIAM J. Comp., 46(6):1920–1950, 2017. arXiv: 1511.02306.
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306

, Claus Diem. L'algoritmo XL e una congettura dall'algebra commutativa. In International Conference on the Theory and Application of Cryptology and Information Security, pagine 323–337. Primavera, 2004.
https:/​/​doi.org/​10.1007/​978-3-540-30539-2_23

, Jintai Ding e Dieter Schmidt. Risolvere grado e grado di regolarità per sistemi polinomiali su campi finiti. In Teoria dei numeri e crittografia, pagine 34–49. Primavera, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-42001-6_4

, Jean-Charles Faugere, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi e Ludovic Perret. Algoritmo quantistico veloce per risolvere equazioni quadratiche multivariate. arXiv: 1712.07211, 2017.
arXiv: 1712.07211

, András Gilyén, Yuan Su, Guang Hao Low e Nathan Wiebe. Trasformazione del valore singolare quantistico e oltre: miglioramenti esponenziali per l'aritmetica della matrice quantistica [versione completa], 2018. arXiv: 1806.01838.
arXiv: 1806.01838

, András Gilyén, Yuan Su, Guang Hao Low e Nathan Wiebe. Trasformazione del valore singolare quantistico e oltre: miglioramenti esponenziali per l'aritmetica della matrice quantistica. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC) STOC, pagine 193–204, 2019. arXiv: 1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366 mila
arXiv: 1806.01838

, Aram W. Harrow, Avinatan Hassidim e Seth Lloyd. Algoritmo quantistico per sistemi lineari di equazioni. Lettere di revisione fisica Phys. Rev. Lett., 103(15):150502, 2009. arXiv: 0811.3171.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171

, Stasys Jukna. Combinatoria estremale - con applicazioni in informatica (2a ed.). Testi in Informatica Teorica. Primavera, 2011.
https:/​/​doi.org/​10.1007/​978-3-642-17364-6

, Iordanis Kerenidis e Anupam Prakash. Sistemi di raccomandazione quantistica. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS) ITCS, pagine 49:1–49:21, 2017. arXiv: 1603.08675.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv: 1603.08675

, Lin Lin e Yu Tong. Filtraggio di autostati quantistici basato su polinomi ottimali con applicazione alla risoluzione di sistemi lineari quantistici. Quantum Quant., 4:361, 2020. arXiv: 1910.14596.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361
arXiv: 1910.14596

, Ludovico Perret. Bases de Gröbner en Cryptographie Post-Quantique. Tesi di dottorato, UPMC-Paris 6 Sorbonne Universités, 2016.

, Herbert Robbins. Un'osservazione sulla formula di Stirling. The American Mathematical Monthly, 62 (1): 26–29, 1955.
https: / / doi.org/ 10.2307 / 2308012 mila

, Il codice sorgente di Mathematica è disponibile anche nel Woflram Notebook Archive: https:/​/​notebookarchive.org/​2022-02-1ec5yyv, 2022.
https://​/​notebookarchive.org/​2022-02-1ec5yyv

, Yiğit Subaşı, Rolando D. Somma e Davide Orsucci. Algoritmi quantistici per sistemi di equazioni lineari ispirati al calcolo quantistico adiabatico. Lettere di revisione fisica Phys. Rev. Lett., 122(6):060504, 2019. arXiv: 1805.10549.
https: / / doi.org/ 10.1103 / PhysRevLett.122.060504
arXiv: 1805.10549

, Changpeng Shao e Hua Xiang. Precondizionatore circolante quantistico per un sistema lineare di equazioni. Revisione fisica A, 98(6):062321, 2018.
https: / / doi.org/ 10.1103 / PhysRevA.98.062321

, Yu Tong, Dong An, Nathan Wiebe e Lin Lin. Inversione rapida, risolutori di sistemi lineari quantistici precondizionati e valutazione rapida delle funzioni di matrice. arXiv: 2008.13295, 2020.
https: / / doi.org/ 10.1103 / PhysRevA.104.032422
arXiv: 2008.13295

, Leslie G. Valiant e Vijay V. Vazirani. NP è facile come rilevare soluzioni uniche. Informatica Teorica Teor. Calcola. Sci., 47:85–93, 1986. Versione precedente in STOC'85.
https:/​/​doi.org/​10.1016/​0304-3975(86)90135-0

, Ronald de Wolf. Calcolo quantistico: appunti delle lezioni, 2019. arXiv: 1907.09415.
arXiv: 1907.09415

, Manuela Wiesinger-Widi. Basi di Gröbner e matrici di Sylvester generalizzate. Tesi di dottorato, Johannes Kepler University Linz, Austria, 2015.
https: / / doi.org/ 10.1145 / 2016567.2016594 mila

Citato da

Impossibile recuperare Crossref citato da dati durante l'ultimo tentativo 2023-07-26 10:46:19: Impossibile recuperare i dati citati per 10.22331 / q-2023-07-26-1069 da Crossref. Questo è normale se il DOI è stato registrato di recente. Su ANNUNCI SAO / NASA non sono stati trovati dati su citazioni (ultimo tentativo 2023-07-26 10:46:19).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

Timestamp:

Di più da Diario quantistico