Les paradis artificiels

Entanglement percolation in complex quantum networks

Ja hem posat aquest article a l'arXiv:

Entanglement percolation in complex quantum networks

Martí Cuquet and John Calsamiglia

A novel quantum effect, entanglement percolation, has been recently proposed by Acin et al. [Nat. Phys. 3, 256 (2007)] as a means to establish long-distance entanglement between arbitrary nodes in some quantum networks with a particular lattice geometry. Here we study entanglement percolation strategies in complex networks, thereby extending the phenomenon to realistic network structures. We develop a theory to study entanglement percolation in random graphs with arbitrary degree distributions and find exact analytical results for some particular models. Our findings are in good agreement with numerical simulations and show that the proposed quantum strategies, which only make use of local information of the network, enhance the percolation threshold substantially. Numerical simulations also show a clear enhancement in small-world and other real-world networks.

En prometo una explicació ben aviat.


Els ponts de Königsberg

Ciència, Grafs — 18 Abril 2009, 18:35

Amb aquest article vull començar una sèrie sobre algunes coses que he anat aprenent últimament sobre teoria de grafs i xarxes complexes. Intentaré esciure una mica de tot, però estic obert a suggerències.

Fa ja un temps que l'estudi de les xarxes està de moda, sobretot en el context d'Internet i la World Wide Web, però també en sistemes biològics i mèdics i en xarxes socials. De totes maneres, és un camp relativament antic estudiat dins la matemàtica discreta per la teoria de grafs.

Els ponts de Königsberg

Les arrels d'aquest camp les trobem al 1736, quan el matemàtic suís Leonhard Euler va publicar la solució del problema dels ponts de Königsberg. Aquesta ciutat estava creuada per un riu, que formava dues grans illes connectades entre elles i amb la resta de la ciutat a través de set ponts, com es veu a la imatge. El problema consistia en trobar una ruta que passés per cada pont exactament una sola vegada, ni més ni menys. Per solucionar-lo, Euler el va reformular de manera abstracta: l'única informació necessària era la llista d'àrees de terra (els punts vermells, a la imatge) i els ponts que les connectaven (les línies negres). D'aquesta manera apareixia l'objecte matemàtic que actualment es coneix com a graf. En el llenguatge actual, a cada massa de terra l'anomenem vèrtex (o punt, o node), i a cada pont aresta (o línia, o enllaç). Així, un graf G consisteix en dos conjunts V i E tals que V no és buit i E és un conjunt de parelles desordenades d'elements de V. Els elements de V són els vèrtexs del graf G, i els de E en són les arestes.

El raonament d'Euler va ser el següent: excepte a l'inici i al final del recorregut, cada vegada que s'arriba a un vèrtex a través d'una aresta se n'ha de marxar a través d'una altra. Per tant, el número d'arestes que toquen un vèrtex ha de ser sempre parell, amb la possible excepció de dos vèrtex (la sortida i l'arribada). Aquest número s'anomena el grau del vèrtex. Ara bé, com es pot veure a la imatge, tots els vèrtex són senars, i per tant no pot existir cap ruta que passi per cada pont exactament una sola vegada.


Powered by LifeType