Q

Non si prosegua l'azione secondo un piano.

Tag: xarxes complexes

Distribució d’entrellaçament en xarxes complexes quàntiques

El proper dilluns 5 de novembre, a les 10:30, a la Sala de Graus II de la Facultat de Ciències de la Universitat Autònoma de Barcelona, defensaré la tesi “Entanglement distribution in quantum complex networks”. Hi esteu tots convidats! (La imatge forma part del disseny de la portada que ha fet la Judit Armengol.)

Aquesta tesi tracta l’estudi de xarxes quàntiques amb una estructura complexa, les implicacions que aquesta estructura té en la distribució d’entrellaçament i com el seu funcionament pot ser millorat mitjançant operacions en el règim quàntic. Primer considerem xarxes complexes d’estats bipartits, tant purs com mescla, i estudiem la distribució d’entrellaçament a llargues distàncies. Després passem a analitzar xarxes de canals sorollosos i estudiem la creació i distribució de grans estats multipartits.

El treball contingut en aquesta tesi està motivat principalment per la idea que la interacció entre la informació quàntica i les xarxes complexes pot donar lloc a una nova comprensió i caracterització dels sistemes naturals. Les xarxes complexes tenen una importància particular en les infraestructures de comunicació, ja que la majoria de xarxes de telecomunicació tenen una estructura complexa. En el cas de xarxes quàntiques, que són el marc necessari per al processament distribuït d’informació i comunicació quàntica, és ben possible que en el futur adquireixin una topologia complexa semblant a la de les xarxes existents, o que fins i tot es desenvolupin mètodes per a utilitzar les infraestructures actuals en el règim quàntic.

Una tasca central en les xarxes quàntiques és dissenyar estratègies per distribuir entrellaçament entre els seus nodes. En la primera part d’aquesta tesi, considerem la distribució d’entrellaçament bipartit com un procés de percolació d’entrellaçament en una xarxa complexa. Des d’aquest enfocament, s’estableix entrellaçament perfecte de manera probabilística entre dos nodes arbitraris. Veiem que, per a xarxes grans, la probabilitat d’aconseguir-ho és una constant estrictament major que zero (i independent de la mida de la xarxa) si la quantitat inicial d’entrellaçament està per sobre d’un cert valor crític. La mecànica quàntica ofereix aquí la possibilitat de canviar l’estructura de la xarxa sense necessitat d’establir nous canals “físics”. Mitjançant una transformació local adequada de la xarxa, es pot disminuir l’entrellaçament crític i augmentar la probabilitat. Apliquem aquesta transformació a models de xarxes complexes amb una distribució de graus arbitrària.

En el cas de xarxes sorolloses d’estats mescla, veiem que per algunes classes d’estat es pot utilitzar el mateix enfocament de percolació d’entrellaçament. Per a estats mescla generals considerem una percolació de llargada de camí limitada per la quantitat de soroll de les connexions. Veiem com les xarxes complexes ofereixen encara un gran avantatge en la probabilitat de connectar dos nodes.

En la segona part, passem a l’escenari multipartit. Estudiem la creació i distribució d’estats graf amb una estructura que imita la de la xarxa de comuicació subjacent. En aquest cas, utilitzem una xarxa complexa arbitrària amb canals sorollosos, i considerem que les operacions i mesures són també sorolloses. Proposem un mètode eficient per a distribuir i purificar petits subgrafs, que després es fusionen per a reproduir l’estat desitjat. Comparem aquest enfocament amb dos protocols bipartits basats en un node central i coneixement complet de l’estructura de la xarxa. Mostrem que la fidelitat dels estats graf generats es pot escriure com la funció de partició d’un sistema desordenat de spins clàssics (un vidre de spins), i la seva taxa de decaïment és l’anàleg de l’energia lliure. Utilitzant els tres protocols en una xarxa unidimensional i en xarxes complexes veiem que són tots comparables, i que en alguns casos el protocol de subgrafs proposat, que necessita només informació local de la xarxa, té inclús un comportament millor.

Informació quàntica i xarxes complexes: ara també a la inversa

Des de fa un temps, la comunitat d’investigadors en informació quàntica ens hem anat interessant més i més en les xarxes complexes, i com la seva estructura gens trivial pot afectar l’entrellaçament i la capacitat de comunicació i computació quàntiques. La veritat és que és la unió de dos camps apassionants. De moment, els estudis que havien sortit utilitzaven idees de xarxes complexes i física estadística, però es feien des de la banda de la informació quàntica: caminades quàntiques en xarxes complexes (Muelken i Blumen, 2010), models de xarxes quàntiques aleatòries (Perseguers et al., 2010) i de mons petits (Wei et al, 2011), distribució d’entrellaçament (Cuquet i Calsamiglia, 2009, 2011, 2012; Wu et al 2011) i, recentment, una implementació quàntica de l’algoritme PageRank de Google (Paparo i Marin-Delgado, 2012).

Avui surt publicat a Scientific Reports un nou article sobre la versió quàntica del PageRank (Sanchez-Burillo, 2012), però aquesta vegada l’article ve firmat per investigadors del camp de les xarxes complexes. En paraules del mateix article, la porta entre els dos camps s’obre aquesta vegada des de l’altra banda. Bones notícies!

Quantum Navigation and Ranking in Complex Networks

Eduardo Sánchez-Burillo, Jordi Duch, Jesús Gómez-Gardeñes & David Zueco

Complex networks are formal frameworks capturing the interdependencies between the elements of large systems and databases. This formalism allows to use network navigation methods to rank the importance that each constituent has on the global organization of the system. A key example is Pagerank navigation which is at the core of the most used search engine of the World Wide Web. Inspired in this classical algorithm, we define a quantum navigation method providing a unique ranking of the elements of a network. We analyze the convergence of quantum navigation to the stationary rank of networks and show that quantumness decreases the number of navigation steps before convergence. In addition, we show that quantum navigation allows to solve degeneracies found in classical ranks. By implementing the quantum algorithm in real networks, we confirm these improvements and show that quantum coherence unveils new hierarchical features about the global organization of complex systems.

Referències

(Els enllaços són les versions dels articles amb accés obert.)

Cuquet, M. and Calsamiglia, J. (2009), Entanglement Percolation in Quantum Complex Networks, Physical Review Letters 103, 240503–4.

Cuquet, M. and Calsamiglia, J. (2011), Limited-path-length entanglement percolation in quantum complex networks, Physical Review A 83, 032319–14.

Cuquet, M. and Calsamiglia, J. (2012), Growth of graph states in quantum networks, arXiv 1208.0710.

Muelken, O. and Blumen, A. (2011), Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks, Physics Reports 502, 37–87.

Paparo, G. D. and Martin-Delgado, M. A. (2012), Google in a quantum network, Scientific Reports 2, 444.

Perseguers, S., Lewenstein, M., Acín, A., and Cirac, J. I. (2010), Quantum random networks, Nature Physics 6, 539–543.

Sánchez-Burillo, E., Duch, J., Gómez-Gardeñes, J., and Zueco, D. (2012), Quantum Navigation and Ranking in Complex Networks, Scientific Reports 2, 605.

Wei, Z.-W., Wang, B.-H., and Han, X.-P. (2011), Renormalization Induced Quantum Small-World Networks, arXiv 1111.0407.

Wu, L. and Zhu, S. (2011), Entanglement percolation on a quantum internet with scale-free and clustering characters, Physical Review A 84, 052304.

Growth of graph states in quantum networks

Més informació quàntica en xarxes complexes. Aquesta vegada, creació d’un estat graf. A l’arXiv:

Growth of graph states in quantum networks

Martí Cuquet and John Calsamiglia

We propose a scheme to distribute graph states over quantum networks in the presence of noise in the channels and in the operations. The protocol can be implemented efficiently for large graph sates of arbitrary (complex) topology. We benchmark our scheme with two protocols where each connected component is prepared in a node belonging to the component and subsequently distributed via quantum repeaters to the remaining connected nodes. We show that the fidelity of the generated graphs can be written as the partition function of a classical Ising-type Hamiltonian. We give exact expressions of the fidelity of the linear cluster and results for its decay rate in random graphs with arbitrary (uncorrelated) degree distributions.

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.

Follow

Get every new post delivered to your Inbox.

Join 158 other followers