Q

Non si prosegua l'azione secondo un piano.

Tag: ciència

Contra la contraciència

LaContraLVFa poc menys d’un any comentava la promoció de la pseudociència que fa La Contra de La Vanguardia. Algunes de les seves perles les podeu trobar en aquest recull d’entrevistes (que fa temps que no actualitzo, si en teniu de noves passeu-me-les!). Amb amics i companys de feina comentàvem sovint la possibilitat, o més aviat la necessitat, d’escriure’ls una carta de queixa, perquè hi va haver moments en què va arribar a ser intolerable.

Doncs bé, l’altre dia vaig veure que, amb d’altres entitats, l’Associació Catalana de Comunicació Científica havia escrit una carta (pdf) al defensor del lector de La Vanguardia que criticava aquesta manca no només de rigor científic sinó també d’ètica periodística, que hauria de posar en dubte aquest tipus de declaracions. La carta anava acompanyada d’unes 1000 adhesions. La resposta de Josep Rovirosa, el dit defensor del lector, es pot llegir aquí. Llegiu-la vosaltres mateixos i jutgeu-la.

Com a únic comentari, trobo preocupant aquesta tendència general a defensar la “llibertat d’opinió” sense posar en dubte i exigir explicacions convincents de les declaracions que fa l’entrevistat de torn. Això no és un problema limitat a l’àmbit de la ciència (o més ben dit, pseudociència o contraciència), sinó àmpliament estès i amb especial incidència en les “notícies” sobre “política”, que no fan sinó limitar-se a reproduir les opinions del “polític” que en aquell moment ha tingut ganes d’obrir la boca. Per agafar un exemple recent, m’és indiferent que en Duran i Lleida “opini públicament” que el seu partit no és culpable de finançament il·legal. El que és important, i hauria de ser notícia, és que la sentència judicial així ho declara (i, a més, el propi partit ho accepta com a cert).

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.

Probabilitats i l’amic invisible: quantes vegades hem de repetir l’assignació?

Abans d’ahir a la feina parlàvem sobre l’amic invisible i la probabilitat que al fer les assignacions a ningú li toqui fer-se un regal a si mateix. És a dir, si un conjunt de persones escriuen el seu nom en un paper, els barregen i en reparteixen aleatòriament un a cada un, quina és la probabilitat que ningú s’hagi quedat amb el paper que té escrit el seu nom?

Resulta que aquesta probabilitat no és res més que la proporció del número de desarranjaments (o derangements, en anglès) respecte el número total de permutacions possibles. Un desarranjament d’un conjunt S és una permutació dels elements d’aquest conjunt en la qual cap dels elements no apareix en la seva posició original. O el que és el mateix, una bijecció f:S\to S sense punts fixos, on f(x)\neq x per qualsevol x\in S.

El número de permutacions possibles d’un conjunt de n elements és el factorial de n: podem escollir el primer element d’entre n elements diferents, el segon d’entre n-1, etc., de manera que el total de combinacions possibles és n!=n(n-1)(n-2)\ldots 1.

Comptar el número de desarranjaments és un xic més complex. Una manera de fer-ho és utilitzar el principi d’inclusió-exclusió. Però com en moltes altres situacions en què hem de “comptar coses”, una bona manera de fer-ho és amb funcions generatrius. Una funció generatriu és “un estenedor on pengem una seqüència de números per mostrar”, o més formalment un sèrie formal de potències, on els coeficients codifiquen la informació d’una seqüència de números \{d_n\}.

Per comptar el número de desarranjaments amb funcions generatrius primer necessitem una relació de recurrència. Considerem que tenim un conjunt de n+1 elements, S_{n+1}=\{1,2,\ldots,n+1\}. Aquest conjunt té d_{n+1} desarranjaments. Agafem el desarranjament \sigma=\{\sigma_1\sigma_2\ldots\sigma_{n+1}\} tal que \sigma_{n+1}=j, on 1\leq j\leq n. Tenim dos casos possibles:

  • Si \sigma_j\neq n+1, cada un dels elements \sigma_i, amb 1\leq i\leq n, té un element prohibit del conjunt \{1,2,\ldots,n\} (tots tenen prohibit el seu índex), i per tant en aquest cas hi ha d_n desarranjaments possibles.
  • Si en canvi \sigma_j=n+1, cada un dels n-1 elements \sigma_i, amb i\neq j,n+1 té un element prohibit del conjunt \{1,2,\ldots,j-1,j+1,\ldots,n\}, i per tant en aquest cas hi ha d_{n-1} desarranjaments possibles.

Finalment, com que hi ha n maneres diferents d’escollir j, podem escriure

\displaystyle d_{n+1} = n (d_n + d_{n-1})

per n\ge3. Si n=1, no hi ha cap desarranjament possible (d_1=0); si n=2, n’hi ha un (d_2=1). Podem definir també d_0=1 i així la relació anterior és vàlida també per n=2. Ja tenim doncs la funció de recurrència. Ara utilitzem la funció generatriu exponencial de d_n:

\displaystyle D(x) = \sum_{n\ge0}\frac{d_n}{n!}x^n.

Fixeu-vos que cada terme de la sèrie és la divisió entre el número de desarranjaments i el número de permutacions per un conjunt de mida n, que és just la probabilitat que estem buscant. Multipliquem per x^n/n! a banda i banda de la relació de recurrència, i sumem per n\ge0:

\displaystyle \sum_{n\ge0}\frac{d_{n+1}}{n!}x^n = \sum_{n\ge0}\frac{n d_n}{n!}x^n + \sum_{n\ge0}\frac{nd_{n-1}}{n!}x^n.

El terme de l’esquerra és la derivada de D(x) respecte x. El primer terme de la dreta és xD^\prime(x), i el segon és directament xD(x). Per tant, ho podem reescriure com

\displaystyle D^\prime(x) = xD^\prime(x)+xD(x).

I d’aquí, trobar una expressió tancada per D(x) fent alguna integral (i utilitzant que D(0)=1):

\displaystyle \frac{D^\prime(x)}{D(x)} = \frac{x}{1-x}

\displaystyle \ln D(x) = \int \frac{x}{1-x}dx = -\ln (1-x) -x

\displaystyle D(x) = \frac{e^{-x}}{1-x}

El terme n-èssim de la sèrie D(x), que escrivim com [x^n]D(x), és d_n/n!. Això, com hem vist abans, és la probabilitat que estem buscant: el número de desarranjaments entre el número de permutacions. D’altra banda, [x^n]e^{-x}=(-1)^n/n!, i per tant la probabilitat que busquem és

\displaystyle \frac{d_n}{n!} = [x^n]\frac{e^{-x}}{1-x} = \sum_{j=0}^n \frac{(-1)^j}{j!}.

A d_n també se l’anomena el subfactorial, que s’escriu com !n. Finalment, una última curiositat: si la mida del conjunt, n, tendeix a infinit, el número de desarranjaments entre el número de permutacions (i per tant la probabilitat que el repartiment en l’amic invisible sigui vàlid) tendeix a l’invers del número e:

\displaystyle \lim_{n\to\infty} \frac{!n}{n!} = \frac{1}{e} \simeq 0.3679.

Per tant, és d’esperar que hàgim de repetir 3 vegades les assignacions en l’amic invisible per a que ningú es tingui a ell mateix. Però això és independent de com de gran sigui el grup que hi participa!

El problema de trobar el número de desarranjaments d’un conjunt de n elements va ser plantejat per primer vegada per Pierre de Montmort el 1708, i solucionat per ell mateix el 1713 i independentment per Nicolaus Bernoulli més o menys a la vegada.

Ciència oberta: Michael Nielsen a Barcelona

Crec que el títol ja ho diu tot. Aquest dimecres, Michael Nielsen farà una conferència a l’Institut d’Estudis Catalans sobre ciència oberta (un terme segurament més conegut en anglès, open science). Abans de promoure la ciència oberta, Michael Nielsen va ser investigador en informació quàntica, i és coautor del llibre Quantum Computation and Quantum Information, que serveix de referència en aquest camp.

La conferència serà dimecres 14 de setembre a les 19:00, a la sala Prat de la Riba de l’Institut d’Estudis Catalans (c. del Carme 47, Barcelona).

Internet està provocant un canvi radical en la manera com es produeixen els descobriments científics. A aquesta conferència explico que les col·laboracions online en massa s’estan fent servir per demostrar teoremes matemàtics i per externalitzar problemes científics. També que compartir projectes científics a la xarxa està fent possible que els aficionats duguin a terme descobriments científics. Emprar els recursos online permet amplificar la nostra intel·ligència col·lectiva i ampliar la nostra capacitat de resoldre problemes científics. Avui dia encara hi ha moltes barreres culturals que cohibeixen els científics a l’hora de fer servir els recursos online a fons. A la conferència es parlarà d’aquestes barreres, i també de la manera de superar-les.

Follow

Get every new post delivered to your Inbox.

Join 158 other followers