Limited-path-length entanglement percolation in quantum complex networks

Doncs això, una mica d’autopropaganda. El divendres de la setmana passa va sortir això a Physical Review A:

Limited-path-length entanglement percolation in quantum complex networks

Martí Cuquet and John Calsamiglia

We study entanglement distribution in quantum complex networks where nodes are connected by bipartite entangled states. These networks are characterized by a complex structure, which dramatically affects how information is transmitted through them. For pure quantum state links, quantum networks exhibit a remarkable feature absent in classical networks: it is possible to effectively rewire the network by performing local operations on the nodes. We propose a family of such quantum operations that decrease the entanglement percolation threshold of the network and increase the size of the giant connected component. We provide analytic results for complex networks with an arbitrary (uncorrelated) degree distribution. These results are in good agreement with numerical simulations, which also show enhancement in correlated and real-world networks. The proposed quantum preprocessing strategies are not robust in the presence of noise. However, even when the links consist of (noisy) mixed-state links, one can send quantum information through a connecting path with a fidelity that decreases with the path length. In this noisy scenario, complex networks offer a clear advantage over regular lattices, namely, the fact that two arbitrary nodes can be connected through a relatively small number of steps, known as the small-world effect. We calculate the probability that two arbitrary nodes in the network can successfully communicate with a fidelity above a given threshold. This amounts to working out the classical problem of percolation with a limited path length. We find that this probability can be significant even for paths limited to few connections and that the results for standard (unlimited) percolation are soon recovered if the path length exceeds by a finite amount the average path length, which in complex networks generally scales logarithmically with the size of the network.

Per veure l’article a PRA cal estar-hi subscrit, tenir-hi accés a través d’una universitat o pagar. Però l’article també està a l’arXiv, com ja vaig comentar fa algun mes. Per cert, aquesta setmana ha sortit a l’arXiv aquest article que també tracta el tema de les xarxes complexes quàntiques, des d’una altra perspectiva.

La revolució egípcia al Twitter

Via el blog sobre xarxes socials i llengües d’en Natxo Sorolla —que últimament segueixo força— he descobert aquest vídeo fet per André Panisson, un investigador predoctoral a Torí, mitjançant el programa Gephi. Es tracta de l’evolució d’una xarxa dinàmica on els nodes són usuaris de Twitter, i un enllaç entre dos nodes es forma si un dels dos usuaris fa un retweet de l’altre que contingui el hashtag #jan25. Les dades són de l’11 de febrer de 2011, el dia que va caure Mubarak. Comencen a les 17:50 (hora local de El Caire) i duren una hora, de manera que enganxen de ple l’anunci de Suleiman de què Mubarak ha renunciat al càrrec. La xarxa va creixent a mesura que es publiquen nous tweets. Tot plegat ho explica el mateix André Panisson aquí. I aquest és el vídeo, resumint una hora en una mica menys de quatre minuts:

És interessant veure com va creixent la xarxa. A l’inici, els primers retweets uneixen parelles de nodes aïllats: hi ha moltíssims usuaris, i el més probable és que un nou retweet es faci entre dos usuaris que encara no n’han fet cap. Poc a poc van apareixent els primers arbres, de 3, 4 i 5 nodes, i segueixen apareixent nous enllaços aïllats. Cap a 0:40 ja passa una cosa interessant, i és que un grupet d’arbres separats s’uneix amb l’arribada de tres o quatre enllaços nous: cada vegada és més fàcil que un enllaç nou vagi a parar a un clúster, i és més probable si més gran és el clúster. Finalment, arriba un moment crític, i els clústers de mida relativament gran que hi havia s’acaben unint en un de gegant. És el punt crític que es coneix com a llindar de percolació. Aquí també apareixen els primers cicles, camins que es tanquen sobre si mateixos. Aquest clúster gegant té una mida significativa (de l’ordre de la mida de la xarxa), i a partir d’ara anirà creixent poc a poc amb l’arribada de nous enllaços que l’uniran als pocs clústers que encara queden aïllats. És gairebé un exemple “de llibre” del fenòmen de percolació.

Hi ha una cosa, però, que trobo ben curiosa: a la primera part de l’evolució (abans del punt crític) només hi ha arbres, i no cicles tancats. Això és típic dels models més senzills de xarxes aleatòries (com el d’Erdős-Rényi o el configuration model), però força estrany en les xarxes socials com ara Twitter mateix. En aquestes xarxes el nivell de clustering (a grans trets, l’amic del teu amic és fàcil que sigui també amic meu) és força alt, i en canvi en aquesta evolució això no es veu. Justament per això, seria interessant veure quina és la xarxa subjacent al graf: quins nodes —usuaris de Twitter— són seguidors de quins. De fet, xafardejant una mica a la imatge que surt al final de l’article es poden veure els noms dels nodes més influents. Buscant-los ràpidament al Twitter descobrim que són usuaris amb un munt de seguidors.

Un segon punt que potser estaria bé estudiar és que el retweet és en realitat un enllaç direccional: és un usuari que fa un retweet d’un altre usuari. Com quedaria, la xarxa, si dibuixéssim els enllaços dirigits? Els nodes influents —amb més quantitat de veïns— ho són perquè els han “retweetejat” molt, o perquè han estat ells qui han fet molts retweets? Finalment, també seria curiós, posats a demanar, veure quins han estat els tweets més influents, més que no pas quins usuaris. Sembla ser, també, que en aquest vídeo només hi ha un 10% de les dades disponibles. A veure si en tornem a sentir parlar.

Un sistema per a analitzar Wikileaks

Via el blog de Natxo Sorolla sobre xarxes socials i llengües llegeixo que un grup de la UPC (el Data Management Group) ha proposat “un sistema d’exploració d’informació en forma de xarxa o graf que ha creat i patentat, per extreure informació de la xarxa Wikileaks”:

El director del grup DAMA-UPC, Josep Lluís Larriba, planteja fer servir aquesta tecnologia per extreure informació de la xarxa Wikileaks, des de dos punts de vista: per obtenir indicadors genèrics que aportin informació, per conèixer si la xarxa d’informació té les característiques d’una xarxa social o bé si es creen comunitats de dades que fan pensar en grups que aporten informació rellevant; i, d’altra banda, per analitzar com evoluciona una temàtica determinada en el temps, a través dels diferents documents allotjats a l’espai web; com es relaciona una persona o un grup de persones amb diferents temàtiques, o bé com s’interrelacionen els documents, entre d’altres aspectes.

El sistema també es pot aplicar en altres contexts. Un dels que trobo interessants és el de buscar referees pels articles científics: estalviaria molta feina d’editors i podria fer més factible un sistema de publicacions científiques obertes.

Network data: OpenPGP Web of Trust

Com ja he comentat, últimament he estudiat com es transmet la informació en una xarxa on el soroll entre nodes de la xarxa limita el número màxim de “salts” que es poden fer sense que la informació es degradi excessivament. I com a exemple d’una xarxa real, he treballat amb la Xarxa de Confiança (Web of Trust) del protocol OpenPGP.

Sense entrar en gaires detalls, l’OpenPGP és un protocol estàndard d’encriptació que s’utilitza per assegurar les communicacions a través d’email utilitzant criptografia de clau pública. Així, si l’Alice vol enviar un missatge segur a en Bob, ha d’utilitzar la clau pública d’en Bob per a encriptar-lo. L’objectiu de la Xarxa de Confiança, en aquest protocol, és resoldre el problema d’autentificació que es produeix quan l’Alice no pot verificar si la clau que està fent servir és realment propietat d’en Bob. Aquesta xarxa social, doncs, representa la confiança entre usuaris d’OpenPGP —confiança pel que fa a que una determinada clau correspon efectivament a una adreça de correu concreta, però no necessàriament en el que aquesta adreça digui. Tot això ho comentava, també per sobre, fa unes setmanes.

El cas és que he decidit posar l’arxiu amb el graf disponible a Internet, per a que qui vulgui el pugui utilitzar. La informació de la Xarxa de Confiança ja és pública de per si. El que penjo jo és una xarxa una mica “processada” i en un format de graf estàndard: el format GML. Espero poc a poc anar construint un petit zoo amb uns quants tipus de xarxa.

Xarxa de Confiança del protocol OpenPGP

A partir de la pàgina del Wotsap, he agafat el component fortament connectat (strongly connected component) de la Xarxa de Confiança completa del servidor de claus suís del 25 de maig de 2010, que conté 41.459 claus (nodes del graf) i 424.577 firmes (arestes). A partir d’aquesta xarxa, considero el graf format únicament per les arestes bidireccionals (és a dir, les que corresponen a dos usuaris que s’han signat les claus mútuament). Això deixa un graf no dirigit amb 38.550 claus i 145.388 firmes bidireccionals.

La xarxa està penjada aquí en un arxiu en format GML i comprimit amb el gzip. Espero que sigui útil (o si més no interessant!). Si el feu servir, podeu citar (de moment), Martí Cuquet and John Calsamiglia, “Limited path entanglement percolation in quantum complex networks”, arXiv:1011.5630v1 [quant-ph] (2010).

Veïns de confiança

Tots haureu sentit parlar alguna vegada dels “mons petits” i els sis graus de separació. Últimament he estat mirant com evolucionen els clústers d’una xarxa quan en limitem el número màxim de passos que podem fer per anar d’un punt a un altre. Per jugar una mica, he mirat què passava en la xarxa de confiança (web of trust) del sistema criptogràfic OpenPGP.

No entraré en detalls, però a grans trets OpenPGP és un protocol de criptografia asimètrica en què cada persona té una parella de claus: la pública i la privada. La gràcia d’aquest sistema és que per enviar un missatge encriptat a una persona no ens cal haver compartit abans cap clau: n’hi ha prou amb descarregar-nos la seva clau pública de qualsevol servidor de claus i fer-la servir per encriptar un missatge que només el destinatari podrà rebre. El missatge és segur (en principi), però el que no queda tan clar és si la clau pública realment pertany a la persona amb qui ens volem communicar. Per a assegurar-nos-en tenim bàsicament dues opcions. Una és trobar-nos almenys una vegada, comprovar que la persona és qui diu ser i signar la clau pública que ens mostra. Com que la nostra firma només la podem fer nosaltres, la propera vegada que volguem utilitzar la seva clau pública només hem de comprovar que la tenim signada. Però això ens torna al problema de què en algun moment ens hem de trobar cara a cara. La segona opció utilitza la xarxa de confiança: si jo signo la clau d’un conegut, i aquest conegut firma la clau d’un desconegut, puc confiar en què el desconegut és qui diu ser. D’aquesta manera, si existeix un camí entre dues persones, aquestes dues persones poden confiar entre elles.

Aquí teniu algunes gràfiques d’exemple. Partint de la meva antiga clau 0x4C899530 (que ja no faig servir, però per desgràcia la nova clau encara no té cap firma), he mirat com creixia la seva xarxa de confiança a mesura que permetia una distància entre claus més gran. El creixement no és espectacular perquè la clau no pertany a la component gegant de la xarxa de confiança (que correspon aproximadament al 86% de la xarxa), sinó a una petita component de 1.500 claus (un 3,9% de la xarxa), però tot i així ja fa el seu efecte.

Per cert, si m’heu d’enviar missatges encriptats, no feu servir la 0x4C899530 que vaig perdre sense certificat de revocació…), sinó la 0×49116823.