Approche hybride diviser pour mieux régner pour les algorithmes de recherche arborescente

Approche hybride diviser pour mieux régner pour les algorithmes de recherche arborescente

Horodatage: 23 mars 2023 9:57
Nœud source: 2029300

Mathys Rennela1, Marque Sebastiaan2, Alphons Laarman2, et Vedran Dunjko2

1Laboratoire de Physique de l'Ecole Normale Supérieure, Inria, CNRS, ENS-PSL, Mines-Paristech, Sorbonne Université, PSL Research University, Paris, France
2LIACS, Université de Leiden, Leiden, Pays-Bas

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

Abstract

L'un des défis des ordinateurs quantiques à court et à moyen terme est le nombre limité de qubits que nous pouvons utiliser pour les calculs. Trouver des méthodes permettant d'obtenir des améliorations quantiques utiles dans des limites de taille est donc une question clé dans le domaine. Dans cette veine, il a été récemment montré qu'une méthode hybride classique-quantique peut aider à fournir des accélérations polynomiales aux algorithmes classiques de division pour régner, même lorsqu'ils n'ont accès qu'à un ordinateur quantique beaucoup plus petit que le problème lui-même. Dans ce travail, nous étudions la méthode hybride diviser pour régner dans le contexte des algorithmes de recherche arborescente, et l'étendons en incluant le retour arrière quantique, qui permet de meilleurs résultats que les méthodes précédentes basées sur Grover. En outre, nous fournissons des critères généraux pour les accélérations polynomiales dans le contexte de la recherche d'arbres et fournissons un certain nombre d'exemples où des accélérations polynomiales, en utilisant des ordinateurs quantiques arbitrairement plus petits, peuvent être obtenues. Nous fournissons des conditions d'accélération pour l'algorithme bien connu de DPLL, et nous prouvons des accélérations sans seuil pour l'algorithme PPSZ (le cœur du solveur de satisfiabilité booléenne exacte le plus rapide) pour des classes de formules bien comportées. Nous fournissons également un exemple simple où des accélérations peuvent être obtenues de manière indépendante de l'algorithme, sous certaines hypothèses théoriques de complexité bien étudiées. Enfin, nous discutons brièvement des limites fondamentales des méthodes hybrides pour fournir des accélérations pour des problèmes plus importants.

Résumé populaire

À court et à moyen terme, avec des ordinateurs quantiques ayant un nombre limité de qubits, certaines instances de problèmes peuvent être trop importantes pour être résolues sur un ordinateur quantique. Dans ce contexte, il est naturel d'examiner les stratégies de division pour mieux régner : divisez classiquement le problème en parties suffisamment petites pour être résolues sur l'ordinateur quantique et combinez ensuite les résultats. C'est ce qu'on appelle un algorithme hybride quantique-classique.

Les algorithmes de recherche arborescente sont particulièrement adaptés à cette approche hybride. Lorsque l'espace de recherche est un arbre binaire complet, il est simple de diviser le problème en parties suffisamment petites pour un ordinateur quantique donné et de se retrouver avec une accélération quantique (plus petite) sur le problème initial. Cependant, dans la plupart des algorithmes de recherche d'arbres classiques, les branches sont élaguées pendant la recherche et il reste un arbre clairsemé. Dans ce cadre, il devient moins évident si une petite accélération polynomiale peut encore être obtenue par un algorithme hybride.

Dans cet article, nous étudions cette méthode hybride diviser pour régner dans le contexte d'algorithmes de recherche arborescente, tels que les algorithmes développés pour la satisfiabilité booléenne. Notre contribution principale est que nous fournissons des conditions suffisantes pour les accélérations quantiques et que nous les appliquons à deux algorithmes de satisfaisabilité booléenne bien connus.

► Données BibTeX

► Références

Vedran Dunjko, Yimin Ge et J Ignacio Cirac. "Accélérations de calcul à l'aide de petits dispositifs quantiques". Lettres d'examen physique 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

Yimin Ge et Vedran Dunjko. "Un cadre d'algorithme hybride pour les petits ordinateurs quantiques avec une application pour trouver des cycles hamiltoniens". Journal de physique mathématique 61, 012201 (2020).
https: / / doi.org/ 10.1063 / 1.5119235

Ashley Montanaro. "Accélération de la marche quantique des algorithmes de retour en arrière". Théorie de l'informatique 14, 1–24 (2018).
https: / / doi.org/ 10.4086 / toc.2018.v014a015

Martin Davis, George Logemann et Donald W Loveland. "Un programme machine pour la démonstration de théorèmes". Université de New York, Institut des sciences mathématiques. (1961).
https: / / doi.org/ 10.1145 / 368273.368557

Ramamohan Paturi, Pavel Pudlák, Michael E Saks et Francis Zane. "Un algorithme de temps exponentiel amélioré pour k-SAT". Journal de l'ACM (JACM) 52, 337–364 (2005).
https: / / doi.org/ 10.1145 / 1066100.1066101

Earl Campbell, Ankur Khurana et Ashley Montanaro. « Application d'algorithmes quantiques à des problèmes de satisfaction de contraintes ». Quantique 3, 167 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-18-167

Simon Martiel et Maxime Rémaud. "Mise en œuvre pratique d'un algorithme de backtracking quantique". Dans Conférence internationale sur les tendances actuelles de la théorie et de la pratique de l'informatique. Pages 597–606. Springer (2020).
https:/​/​doi.org/​10.1007/​978-3-030-38919-2_49

Thomas Dueholm Hansen, Haim Kaplan, Or Zamir et Uri Zwick. "Algorithmes k-sat plus rapides utilisant ppsz biaisé". Dans Actes du 51e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 578–589. STOC 2019New York, NY, États-Unis (2019). ACM.
https: / / doi.org/ 10.1145 / 3313276.3316359

Armin Biere, Marijn Heule et Hans van Maaren. "Manuel de satisfaisabilité". Volume 185. Presse IOS. (2009).

Marc Mézard, Marc Mézard et Andrea Montanari. "Information, physique et informatique". Presse universitaire d'Oxford. (2009).
https: / / doi.org/ 10.1063 / 1.3397047

Martin Davis et Hillary Putnam. "Une procédure de calcul pour la théorie de la quantification". J.ACM 7, 201-215 (1960).
https: / / doi.org/ 10.1145 / 321033.321034

Marijn JH Heule, Matti Juhani Järvisalo, Martin Suda, et al. "Descriptions des solveurs et des benchmarks". Dans Actes du concours SAT 2018. Département d'informatique, Université d'Helsinki (2018). URL : http://​/​hdl.handle.net/​10138/​237063.
http: / / hdl.handle.net/ 10138 / 237063

Robert Nieuwenhuis, Albert Oliveras et Cesare Tinelli. "Théories DPLL abstraites et modulo DPLL abstraites". Dans Conférence internationale sur la logique pour la programmation de l'intelligence artificielle et du raisonnement. Pages 36–50. Springer (2005).
https:/​/​doi.org/​10.1007/​978-3-540-32275-7_3

Jasmin Christian Blanchette, Sascha Böhme et Lawrence C Paulson. "Étendre Sledgehammer avec des solveurs SMT". Journal de raisonnement automatisé 51, 109-128 (2013).
https:/​/​doi.org/​10.1007/​s10817-013-9278-5

Daniel Rolf. "Dérandomisation de PPSZ pour unique-k-SAT". Dans Conférence internationale sur la théorie et les applications des tests de satisfaction. Pages 216–225. Springer (2005).
https: / / doi.org/ 10.1007 / 11499107_16

Dominik Scheder et John P Steinberger. "PPSZ pour le k-SAT général rendant l'analyse de Hertli plus simple et 3-SAT plus rapide". Dans la 32e conférence sur la complexité computationnelle (CCC 2017). Tome 79, pages 9:1–9:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.9

Daniel Rolf. "Liaison améliorée pour l'algorithme PPSZ / schoning pour 3-SAT". Journal on Satisfiability, Boolean Modeling and Computation 1, 111–122 (2006).
https://​/​doi.org/​10.3233/​SAT190005

Timon Hertli. "3-SAT plus rapide et plus simple - les limites SAT uniques pour PPSZ tiennent en général". SIAM Journal on Computing 43, 718–729 (2014).
https: / / doi.org/ 10.1137 / 120868177

Timon Hertli. "Briser la barrière PPSZ pour un 3-SAT unique". In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhague, Danemark, 8-11 juillet 2014, Actes, Partie I 41. Pages 600–611. Springer (2014).
https:/​/​doi.org/​10.1007/​978-3-662-43948-7_50

Dominik Scheder. "PPSZ est meilleur que vous ne le pensez". En 2021, 62e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS). Pages 205–216. (2022).
https://​/​doi.org/​10.1109/​FOCS52979.2021.00028

Amour K Grover. "Un algorithme de mécanique quantique rapide pour la recherche de bases de données". Dans Actes du vingt-huitième symposium annuel de l'ACM sur la théorie de l'informatique. Pages 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

Andris Ambainis. "Algorithmes de recherche quantique". ACM SIGACT News 35, 22–35 (2004).
https: / / doi.org/ 10.1145 / 992287.992296

Andris Ambainis et Martins Kokainis. "Algorithme quantique pour l'estimation de la taille des arbres, avec des applications au backtracking et aux jeux à 2 joueurs". Dans Actes du 49e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 989–1002. (2017).
https: / / doi.org/ 10.1145 / 3055399.3055444

Michael Jarret et Kianna Wan. "Algorithmes de backtracking quantiques améliorés utilisant des estimations de résistance efficaces". Examen physique A 97, 022337 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022337

Dominic J. Moylett, Noah Linden et Ashley Montanaro. "Accélération quantique du problème du voyageur de commerce pour les graphes à degrés bornés". Phys. Rév. A 95, 032323 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032323

Neil D. Jones et William T. Laaser. "Problèmes complets pour temps polynomial déterministe". Informatique théorique 3, 105 - 117 (1976).
https:/​/​doi.org/​10.1016/​0304-3975(76)90068-2

Raymond Greenlaw, H James Hoover, Walter L Ruzzo, et al. « Limites au calcul parallèle : théorie de la P-complétude ». Oxford University Press sur demande. (1995).

Thomas Lengauer et Robert E Tarjan. "Des limites asymptotiquement serrées sur les compromis espace-temps dans un jeu de galets". Journal de l'ACM (JACM) 29, 1087-1130 (1982).
https: / / doi.org/ 10.1145 / 322344.322354

Charles H. Bennett. « Compromis temps/​espace pour le calcul réversible ». SIAM Journal on Computing 18, 766–776 (1989).
https: / / doi.org/ 10.1137 / 0218053

T. Altman et Y. Igarashi. « Tri grossier : Approche séquentielle et parallèle ». J. Inf. Processus. 12, 154-158 (1989). URL : http://​/​id.nii.ac.jp/​1001/​00059782/​.
http://​/​id.nii.ac.jp/​1001/​00059782/​

Hong-Yu Liang et Jing He. "Satisfiabilité avec la dépendance à l'indice". Journal of Computer Science and Technology 27, 668–677 (2012).
https:/​/​doi.org/​10.1007/​978-3-642-17517-6_7

Marcello Benedetti, John Realpe-Gómez et Alejandro Perdomo-Ortiz. "Machines Helmholtz assistées par quantique: un cadre d'apprentissage profond quantique-classique pour les ensembles de données industrielles dans des dispositifs à court terme". Science et technologie quantiques 3, 034007 (2018).
https: / / doi.org/ 10.1088 / 2058-9565 / aabd98

Aram W. Harrow. "Petits ordinateurs quantiques et grands ensembles de données classiques" (2020) arXiv:2004.00026.
arXiv: 2004.00026

Michael A Nielsen et Isaac Chuang. "Calcul quantique et information quantique". Association américaine des professeurs de physique. (2002).
https: / / doi.org/ 10.1017 / CBO9780511976667

Robert B. Griffiths et Chi-Sheng Niu. "Transformée de Fourier semi-classique pour le calcul quantique". Phys. Rév. Lett. 76, 3228-3231 (1996).
https: / / doi.org/ 10.1103 / PhysRevLett.76.3228

Robert Raussendorf et Hans J. Briegel. "Un ordinateur quantique unidirectionnel". Phys. Rév. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

Thomas E O'Brien, Brian Tarasinski et Barbara M Terhal. "Estimation de phase quantique de plusieurs valeurs propres pour des expériences à petite échelle (bruyantes)". Nouveau Journal de Physique 21, 023022 (2019).
https://​/​doi.org/​10.1088/​1367-2630/​aafb8e

Akshay Ajagekar, Travis Humble et Fengqi You. "Stratégies de solutions hybrides basées sur l'informatique quantique pour les problèmes d'optimisation discrète-continue à grande échelle". Informatique et génie chimique 132, 106630 (2020).
https://​/​doi.org/​10.1016/​j.compchemeng.2019.106630

Tianyi Peng, Aram W Harrow, Maris Ozols et Xiaodi Wu. "Simuler de grands circuits quantiques sur un petit ordinateur quantique". Lettres d'examen physique 125, 150504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.150504

Sergey Bravyi, Graeme Smith et John A. Smolin. « Échanger des ressources informatiques classiques et quantiques ». Examen physique X 6 (2016).
https: / / doi.org/ 10.1103 / physrevx.6.021043

Martin Swenne. "Résoudre SAT sur des ordinateurs quantiques bruyants". https:/​/​theses.liacs.nl/​1725 (2019). Thèse de baccalauréat.
https://​/​theses.liacs.nl/​1725

Théodore J Yoder, Guang Hao Low et Isaac L Chuang. "Recherche quantique en virgule fixe avec un nombre optimal de requêtes". Lettres d'examen physique 113 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501

Alessandro Cosentino, Robin Kothari et Adam Paetznick. "Déquantification des formules quantiques lues une fois". Dans la 8e conférence sur la théorie du calcul quantique, de la communication et de la cryptographie (TQC 2013). Volume 22 de Leibniz International Proceedings in Informatics (LIPics), pages 80–92. Dagstuhl, Allemagne (2013). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.80

David A Barrington. "Les programmes de branchement de taille polynomiale à largeur limitée reconnaissent exactement ces langages dans NC1". Journal of Computer and System Sciences 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

Cité par

[1] Casper Gyurik, Chris Cade et Vedran Dunjko, "Vers un avantage quantique via l'analyse des données topologiques", arXiv: 2005.02607, (2020).

[2] Kyle EC Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield et Eleanor Rieffel, « Programmation par contrainte accélérée par le quantum », Quantique 5, 550 (2021).

[3] Casper Gyurik, Chris Cade et Vedran Dunjko, "Vers un avantage quantique via l'analyse des données topologiques", Quantique 6, 855 (2022).

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

On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2023-03-25 02:01:59).

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