Méthodes de points intérieurs quantiques pour l'optimisation semi-définie

Méthodes de points intérieurs quantiques pour l'optimisation semi-définie

Horodatage: 11 septembre 2023 11:39 AM
Méthodes de points intérieurs quantiques pour l'optimisation semi-définie PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

Brandon Augustino1, Giacomo Nannicini2, Tamas Terlaky1, et Luis F. Zuluaga1

1Département d'ingénierie industrielle et des systèmes, laboratoire d'informatique quantique et d'optimisation, Université Lehigh
2Département d'ingénierie industrielle et des systèmes, Université de Californie du Sud

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Nous présentons deux méthodes de points intérieurs quantiques pour des problèmes d'optimisation semi-définis, en s'appuyant sur les progrès récents des algorithmes de systèmes linéaires quantiques. Le premier schéma, plus similaire à un algorithme de solution classique, calcule une direction de recherche inexacte et n'est pas garanti d'explorer uniquement les points réalisables ; le deuxième schéma utilise une représentation en espace nul du système linéaire de Newton pour garantir la faisabilité même avec des directions de recherche inexactes. Le second est un nouveau schéma qui peut sembler peu pratique dans le monde classique, mais il convient bien à un contexte hybride quantique-classique. Nous montrons que les deux schémas convergent vers une solution optimale du problème d’optimisation semi-définie sous des hypothèses standard. En comparant les performances théoriques des méthodes de points intérieurs classiques et quantiques par rapport à divers paramètres d'entrée, nous montrons que notre deuxième schéma obtient une accélération par rapport aux algorithmes classiques en termes de dimension du problème $n$, mais qu'il dépend davantage d'autres algorithmes numériques. paramètres.

Résumé populaire

L'optimisation semi-définie (SDO) génère une famille fondamentale de problèmes d'optimisation convexe dotés d'un vaste pouvoir d'expression. Les problèmes SDO généralisent les problèmes d'optimisation linéaire et, en plus de trouver des applications dans le contrôle, la théorie de l'information, les statistiques et l'apprentissage automatique, SDO peut également être utilisé pour approximer la solution aux problèmes d'optimisation combinatoire. Les algorithmes classiques les plus performants pour résoudre les problèmes SDO sont les méthodes des points intérieurs (IPM), et il est donc naturel de rechercher si le cadre IPM peut être accéléré dans un environnement quantique. Nous proposons deux IPM quantiques convergents pour SDO, obtenant une accélération quantique dans la dimension du problème au prix d'une pire dépendance à l'égard de la précision et d'un nombre de conditions lié aux systèmes linéaires de Newton qui surviennent à chaque itération.

► Données BibTeX

► Références

Léonid G. Khachiyan. "Algorithmes polynomiaux en programmation linéaire". Mathématiques computationnelles et physique mathématique de l'URSS 20, 53-72 (1980).
https: / / doi.org/ 10.1145 / 800057.808695

Narendra Karmarkar. "Un nouvel algorithme en temps polynomial pour la programmation linéaire". Combinatorica Pages 373-395 (1984).
https: / / doi.org/ 10.1145 / 800057.808695

Yurii E. Nesterov et Arkadi Nemirovskii. "Une approche générale de la conception d'algorithmes en temps polynomial pour la programmation convexe". Rapport, Institut central d'économie et de mathématiques, Académie des sciences de l'URSS, Moscou (1988).

Yurii E. Nesterov et Arkadi Nemirovskii. "Algorithmes polynomiaux de points intérieurs en programmation convexe". Tome 13. SIAM. (1995).
https: / / doi.org/ 10.1137 / 1.9781611970791

Stephen Boyd, Laurent El Ghaoui, Eric Feron et Venkataramanan Balakrishnan. "Inégalités matricielles linéaires dans la théorie des systèmes et du contrôle". SIAM. (1994).
https: / / doi.org/ 10.1137 / 1.9781611970777

Éric M. Rains. "Un programme semi-défini pour l'enchevêtrement distillable". Transactions IEEE sur la théorie de l'information 47, 2921-2933 (2001).
https: / / doi.org/ 10.1109 / 18.959270

Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui et Michael I. Jordan. "Apprentissage de la matrice du noyau avec programmation semi-définie". Journal de recherche sur l'apprentissage automatique 5, 27-72 (2004).

Kilian Q. Weinberger et Lawrence K. Saul. "Apprentissage non supervisé de variétés d'images par programmation semi-définie". Journal international de vision par ordinateur 70, 77-90 (2006).
https: / / doi.org/ 10.1007 / s11263-005-4939-z

Alexandre d'Aspremont, Laurent El Ghaoui, Michael I. Jordan et Gert RG Lanckriet. "Une formulation directe pour une PCA clairsemée utilisant une programmation semi-définie". Revue SIAM 49, 434-448 (2007). arXiv :https:/​/​doi.org/​10.48550/​arXiv.cs/​0406021.
https://​/​doi.org/​10.48550/​arXiv.cs/​0406021
arXiv :https://doi.org/10.48550/arXiv.cs/0406021

Henry Wolkowicz, Romesh Saigal et Lieven Vandenberghe. "Manuel de programmation semi-définie : théorie, algorithmes et applications". Médias scientifiques et commerciaux Springer. (2012).
https:/​/​doi.org/​10.1007/​978-1-4615-4381-7

Yonina C.Eldar. "Une approche de programmation semi-définie pour une discrimination optimale et sans ambiguïté des états quantiques". Transactions IEEE sur la théorie de l'information 49, 446-456 (2003).
https: / / doi.org/ 10.1109 / TIT.2002.807291

Aram W. Harrow, Anand Natarajan et Xiaodi Wu. "Une hiérarchie de programmation semi-définie améliorée pour tester l'intrication". Communications en physique mathématique 352, 881–904 (2017).
https:/​/​doi.org/​10.1007/​s00220-017-2859-0

Jean Watrous. « Programmes semi-définis pour des normes complètement limitées » (2009).
arXiv: 0901.4709

Michel X. Goemans et David P. Williamson. "Algorithmes d'approximation améliorés pour les problèmes de coupe maximale et de satisfiabilité utilisant la programmation semi-définie". Journal de l'ACM (JACM) 42, 1115-1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

Lászlo Lovász. « Sur la capacité de Shannon d'un graphe ». Transactions IEEE sur la théorie de l'information 25, 1–7 (1979).
https: / / doi.org/ 10.1109 / TIT.1979.1055985

Erling D. Andersen et Knud D. Andersen. « L'optimiseur de points intérieurs MOSEK pour la programmation linéaire : une implémentation de l'algorithme homogène ». Dans Hans Frenk, Kees Roos, Tamás Terlaky et Shuzhong Zhang, éditeurs, High Performance Optimization. Pages 197 à 232. Springer (2000).
https:/​/​doi.org/​10.1007/​978-1-4757-3216-0_8

Jos F. Sturm. "Utilisation de SeDuMi 1.02, une boîte à outils MATLAB pour l'optimisation sur cônes symétriques". Méthodes et logiciels d'optimisation 11, 625-653 (1999).
https: / / doi.org/ 10.1080 / 10556789908805766

Kim-Chuan Toh, Michael J. Todd et Reha H. Tütüncü. « SDPT3 — un progiciel MATLAB pour la programmation semi-définie, version 1.3 ». Méthodes et logiciels d'optimisation 11, 545-581 (1999).
https: / / doi.org/ 10.1080 / 10556789908805762

Farid Alizadeh, Jean-Pierre A. Haeberly et Michael L. Overton. "Méthodes primal-dual de points intérieurs pour la programmation semi-définie : taux de convergence, stabilité et résultats numériques". SIAM Journal sur l'optimisation 8, 746-768 (1998).
https: / / doi.org/ 10.1137 / S1052623496304700

Haotian Jiang, Yin Tat Lee, Zhao Song et Sam Chiu-wai Wong. "Une méthode de plan de coupe améliorée pour l'optimisation convexe, les jeux convexes-concaves et ses applications". Dans Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath et Julia Chuzhoy, rédacteurs, Actes du 52e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 944 à 953. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384284

Yin Tat Lee, Aaron Sidford et Sam Chiu-wai Wong. "Une méthode de plan de coupe plus rapide et ses implications pour l'optimisation combinatoire et convexe". Dans Rafail Ostrovsky et Venkatesan Guruswami, éditeurs, 2015e Symposium annuel IEEE 56 sur les fondements de l'informatique (FOCS). Pages 1049 à 1065. IEEE (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.68

Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan et Zhao Song. "Une méthode de point intérieur plus rapide pour la programmation semi-définie". Dans Sandy Irani, Lisa O'Conner et Patrick Kellenberger, rédacteurs, 2020e Symposium annuel IEEE 61 sur les fondements de l'informatique (FOCS). Pages 910 à 918. IEEE (2020).
https://​/​doi.org/​10.1109/​FOCS46700.2020.00089

Renato DC Monteiro. "Convergence polynomiale d'algorithmes primal-dual pour la programmation semi-définie basée sur la famille de directions de Monteiro et Zhang". SIAM Journal sur l'optimisation 8, 797-812 (1998).
https: / / doi.org/ 10.1137 / S1052623496308618

Yurii E. Nesterov et Michael J. Todd. "Barrières auto-évolutives et méthodes de points intérieurs pour la programmation convexe". Mathématiques de la recherche opérationnelle Pages 1 à 42 (1997).
https: / / doi.org/ 10.1287 / moor.22.1.1

Yurii E. Nesterov et Michael J. Todd. "Méthodes de points intérieurs primal-double pour les cônes à échelle automatique". SIAM Journal sur l'optimisation 8, 324-364 (1998).
https: / / doi.org/ 10.1137 / S1052623495290209

Sanjeev Arora, Elad Hazan et Satyen Kale. « La méthode des poids multiplicatifs : un méta-algorithme et ses applications ». Théorie de l'informatique, 8(6) 121-164 (2012).
https: / / doi.org/ 10.4086 / toc.2012.v008a006

Fernando GSL Brandão et Krysta M. Svore. "Accélérations quantiques pour la résolution de programmes semi-définis". Dans Rafail Ostrovsky et Chris Umans, éditeurs, 2017e Symposium annuel IEEE 58 sur les fondements de l'informatique (FOCS). Pages 415-426. IEEE (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.45

Joran van Apeldoorn, András Gilyén, Sander Gribling et Ronald de Wolf. « Solveurs Quantum SDP : meilleures limites supérieures et inférieures ». Quantique 4, 230 (2020).
https:/​/​doi.org/​10.22331/​q-2020-02-14-230

Sandre Gribling. "Applications de l'optimisation aux rangs de factorisation et à la théorie de l'information quantique". Doctorat. Thèse, CentER, Université de Tilburg. (2019).

Joran van Apeldoorn et András Gilyén. « Améliorations de la résolution Quantum SDP avec des applications ». Dans Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini et Stefano Leonardi, éditeurs, 46e Colloque international sur les automates, les langages et la programmation (ICALP 2019). Volume 132 de Leibniz International Proceedings in Informatics (LIPIcs), pages 99 :1–99 :15. Dagstuhl, Allemagne (2019). Château Dagstuhl–Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99

Iordanis Kerenidis et Anupam Prakash. "Une méthode de point intérieur quantique pour les LP et les SDP". Transactions ACM sur l'informatique quantique 1, 1-32 (2020).
https: / / doi.org/ 10.1145 / 3406306

Pablo AM Casares et Miguel Ángel Martín-Delgado. "Un algorithme quantique de prédicteur-correcteur de point intérieur pour la programmation linéaire". Journal of Physics A : Mathématique et Théorique 53, 445305 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / abb439

Iordanis Kerenidis, Anupam Prakash et Dániel Szilágyi. "Algorithmes quantiques pour la programmation de cônes de second ordre et les machines vectorielles de support". Quantique 5, 427 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-08-427

Aharon Ben-Tal et Arkadi Nemirovskii. « Cours sur l'optimisation convexe moderne : analyse, algorithmes et applications d'ingénierie ». SIAM. (2001).
https: / / doi.org/ 10.1137 / 1.9780898718829

Michael J.Todd. "Une étude des directions de recherche dans les méthodes primal-dual de points intérieurs pour la programmation semi-définie". Méthodes et logiciels d'optimisation 11, 1–46 (1999).
https: / / doi.org/ 10.1080 / 10556789908805745

Masakazu Kojima, Susumu Shindoh et Shinji Hara. "Méthodes de points intérieurs pour le problème de complémentarité linéaire semi-définie monotone dans les matrices symétriques". SIAM Journal sur l'optimisation 7, 86-125 (1997).
https: / / doi.org/ 10.1137 / S1052623494269035

Renato DC Monteiro. "Algorithmes de suivi de chemin primal-double pour la programmation semi-définie". SIAM Journal sur l'optimisation 7, 663-678 (1997).
https: / / doi.org/ 10.1137 / S1052623495293056

Renato DC Monteiro et Yin Zhang. "Une analyse unifiée pour une classe d'algorithmes de point intérieur de suivi de chemin primal-double à étapes longues pour la programmation semi-définie". Programmation mathématique 81, 281-299 (1998).
https: / / doi.org/ 10.1007 / BF01580085

Yin Zhang. "Sur l'extension de certains algorithmes primal-dual de points intérieurs de la programmation linéaire à la programmation semi-définie". SIAM Journal sur l'optimisation 8, 365-386 (1998).
https: / / doi.org/ 10.1137 / S1052623495296115

Renato DC Monteiro et Takashi Tsuchiya. "Convergence polynomiale d'une nouvelle famille d'algorithmes primal-dual pour la programmation semi-définie". SIAM Journal sur l'optimisation 9, 551-577 (1999).
https: / / doi.org/ 10.1137 / S1052623496312836

Paul Tseng. "Directions de recherche et analyse de convergence de certaines méthodes de suivi de chemin infaisables pour le LCP semi-défini monotone". Méthodes et logiciels d'optimisation 9, 245-268 (1998).
https: / / doi.org/ 10.1080 / 10556789808805695

Florian A. Potra et Rongqin Sheng. "Un algorithme de point intérieur infaisable primal-dual superlinéairement convergent pour la programmation semi-définie". SIAM Journal sur l'optimisation 8, 1007-1028 (1998).
https: / / doi.org/ 10.1137 / S1052623495294955

Yin Zhang. "Sur la convergence d'une classe de méthodes de points intérieurs infaisables pour le problème de complémentarité linéaire horizontale". SIAM Journal sur l'optimisation 4, 208-227 (1994).
https: / / doi.org/ 10.1137 / 0804012

Janos Korzak. "Analyse de convergence d'algorithmes inexacts de points intérieurs infaisables pour résoudre des problèmes de programmation linéaire". SIAM Journal sur l'optimisation 11, 133-148 (2000).
https: / / doi.org/ 10.1137 / S1052623497329993

Shinji Mizuno et Florian Jarre. "Convergence globale et en temps polynomial d'un algorithme de point intérieur infaisable utilisant un calcul inexact". Programmation mathématique 84 (1999).
https://​/​doi.org/​10.1007/​s10107980020a

Jacek Gondzio. "Analyse de convergence d'une méthode de point intérieur réalisable inexacte pour la programmation quadratique convexe". SIAM Journal sur l'optimisation 23, 1510-1527 (2013).
https: / / doi.org/ 10.1137 / 120886017

Guanglu Zhou et Kim-Chuan Toh. « Polynomialité d'un algorithme de point intérieur inexact et infaisable pour la programmation semi-définie ». Programmation mathématique 99, 261-282 (2004).
https:/​/​doi.org/​10.1007/​s10107-003-0431-5

Christoph Helmberg, Franz Rendl, Robert J. Vanderbei et Henry Wolkowicz. "Une méthode de point intérieur pour la programmation semi-définie". SIAM Journal sur l'optimisation 6, 342-361 (1996).
https: / / doi.org/ 10.1137 / 0806020

Michael B. Cohen, Yin Tat Lee et Zhao Song. "Résolution de programmes linéaires dans le temps de multiplication matricielle actuel". Journal de l'ACM (JACM) 68, 1-39 (2021).
https: / / doi.org/ 10.1145 / 3424305

Fernando GSL Brandão, Richard Kueng et Daniel Stilck França. « Des approximations quantiques et classiques SDP plus rapides pour l'optimisation binaire quadratique ». Quantique 6, 625 (2022).
https:/​/​doi.org/​10.22331/​q-2022-01-20-625

Aram W. Harrow, Avinatan Hassidim et Seth Lloyd. "Algorithme quantique pour systèmes d'équations linéaires". Lettres d'examen physique 103, 150502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

Ambros M. Gleixner et Daniel E. Steffy. "Programmation linéaire utilisant des oracles de précision limitée". Programmation mathématique 183, 525-554 (2020).
https:/​/​doi.org/​10.1007/​s10107-019-01444-6

Ambros M. Gleixner, Daniel E. Steffy et Kati Wolter. "Améliorer la précision des solveurs de programmation linéaire avec un raffinement itératif". Dans Joris van der Hoeven et Mark van Hoeij, éditeurs, Actes du 37e Symposium international sur le calcul symbolique et algébrique. Pages 187 à 194. (2012).
https: / / doi.org/ 10.1145 / 2442829.2442858

Ambros M. Gleixner, Daniel E. Steffy et Kati Wolter. « Raffinement itératif pour la programmation linéaire ». INFORMS Journal sur l'informatique 28, 449-464 (2016).
https: / / doi.org/ 10.1287 / ijoc.2016.0692

Rolando D. Somma et Yiğit Subaşı. "Complexité de la vérification de l'état quantique dans le problème des systèmes linéaires quantiques". PRX Quantique 2, 010315 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010315

Shantanav Chakraborty, András Gilyén et Stacey Jeffery. "La puissance des puissances matricielles codées par blocs : techniques de régression améliorées via une simulation hamiltonienne plus rapide". Dans Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini et Stefano Leonardi, éditeurs, 46e Colloque international sur les automates, les langages et la programmation (ICALP 2019). Volume 132, pages 33 : 1 à 33 : 14. Dagstuhl, Allemagne (2019). Château Dagstuhl–Leibniz-Zentrum für Informatik.
https://​/​doi.org/​10.48550/​arXiv.1804.01973

András Gilyén, Yuan Su, Guang Hao Low et Nathan Wiebe. « Transformation quantique des valeurs singulières et au-delà : améliorations exponentielles pour l'arithmétique matricielle quantique ». Dans Moses Charikar et Edith Cohen, rédacteurs, Actes du 51e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 193-204. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316366

Andrew M. Childs, Robin Kothari et Rolando D. Somma. "Algorithme quantique pour les systèmes d'équations linéaires avec une dépendance exponentiellement améliorée à la précision". Journal SIAM sur l'informatique 46, 1920-1950 (2017).
https: / / doi.org/ 10.1137 / 16M1087072

Lov Grover et Terry Rudolph. « Créer des superpositions qui correspondent à des distributions de probabilité efficacement intégrables » (2002). arXiv :https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0208112.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0208112
arXiv :https://doi.org/10.48550/arXiv.quant-ph/0208112

Iordanis Kerenidis et Anupam Prakash. « Systèmes de recommandation quantique » (2016). arXiv :https:/​/​doi.org/​10.48550/​arXiv.1603.08675.
https://​/​doi.org/​10.48550/​arXiv.1603.08675
arXiv :https://doi.org/10.48550/arXiv.1603.08675

Michael Keyl. "Estimation de l'état quantique et grands écarts". Revues dans Mathematical Physics 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

Ryan O'Donnell et John Wright. « Tomographie quantique efficace ». Dans les actes du quarante-huitième symposium annuel de l'ACM sur la théorie de l'informatique. Pages 899 à 912. (2016).
https: / / doi.org/ 10.1145 / 2897518.2897544

Joran van Apeldoorn, Arjan Cornelissen, András Gilyén et Giacomo Nannicini. "Tomographie quantique utilisant des unitaires de préparation d'état". Dans les actes du symposium annuel ACM-SIAM 2023 sur les algorithmes discrets (SODA). Pages 1265-1318. SIAM (2023).
https: / / doi.org/ 10.1137 / 1.9781611977554.ch47

Etienne de Klerk, Cornelis Roos et Tamás Terlaky. "Initialisation en programmation semi-définie via un intégration auto-duale antisymétrique". Lettres de recherche opérationnelle 20, 213-221 (1997).
https:/​/​doi.org/​10.1016/​S0167-6377(97)00011-4

Michael J. Todd, Kim-Chuan Toh et Reha H. Tütüncü. "Sur la direction Nesterov-Todd en programmation semi-définie". SIAM Journal sur l'optimisation 8, 769-796 (1998).
https: / / doi.org/ 10.1137 / S105262349630060X

Ron S. Dembo, Stanley C. Eisenstat et Trond Steihaug. "Méthodes de Newton inexactes". Journal SIAM sur l'analyse numérique 19, 400-408 (1982).
https: / / doi.org/ 10.1137 / 0719025

Carl T. Kelley. "Méthodes itératives pour les équations linéaires et non linéaires". SIAM. (1995).
https: / / doi.org/ 10.1137 / 1.9781611970944

Peter Bürgisser, Michael Clausen et Mohammad A. Shokrollahi. « Théorie de la complexité algébrique ». Médias scientifiques et commerciaux Springer. (2013).
https:/​/​doi.org/​10.1007/​978-3-662-03338-8

Volker Strassen. "L'élimination gaussienne n'est pas optimale". Numerische Mathematik 13, 354-356 (1969).
https: / / doi.org/ 10.1007 / BF02165411

Raphaël Yuster et Uri Zwick. « Multiplication matricielle clairsemée rapide ». Transactions ACM sur algorithmes (TALG) 1, 2–13 (2005).
https: / / doi.org/ 10.1145 / 1077464.1077466

Iordanis Kerenidis et Anupam Prakash. «Une méthode de point intérieur quantique pour les LP et les SDP» (2018). arXiv :https:/​/​doi.org/​10.48550/​arXiv.1808.09266.
https://​/​doi.org/​10.48550/​arXiv.1808.09266
arXiv :https://doi.org/10.48550/arXiv.1808.09266

Youssef Saad. "Méthodes itératives pour les systèmes linéaires clairsemés". SIAM. (2003).
https: / / doi.org/ 10.1137 / 1.9780898718003

Nisheeth K. Vishnoi. « $Lx= b$ : Solveurs laplaciens et leurs applications algorithmiques ». Fondements et tendances® en informatique théorique 8, 1–141 (2013).
https:/​/​doi.org/​10.1007/​978-3-642-13562-0_2

Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore et Xiaodi Wu. « Solveurs Quantum SDP : accélérations importantes, optimalité et applications à l'apprentissage quantique ». Dans Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini et Stefano Leonardi, éditeurs, 46e Colloque international sur les automates, les langages et la programmation (ICALP 2019). Volume 132, pages 27 : 1 à 27 : 14. Dagstuhl, Allemagne (2019). Château Dagstuhl–Leibniz-Zentrum für Informatik.
https://​/​doi.org/​10.48550/​arXiv.1710.02581

Yin Tat Lee et Swati Padmanabhan. "Un algorithme $widetilde{mathcal{O}}(m/​varepsilon^{3.5})$-cost pour les programmes semi-définis avec des contraintes diagonales". Dans Jacob Abernethy et Shivani Agarwal, éditeurs, Conference on Learning Theory. Pages 3069 à 3119. PMLR (2020).
https://​/​doi.org/​10.48550/​arXiv.1903.01859

Cornelis Roos, Tamás Terlaky et Jean-Phillipe Vial. "Méthodes de points intérieurs pour l'optimisation linéaire". Médias scientifiques et commerciaux Springer. (2005).
https: / / doi.org/ 10.1007 / b100325

Ali Mohammad-Nezhad et Tamas Terlaky. "Sur l'identification de la partition optimale pour l'optimisation semi-définie". INFOR : Systèmes d'information et recherche opérationnelle 58, 1–39 (2019). arXiv :https:/​/​doi.org/​10.1080/​03155986.2019.1572853.
https: / / doi.org/ 10.1080 / 03155986.2019.1572853
arXiv: https: //doi.org/10.1080/03155986.2019.1572853

Cité par

[1] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia et Yuri Alexeev, « L'informatique quantique pour la finance », Nature Avis Physique 5 8, 450 (2023).

[2] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao et Ruizhe Zhang, « Un algorithme quantique plus rapide pour la programmation semi-définie via un cadre IPM robuste », arXiv: 2207.11154, (2022).

[3] Taylor L. Patti, Jean Kossaifi, Anima Anandkumar et Susanne F. Yelin, « Algorithme quantique de Goemans-Williamson avec le test Hadamard et les contraintes d'amplitude approximatives », Quantique 7, 1057 (2023).

[4] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin JA Schuetz, Fernando GSL Brandão, Helmut G. Katzgraber et William J. Zeng, « Analyse des ressources de bout en bout pour les méthodes quantiques de points intérieurs et l'optimisation du portefeuille », arXiv: 2211.12489, (2022).

[5] Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Zeguan Wu et Tamás Terlaky, « Une méthode de point intérieur réalisable inexact pour l'optimisation linéaire avec une grande adaptabilité aux ordinateurs quantiques », arXiv: 2307.14445, (2023).

[6] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta et William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", arXiv: 2206.03505, (2022).

[7] Ojas Parekh, "Synergies entre la recherche opérationnelle et la science de l'information quantique", arXiv: 2301.05554, (2023).

[8] Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi et Tamás Terlaky, « Utilisation efficace des algorithmes de systèmes linéaires quantiques dans les méthodes de points intérieurs pour l'optimisation linéaire », arXiv: 2205.01220, (2022).

[9] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky et Luis Zuluaga, « Résoudre la relaxation semi-définie des QUBO en temps de multiplication matricielle, et plus rapidement avec un ordinateur quantique », arXiv: 2301.04237, (2023).

[10] Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Xiu Yang et Tamás Terlaky, « Une méthode de point intérieur quantique réalisable et inexacte pour une optimisation quadratique à contraintes linéaires », Entropie 25 2, 330 (2023).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2023-09-11 15:42:21). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

Impossible de récupérer Données de référence croisée lors de la dernière tentative 2023-09-11 15:42:20: Impossible de récupérer les données citées par 10.22331 / q-2023-09-11-1110 de Crossref. C'est normal si le DOI a été enregistré récemment.

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique