Traffic Analysis of Quantum Computing Algorithms Mapped in Multicore Architectures

id178779   TRAFFIC ANALYSIS OF QUANTUM COMPUTING ALGORITHMS MAPPED IN MULTICORE ARCHITECTURES ISAAC LÓPEZ AGUDO Director/a: SERGIABADALCAVALLÉ(Departamentd'ArquitecturadeComputadors) Codirector/a: SAHARBENRACHED Titulació:GrauenEnginyeriaInformàtica(Computació) Memòria del projecte Facultat d'Informàtica de Barcelona (FIB) Universitat Politècnica de Catalunya (UPC) - BarcelonaTech 27/06/2023 Agraïments Primerament voldria agraïr al doctor en Arquitectura de Computadors, Sergi Abadal Cavallé per donar-me l’oportunitat de poder treballar amb ell i tutoritzar aquest treball. També agrair a la estudiant de doctorat Sahar Ben Rached com a codirectora per tot el suport rebut durant el treball, sense ella no hagues estat possible. M’agradaria agrair també al NaNoNetworking Center in Catalonia, centre d’investigació de la UPC, per permetre relitzar la major part dels experiments en un dels seus servidors. Finalment, m’agradaria agraïr a tots els companys que he conegut durant aquesta etapa, amics que sempre han estat donant suport i sobre tot a la meva família per permetre que tot aixó sigui possible, en especial als meus pares Maria Isabel Agudo Villafaina i Enrique López Molina per el seu suport incondicional i per donar-me la millor vida académica possible. Gracias mama, gracias papa. Resum Els processadors quàntics multicores són possiblement la millor solució al problema de l'escalabilitat que afronta la Computació Quàntica més enllà de l'era NISQ. Basant-se en la interconnexió de petits xips formats per desenes o centenars de qubits via una intranet quàntica. Aquest treball per tant busca contribuir modelant aquestes xarxes de xips i estudiar-la en profunditat per obtenir les primeres indicacions per el futur diseny d’arquitectures multicore i compiladors eficients en aquest nou paradigma. Analitzem el tràfic en aquesta xarxa de processadors quàntics basant-nos en diferents mètriques de comunicació, computació i espaciotemporals per qubits i cores que ens permetran caracteritzar el comportament de diferents aplicacions. Resumen Los procesadores cuánticos multicore son vistos como la posible mejor solución al problema de la escalabilidad que afrontará la Computación Cuántica más allá de la era NISQ. La solución se basa en la conexión de pequeños chips robustos formados por decenas o cientos de qubits mediante una intranet cuántica. Este trabajo busca contribuir modelando estas redes de chips i estudiando en profundidad su comportamiento para obtener las primeras indicaciones para el futuro diseño de arquitecturas multicore i compiladores eficientes para este nuevo paradigma. Analizamos el tráfico de esta red de procesadores cuánticos basándonos en diferentes métricas de computación, comunicacion i espaciotemporales para qubits i cores que nos permitirán caracterizar el comportamiento de diferentes aplicaciones. Abstract Quantum multi-core processors are envisioned as the ultimate solution for the scalability of Quantum Computing beyond the NISQ era. Based upon interconnecting ten to hundred qubit chips via a quantum intranet. This work main goal is to contribute into the guidelines to design multicore architectures and developing eficient compilers for this new multicore paradigm by modeling and studying this on chip network for a set of aplications. We analyze the traffic of the network based on performance metrics divided into computing metrics, communication metrics and spatio-temporal metrics for both qubits and cores that characterize the behaviour of the overall execution of algorithms. Sigles BA Model de generació de grafs Barabási-Albert ER Model de generació de grafs Erdös-Renyi NISQ Noisy intermediate-Scale Quantum QAOA Quantum Approximate Optimization Algorithm QAOA BA Algorisme QAOA amb una instància del graf Barabási-Albert com input del problema QAOA WS Algorisme QAOA amb una instància del graf Watts-Strogatz com input del problema QAOA 02 Algorisme QAOA amb una instància del graf Erdös-Renyi amb probabilitat 0.2 com input del problema QAOA 05 Algorisme QAOA amb una instància del graf Erdös-Renyi amb probabilitat 0.5 com input del problema QAOA 08 Algorisme QAOA amb una instància del graf Erdös-Renyi amb probabilitat 0.8 com input del problema VQE Variational Quantum Eigensolver VQE (HEA1) VQE implementat amb un Hardware Efficient Ansatz amb interaccions esglaonades VQE (HEA2) VQE implementat amb un Hardware Efficient Ansatz amb interaccions en paral·lel WS Model de generació de graf Watts-Strogatz (N)x(M) Referent a l’arquitectura, on N es el numero de qubits per core i M el numero de cores Índex INTRODUCCIÓ 1 1.1 Descripció del problema 2 1.2 Objectius 3 1.3 Parts interessades 4 CONTEXTUALITZACIÓ 6 2.1 Conceptes previs 6 2.2 Algorismes 9 2.3 Tecnologies quàntiques 11 2.4 Compilació: Algorisme de Chong 12 ESTAT DE L’ART 14 3.1 Justificació de la tria 16 METODOLOGIA 17 4.1 Metodologia de recerca 17 4.2 Strong scaling i Weak scaling 18 4.3 Algorismes estudiats 19 4.3.1 Algorismes quàntics 19 4.3.2 Algorismes quàntics variacionals 22 4.5 Compilació d’algorismes 25 4.6 Mètriques 27 RESULTATS 30 5.1 Traces 30 5.2 Comunicació i computació 33 5.3 Burstiness 34 5.4 Core Hotspotness 35 5.5 Operacions Intra-core i Teleportacions per qubit 36 5.6 Operacions Intra-core per core 38 5.7 Escalabilitat 40 5.7.1 Strong Scaling 40 5.7.2 Weak Scaling 42 CONCLUSIONS 45 6.1 Discussió 47 6.2 Treball futur 47 REFERÈNCIES 48 Índex de figures 1.1 Arquitectura processador multicore quàntic ……………...……………………………………… 3 2.1 Bloch Sphere …………………………………………...………………………………………… 6 2.1 Portes quàntiques ……………………………………...…………………………………………. 7 2.1 Algorisme de teleportació ……………………………...………………………………………… 8 2.1 Mapejat d’un circuit a un xip de 7 qubits ……………..…………………………………………. 9 2.4 Algorisme de Chong ………………………………….………………………………………… 12 3 Roadmap d’IBM ……………………………………….………………………………………… 14 4.1 Diagrama de flux de l’eina utilitzada ………………..………………………………………….. 18 4.3.1 Circuit Cuccaro adder …………………………….………………………………………….. 20 4.3.1 Circuit GHZ State ……………………………….……………………………………………. 20 4.3.1 Circuit Grover ………………………………….……………………………………………... 21 4.3.1. Circuit QFT …………………………………….…………………………………………….. 21 4.3.1. Circuit QPE …………………………………….…………………………………………….. 22 4.3.2 Estructura dels VQA …………………………….……………………………………………. 23 4.3.2 Ansatz per VQE ………………………………….…………………………………………… 24 4.3.2 Estructura del Ansatz per QAOA ………………..……………………………………………. 24 4.3.2 Ansatz per QAOA ………………………………..…………………………………………… 25 4.5 Model ER …………………………………………..…………………………………………… 26 4.5 Model WS …………………………………………..……………………………………………26 4.5 Model BA …………………………………………..…………………………………………… 27 5.1 Traces Cuccaro adder ……………………………..…………………………………………….. 31 5.1 Traces QFT ……………………………………………………………..……………………….. 31 5.1 Traces VQE (HEA1) …………………………………………………..………………………... 32 5.1 Traces GHZ ……………………………………………………………..………………………. 32 5.1 Traces comparatives QFT ……………………………………………….……………………… 33 5.1 Traça QAOA …………………………………………………………….……………………… 33 5.2 Ratios comm. vs comp. ………………………………………………….……………………… 34 5.3 Burstiness QAOA ……………………………………………………….……………………… 35 5.4 Core Hotspotness ……………………………………………………….………………………. 35 5.5 Distribució d’operacions per qubit VQE ……………………………….………………………. 36 5.5 Distribució d’operacions per qubit Grover …………………………….……………………….. 37 5.5 Distribució d’operacions per qubit QFT ……………………………….………………………. 37 5.6 Distribució d’operacions per core QAOA …………………………….………………………. 38 5.6 Distribució d’operacions per core VQE i Cuccaro adder …………….……………………….. 39 5.6 Distribució d’operacions per core Grover …………………………….………………………. 39 5.7 Slowdown, parallelization speedup i comp. vs com. per Strong scaling ………………………. 40 5.7 Hotspotness i nombre màxim d’operacions per Strong scaling ……………………………….. 41 5.7 Burstiness i localitats temporal i espacial per Strong scaling ………………………………….. 41 5.7 Slowdown, parallelization speedup i comp. vs com. per Weak scaling ……………………….. 42 5.7 Hotspotness i nombre màxim d’operacions per Weak scaling ………………………………… 43 5.7 Burstiness i localitats temporal i espacial per Weak scaling …………………………………… 43 6 Mètriques de computació ………………………………………………………………………… 46 6 Mètriques de comunicació ……………………………………………………………………….. 46 Capítol I INTRODUCCIÓ La computació quàntica és una ciència emergent que promet una capacitat de processar informació sense precedents, obrint les portes a resoldre problemes complexos que són intractables per ordinadors convencionals i fins i tot, per superordinadors. El ‘processador quàntic’ va ser imaginat per primer cop per Richard Feyman [1], un dels millors físics dels últims segles. Ho va descriure com una màquina capaç de replicar les lleis de la natura en un sistema quàntic. Això ha donat lloc a múltiples investigacions sobre com implementar i dissenyar aquest processador quàntic de manera eficient. Des de fotons polaritzats i trapped ions fins a circuits superconductors. L’interès per aquesta tecnologia ha crescut de manera notòria durant els últims anys principalment per l’aparició de nous algorismes que fan ús d’aquestes extraordinàries propietats de la mecànica quàntica per resoldre problemes de manera significativament més ràpida que les millors solucions clàssiques actuals. Des de Deutsch-Jozsa [67], passant per Shor [18,19] fins a arribar als algorismes quàntics variacionals [42]. La computació quàntica es troba encara en el seu naixement però ja s’han pogut obtenir resultats sorprenents que avalen el potencial del qual presumeix, com per exemple, l’anomenat ‘quantum advantage’ de Google demostrant que ordinadors quàntics van ser capaços de resoldre un problema de manera més ràpida que un ordinador clàssic [2, 58]. Amb tota aquesta potència de càlcul s’espera que els ordinadors quàntics puguin resoldre problemes complexos en diferents àrees com la física, la química [68], finances, salut [69], aprenentatge automàtic, etc. obrint la porta a noves ciències i descobriments. Actualment, ens trobem en l’era Noisy Intermediate Scale Quantum (NISQ) [22], xips que contenen com a màxim un parell de centenars de qubits. Tecnologies prematures per a la implementació dels qubits donen lloc a molts errors per la falta d’aïllament d’aquest delicat sistema. Per tant, no s’ha pogut extreure tot el potencial possible fent així inpràctics els xips actuals per resoldre problemes reals. 1 CAPÍTOL I - INTRODUCCIÓ La clau per construir dispositius que tolerin aquestes tasses d’errors passa per incrementar el nombre de qubits per compensar els errors produïts per les interaccions del sistema quàntic amb l’exterior. No obstant, afegir un nombre elevat de qubits en un espai reduït d’un únic processador resulta en més errors deguts al pobre aïllament entre qubits [66], a més de la complexitat afegida d’incrementar tots els sistemes de control necessaris per cada qubit. Són per aquests motius pels quals les arquitectures single-processor no són la millor manera d’escalar els dispositius actuals més enllà de l’era NISQ. Per tant, la proposta d’arquitectures multicore sembla prometedora encara que afronta els seus problemes. L’objectiu d’aquest treball és explorar diferents aplicacions en diferents arquitectures i poder caracteritzar el seu comportament en aquesta xarxa de processadors per poder donar les primeres indicacions en el disseny d’algorismes i processos de compilació per dispositius modulars de gran escala i poder contribuir en l’objectiu comú de construir ordinadors quàntics pràctics. 1.1 Descripció del problema El major problema que afronta actualment la computació quàntica és la falta de qubits, es necessita un nombre de qubits significativament més gran dels que es disposen actualment, per a poder resoldre problemes reals. El no-cloning theorem comporta no disposar d’una memòria tal com es coneix en computació clàssica. És a dir, no es poden copiar ni guardar estats en memòria per processar-los posteriorment, això ens limita els temps d’execució, ja que ha de ser inferior al temps de coherència del qubit, el temps màxim que un qubit pot estar actiu. Aquests són els problemes que defineixen l’era actual en la qual es troba la computació quàntica, l’era NISQ. Aconseguir un nombre elevat de qubits requereix de moltes condicions. Primer, els qubits són molt sensibles, per tant, has d’aconseguir aïllar-los els uns dels altres i de possibles alteracions del món exterior, per fer-ho es necessita una sèrie hardware que escala amb el nombre de qubits en un espai reduït. Segon, els qubits necessiten estar a temperatures molt i molt baixes [14] sigui amb sistemes criogènics o mitjançant altres tecnologies, a mesura que el nombre de qubits augmenta és més difícil mantenir la temperatura òptima de treball donat que es necessita refredar un volum d’espai més gran. Per tant, hi ha un problema evident en l’integració de més qubits. Una de les solucions que s’està plantejant és l'ús de processadors quàntics multicore. Aquesta solució es basa en la interconnexió de múltiples processadors quàntics que poden operar de forma robusta i fiable per tal de produir l’efecte d’estar treballant amb un gran nombre qubits en conjunt, la Figura 1 mostra un esquema de com es podria crear aquesta xarxa de processadors quàntics. Un exemple que dona suport a aquesta solució és el roadmap d'IBM [15] on al 2022 van posar-se com a objectiu aconseguir un nombre major de qubits fent ús d’arquitectures multicore (Figura 7, pàgina 14). 2 CAPÍTOL II - CONTEXTUALITZACIÓ A sota podem veure com es fa el mapping dels qubits virtuals (qi) a qubits reals (Qi). Podem observar com en temps de compilació s’ha afegit una SWAP gate (entre q3 iq5) per tal de poder fer les operacions CNOT entre qubits q1,q5 i qubits q5, q6 (encerclades en vermell) ; donat que en el chip, Q5 no té connectivitat amb Q1 ni Q6. Fig. 5 Mapejat d’un circuit a un xip de 7 qubits. Amunt a l’esquerra es mostra el graf d’interacció del circuit. A sota a l’esquerra podem veure el circuit original. A la part superior centre/dreta es mostra la topolgia del xip.. A sota es mostra el circuit resultant al compilar el circuit original tenint en compte la topologia del xip. [Font: Interaction graph-based profiling of quantum benchmarks for improving quantum circuit mapping techniques [25] ] 2.2 Algorismes A continuació s'introduïxen els algorismes concrets que s'analitzaran en aquesta tesi. La seva implementació i visualització del circuit es presenta més endavant en la Secció 4.3. Cuccaro adder L'algorsime de Cuccaro implementa un operador aritmètic per sumar números de la mateixa mida en nombre de bits per ordinadors quàntics. L’algorisme es basa en el concepte de ripple-carry necessitant un qubit ancilla (qubits extra necessaris per poder satisfer els requisits de reversibilitat) i aplicant de manera consecutiva portes CNOT i CCNOT (conditional NOT i double conditional NOT) agrupades en blocs anomenats Majority (MAJ) i UnMajority and Add (UMA). GHZ State L’estat de Greenberger-Horne-Zeilinger (GHZ) [57] ens permet crear un estat de màxim entrellaçament entre tots els qubits del circuit per acabar reproduint l’estat equiprobable: 9 CAPÍTOL II - CONTEXTUALITZACIÓ (∣00…0⟩+∣11…1⟩) 2 La profunditat d’aquest circuit també escala de manera lineal com l’algorisme de Cuccaro. Grover L’algorisme de Grover va ser un dels primers algorismes quàntics proposats. Ens permet cercar un element en una base de dades no ordenada amb un speed up quadràtic respecte a la solució clàssica. Els algorismes de cerca són extremadament útils per resoldre la majoria de problemes reals i és utilitzat com a subrutina d’altres algorismes amb moltes aplicacions en l’àrea de l’aprenentatge automàtic. L’algorisme efectua dos grans blocs d’operacions coneguts com l’Oracle i el Difusor. L’Oracle és capaç de ‘detectar’ l’estat que s’està buscant i el Difusor fa augmentar la probabilitat de mesurar aquest estat. QFT Aquest algorisme implementa la transformada de Fourier discreta per dispositius quàntics mitjançant diverses codificacions en la funció d’ona que representa el teu sistema quàntic. És una subrutina essencial per altres algorismes quàntics com per exemple el famós algorisme de Shor per factoritzar números o l’algorisme de Quantum Phase Estimation (QPE). Les implicacions d’aquest algorisme són molt diverses i essencialment és una part fonamental per algorismes que necessiten un gran nombre de qubits per resoldre problemes reals com els algorismes esmentats anteriorment. En concret l’algorisme de Shor que ens permet solucionant problemes logarítmics discrets, amb una implicació clau en el món de la criptografia i ciberseguretat. QPE L’algorisme de QPE té una importància similar al QFT i a més és també una de les subrutines de l’algorisme de Shor. Ens permet estimar la fase de l'eigenstate d’un operador unitari. Una de les altres aplicacions d’aquest algorisme recau en l’obtenció dels eiguenstates i eiguenvalues d’un sistema quàntic de manera exacta. Amb aplicacions importants en química molecular. S’ha escollit aquest algorisme donada la seva complexitat on la profunditat del circuit escala de manera exponencial amb el nombre de qubits. VQE El Variational Quantum Eiguensolver (VQE) és un algorisme híbrid dissenyat per trobar els estats de mínima energia d’un Hamiltonià. El Hamiltonià no es mes que la descripció de manera matemàtica de tota l’energia d’un sistema. Té importants aplicacions en el sector de la química. No obstant, al ser un algorisme híbrid, el seu potencial està reduït però a canvi podem obtenir solucions per problemes més grans degut a que la complexitat del circuit no escala de manera exponencial com QPE. 10 CAPÍTOL II - CONTEXTUALITZACIÓ Comparem aquests dos algorismes donat que es poden arribar a utilitzar per resoldre mateixos problemes concrets, no obstant són molt diferents ja que QPE sempre et dona una solució exacta mentre VQE ha de convergir a una solució. QAOA El Quantum Approximate Optimization Algorithm (QAOA) és un altre algorisme híbrid dissenyat per resoldre problemes d’optimització combinatoris. Per fer-ho es formalitza el problema d’optimització com una funció objectiu que cal maximitzar o minimitzar, l’algorisme després construeix un circuit parametritzat a partir dels Hamiltonians i la funció objectiu. Al Capítol IV es descriuen de manera més il·lustratives les implementacions d’aquests dos últims algorismes com dels algorismes quàntics variacionals (VQA). 2.3 Tecnologies quàntiques Hi han diferents tecnologies per obtenir un qubit amb les seves avantatges i inconvenients. A continuació es presenten dos tipus de tecnologies per dissenyar el hardware necessari per obtenir un ordinador quàntic. Donat que aquest treball estudia les possibles futures comunicacions en arquitectures multi-core també es contextualitza diferents protocols de comunicació per transferir informació en sistemes quàntics. Superconducting qubits Aquesta tecnologia implementa qubits amb circuits superconductors. Un qubit s’implementa amb un circuit superconductor que formi un cercle, el corrent del circuit girarà en un sentit o l'altre. Aquests circuits permeten simular un àtom i per tant tenen les mateixes propietats com superposició entrellaçament, etc. Aquest tipus de qubits necessiten temperatures properes als 0 Kelvin per tant necessiten unes condicions molt específiques per poder treballar de manera òptima, en cas contrari només tindríem un circuit de corrent normal sense cap propietat quàntica. D’altra banda, el seu reduït tamany ens permet una possible major escalabilitat i millors maneres de fer que diferents qubits interactuïn. Ion-trapped qubits Per altra banda tenim els Ion-trapped qubits on els qubits són ions per tant partícules físiques que ja de per si mostren un comportament quàntic, per aïllar els qubits es necessita encapsular els ions entre camps electromagnètics. Aquest tipus de tecnologia necessita també mantenir una temperatura baixa i controlada però no s’aconsegueix amb sistemes criogènics sinó amb làsers que interactuen amb els ions de tal manera que la seva energia va disminuint. Pel contrari, la capacitat d’escalabilitat d’aquests dispositius és molt reduïda actualment i la interacció entre qubits és més costosa d’implantar donat que els ions estan fortament aïllats i, per tant, aïllats entre ells també. 11 CAPÍTOL II - CONTEXTUALITZACIÓ Comunicacions quàntiques Les comunicacions quàntiques tenen com a objectiu principal moure informació quàntica utilitzant les lleis i principis de la mecànica quàntica. Com tot protocol de transmissió d’informació es busca transmetre informació entre dues parts interessades de manera segura. Pel simple fet de tractar amb informació quàntica alguns dels problemes que han de solucionar protocols de transmissió clàssica són inexistents, un exemple d’això seria el problema de l'eavesdropping [59] on hi ha ‘observadors’ externs que poden obtenir informació simplement observant el canal de transmissió, això no seria un problema per transmissions quàntiques donat que un estat quàntic en si està ‘encriptant’ informació, per tant, per poder observar la informació que s’està transmetent l’atacant hauria de mesurar els qubits cosa que alteraria el resultat final. Aquest últim exemple serveix per explicar el protocol Quantum Key Distribution (QKD) [60] i perquè és segur. Altres protocols són els que fan ús d’un model d’entrellaçament i realitzar l’algorisme de teleportació o algun altre variant d’aquest. 2.4 Compilació: Algorisme de Chong Per la correcta compilació en arquitectures multicore es necessita un algorisme de mapejat de qubits adaptat. Una de les solucions proposades és l’Algorisme de Chong [24].En aquest apartat explicarem breument la idea de l'algorisme per tenir un major coneixement de tot el procés de compilació. Fig. 6 Algorisme de Chong. a) Mostra el circuit quàntic amb les tres finestres de temps resaltades. b) Graf d’interacions total c) Graf d’interaccions per finestra de temps (pesos de les arestes no calculats encara) [Font: Presentació de Pau Escofet ] 12 CAPÍTOL II - CONTEXTUALITZACIÓ L’objectiu de l'algorisme és assignar un grup de qubits a un core a cada finestra de temps i assegurar que dos qubits que han d’interactuar en la segona finestra de temps estiguin en el mateix core. A la Figura 6 podem veure com el circuit té tres finestres de temps, per tant, s'obté un graf d’interaccions per cada finestra. Imaginem que tenim que mapejar els 4 qubits en una arquitectura 2x2, llavors de manera intuïtiva podem veure quines serien les particions a cada finestra de temps. No obstant particionar aquest graf té una sèrie de restriccions, les particions han de tenir sempre el mateix tamany i els moviments possibles únicament són intercanvis d’elements entre dues particions. El factor que diferencia l’algorisme de Chong és que les arestes dels grafs tenen pesos i aquests pesos es calculen a partir de les interaccions actuals però també tenint en compte interaccions futures. 13 Capítol III ESTAT DE L’ART L’estat de l’art en computació quàntica multicore és molt nova i recent. Com s’ha comentat abans, IBM [15] es va posar l’any 2022 com aobjectiu principal l’ús de tecnologies multicore com mètode principal d’obtenció de més qubits, a la Figura 7 podem veure el seu roadmap. Pel que fa a com hauria de ser l'arquitectura dels processadors multicore del futur s’han realitzat diferents treballs [21,22,23] per poder assolir una arquitectura full stack amb el processador quàntic i el processador clàssic encarregat de controlar el fluxe de comunicacions a part de la intranet quàntica per poder transmetre informació en el nostre sistema quàntic. Un cop vist les possibles arquitectures que poden tenir els xips multicore quàntics, un altre problema que sorgeix és la compilació dels algorismes quàntics en aquest tipus d’ordinadors. El compilador ha de ser capaç de garantir la correcta execució del programa, per tant, s’haurà d'encarregar de mapejar cada qubit a un processador i gestionar les comunicacions entre cores. Una de les principals idees per poder aconseguir això és tractar els algorismes quàntics com grafs [24,25]. L’objectiu darrere aquesta idea és poder representar els qubits com nodes i les connexions com les interaccions entre qubits, un cop definit el graf, realitzar una partició i assignar cada partició a un core. Fig. 7 Roadmap d’IBM. Veiem com els ordinadors ‘Crossbill’, ‘Heron’ o ‘Flamingo’ tindrán una arquitectura multicore. [Font: Web d’IBM [55] ] 14 CAPÍTOL III - ESTAT DE L’ART S’han fet diverses investigacions sobre possibles algorismes de mapeig, una de les més importants és l’algorisme proposat per F.Chong i investigadors de la universitat de Chicago (veure Secció 2.4) [24].No obstant es fan unes assumpcions no gaire realistes donat que s'assumeix que es disposa d’una arquitectura on tots els cores estan connectats entre ells perfectament i on només s'assigna qubits a cores però no es mapeja els qubits a un qubit en concret dins del core. Per tant, s’estan investigant altres possibles mètodes de partionament dels grafs com l'ús de GNN [26], com per exemple l'estudi que està realitzant el grup BNN [27] oen maneres d’estendre l’algorisme de Chong com el que està investigant l’alumne de la UPC Pau Escofet [28] on intenta estendre l’algorisme per tal que un cop assignats els qubits que aniran a cada core, fer un mapeig eficient també a l’hora d’assignar els qubits virtuals als qubits reals dintre del core. Hi han articles com SupermaQ [52] on es realitza benchmarking amb diferents aplicacions però amb un nombre molt reduït de qubits i en ordinadors quàntics d’un únic processador, per tant les mètriques utilitzades per quantificar el rendiment dels diferents algorismes no inclouen comunicacions. S’han desenvolupat eines per a l'anàlisi de tràfic en processador multicore quàntics [29] i altres estudis a més baix nivell sobre les comunicacions entre cores, és a dir comunicacions bàsiques d’informació quàntica a petita escala o curta distància [30]. Concretament, en Santiago Rodrigo va desenvolupar l’eina per fer tràfic anàlisis i va dur a terme un primer estudi a una escala reduida i per un conjunt d’algorismes limitat sense incloure algorismes quàntics variacionals (detellats amb més deteniment en la Secció 4.3.2). Aquest treball per tant te com a punt de partida l’estudi inicial d’en Santiago Rodrigo pero ampliant el conjunt d’algorimes a estudiar i sobre tot, sense precedents, estudiar el trafic en aquestes arquitectures ab un nombre molt superior de qubits de l’ordre de milers de qubits abstraient-nos de les diferents implementacions de les comunicacions a nivell de hardware i centrant-nos en el comportament dels algorismes al ser executats en arquitectures multicore. 15 CAPÍTOL III - ESTAT DE L’ART 3.1 Justificació de la tria L’eina escollida per aquest treball és l’eina desenvolupada per en Santiago Rodrigo membre del grup de recerca N3Cat [20] en el treball mencionat anteriorment [29]. S’ha decidit l’ús d’aquesta eina donat que és flexible a diferents dissenys o topologies del possible processador, és a dir, ens permet simular com resultarien les traces en diferents arquitectures. Amés, utilitza OpenQL que té integrat l’algorisme de Chong [24] per compilar i mapejar els qubits. Aquesta eina s’ha escollit per altres motius donat el curt termini d’aquest treball. S’ha considerat que utilitzar una eina desenvolupada per un investigador d’aquesta universitat i membre del grup N3Cat ens permet una fàcil comprensió sobre el funcionament de l’eina i una bona comunicació amb el desenvolupador per resoldre qualsevol dubte. També es justifica la tria de l’ús d’OpenQL ja que implementa l’algorisme de Chong i ens proporciona moltes facilitats per poder automatitzar processos. 16 Capítol IV METODOLOGIA Tot el projecte està realitzat amb python 3.8 utilitzant la llibreria OpenQL v0.10.0 amb la integració de l’algorisme de Chong (no present a la versió principal en el moment de realització d’aquest projecte sinó en la versió de desenvolupament [56]). A més d’altres llibreries per poder visualitzar millor els nostres resultats. Per poder realitzar quest treball s’han implementat nous algorismes a l’eina de treball seleccionada (vista a la Secció 1.3) que són tots els algorismes variacionals quàntics, l’estat GHZ i una nova implementació del QFT inspidada en la versió de qiskit diferent a l’existent. També s’ha millorat i adaptat tot el sistema per generar de manera automatica les prataformes per poder estudiar el tràfic amb un conjunt de arquitectures més ampli. 4.1 Metodologia de recerca A continuació es descriu de manera més detallada com es farà ús de totes les eines mencionades i el procés d’obtenció d’un traça. Podem visualitzar com seria el procès d’obtenció de traces a la Figura 8. ●Representar l’algorisme o circuit quàntic que es vol estudiar amb alguna estructura de dades com a Intermediate Representation (IR). ●Generar un script de python per tal que la nostre IR passi a tenir un format adequat per que OpenQL pugui fer la compilació [54]. ●Generar la plataforma on es vol mapejar el circuit. La plataforma ha d’especificar el tipus de portes quàntiques que suporta amb altres dades com per exemple la duració de les operacions en cicles, la connectivitat entre qubits o la topologia dintre del core, el nombre de cores, el nombre de qubits per core, etc[54]. En l’ Annex E s’adjunta un template de la plataforma utilitzada. Es suposarà una topologia amb connectivitat total entre qubits i entre cores. ●Un cop implementada la plataforma i generat el script OpenQL, s’executa el script i OpenQL generarà el codi en OpenQASM afegint operacions de teleportació i SWAPs necessaris per l’execució en una plataforma multicore. A més, es generen altres arxius de processos interns que també proporcionen informació rellevant com el mapeig final dels qubits virtuals a qubits físics o el nombre total en cicles que cada qubit està actiu. 17 CAPÍTOL IV - METODOLOGIA ●Un cop el codi en OpenQASM és generat, es fa un parsing de l’arxiu i es va comptabilitzant tots els tipus d’operacions, en quin moment de l’execució ocorren, teleportacions i comunicacions, quins qubits interaccionesn entre ells, quins cores són els que contenen els qubits que operen entre ells, el temps que està cada qubit a un core i més informació necessària per poder fer l’anàlisi de tràfic (veure secció de mètriques). Tot això es guarda en diferents estructures de dades per poder treballar de manera més còmoda i poder processar les dades posteriorment. ●Finalment s’analitza tota la traça i es calculen les mètriques que definim més endavant. Les mètriques obtingudes per cada algorisme són visualitzades de diferent manera per tots els algorismes. ●Un cop hem pogut estudiar i entendre el rendiment dels algorisme respecte a les mètriques definides, realitzem estudis de strong i weak scaling per cada aplicació. Fig. 8 Diagrama de flux de l’eina utilitzada. [Font: Characterizing Qubit Traffic of a Quantum Intranet aiming at Modular Quantum Computers. [29] ] 4.2 Strong scaling i Weak scaling A continuació es defineixen breument en què consisteixen els estudis de strong i weak scaling ies descriu com s’han realitzat en aquest treball. -Strong scaling mesura com de bé escala un problema si augmentem la seva dimensió mantenint el tamany de les particions constant. En el nostre cas mantindrem fix el nombre de qubits per core i incrementarem el nombre de cores, incrementant així el nombre total de qubits. Per tant aquest tipus d’estudi escala l’algorisme alhora que escala l’arquitectura. -Weak scaling pretén estudiar com de bo és l’algorisme al ser particionat. És a dir, es manté una mida constant del problema i augmentem el nombre de particions. En el nostre cas tindrem un nombre fixat de qubits total i dividirem l’algorisme en diferents parts de tal manera que el nombre de cores i els qubits per cores variaran. Per tant en aquest cas només escalarà l’arquitectura, el circuit de l’algorisme serà sempre el mateix. 18 CAPÍTOL IV - METODOLOGIA Fig. 17 Ansatz per QAOA. Diferents implementacions del PH i MH, la implementació escollida ha estat el ‘QAOA’ estandard, La implementació consta del bloc de portes de la figura c per cada aresta del graf. [Font: An Expressive Ansatz for Low-Depth Quantum Optimisation. [53]] 4.5 Compilació d’algorismes Els circuits generats pels algorismes són els mateixos presentats en la secció d’algorismes. Com hem comentat prèviament, els algorismes quàntics variacionals són dependents de l'input del problema, és a dir, no tan sols afecten al estat inicial sinó a la construcció del circuit. Per VQE hem optat pel Hardware Efficient Ansatz que no depèn de la instància del problema. No obstant pel QAOA hem de crear un circuit diferent segons el problema i segons l’input del problema, com hem comentat implementarem circuits per resoldre el problema de MaxCut. Per generar els grafs pel nostre problema de MaxCut utilitzarem tres models de generació de grafs diferents. Aquests models ens permeten generar grafs que compleixen diferents propietats presents en xarxes reals. El model Erdös-Renyi (ER) és un model de graf que presenta el que es coneix com a small world phenomenon [62], Figura 18.Aquesta propietat ens indica que el diàmetre del graf és petit, és a dir, qualsevol node pot tenir un camí cap a un altre node del graf format per un nombre petit d’arestes, sovint del orde de . 𝑂(𝑙𝑜𝑔 𝑛) 25 CAPÍTOL IV - METODOLOGIA Fig. 18 Model ER. Exemple de graf generat amb el model Erdos-Renyi[Font: M. Francesche[63] ] També s’utilitzarà aquest model per generar grafs esparsos i densos variant la probabilitat d’aparició d’arestes entre nodes. El model Watts-Strogatz (WS) és un model que sota unes condicions especifiques [63] ens petmet generar grafs que tinguin la propietat del small world amés d’un clustering coefficient elevat, Figura 19. El clustering coefficient ens indica que el graf presenta transitivitat en els nodes, si un node estè connectat a un segon node i aquest a un tercer node, el primer i el tercer node molt possiblement estiguin connectats també, conegut a les xarxes reals com ‘l’amic del meu amic és el meu amic’. Fig. 19 Model WS. Exemple de graf generat amb el model Watts-Strogatz[Font: Dr.Serguei A. Mokhov[64] ] Per últim, el model Barabási-Albert (BA) ens permet generar grafs que modelin el fenomen conegut com preferencial attachment [63], a part del small world phenomenon. Aquesta propietat fa que la distribució dels graus dels nodes segueixi una distribució power-log, on un nombre petit de nodes tenen la majoria de les arestes connectats a ells formant el que s’anomenen hubs. Aquest fenomen es presenta a les xarxes socials reals amb l’expressió de ‘rich get richer’, la Figura 20 mostra un exemple d’un graf generat a partis d’aquest model. 26 CAPÍTOL IV - METODOLOGIA Fig. 20 Model BA. Exemple de graf generat amb el model Barabási-Albert[Font: I, Keiono, CC BYSA 2.5[65]] 4.6 Mètriques Les mètriques seleccionades s’han escollit tenint en compte altres treballs similars de benchmarking d’algorismes quàntics [52], concretament les relacionades amb el critical depth i qubit hotspotness. La resta de metriques han sigut definides i modificades a partir de les que es presenten de manera introductoria al trball d’en Santiago Rodrigo [29] donat que no s’havien estudiat prèviament les arquitectures multicore d’aquesta manera ni a aquesta escala. -Slowdown: Increment en el temps d’execució de l’execució multicore 𝑇𝑒𝑥𝑒𝑐 𝑚𝑢𝑙𝑡𝑖−𝑐𝑜𝑟𝑒 respecte executar en un únic core, . Els ordinadors quàntics són diferents 𝑇𝑒𝑥𝑒𝑐 𝑠𝑖𝑛𝑔𝑙𝑒−𝑐𝑜𝑟𝑒 als clàssics ila definició de slowdown i paral·lelització són també diferents. Els dispositius quàntics ja ofereixen una paral·lelització total entenent-ho com l’aplicació de portes quàntiques de manera simultània a tots els qubits, per tant les arquitectures single-core són les que aconsegueixen el temps d’execució mínim. - Parallelization speed-up:El nombre mitjà d’operacions que s’executen en paral·lel en l’execució multicore respecte a l’execució en un únic core . 𝑁𝑜𝑝𝑠 𝑚𝑢𝑙𝑡𝑖−𝑐𝑜𝑟𝑒 𝑁𝑜𝑝𝑠 𝑠𝑖𝑛𝑔𝑙𝑒−𝑐𝑜𝑟𝑒 Aquesta mètrica a diferència de l’anterior no té en compte si s’han fet diverses operacions a l’hora donat que no depèn del temps sinó del nombre operacions realitzades. 27 CAPÍTOL IV - METODOLOGIA - COMM-to-COMP ratio:La relació entre les operacions de comunicació que executa un qubit a les operacions de computació , normalitzat. Així podem veure 𝑛𝑡𝑒𝑙𝑒𝑝𝑠 𝑖 𝑛𝑜𝑝𝑠 𝑖 si un qubit s’està utilitzant només per moure informació a través dels cores o si es queda en un mateix core computant. Si el ràtio s’aproxima a 1 podem afirmar que les computacions són dominants, en cas contrari si s’aproxima a -1 diem que les comunicacions són dominants i finalment si ens aproximem a 0 vol dir que l’arquitectura aconsegueix balancejar les comunicacions i computacions. - Core/Qubit hotspotness: Cores o qubits que atreuen la majoria de les comunicacions entre cores. Volem evitar que les comunicacions o recursos del processador no es distribueixin de manera uniforme per tant poder detectar quins cores o qubits estan sent utilitzats per les comunicacions i poder estudiar com evitar estressar el sistema donat que pot donar lloc a la pèrdua d’informació i a la decoherència dels qubits. Estudiem la distribució de les operacions que realitzen els qubits i les comunicacions que realitzen els cores de la següent manera, donant una major importància a la qubit hotspotness donat que són els encarregats de contenir la informació. La mètrica es calcula a partir del quocient entre la variança sobre la mitjana , per cores tindrem σ2µ en compte les teleportacions i per els qubits tindrem en compte les 𝑡𝑒𝑙𝑒𝑝/𝑐𝑜𝑟𝑒 operacions . 𝑜𝑝𝑠/𝑝ℎ𝑦𝑠𝑞𝑢𝑏𝑖𝑡 - Critical depth:És una mètrica utilitzada de manera recurrent per caracteritzar l’eficiència d’un circuit. Es determina a partir del camí màxim en termes d’operacions des dels qubits d’entrada fins als de sortida. Reduir aquest camí crític és crucial per ja que no només pot arribar afectar a les comunicacions i a la xarxa de processadors quàntics sinó que també a la correctesa dels càlculs. Per tant, predir la seqüència d’operacions més llarga aplicada a un qubit ens ajuda a quantificar el soroll resultant. - Burstiness: Relaciona el nombre de teleportacions que ocorren en la mateixa finestra de temps. És a dir, diem que un sistema té una burstiness elevada si donat un moment de l'execució s’experimenta de manera sobtada un increment en les teleportacions durant breus períodes de temps, indicant així una distribució no uniforme de les teleportacions durant l’execució. 28 CAPÍTOL IV - METODOLOGIA Aquest comportament te un gran impacte en el funcionament del sistema, l’assignació i distribució de recursos i en la planificació de les operacions. Es calcula de manera similar al hotspotness de cores on la variança es en funció del temps i la σ2𝑡𝑒𝑙𝑒𝑝(𝑡) mitjana també µ𝑡𝑒𝑙𝑒𝑝(𝑡) -Temporal locality: Estimada analitzant el nombre de teleportacions que ocorren a mesura que varia el nombre de qubits per cores, indicaria quin seria el nombre òptim de cores en que es tindria que particionar uniformement cada algorisme per mantenir una estabilitat en el sistema. Es calcula com el nombre total de teleportacions que 𝑇𝑡𝑠 demanda una arquitectura. -Spatial locality:Estima el temps mitjà que els qubits es quedaran en un mateix core interactuant entre ells, fent computacions intentant maximitzar les intra-core operations i minimitzar les operacions inter-core. Aconseguim també intentar interferir el mínim possible sobre el qubit, crucial pel correcte desenvolupament de l’execució. Es pot calcular com la relació entre el temps mitjà que un qubit està en un core sobre el temps d’execució total . 𝑑𝑞𝑢𝑏𝑖𝑡/𝑐𝑜𝑟𝑒 𝑡𝑒𝑥𝑒𝑐 29 Capítol V RESULTATS En aquest apartat es mostraran els resultats de totes les mètriques obtingudes per cada algorisme i es compararan entre elles. També es mostrarà els resultats del estudis de weak i strong scaling a més de les traces obtingudes per alguns algorismes, la metodologia i els paràmetres exactes per la replicació dels nostres resultats. Tots aquests resultats s’han obtingut amb la configuració de la plataforma especificada a l’Annex E. Només es mostren les imatges mes il·lustratives, podeu trobar totes les figures obtingudes a l’Annex F. La plataforma, mencionada al Capítol III, és la implementació de l’arquitectura de la nostra multi-core QPU (Quantum Process Unit) i és necessària per poder compilar circuits amb OpenQL. La component temporal es mesura en timeslices. Aquestes timeslices són definides com unitats de temps similar als cicles que definim en la duració de les portes definides a la nostra plataforma. Llavors, tots els resultats que es presenten a continuació tindran com a component temporal timeslices i no nanosegons, que seria l’escala típica de temps si executéssim el codi en un ordinador quàntic real d’aquestes característiques. 5.1 Traces Els primers resultats que observem són les traces de la compilació, són importants per veure el comportament dels algorismes. Aquestes traces són obtingudes a partir del codi compilat, es té en compte per cada qubit si està sent utilitzat per computar o per teleportar informació a altres cores. Ala Figura 21 podem observar la traça pel Cuccaro adder.En groc observem les timeslices on el qubit és utilitzat per comunicacions i en vermell si el qubit està sent utilitzat per computacions. Podem observar com les comunicacions triguen un temps elevat en comparació amb les operacions de computació. 30 CAPÍTOL V - RESULTATS Fig. 21 Traces Cuccaro adder. Traça virtual i física per l’algorisme de Cuccaro amb un total de 64 qubits i 4 cores. En vermell els moments que el qubit esta realitzant computacions i groc els moments on realitza comunicacions. Podem observar com tenim traces per virtual qubits iphysical qubits, la diferència és que les traces de qubits vituals són prèvies a aplicar el mapping mentre que la de qubits físics és després del mapping. La important és la traça de qubits físics però la de qubits virtuals també ens pot servir per visualitzar com treballa l’algorisme de mapeig i veure que per certes aplicacions el mapping resultant és bastant directe (Figura 21) mentre que per altres aplicacions les dues traces són bastant diferents, Figura 22. Fig. 22 Traces QFT. Traça virtual i física per l’algorisme QFT amb un total de 64 qubits i 4 cores. Podem observar que en casos com el de Cuccaro adder oQPE, les traces són molt semblants en quant a l’estructura del circuit original es refereix. Indicant així que l’algorisme de mapeig és capaç de mantenir l’estructura original del circuit. Per altres aplicacions ta traça és més caòtica i no ens permet visualitzar de manera tan fàcil l’estructura original, la Figura 22 mostra l’exemple per QFT. 31 CAPÍTOL V - RESULTATS També es poden apreciar per l’algorisme de VQE el nombre de layers que tenim, a la Figura 23 podem observar el nombre de repeticions del bloc principal. Es poden comptar com la seqüència de operacions de computació (línies vermelles esglaonades) es repeteixen 10 i 15 vegades respectivament. Fig. 23 Traces VQE (HEA1). Traça física per l’algorisme VQE HEA1 amb un total de 64 qubits i 4 cores, variant el parametre pper tenir una repetició de 10 i 15 blocs. A partir de la traça també podem començar a veure comportaments diferents en l’escalabilitat. El GHZ és un exemple, veiem com al tenir una arquitectura de més de 8 cores amb un tamany fixe de 16 qubits per core, les traces són diferents, Figura 24. En contrast, a la traces com la de Cuccaro per 512 qubits es manté molt semblant comparada amb la traça per un menor nombre de qubits. Fig. 24 Traces GHZ. Traça física per l’algorisme GHZ. A l’esquerra amb un total de 64 qubits i 4 cores. A la dreta amb 256 qubits i 16 cores Pel cas de QFT ja podem apreciar des de la traça un comportament diferent utilitzant diferents implementacions del mateix algorisme, Figura 25. 32 CAPÍTOL V - RESULTATS Fig. 25 Traces comparatives QFT. Traça física per les dues implementacions de QFT per 128 qubits i 8 cores (implementació QFT qiskit a la dreta) L’algorisme de QAOA al dependre de l’input del problema, en aquest cas un graf, s’han realitzat estudis amb diferents tipus de grafs esmentats al Capítol IV. La Figura 26 mostra del model WS on s’obte una traça molt estructurada a diferencia dels altres dos models (figures a l’annex). No obstant, aquestes traces són per instàncies del problema amb un nombre de qubits petit, per tant el graf resultat utilitzant un model de WS és similar a un graf cercle per tant també podem mencionar que per grafs estructurats podem esperar una traça estructurada. Fig. 26 Traça QAOA. Models ER, WS i BA respectivament (les línies horitzontals de la primera traça són d’un error en la visualització) 5.2 Comunicació i computació Per tots els algorismes s’ha calculat el percentatge d'operacions que s’han realitzat durant l’execució de l’algorisme. Tenint en compte si l’algorisme ha sigut capaç de paral·lelitzar comunicacions i computacions, això fa referència a la capacitat de poder fer operacions de computació i comunicació a l’hora. 33 CAPÍTOL V - RESULTATS Fig. 27 Ratios comm. vs. comp. Percentatge de temps que cada algorisme realitza per tipus d’operació. En blau comunicacions, en taronja comunicacions i computació simultaneament i en verd només computació. Algorismes QPE, QFT iVQE HEA2 respectivament per arquitectures 4x4 (QPE) i 16x8 (QFT, VQE HEA2) En la Figura 27 veiem diferents ratios obtinguts per diferents algorismes per 64 qubits. Podem destacar com algorismes com QPE la majoria de temps realitza només computació mentre que algorismes com QFT iVQE tenen un gran nombre de comunicacions, no obtant pel VQE observem com moltes d’aquestes comunicacions es poden executar en paral·lel a les computacions. 5.3 Burstiness Podem apreciar diferents comportaments per les distribucions de les comunicacions durant el transcurs de l’execució del sistema a partir de la traça dels diferents algorismes. Podem comparar les dues implementacions del VQE i obtenim que la segona implementació (HEA2) té una burstiness més elevada donat que hi ha més variació en el nombre de teleportacions durant l’execució, per l’altre cas (HEA1) el nombre de teleportacions es manté més constant en comparació, per tant el sistema s’estressa en menor manera. Per altres aplicacions com Cuccaro, el sistema sofreix un elevat nombre de teleportacions al principi però es manté constant durant la resta de l’execució. De manera similar,el GHZ experimenta clarament el mateix tipus de comportament, pot indicar que al començament de l’execució s’experimenta una espècie de setup. Un comportament similar però de manera inversa es pot apreciar amb el QPE, és al final de l’execució on s’experimenta un increment del nombre de teleportacions, aquestes teleportacions estan justificades a partir de la traça i del circuit original on la part final del circuit inclou com a subrutina el circuit de QFT invertit. En el cas de QFT apreciem diferències en la distribució de teleportacions durant l’execució, la implementació de quiskit té una distribució menys uniforme. Finalment, pel QAOA veiem com novament el comportament depèn del graf d’entrada. Podem observar que pel model ER, la distribució de les teleportacions és més uniforme per grafs més espars respecte a grafs més densos, veure Figura 28. 34 CAPÍTOL V - RESULTATS els qubits de teleportació en aquest últim cas mentre en la implementació de quiskit les teleportacions són distribuïdes de manera més uniforme entre els qubits augmentant així el nombre mitjà de comunicacions dels cores. La resta d’algorismes tenen una tendència molt similar respecte al qubit hotspotness. Fig. 37 Hotspotness i nombre màxim d’operacions per Strong scaling. Respecte el màxim nombre d’operacions per qubit, observem com sempre hi ha una tendència a augmentar el nombre d’operacions màximes que es fa sobre els qubits a excepció de Grover que està justificat per l’estructura del circuit. Per ala mètrica de burstiness veiem a la següent figura com més o menys tots els algorismes presenten un comportament similar encara que Grover sembla tenir una tendència a créixer de manera diferent a la resta. Fig. 38 Burstiness i localitats temporal i espacial per Strong scaling. Finalment, per a la localitat temporal tornem a distingir dos grups entre els circuits més complexos on només hem pogut escalar-los fins 256 qubits i els menys complexos que hem sigut capaços d’arribar als 960. Respecte a la localitat espaial, trobem els algorismes menys complexos més repartits per l’espai mentre que els més complexos tenen un comportament molt similar on els qubits passen molt menys temps dins d’un mateix core indicant possiblement un mapeig pobre, de similar al paralleization speed up. Observant mes detingudament la mètrica que relaciona comunicacions i computació per tots els algorismes (totes les imatges es troben a l’annexe), podem veure com per algorismes com 41 CAPÍTOL V - RESULTATS Cuccaro o Grover gairebé no hi ha variació en el percentatge del tipus d’operacions que es realitza a mesura que escalem. Altres aplicacions sí que experimenten un canvi en aquests ratios com per exemple els VQEs, QFTs i QAOAs, però totes tendeixen a augmentar les comunicacions. 5.7.2 Weak Scaling Per el weak scaling observem com les mètriques de slowdown iparallelization speedup mostren un comportament similar però invertit. Observem com no hi ha una tendència clara en variar el nombre de particions que fem del problema ja que a partir de dos cores la majoria d’algorismes s’estanquen i obtenen el mateix valor constant en ambdues mètriques. Fig. 39 Slowdown, parallelization speed up i comp. vs com. per Weak scaling. Observant la tendència del ratio entre computació i comunicacions veiem que tenim algorismes que pateixen molt poca variació inclús comparat amb arquitectures single-core com Cuccaro o VQE (HEA2) mentre altres decreixen el ratio però a mesura que fem més particions i augmentem el nombre de cores no varia de manera tan pronunciada. A continuació es mostren les tendències en hotspotness per cores i qubits. Podem veure totes les aplicacions tenen una tendència ascendent a excepció del VQE (HEA1) on sembla que particionar el problema ajuda al sistema a distribuir de millor manera les comunicacions. En quant al qubit hotspotness viem com en aquest cas augmentar el nombre de cores disminueix per l’algorisme de Grover. 42 CAPÍTOL V - RESULTATS Fig. 40 Hotspotness i nombre màxim d’operacionsper Weak scaling. Respecte a la tendència de la critical depth podem observar el nombre màxim d’operacions aplicat a un qubit. Esperem un nombre gairebé constant per a tots els algorismes ja que el número d’operacions no hauria de canviar a partir del circuit original donat que la instància del problema sempre té el mateix tamany. Veiem com tots tendeixen a un número constant. Si observem la burstiness ala següent figura, veiem com obtenim una tendència similar al strong scaling a excepció d’algunes instàncies de QAOA. No obstant per la resta d’algorismes sembla que la burstiness augmenta a l'augmentar el nombre de particions menys en el cas del VQE (HEA2) on podem veure que decreix en contrast amb els resultats obtinguts per aquesta mateixa mètrica en el strong scaling. Fig. 41 Burstiness i localitats temporal i espacial per Weak scaling. Ala Figura 41 també podem veure les tendències de localitat temporal iespacial. Algorismes com Grover o Cuccaro no varien res el nombre de teleportacions si incrementem el nombre de particions cosa bastant sorprenent, mentre augmenta per la resta. Respecte a la localitat espacial observem resultats similars al strong scaling, algorismes complexos tendeixen a mantenir els qubits menys temps en els cores i per als altres algorismes el temps que està un qubit en un core sembla ser independent del nombre de cores en el qual particionem el problema. 43 CAPÍTOL V - RESULTATS De manera anàloga al strong scaling, hem observat de manera mes detallada la distribució del tipus d’operacions que s’obtenen al escalar cada algorisme. Podem observar com notòriament per la majoria d’algorismes, un tamany gran del core maximitza el percentatge de temps que estem fent computació exclusivament que és el que voldríem idealment. Grover i especialment GHZ mostren que és amb cores de mides menors obtenim un increment en aquest percentatge de computació. Tant en el Strong scaling com en el Weak scaling podem veure com cada aplicació és diferent, creiem que el disseny d’arquitectures multicore i dels compiladors haurien de maximitzar el temps de computació. Per les comunicacions, un cop el hardware permet la simultaneïtat de múltiples operacions de comunicació i computació alhora, és treball del compilador en minimitzar el nombre de comunicacions o en cas de no poder ser així, poder ser capaç de realitzar la major part d’aquestes en paral·lel amb altres operacions. 44 Capítol VI CONCLUSIONS Hem pogut veure com principalment hi ha dos grups d’algorismes que presenten un comportament similar entre ells per la majoria de mètriques. El que diferencia els dos grups trobats entre les aplicacions seleccionades principalment és la complexitat en el nombre d’interaccions entre qubits i la manera que tenen aquests d’interaccionar. Un exemple clar són les dues implementacions del VQE on s’obtenen diferents rendiments per una estructura on les interaccions entre qubits són esglaonades i repartides en l’espai contra interaccions paral·leles en un curt període de temps. Hem pogut observar que distingim entre dos tipus d’operacions molt diferents, teleportacions i operacions intra-core, relacionades amb comunicació i computació. Donat que les operacions de comunicació són costoses en recursos i en temps, hem d’assegurar-nos de reduir al mínim l’impacte de les teleportacions. S’ha de tenir molt present reduir el temps d’execució al màxim per treballar dins del temps de coherència dels qubits, executar aplicacions que sobrepassin el temps de coherència pot implicar errors d’execució. És per això que considerem la mètrica del ratio entre computacions i comunicacions molt important i representativa. També hem pogut veure alguns algorismes amb diferents implementacions on s’aconsegueixen comportaments diferents, per tant podem concloure també que aquest nou paradigma multicore pot donar lloc a noves implementacions diferents de les actuals que permetin adaptar-se de manera més eficient a les noves arquitectures. Pel weak scaling, hem observat que incrementar el tamany del core té un impacte positiu a l'incrementar el nombre d’operacions de computació. Per poder representar o visualitzar diverses mètriques alhora hem dividit el conjunt de mètriques en dos, les que afecten a les computacions i a les comunicacions. Observem com la majoria d’algorismes, les mètriques de computació escalen d’una manera molt similar amés tendeixen a ocupar tot l’espai, indicant que cada mètrica tendeix a créixer. 45 CAPÍTOL VI - CONCLUSIONS Fig. 42 Mètriques de computació. Mètriques de computació seleccionades a partir de les dades de Strong scaling per Cuccaro i VQE (HEA1) No obstant d’altra banda les mètriques relacionades amb les comunicacions són més variades per algorisme. Veiem ala Figura 43 com les ‘formes’ són diferents indicant una escalabilitat diferent de les mètriques de comunicació pels algorismes. Fig. 43 Mètriques de comunicació. Mètriques de comunicació seleccionades a partir de les dades de Strong scaling per Cuccaro i VQE (HEA1) Per tant, això confirma que les comunicacions són el que diferencia el comportament de cada algorisme en una arquitectura multicore, on novament veiem diferents mètriques involucrades que afecten els diferents actors implicats en l’execució d'un algorisme en una arquitectura multicore: -Els dissenyadors d’arquitectures multicore han de permetre una paral·lelització entre operacions i comunicacions a més de poder permetre tenir nombroses comunicacions a l’hora. Els protocols de comunicació són extremadament crítics, s’ha de seleccionar la millor tecnologia per implementar les comunicacions i permetre el màxim de connectivitat entre cores possible reduint els temps de latència. 46 CAPÍTOL VI - CONCLUSIONS -Els dissenyadors de tècniques de compilació han de desenvolupar compiladors capaços de generar codi que permeti utilitzar totes les avantatges que el hardware proporciona i fer una bona gestió i organització de les comunicacions. Distribuint al màxim la càrrega de treball entre qubits i cores a més d’intentar distribuir les operacions de comunicació de manera uniforme durant l’execució sempre que sigui possible. -Els dissenyadors d’algorismes per buscar implementacions equivalents a les pensades per arquitectures single-core realitzant interaccions entre qubits de diferent manera per ajudar a no estressar el sistema. 6.1 Discussió La computació quàntica s’està tornant cada dia en un tema més interessant per nous investigadors de totes les àrees, noves aplicacions d’aquesta tecnologia s’estan descobrint de manera més freqüent però l’actual era NISQ limita poder explotar-les al màxim. Amb aquest treball esperem ajudar a poder accelerar el desenvolupament de nou hardware que pugui habilitar poder executar totes aquestes aplicacions a gran escala. No només a ajudar en el disseny de noves arquitectures multicore sinó també com explotar-les al màxim per aplicacions concretes. Per això també fan falta compiladors que siguin capaços d’utilitzar tots els recursos que el hardware proporciona de manera eficient, per tant, esperem que aquest treball pugui començar a donar les primeres indicacions sobre quins són els problemes que hauran de solucionar els compiladors moderns. 6.2 Treball futur Durant el transcurs d’aquest treball hem trobat problemes nous i limitacions que podrien donar lloc a treballs futurs. Primerament, estudiar i analitzar el tràfic dels mateixos algorismes en arquitectures multicore però amb diferents topologies, ja que s’ha considerat una connectivitat entre qubits total i si bé en un futur pròxim es podria arribar a tenir xips d’un tamany d’unes poques desenes de qubits amb connexió total, no és el cas dels xips actuals. D’altra banda hem trobat limitacions amb l’ús d’OpenQL a l'escalar a un nombre elevat de qubits. En un futur l’aparició de noves eines de compilació o la millora de les actuals podria permetre elaborar el mateix anàlisis però arribant a un major nombre de qubits. Finalment, es podria ampliar el treball presentat en aquest projecte estudiant altres aplicacions diferents, en especial Algorismes Quàntics Variacionals que són els que més interès desperten actualment en l'era NISQ. 47 REFERÈNCIES [1] Demmer, M., Fonseca, R., & Koushanfar, F. (s. f.). RICHARD FEYNMAN: SIMULATING PHYSICS WITH COMPUTERS. [2] Thomas, A. C. (2020, enero 31). What Is Quantum Supremacy? The Ultimate Engineer. https://medium.com/the-ultimate-engineer/what-is-quantum-supremacy-cb74c37185d7 [3] ¿Qué es un qubit? | Microsoft Azure. (s. f.). Recuperado 26 de febrero de 2023, de https://azure.microsoft.com/es-es/resources/cloud-computing-dictionary/what-is-a-qubit/ [4] Superposition State—An overview | ScienceDirect Topics. (s. f.). Recuperado 26 de febrero de 2023, de https://www.sciencedirect.com/topics/mathematics/superposition-state [5] Quantum Teleportation. (s. f.). Recuperado 26 de febrero de 2023, de https://qiskit.org/textbook/ch-algorithms/teleportation.html [6] Single Qubit Gates. (s. f.). Recuperado 26 de febrero de 2023, de https://community.qiskit.org/textbook/ch-states/single-qubit-gates.html [7] Proving Universality. (s. f.). Recuperado 26 de febrero de 2023, de https://community.qiskit.org/textbook/ch-gates/proving-universality.html [8] Unitary matrix. (2023). En Wikipedia. https://en.wikipedia.org/w/index.php?title=Unitary_matrix&oldid=1136840978 [9] Defining Quantum Circuits. (s. f.). Recuperado 26 de febrero de 2023, de https://community.qiskit.org/textbook/ch-algorithms/defining-quantum-circuits.html [10] Wootters, W. K., & Zurek, W. H. (1982). A single quantum cannot be cloned. Nature,299(5886), Art. 5886. https://doi.org/10.1038/299802a0 [11] Multiple Qubits and Entangled States. (s. f.). Recuperado 26 de febrero de 2023, de https://community.qiskit.org/textbook/ch-gates/multiple-qubits-entangled-states.html [12] La paradoja del gato de Schrödinger. ¿Vivo o muerto? (s. f.). Recuperado 26 de febrero de 2023, de https://www.astromia.com/astronomia/paradojagato.htm [13] Dieks, D. (1982). Communication by EPR devices. Physics Letters A,92(6), 271-272. https://doi.org/10.1016/0375-9601(82)90084-6 [14] Quantum computer chips demonstrated at the highest temperatures ever.New Scientist. Recuperado 26 de febrero de 2023, de https://www.newscientist.com/article/2240539-quantum-computer-chips-demonstrated-at-the-highest-tempera tures-ever/ [15] IBM Quantum roadmap to build quantum-centric supercomputers. (2021, febrero 9). IBM Research Blog. https://research.ibm.com/blog/ibm-quantum-roadmap-2025 [16] Quantum Computing. (s. f.). Intel. Recuperado 26 de febrero de 2023, de https://www.intel.com/content/www/us/en/research/quantum-computing.html [17] Wayback Machine. (2007, enero 27). https://web.archive.org/web/20070127130201/http://theory.lcs.mit.edu/~rivest/rsapaper.pdf [18] Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing,26(5), 1484-1509. https://doi.org/10.1137/S0097539795293172 [19] Shor’s algorithm. (s. f.). IBM Quantum. Recuperado 26 de febrero de 2023, de https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm [20] NaNoNetworking Center in Catalonia—N3Cat. (s. f.). Recuperado 26 de febrero de 2023, de https://www.n3cat.upc.edu/ [21] Brown, K. R., Kim, J., & Monroe, C. (2016). Co-designing a scalable quantum computer with trapped atomic ions. Npj Quantum Information,2(1), Art. 1. https://doi.org/10.1038/npjqi.2016.34 [22] Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum,2, 79. https://doi.org/10.22331/q-2018-08-06-79 [23] Rodrigo, S., Abadal, S., Alarcon, E., Bandic, M., Someren, H. van, & Almudever, C. G. (2021). On Double Full-Stack Communication-Enabled Architectures for Multicore Quantum Computers. IEEE Micro,41(5), 48-56. https://doi.org/10.1109/MM.2021.3092706 [24] Baker, J. M., Duckering, C., Hoover, A., & Chong, F. T. (2020). Time-Sliced Quantum Circuit Partitioning for Modular Architectures. Proceedings of the 17th ACM International Conference on Computing Frontiers, 98-107. https://doi.org/10.1145/3387902.3392617 48 [25] Bandić, M., Almudever, C. G., & Feld, S. (2022). Interaction graph-based profiling of quantum benchmarks for improving quantum circuit mapping techniques (arXiv:2212.06640). arXiv. http://arxiv.org/abs/2212.06640 [26] Menzli, A. (2022, julio 21). Graph Neural Network and Some of GNN Applications: Everything You Need to Know. Neptune.Ai. https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications [27] Barcelona Neural Network Center. (s. f.). BNN-UPC. Recuperado 26 de febrero de 2023, de https://bnn.upc.edu/ [28] Escofet, P., Abadal, S., Alarcón, E., & Almudéver, C. G. (2023). Theoretical Architecture-Based Mapping Algorithm for Multi-Core Quantum Computers. [29] Rodrigo, S., Spanò, D., Bandic, M., Abadal, S., van Someren, H., Ovide, A., Feld, S., Almudever, C. G., & Alarcón, E. (2022). Characterizing Qubit Traffic of a Quantum Intranet aiming at Modular Quantum Computers. Proceedings of the 9th ACM International Conference on Nanoscale Computing and Communication, 1-7. https://doi.org/10.1145/3558583.3558846 [30] Rodrigo, S., Abadal, S., Almudéver, C. G., & Alarcón, E. (2021). Modelling Short-range Quantum Teleportation for Scalable Multi-Core Quantum Computing Architectures. Proceedings of the Eight Annual ACM International Conference on Nanoscale Computing and Communication, 1-7. https://doi.org/10.1145/3477206.3477461 [31] Asana. (s. f.). Qué es la metodología waterfall y cuándo utilizarla • Asana. Asana. Recuperado 26 de febrero de 2023, de https://asana.com/es/resources/waterfall-project-management-methodology [32] Pursell, S. (s. f.). Metodología Agile: Qué es y cómo aplicarla a tu proyecto. Recuperado 26 de febrero de 2023, de https://blog.hubspot.es/marketing/metodologia-agile [33] Google Meet. (s. f.). Recuperado 26 de febrero de 2023, de https://meet.google.com/ [34] ¿Qué es Slack? | Slack. (s. f.). Recuperado 26 de febrero de 2023, de https://slack.com/intl/es-es/help/articles/115004071768-%C2%BFQu%C3%A9-es-Slack- [35] Free Online Gantt Chart Maker That’s Easy to Use | TeamGantt. (s. f.). Recuperado 5 de marzo de 2023, de https://www.teamgantt.com/h2 [36] Build software better, together. (s. f.). GitHub. Recuperado 5 de marzo de 2023, de https://github.com [37] Visual Studio Code—Code Editing. Redefined. (s. f.). Recuperado 5 de marzo de 2023, de https://code.visualstudio.com/ [38] Welcome to Python.org. (2023, febrero 15). Python.Org. https://www.python.org/ [39] Company Salaries. (s. f.). Glassdoor. Recuperado 12 de marzo de 2023, de https://www.glassdoor.com/Salaries/index.htm [40] Hervás, L. V. (2014, octubre 29). La oficina ideal: 14m 2 por empleado. Cinco Días. https://cincodias.elpais.com/cincodias/2014/10/28/pyme/1414500383_553511.html [41] Inici—Agència desenvolupament econòmic—Àrea Metropolitana de Barcelona. (s. f.). Agència desenvolupament econòmic. Recuperado 12 de marzo de 2023, de https://agenciaeconomica.amb.cat [42] Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., Mok, W.-K., Sim, S., Kwek, L.-C., & Aspuru-Guzik, A. (2022). Noisy intermediate-scale quantum (NISQ) algorithms. Reviews of Modern Physics,94(1), 015004. https://doi.org/10.1103/RevModPhys.94.015004 [43] Cuccaro, S. A., Draper, T. G., Kutin, S. A., & Moulton, D. P. (2004). A new quantum ripple-carry addition circuit (arXiv:quant-ph/0410184). arXiv. http://arxiv.org/abs/quant-ph/0410184 [44] Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing - STOC ’96, 212-219. https://doi.org/10.1145/237814.237866 [45] Hilbert spaces | Quantiki. (s. f.). Recuperado 25 de mayo de 2023, de https://www.quantiki.org/wiki/hilbert-spaces [46] Lomont, C. (2004). A quantum Fourier transform algorithm (arXiv:quant-ph/0404060). arXiv. http://arxiv.org/abs/quant-ph/0404060 [47] MaxCut Problem. (s. f.). Recuperado 25 de mayo de 2023, de https://grafo.etsii.urjc.es/optsicom/maxcut [48] Musk, D. (2020). A Comparison of Quantum and Traditional Fourier Transform Computations [Preprint]. Preprints. https://doi.org/10.22541/au.160614804.47667838/v1 [49] Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum,2, 79. https://doi.org/10.22331/q-2018-08-06-79 [50] Rapid solution of problems by quantum computation. (1992). Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences,439(1907), 553-558. https://doi.org/10.1098/rspa.1992.0167 49 [51] Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G. H., & Tennyson, J. (2022). The Variational Quantum Eigensolver: A review of methods and best practices. Physics Reports,986, 1-128. https://doi.org/10.1016/j.physrep.2022.08.003 [52] Tomesh, T., Gokhale, P., Omole, V., Ravi, G. S., Smith, K. N., Viszlai, J., Wu, X.-C., Hardavellas, N., Martonosi, M. R., & Chong, F. T. (2022). SupermarQ: A Scalable Quantum Benchmark Suite (arXiv:2202.11045). arXiv. http://arxiv.org/abs/2202.11045 [53] Vijendran, V., Das, A., Koh, D. E., Assad, S. M., & Lam, P. K. (2023). An Expressive Ansatz for Low-Depth Quantum Optimisation (arXiv:2302.04479). arXiv. http://arxiv.org/abs/2302.04479 [54] Welcome to OpenQL’s documentation! —OpenQL documentation. (s. f.). Recuperado 25 de mayo de 2023, de https://openql.readthedocs.io/en/latest/ [55] IBM Quantum Computing | Roadmap. (2015, octubre 1). https://www.ibm.com/quantum/www.ibm.com/quantum/roadmap [56] Hopery/MyOpenQL. (s. f.). GitHub. Recuperado 26 de mayo de 2023, de https://github.com/Hopery/MyOpenQL [57] GHZ state example. (s. f.). IBM Quantum. Recuperado 18 de junio de 2023, de https://quantum-computing.ibm.com/composer/docs/iqx/example-circuits/ghz [58] Quantum Supremacy Using a Programmable Superconducting Processor. (2019, octubre 23). https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html [59] Quantum Supremacy Using a Programmable Superconducting Processor. (2019, octubre 23). https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html [60] Quantum key distribution—Wikipedia. (s. f.). Recuperado 18 de junio de 2023, de https://en.wikipedia.org/wiki/Quantum_key_distribution [61] (PDF) Quantum Approaches to Logic Circuit Synthesis and Testing. (s. f.). Recuperado 18 de junio de 2023, de https://www.researchgate.net/publication/235083817_Quantum_Approaches_to_Logic_Circuit_Synthesis_an d_Testing [62] Porter, M. A. (2012). Small-world network. Scholarpedia,7(2), 1739. https://doi.org/10.4249/scholarpedia.1739 [63] Network models. (s. f.). Recuperado 11 de junio de 2023, de https://users.dimi.uniud.it/~massimo.franceschet/networks/nexus/models.html [64] Porter, M. A. (2012). Small-world network. Scholarpedia,7(2), 1739. https://doi.org/10.4249/scholarpedia.1739 [65] Ono, K. (2007). Scale Free network generated by Barabasi-Albert model. Cytoscape2.5 and igraph and R. https://commons.wikimedia.org/w/index.php?curid=2459900 [66] Vandersypen, L. M. K., Bluhm, H., Clarke, J. S., Dzurak, A. S., Ishihara, R., Morello, A., Reilly, D. J., Schreiber, L. R., & Veldhorst, M. (2017). Interfacing spin qubits in quantum dots and donors—Hot, dense and coherent. Npj Quantum Information,3(1), 34. https://doi.org/10.1038/s41534-017-0038-y [67] Rapid solution of problems by quantum computation | Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences. (s. f.). Recuperado 20 de junio de 2023, de https://royalsocietypublishing.org/doi/10.1098/rspa.1992.0167 [68] Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014). A variational eigenvalue solver on a quantum processor. Nature Communications,5(1), 4213. https://doi.org/10.1038/ncomms5213 [69] Srikanth, P., & Kumar, A. (2022). Secure Quantum Computing for Healthcare Sector: A Short Analysis (arXiv:2211.10027). arXiv. https://doi.org/10.48550/arXiv.2211.10027 50 ANNEX A - PLANIFICACIÓ TEMPORAL A.3 Resum i representació gràfica de tasques Un cop definides les tasques i recursos necessaris, en aquesta secció es presenta de manera visual a la taula 1 un resum on es descriuen les tasques amb les dependències, recursos necessaris i el nombre d’hores dedicades. Cal comentar que no es mencionen els recursos materials definits com a general perquè s’utilitzen de manera implícita a totes les tasques. A.3.1 Diagrama de Gantt A partir de les fites establertes durant la secció per cada tasca (inici i fi de cadascuna d’elles) i les seves dependències generem el següent diagrama de Gantt presentat a la Figura A1. Juntament amb la Taula 1 de la secció anterior ajuda a veure la planificació global del treball. A.4 Obstacles i riscos En qualsevol projecte poden sorgir diferents obstacles que impedeixin el correcte desenvolupament d’aquest. Per tant, és important tenir clar i saber identificar els possibles riscos que puguin influir negativament en el treball. A continuació es llisten els riscos que són més probables, a priori, que puguin sorgir durant el transcurs del treball. Error de planificació de temps. És un risc amb una probabilitat baixa d’aparèixer donada l'alta planificació prèvia amb l’assignatura de GEP, no obstant és un risc amb un impacte molt alt donat que el treball s’ha d’entregar en finalitzar el semestre i no es pot demorar. Normalment produït per una estimació poc realista o optimista de les càrregues de treball. Malaltia o lesions. És un risc amb una probabilitat baixa d'aparèixer i amb un impacte variable. L’impacte de la lesió determinaria l’impacte que tindria sobre aquest treball. Error en l'anàlisi de les dades. És un risc amb una probabilitat d'aparèixer i amb un impacte mitjà. L’error no deixaria de ser un error d’interpretació sobre un resultat correcte, a no ser que sigui una interpretació errònia de manera molt flagrant que succeeixi de manera reiterada amb diversos algorismes no tindrà un impacte elevat i serà fàcil de detectar. Capacitat computacional limitada. És un risc amb una possibilitat alta d'aparèixer i amb un impacte variable. A priori la compilació no hauria de ser mes costosa que la simulació de sistemes quàntics en ordinadors clàssics peró esperem trobar limitacions, per tant, la probabilitat que la capacitat computacional sigui un problema és gairebé alta. L’impacte variarà si la limitació computacional és causada pel temps d’execució o la quantitat de memòria necessària. Es preveu un impacte baix i mitja a priori respectivament. 57 ANNEX A - PLANIFICACIÓ TEMPORAL Resultats no esperats o sense sentit. És un risc amb una probabilitat baixa donat que a priori seria causat per algun bug en la simulació o algun altre factor que no podem saber i amb un baix impacte donat que es pot detectar ràpidament abans de l'estudi dels resultats. A.5 Gestió del risc Durant el transcurs del projecte poden aparèixer problemes o impediments que afectin el correcte desenvolupament del projecte. Prèviament a la secció A.4 es fa una introducció i s’identifiquen els riscos que poden aparèixer. En aquesta secció presentem el pla de contingència i les diferents alternatives que s’adoptaran en cas que n’apareguin. Error de planificació de temps. Aquest risc pot tenir un impacte molt gran en el projecte, per tant, en el moment que es detecti un error en la planificació de temps es comentarà immediatament amb el director del TFG per trobar la solució més viable. Es proposen dos tipus de solucions, la primera tornar a fer una nova planificació per les tasques restants i això implicaria un augment d'hores per dia de càrrega de treball. La segona opció és la més desagradable, per tant, intentarem evitar-ho sempre que es pugui, s'eliminaran tasques del projecte final de manera que es pugui utilitzar el temps restant en tasques de prioritat més elevada. Malaltia o lesions. El pla de contingència per aquest risc pot variar donat que encara que aparegui una malaltia o lesió no té impacte sobre l’estimació d’hores per tasca sinó de la seva distribució. Llavors, en cas que aparegui alguna indisposició s'haurà de reestructurar la distribució de les tasques o treballar més hores al dia per poder recuperar el temps perdut. Error en l'anàlisi de les dades. Com s’ha comentat prèviament, aquest risc apareix en donar una interpretació errònia sobre un resultat correcte. Per tant, l’alternativa que s’adopta en detectar un error en l’anàlisi és tornar a interpretar els resultats de la manera que pertoca. A més, en les reunions setmanals amb el director i codirectora del TFG es dedicarà un temps afegit per discutir l'error per no repetir-ho novament, així s’evita que es converteixi en un error sistemàtic per tots els diferents anàlisis. Implica un augment en el nombre d’hores de treball per poder escriure de nou la interpretació dels resultats i un augment puntual en la durada de les reunions de control. 58 ANNEX A - PLANIFICACIÓ TEMPORAL Capacitat computacional limitada. En cas de sofrir limitacions de capacitat computacional en el principal ordinador de treball, MacBook portàtil referit en la secció 4.1, es disposa d’uns altres dos ordinador amb millors prestacions de hardware, els ordinadors estan referits també en la secció 4.1. A continuació es descriu el pla de contingència en cas que els problemes segueixin apareixent així i tot utilitzant l’ordinador amb més potència. En cas que el temps necessari per a la computació sigui molt elevat a l’esperat, estem parlant d'hores, s’ha decidit continuar amb l’execució. En cas que l’execució fos de dies, s'avorta l’execució i es redueix l’espai d’exploració de paràmetres per intentar reduir el temps d’execució. En cas que la limitació de capacitat computacional sigui causada per la limitació de memòria de l’ordinador es decideix que l’execució s'avortaria com en el cas anterior. Resultats no esperats o sense sentit. Els resultats sense sentit o no esperats es produeixen per possibles bugs de l’eina o per altres raons externes. S’ha decidit que en trobar-se amb un resultat sense sentit es tornarà a executar l’eina per veure si l’error és causat per un error puntual o determinista. En cas que l’error persisteixi o en cas de seguir obtenint els mateixos resultats sense sentit es descartaran aquests resultats. Es llista ala Taula 2 els riscos amb la seva probabilitat, impacte i hores que s’haurien d’afegir ala planificació. Cal destacar que en l'afegir 0 hores, no vol dir que no tingui impacte donat que en aquests casos es faria una redistribució de tasques. 59 ANNEX A - PLANIFICACIÓ TEMPORAL ID Tasca Temps Dependències Recursos T1 Gestió del projecte 163 T1.1 Context i abast 22 RH, RHW T1.2 Planificació temporal 8 T1.1 RH, RHW T1.3 Pressupost i sostenibilitat 8 T1.2 RH, RHW T1.4 Reunions 20 RH, RHW,RSW T1.5 Memòria 80 RH, RHW T1.6 Preparació de la defensa 25 T1.5 RH, RHW, RSW T2 Treball previ 104 T2.1 Decisió algorismes quàntics 4 RH T2.2 Aprenentatge algorismes quàntics 40 T2.1 RH,RM T2.3 Aprenentatge anàlisi xarxes 30 RH,RM T2.4 Aprenentatge eina anàlisi tràfic 30 RH,RM T3 Generar resultats 50 T3.1 Programació i codificació 26 T2.2 RH,RHW,RSW T3.2 Decisió de paràmetres 4 T2.4 RH T3.3 Obtenció de traces 20 T2.4 RH,RWH,RSW T4 Anàlisi 140 T4.1 Estudi previ de traces 20 T2.2,T3.3 RH T4.2 Decisió de mètriques 4 T2.3 RH T4.3 Obtenció de gràfics 26 T3.3, T4,2 RH,RHW,RSW T4.4 Anàlisi individual 40 T4.3,T3.3,T2.3 RH,RHW,RSW T5.5 Anàlisi en conjunt 40 T4.3,T4.4,T2.3 RH,RHW,RSW Total 457 Taula A.1 Resum i representació gràfica de tasques. [Font: Elaboració propia] 60 ANNEX A - PLANIFICACIÓ TEMPORAL Risc Probabilitat Impacte Hores Error de planificació de temps Baixa Alt 0 Malaltia o lesions Baixa Variable 0 Error en l'anàlisi de les dades Mitjà Mitjà 20 Capacitat computacional limitada Alta Variable 20 Resultats no esperats o sense sentit Baixa Baix 4 Total 44 Taula A.2 Resum de riscos amb estimació d’hores. [Font: Elaboració propia] Finalment, com que no es pot allargar la data límit del projecte, aquestes hores s’afegirien a les hores estimades per fer el projecte i implicaria treballar més hores per dia en el moment que aparegui algun d’aquests problemes. A.6 Metodologia de treball Un dels mètodes de treball més coneguts i més intuïtius és el mètode en cascada [31]. S’utilitzarà el mètode en cascada per aquest treball a causa de la linealitat de la nostra metodologia especificada anteriorment. Altres mètodes de treball com el mètode àgil [32] han estat considerats però descartats donat que creiem que fer iteracions en comptes d'organitzar el treball en fases pot tenir un impacte no desitjat. Un exemple d'això pot ser que en el mètode en cascada al fer tot l'anàlisi de tràfic al final potser podem veure patrons o comportaments genèrics entre tots ells i disposar d’una imatge més general d’alguna mètrica en concret que es comporti d’alguna manera determinada en tot l'anàlisi en comú. En canvi, si féssim iteracions com suggereix el mètode àgil, creiem que arribar a aquest tipus de conclusions seria més difícil donat que faríem un anàlisi d'un algorisme a la vegada i transcorreria una quantitat considerable de temps entre iteració i iteració, i al final, entre anàlisi i anàlisi. A.7 Eines de seguiment Les eines amb les quals es farà el seguiment d’aquest treball són les esmentades a continuació. 61 ANNEX A - PLANIFICACIÓ TEMPORAL Google meet. L’eina Google Meet[33] ens permet tenir reunions tant amb el director com amb la codirectora del treball per poder discutir el correcte. Slack. Slack[34] és una eina de comunicació que facilita la comunicació entre més d’una persona, resulta en conversacions més breus i menys formals que amb Google Meet. Email. El correu electrònic és l’eina de comunicació més senzilla per poder contactar primerament amb una persona en concret. A.8 Mètode d'avaluació El mètode d’avaluació en termes de l'avaluació de la metodologia de treball, planificació de temps de cada fase o per avaluar l'assoliment d’objectius es realitza amb les eines esmentades anteriorment, sent el mètode principal d’avaluació reunions amb el director i codirectora del treball. D’altra banda, l'avaluació sobre la correctesa del contingut del treball es farà novament amb reunions amb els directors del treball, reunions bi-setmanals amb el grup d'investigació N3Cat i validació amb la teoria sobre els algorismes i en conjunt amb les traces generades comprovar si és el comportament esperat a priori. 62 Fig. A.1 Diagrama de Gantt de tasques. [Font: Elaboració propia amb l’eina team gantt] 63 Annex B GESTIÓ ECONÒMICA En aquest capítol es tracta la part econòmica del projecte. Es tracta d’una part vital de qualsevol projecte de certa magnitud, és per això que cal identificar tots els costos durant el desenvolupament del projecte per tal de poder estimar el seu cost i donar així un pressupost del projecte. B.1 Costos de personal En aquesta secció es calcula el cost de les tasques dutes a terme on es fa ús de recursos humans. Per fer-ho s’identifiquen els rols que es necessiten en aquest projecte juntament amb el sou brut per hora i el sou per hora inclosa la seguretat social. A continuació a la Taula B.1 es resumeix els conceptes esmentats anteriorment juntament amb l'assignació de cada rol a un tipus de recurs humà. ID Rol Sou brut Sou + SS Recurs humà CP Cap de projecte 18.31 €/h 24.72 €/h D,CD,T,A P Programador 10.85 €/h 14.65 €/h A I Investigador 15.05 €/h 20.32 €/h A,N3Cat Taula B.1 Identificació de rols amb assignació de recursos humans i cost. [Font: Elaboració propia] D: Director TFG, CD: Codirectora TFG, T: Tutor de GEP,A: Autor TFG, N3Cat: membres del grup N3Cat Preu per hora calculat a partir del salari anual mitjà obtingut a Glassdoor [39] Un cop definits els rols, a la Taula B.2 es desglossen les tasques definides al diagrama de Gantt que necessiten recursos humans indicant el número d’hores per rol que es necessitaran pel compliment de la tasca amb el preu total que costarà. 64 ANNEX B - GESTIÓ ECONÒMICA ID Tasca Temps CP P I Cost T1 Gestió del projecte 163 163 4,029.36 € T1.1 Context i abast 22 22 543.84 € T1.2 Planificació temporal 8 8 197.76 € T1.3 Pressupost i sostenibilitat 8 8 197.76 € T1.4 Reunions 20 20 494.40 € T1.5 Memòria 80 80 1977.60 € T1.6 Preparació de la defensa 25 25 618.00 € T2 Treball previ 104 4 100 2,130.88 € T2.1 Decisió algorismes quàntics 4 4 98.88 € T2.2 Aprenentatge algorismes quàntics 40 40 812.80 € T2.3 Aprenentatge anàlisi xarxes 30 30 609.60 € T2.4 Aprenentatge eina anàlisi tràfic 30 30 609.60 € T3 Generar resultats 50 4 46 772.78 € T3.1 Programació i codificació 26 26 380.90 € T3.2 Decisió de paràmetres 4 4 98.88 € T3.3 Obtenció de traces 20 20 293.00 € T4 Anàlisi 140 4 52 74 2,364.36 € T4.1 Estudi previ de traces 20 20 406.40 € T4.2 Decisió de mètriques 4 4 98.88 € T4.3 Obtenció de gràfics 26 26 380.90 € T4.4 Anàlisi individual 40 10 30 756.10 € T5.5 Anàlisi en conjunt 40 16 24 722.08 € Total 457 9,297.38 € Taula B.2 Estimació d’hores per tasca i rol amb cost. [Font: Elaboració propia] 65 ANNEX B - GESTIÓ ECONÒMICA B.2 Costos genèrics Un cop hem estimat els costos de personal hem de tenir en compte que durant tot el treball s’utilitzen altres recursos ja siguin materials com hardware, software i l’espai de treball o bé siguin serveis com accés a internet o una font d’electricitat. B.2.1 Espai de treball Cal comentar que aquest projecte es realitza totalment des de casa, per tant, s’ha optat per estimar el que podria costar si es fes a una oficina. La Figura B.1 ens mostra com s’ha calculat l’estimació, el tamany mitjà d’oficina es calcula segons un estudi d’El País [40] iel preu mitjà de lloguer del metre quadrat es calcula sobre el preu proporcionat per l'Agència de Desenvolupament Econòmic de l'àrea metropolitana de Barcelona [41] del mes de Febrer de 2023. (𝑃𝑟𝑒𝑢 𝑝𝑒𝑟 𝑚2 𝑙𝑙𝑜𝑔𝑢𝑒𝑟 𝑜𝑓𝑖𝑐𝑖𝑛𝑎) 𝑥 (𝑀𝑖𝑑𝑎 𝑚𝑖𝑡𝑗𝑎𝑛𝑎 𝑑'𝑜𝑓𝑖𝑐𝑖𝑛𝑎 𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙) 𝑥 (𝑡𝑒𝑚𝑝𝑠) 17.39 𝑥 3.5 𝑥 5 = 304.32€ Fig. B.1 Estimació del cost del lloguer d’una oficina de treball a Barcelona. [Font: Elaboració propia] Finalment, ens falta estimar el preu d’altres recursos materials necessaris per a qualsevol espai de treball, a la Taula B.3 trobem una llista completa amb l’estimació del cost de tot l’espai de treball. Recurs Preu Lloguer oficina 304.32 € Escriptori d’oficina* 6 € Cadira d’oficina* 5 € Total 315.32 € Taula B.3 Estimació total del cost per l’espai de treball. [Font: Elaboració propia] *Estimació de preus obtinguda de IKEA amb amortització a 10 anys B.2.2 Hardware L’únic dispositiu que s’utilitza és un ordinador portàtil de gamma alta amb un cost de 1200 €. Si suposem que la seva vida útil és de 4 anys llavors l’amortització es calcula a la Figura B.2. 𝑚𝑒𝑠𝑜𝑠 𝑑'ú𝑠 𝑚𝑒𝑠𝑜𝑠 𝑣𝑖𝑑𝑎 ú𝑡𝑖𝑙 𝑥 𝑝𝑟𝑒𝑢 𝑜𝑟𝑑𝑖𝑛𝑎𝑑𝑜𝑟 5/48 𝑥 1200 = 125 € Fig. B.2 Amortització de hardware. [Font: Elaboració propia] 66 Annex D REVISIÓ DE PLANIFICACIÓ Al començament d’aquest projecte es va fer una planificació inicial i una estimació en temps i diners de les tasques i recursos necessaris per dur a terme el projecte. També es van identificar diferents riscos i com actuar en cas d’aparèixer. En aquest apartat compararem i verificarem a posteriori si la planificació estava ben estimada o no i si ha aparegut cap problema durant el transcurs del treball. D.1 Recursos necesaris Els recursos de hardware necesaris finals han estat diferents als planificats anteriorment. S’ha optat per no fer us de l’ordinador personal per realitzar tots els experiments i s’han realitzat la majoria en el servidor. S’ha optat per aquesta solució per intentar reduir el consum electric al utilitzar un hardware mes sofistcat i optimitzat on el consum pot ser mes elevat pero els temps d’execució esperats son molt més reduïts, amortitzant d’aquesta manera el consum total amb uns temps d’us menor. D.2 Planificació temporal Respecte a la planificació temporal ens hem trobat amb què podíem fer moltes tasques a la vegada per tant s’ha pogut començar abans amb les tasques de codificació i obtenció de traces i per tant s’han dedicat més hores sense afectar a les estimacions de les deadlines. Això també ens ha permès realitzar més estudis i entendre millor els resultats i obtenir resultats per algorismes que en un principi no teníem pensat. Per tant a la Figura D.1 es mostra el nou diagrama de Gantt. També s’han pogut obtenir visualitzacions i grafics que no s’habien planificat inicialment que hem pogut realitzar al haber pogut començar avans amb aquesta tasca. D.3 Problemes i riscos trobats Vam estimar amb una alta probabilitat l’aparició de limitacions en la capacitat de computació i així ha estat. Concretament pels algorismes de QAOA, QFT i especialment QPE ens hem trobat amb aquest problema. El pla de contingència per aquesta situació era l’ús del servidor per les tasques més pesades, tot i així no ha sigut suficient, per tant, no queda més remei a executar i obtenir resultats fins on l’ordinador pugui calcular i treballar amb els resultats obtinguts. Els resultats de strong i weak scaling per aquests algoritmes no estaran del tot complets donat que faltarà per calcular les últimes iteracions de l’estudi. Fig. D.1 Diagrama de Gantt revisat. [Font: Elaboració propia amb l’eina team gantt] Annex E REPLICACIÓ DE RESULTATS Aquest Annex conté la configuració de la plataforma utilitzada per OpenQL per a la replicaió d’aquests resultats. E.1 Descripció de la plataforma La plataforma es descriu en format JSON on s’han de descriure una serie de configuracions. Les configuracions per compilador i hardware són: "eqasm_compiler" :"cc_light_compiler", "hardware_settings": { "qubit_number":NTOTALQUBITS, "cycle_time" :20, "mw_mw_buffer":0, "mw_flux_buffer":0, "mw_readout_buffer":0, "flux_mw_buffer":0, "flux_flux_buffer": 0, "flux_readout_buffer":0, "readout_mw_buffer":0, "readout_flux_buffer":0, "readout_readout_buffer":0 } També es necessiten especificar paràmetres per qubits i la topología: "qubit_attributes": { "relaxation_times": { "0" : [3000,1500], "1" : [3000,1500], "2" : [3000,1500], "3" : [3000,1500], "4" : [3000,1500] } }, "topology" : { "number_of_cores":NCORES, "connectivity":"full", "form":"irregular", "comm_qubits_per_core":NQUBITS_PER_CORE } 75 Finalment cal descriure paràmetres de comunicació i especificar les portes quàntiques que suporta la plataforma, mostrem una com exemple. "resources": { "qubits": { "description":"Each qubit can be used by only one gate at atime. There are 'count' qubits.", "count":NTOTALQUBITS }, "channels": { "description":"Each inter-core gate uses one channel in each core. There are 'count' such channels per core.", "count":NCHANNELS } }, "instructions": { "prepx": { "duration":20, "latency":0, "type":"mw", "cc_light_instr":"prepx" }, 76 Annex F FIGURES Aquest annex recull totes les figures que no s’han presentat en el capítol de resultats. Fig. F1 Traces Cuccaro 512 i QPE. A l’esquerra, traça física per l’algorisme de Cuccaro amb un total de 512 qubits i 32 cores. A la dreta, traça QPE per 16 qubits i 4 cores. Fig. F2 Traça QAOA model ER. Traces per grafs esparsos i densos (les línies horitzontals de la primera traça són d’un error en la visualització) 77 Fig. F3 Burstiness VQE. Burstiness per l’algorisme de VQE (HEA1 i HEA2 respectivament) amb un total de 128 qubits i 8 cores. (Nombre de Teleportacions en el eix vertical) Fig. F4 Burstiness Cuccaro i GHZ. Burstiness pels algorismes de Cuccaro i GHZ amb un total de 128 qubits i 8 cores. 78 Fig. F5 Burstiness QPE. Burstiness per l’algorisme de QPE amb un total de 16 qubits i 4 cores Fig. F6 Burstiness QFT. Burstiness per l’algorisme de QFT (implementació de qiskit a la dreta) amb un total de 128 qubits i 8 cores. 79 Fig. F7 Core Hotspotness, comunicacions uniformes. Core Hotspotness pels algorismes (model QAOA (model BA), QFT iVQE (HEA2) amb un total de 128 qubits i 8 cores respectivament. Fig. F8 Core Hotspotness, comunicacions concentrades. Core Hotspotness pels algorismes QPE iQAOA (model WS) amb unes arquitectures 4x4 i 16x8 respectivament. 80 Fig. F9 Core Hotspotness, comunicacions esglaonades. Core Hotspotness pels algorismes Cuccaro, Grover i QFT (implementació de quiskit) amb un total de 128 qubits i 8 cores respectivament. Fig. F10 Distribució d’operacions per qubit Cuccaro. Distribució segons el tipus d’operacions per qubit per Cuccaro amb 128 qubits i 8 cores. 81 Fig. F11 Distribució d’operacions per qubit GHZ i QPE. Distribució segons el tipus d’operacions per qubit per GHZ iQPE amb arquitectures 16x8 i 4x4 respectivament. Fig. F12 Distribució d’operacions per qubit QFT qiskit. Distribució segons el tipus d’operacions per qubit per QFT (implementació de qiskit) amb 128 qubits i 8 cores. Fig. F13 Distribució d’operacions per qubit QAOA. Distribució segons el tipus d’operacions per qubit per QAOA (models BA i WS) amb 128 qubits i 8 cores. 82