Q

Non si prosegua l'azione secondo un piano.

Tag: informació quàntica

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.

Criptografia quàntica (i II)

Ve de “Criptografia quàntica (I)”.

Aquesta segona part de l’article explica el BB84, el primer protocol de criptografia quàntica i també el més senzill. Aquest protocol el van proposar el 1984 Charles H. Bennet, d’IBM New York, i Gilles Brassard, de la Universitat de Montréal.

Estats i bases

En aquest protocol s’utilitza un sistem quàntic de dos nivells, és a dir, que qualsevol estat posible d’aquest sistema es pot representar mitjançant una combinació lineal de dos estats que formen una base. D’aquest sistema s’utilitzen dues bases, cada una formada per dos estats, de manera que en total estarem utilitzant quatre estats diferents.

Normalment s’utilitza la polartització de la llum: els fotons, que es poden entendre com paquets indivisibles de llum. Cada fotó pot estar polaritzat verticalment |\uparrow\,\rangle, horitzontalment |\to\,\rangle, +45 graus |\nearrow\,\rangle o -45 graus |\searrow\,\rangle. Els dos primers formen la base horitzontal-vertical +, i els dos últims la base diagonal \times.

Així, si mesurem l’estat |\uparrow\,\rangle amb la base + obtenim el mateix estat amb probabilitat 1, ja que estem mesurant un estat que és “propi” de la base utilitzada. Si en canvi mesurem l’estat |\nearrow\,\rangle amb la base +, podem obtenir o bé |\uparrow\,\rangle amb probabilitat 0.5 o bé |\to\,\rangle amb probabilitat 0.5, ja que l’estat no és propi de la base utilitzada. Per conveni, s’assigna el valor binari 0 als estats |\uparrow\,\rangle|\nearrow\,\rangle i el valor 1 als altres dos. A aquests estats se’ls anomena qubits, de quantum bits.

El protocol

Vist això, el protocol segueix uns passos molt senzills. Suposem que l’Alice i en Bob volen crear una clau, i que l’Eve els espia per intentar conèixer quina clau faran servir.

Primer, l’Alice genera aleatòriament una cadena de fotons, cada un amb una polarització a l’atzar, i els envia a en Bob. La cadena pot ser realment aleatòria, i no simplement pseudoaleatòria, perquè pot utilitzar la mecànica quàntica.

En Bob mesura els estats que li van arribant de l’Alice, cada vegada amb una de les dues bases + o \times a l’atzar. D’aquesta manera, si l’estat que li arriba és propi de la base amb què mesura, obté el mateix estat que li ha arribat, mentre que si li arriba un estat que no és propi, obté la meitat de resultats bons i la meitat de dolents. Com que aproximadament en la meitat dels casos haurà utilitzat la base bona i en l’altra meitat la dolenta, en resum en Bob obté l’anomenada raw key o clau en brut, que té aproximadament un 25% d’errors.

Evidentment, no pot fer servir aquesta clau perquè hi ha massa errors. El que fa en Bob ara és anunciar públicament quina base ha utilitzat cada vegada, i l’Alice respon públicament si la base que en Bob ha utilitzat cada vegada és bona o no, és a dir, si l’estat que enviava era propi d’aquesta base o no. Això no revela cap mena d’informació, perquè l’únic que s’ha fet públic és la base utilitzada, i no el bit transmès cada vegada.

Així doncs, tant l’Alice com en Bob es queden amb els estats mesurats amb bases bones i descarten els dolents, de manera que es queden amb la shifted key, aproximadament la meitat de llarga que la raw key però sense cap error.

Posant un exemple, l’Alice podria enviar, a l’atzar, els estats

| \nearrow \, \rangle | \to \, \rangle | \uparrow \, \rangle | \uparrow \, \rangle | \searrow \, \rangle | \searrow \, \rangle | \to \, \rangle | \nearrow \, \rangle

En Bob els mesuraria utilitzant les bases, també escollides a l’atzar,

+ + \times + \times + \times \times

Quan en Bob mesura l’estat mesura amb la base compatible, obté el mateix qubit que li havia enviat l’Alice. Quan mesura amb la base incompatible, pot obtenir amb igual probabilitat un resultat o un altre. Per exemple, quan mesuri | \nearrow \, \rangle amb la base + pot obtenir o bé | \uparrow \, \rangle o bé | \to \, \rangle, que són els dos estats propis de la base amb què ha mesurat.

Després d’haver mesurat, en Bob anunciaria les bases que ha utilitzat i l’Alice li diria que només s’ha de quedar amb els resultats 2, 4, 5 i 8. Resumint, i fent servir el conveni de 0 i 1 d’abans,

\begin{array}{lcccccccc}  \textrm{Enviat per l'Alice:} & | \nearrow \, \rangle & | \to \, \rangle & | \uparrow \, \rangle & | \uparrow \, \rangle & | \searrow \, \rangle & | \searrow \, \rangle & | \to \, \rangle & | \nearrow \, \rangle \\  \textrm{Base d'en Bob:} & + & + & \times & + & \times & + & \times & \times \\  \textrm{Rebut per en Bob:} & | \uparrow \, \rangle & | \to \, \rangle & | \searrow \, \rangle & | \uparrow \, \rangle & | \searrow \, \rangle & | \to \, \rangle & | \nearrow \, \rangle & | \nearrow \, \rangle \\  \textrm{Acceptat:} & & | \to \, \rangle & & | \uparrow \, \rangle & | \searrow \, \rangle & & & | \nearrow \, \rangle \\  \textrm{Shifted key:} & & 1 & & 0 & 1 & & & 0  \end{array}

El canal que utilitzen l’Alice i en Bob no cal que sigui confidencial. Això és així perquè Eve no pot interceptar qubits i reenviar-los en el seu estat original mantenint-ne una còpia. És l’anomenat teorema de no clonació (No cloning theorem), demostrat per Wootters i Zurek el 1982. L’Eve simplement es podria quedar el qubit, i no reenviar-ne cap a en Bob, però llavors en Bob podria avisar l’Alice que descartés el qubit que no ha rebut.

Estratègia d’interceptar-reenviar

Tanmateix, l’Eve pot dur a terme un senzill atac consistent en mesurar a l’atzar amb una de les dues bases possibles cada qubit que l’Alice envia a en Bob, i una vegada mesurat enviar a en Bob el qubit corresponent al resultat obtingut. Així, en un 50% dels casos l’Eve mesurarà amb la base correcta, sense modificar l’estat, obtenint la informació i sense que l’Alice o en Bob ho puguin detectar. En l’altre 50% dels casos, utilitzarà la base incorrecta. Llavors, el qubit enviat tindrà un 50% de probabilitat de ser mesurat per en Bob com si fos el correcte, i un 50% com si fos l’incorrecte.

Resumint, mesurant tots els estats enviats l’Eve obté un 50% de la informació, mentre que l’Alice i en Bob acaben amb una shifted key que té un 25% d’errors. Aquest nivell d’errors és detectable, però si Eve només interceptés el 10% dels qubits enviats, obtindria un 5% de la informació mentre que l’error final de la shifted key seria tan sols d’un 2.5%, que és comparable a l’error obtingut per causes tècniques.

Utilitzant el mateix exemple, l’Alice envia els mateixos estats i en Bob utilitza les mateixes bases, abans que els qubits arribin a en Bob l’Eve els mesura amb les seves bases, també escollides a l’atzar. Així,

\begin{array}{lcccccccc}  \textrm{Enviat per l'Alice:} & | \nearrow \, \rangle & | \to \, \rangle & | \uparrow \, \rangle & | \uparrow \, \rangle & | \searrow \, \rangle & | \searrow \, \rangle & | \to \, \rangle & | \nearrow \, \rangle \\  \textrm{Base de l'Eve:} & \times & + & \times & \times & \times & + & \times & + \\  \textrm{Rebut i enviat per l'Eve:} & | \nearrow \, \rangle & | \to \, \rangle & | \nearrow \, \rangle & | \searrow \, \rangle & | \searrow \, \rangle & | \to \, \rangle & | \searrow \, \rangle & | \to \, \rangle \\  \textrm{Base d'en Bob:} & + & + & \times & + & \times & + & \times & \times \\  \textrm{Rebut per en Bob:} & | \uparrow \, \rangle & | \to \, \rangle & | \nearrow \, \rangle & | \uparrow \, \rangle & | \searrow \, \rangle & | \to \, \rangle & | \searrow \, \rangle & | \searrow \, \rangle \\  \textrm{Acceptat:} & & | \to \, \rangle & & | \uparrow \, \rangle & | \searrow \, \rangle & & & | \searrow \, \rangle \\  \textrm{Shifted key de l'Alice:} & & 1 & & 0 & 1 & & & 0 \\  \textrm{Shifted key de l'Eve:} & & 1 & & - & 1 & & & - \\  \textrm{Shifted key d'en Bob} & & 1 & & 0 & 1 & & & 1  \end{array}

Com es veu, les claus de l’Alice i en Bob tenen errors (en aquest cas, en l’últim bit). Per la seva banda, l’Eve ha aconseguit informació parcial sobre la clau. Sap que el primer i el tercer bit de la shifted key són un 1, i s’ha adonat que els qubits mesurats en segon i quart lloc són probablement incorrectes perquè la seva base no coincideix amb la d’en Bob (que s’ha fet pública).

Per saber si l’Eve ha espiat la seva comunicació, l’Alice i en Bob poden comparar una part aleatòria de la shifted key i estimar-ne l’error. Si el nivell d’errors és acceptable dins els marges tècnics, accepten la clau, descartant evidentment la part comparada; sinó, tornen a començar el protocol.

Correcció d’errors i ampliació de privacitat

Els dos últims passos en un protocol de criptografia quàntica utilitzen algoritmes clàssics: d’una banda, per corregir els errors de la clau, i de l’altra, per reduir la informació que té l’Eve de la clau final. Aquests algortimes van ser proposats inicialment per Bennett, Brassard i Robert (1988).

En primer lloc, cal corregir els errors en la clau, que poden ser deguts tant a causes tècniques com a l’Eve. En el cas més simple d’algoritme de correcció d’errors, l’Alice escull una parella aleatòria de bits i els suma XOR, és a dir, 0\oplus0=00\oplus1=11\oplus0=1 i 1\oplus1=0. Si la suma corresponent d’en Bob coincideix, l’Alice i en Bob mantenen el primer bit i rebutgen el segon. Si la suma no coincideix, rebutgen els dos. A la pràctica, s’utilitzen algoritmes més sofisticats i eficients.

Després de la correcció d’errors, l’Alice i en Bob tenen claus idèntiques, però l’Eve encara pot tenir informació. Per reduir-la, l’Alice suma XOR altra vegada dos bits aleatoris, i en Bob fa el mateix amb els seus corresponents. Llavors, l’Alice i en Bob es queden només amb el resultat de la suma. Així, si l’Eve no té informació d’algun dels dos bits, no té cap mena d’informació de la seva suma XOR.

En resum, la criptografia quàntica només s’aplica en la creació i distribució d’una clau simètrica. A més, el canal necessita autentificació: l’Alice i en Bob poden utilitzar un canal no confidencial però han de saber que efectivament l’altra persona és qui diu ser. Per a fer-ho, poden utilitzar una clau més curta, i llavors amb la criptografia quàntica n’obtenen una de més llarga, de la qual en poden guardar una part per a la següent sessió.

Criptografia quàntica (I)

L’altre dia vaig trobar aquest article doble, escrit fa 6 anys a la carrera de física, i m’ha fet gràcia. Així que el reprodueixo aquí. És una petita introducció a la criptografia quàntica.

La criptografia clàssica asimètrica és dèbil perquè basa la seva seguretat en suposicions no demostrades, mentre que la criptografia clàssica simètrica no pot solucionar el problema de l’intercanvi de clau. La criptografia quàntica obre una possible via per solucionar aquests problemes.

Aquesta primera part de l’article introdueix la criptografia clàssica i explica els conceptes necessaris de mecànica quàntica per tal de poder explicar els protocols de la criptografia quàntica.

Criptografia clàssica

La criptografia és l’art d’inventar codis i xifres, i la criptoanàlisi el de trencar-los. La criptologia és la branca de les matemàtiques que inclou la criptografia i la criptoanàlisi.

L’objectiu de la criptografia és transmetre informació de tal manera que només el receptor desitjat hi pugui accedir. Per a fer-ho, s’utilitza un algoritme (anomenat també criptosistema o xifra) que combina el missatge sense encriptar (text pla) amb altra informació (clau) per a obtenir el missatge encriptat (criptograma). Per a que un sistema sigui segur, ha de ser impossible recuperar el missatge original a partir del missatge encriptat sense tenir la clau. A la pràctica, s’accepta que sigui només extremadament difícil de recuperar.

Una vegada emissor i receptor s’han posat d’acord amb el sistema i la clau a utilitzar, es poden intercanviar missatges encriptats a través d’un canal insegur (és a dir, que pot ser espiat) sense que la informació que s’enviin estigui compromesa.

Hi ha dues classes en la criptografia moderna: els criptosistemes asimètrics (o de clau pública) i els simètrics. En els criptosistemes simètrics s’utilitza la mateixa clau per encriptar que per desencriptar. En els asimètrics, en canvi, existeixen dues claus: la pública, utilitzada per encriptar, i la privada, utilitzada per desencriptar. Aquests sistemes confien en què hi ha alguns problemes matemàtics que són extremadament difícils de solucionar, com ara la factorització del producte de dos nombres primers molt grans.

El problema dels criptosistemes asimètrics és que descobriments nous poden convertir els problemes matemàtics extremadament difícils en no tan difícils i, per tant, comprometre la seguretat. Per exemple, Peter Shor va descobrir el 1994 un algoritme polinòmic que permet la ràpida factorització d’enters en un ordiandor quàntic.

El problema dels criptosistemes simètrics és que emissor i receptor han de compartir un canal completament segur en algun moment de la comunicació per tal d’intercanviar la clau.

Criptografia quàntica

La criptografia quàntica es va descobrir independentment als Estats Units i a Europa. El primer a proposar-la va ser Stephen Wiesner a principis dels anys 70 amb la introducció del concepte de codificació quàntica conjugada, Conjugate Coding, publicat el 1983. Explicava com emmagatzemar o transmetre informació utilitzant “observables conjugats” com ara la polarització lineal i circular de la llum, de manera que un dels dos, però no els dos, es pogués rebre i interpretar. Una dècada després, el 1984, Charles H. Bennett i Gilles Brassard van proposar el primer protocol de criptografia quàntica, anomenat BB84. El 1991 es va aconseguir el primer prototip experimental, treballant amb una distància de 32 centímetres. El 1990, Artur Ekert va desenvolupar de manera independent un protocol de criptografia quàntica basada en les correlacions quàntiques anomenades entrellaçaments (entanglenment). Actualment la criptografia quàntica s’ha convertit en un camp experimental i ja han sortit les primeres aplicacions comercials.

Mecànica quàntica

Evidentment els protocols de criptografia quàntica utilitzen els conceptes desenvolupats en la mecànica quàntica.

En la visió clàssica, una magnitud (per exemple, la posició d’una partícula o la seva velocitat) ens pot ser desconeguda, però tanmateix aquesta partícula la té. És a dir, potser no sabem on està situada la partícula, però aquesta està sens dubte situada en algun lloc. Quan nosaltres mesurem aquesta magnitud que desconeixem, el que estem fent és “llegir” el valor que ja tenia el sistema.

En la visió quàntica, hi ha magnituds que ens són desconegudes i que a més no tenen un valor concret assignat, sinó una certa distribució de probabilitat. Tornant al mateix exemple, una partícula pot estar a dos o més llocs simultàniament, d’alguna manera difuminada per l’espai. És un concepte totalment contraintuïtiu però que s’ha demostrat experimentalment. Quan mesurem aquesta magnitud, el que estem fent és que el sistema “es decideixi”, aleatòriament, per un dels seus valors possibles. D’aquesta manera, obtenim un resultat i modifiquem el sistema, que passa ara a estar en l’estat que ha resultat de la mesura. És a dir, si hem observat en quina posició està una partícula difuminada per l’espai, hem obtingut que està en un determinat lloc i a partir d’ara la partícula està efectivament en aquest lloc. Obtenim un valor i modifiquem el sistema. Evidentment, de vegades el sistema quàntic ja té un determinat valor compatible amb la mesura, i en mesurar simplement el llegim, igual que fèiem en la visió clàssica.

Aquest, com veurem més endavant, és un dels principis claus que s’utilitzen en els protocols de criptografia quàntica: Qualsevol mesura pertorba el sistema, excepte si l’estat quàntic és compatible amb la mesura.

També és clarament molt important la capacitat d’un sistema quàntic de generar valors completament aleatoris. Com sabem, els ordinadors són sistemes deterministes i fins ara només podíem obtenir números pseudoaleatoris.

Segueix a “Criptografia quàntica (i II)”.

Follow

Get every new post delivered to your Inbox.

Join 158 other followers