EITC/QI/QIF Quantum Information Fundamentals és el programa europeu de certificació informàtica sobre aspectes teòrics i pràctics de la informació quàntica i la computació quàntica, basat en les lleis de la física quàntica en lloc de les de la física clàssica i que ofereix avantatges qualitatius respecte als seus homòlegs clàssics.
El currículum dels Fonaments d'Informació Quàntica EITC/QI/QIF inclou la introducció a la mecànica quàntica (incloent la consideració de l'experiment de doble escletxa i la interferència d'ones de matèria), introducció a la informació quàntica (qubits i la seva representació geomètrica), polarització de la llum, principi d'incertesa, entrellaçament, paradoxa EPR, violació de la desigualtat de Bell, abandonament del realisme local, processament d'informació quàntica (incloent transformació unitària, portes d'un sol qubit i de dos qubits), teorema de no clonació, teletransportació quàntica, mesura quàntica, càlcul quàntic (inclosa la introducció a la multi - sistemes qubit, família universal de portes, reversibilitat de la computació), algoritmes quàntics (incloent la transformada quàntica de Fourier, l'algoritme de Simon, la tesi ampliada de Churh-Turing, l'algoritme de factorització quàntica de Shor'q, l'algoritme de cerca quàntica de Grover), observables quàntics, l'equació de Shrodinger, implementacions de qubits, teoria de la complexitat quàntica, computació quàntica adiabàtica ion, BQP, introducció a l'espin, dins de l'estructura següent, que inclou un contingut didàctic de vídeo complet com a referència per a aquesta Certificació EITC.
La informació quàntica és la informació de l'estat d'un sistema quàntic. És l'entitat bàsica d'estudi de la teoria de la informació quàntica i es pot manipular mitjançant tècniques de processament de la informació quàntica. La informació quàntica fa referència tant a la definició tècnica en termes d'entropia de Von Neumann com al terme computacional general.
La informació i la computació quàntica és un camp interdisciplinari que inclou la mecànica quàntica, la informàtica, la teoria de la informació, la filosofia i la criptografia entre altres camps. El seu estudi també és rellevant per a disciplines com la ciència cognitiva, la psicologia i la neurociència. El seu objectiu principal és extreure informació de la matèria a escala microscòpica. L'observació en la ciència és un criteri distintiu fonamental de la realitat i una de les maneres més importants d'adquirir informació. Per tant, és necessària la mesura per quantificar l'observació, per la qual cosa és crucial per al mètode científic. En mecànica quàntica, a causa del principi d'incertesa, no es poden mesurar amb precisió simultàniament els observables que no es desplacen, ja que un estat propi en una base no és un estat propi en l'altra base. Com que ambdues variables no estan ben definides simultàniament, un estat quàntic mai pot contenir informació definitiva sobre ambdues variables. A causa d'aquesta propietat fonamental de la mesura en mecànica quàntica, aquesta teoria es pot caracteritzar en general com a no determinista en contrast amb la mecànica clàssica, que és totalment determinista. L'indeterminisme dels estats quàntics caracteritza la informació definida com a estats dels sistemes quàntics. En termes matemàtics, aquests estats es troben en superposicions (combinacions lineals) dels estats dels sistemes clàssics.
Com que la informació sempre està codificada en l'estat d'un sistema físic, és física en si mateixa. Mentre que la mecànica quàntica s'ocupa d'examinar les propietats de la matèria a nivell microscòpic, la ciència de la informació quàntica se centra a extreure informació d'aquestes propietats, i la computació quàntica manipula i processa la informació quàntica, realitza operacions lògiques, utilitzant tècniques de processament d'informació quàntica.
La informació quàntica, com la informació clàssica, es pot processar mitjançant ordinadors, transmetre's d'un lloc a un altre, manipular-se amb algorismes i analitzar-se amb informàtica i matemàtiques. De la mateixa manera que la unitat bàsica de la informació clàssica és el bit, la informació quàntica tracta els qubits, que poden existir en superposició de 0 i 1 (simultàniament sent una mica cert i fals). La informació quàntica també pot existir en els anomenats estats entrellaçats, que manifesten correlacions no locals purament no clàssiques en les seves mesures, permetent aplicacions com la teletransportació quàntica. El nivell d'entrellaçament es pot mesurar mitjançant l'entropia de Von Neumann, que també és una mesura de la informació quàntica. Recentment, el camp de la computació quàntica s'ha convertit en una àrea de recerca molt activa a causa de la possibilitat d'interrompre la computació, la comunicació i la criptografia modernes.
La història de la informació quàntica va començar a principis del segle XX, quan la física clàssica es va revolucionar en física quàntica. Les teories de la física clàssica prediuen absurditats com la catàstrofe ultraviolada o els electrons en espiral cap al nucli. Al principi, aquests problemes es van deixar de banda afegint hipòtesis ad hoc a la física clàssica. Aviat, es va fer evident que s'havia de crear una nova teoria per tal de donar sentit a aquests absurds, i va néixer la teoria de la mecànica quàntica.
La mecànica quàntica va ser formulada per Schrödinger mitjançant la mecànica ondulatòria i Heisenberg amb la mecànica matricial. L'equivalència d'aquests mètodes es va demostrar més tard. Les seves formulacions descriuen la dinàmica dels sistemes microscòpics, però tenien diversos aspectes insatisfactoris en la descripció dels processos de mesura. Von Neumann va formular la teoria quàntica utilitzant àlgebra d'operadors d'una manera que descrivia tant la mesura com la dinàmica. Aquests estudis van emfatitzar els aspectes filosòfics de la mesura més que un enfocament quantitatiu per extreure informació mitjançant mesures.
A la dècada de 1960, Stratonovich, Helstrom i Gordon van proposar una formulació de comunicacions òptiques utilitzant la mecànica quàntica. Aquesta va ser la primera aparició històrica de la teoria de la informació quàntica. Van estudiar principalment les probabilitats d'error i les capacitats de canal per a la comunicació. Més tard, Holevo va obtenir un límit superior de velocitat de comunicació en la transmissió d'un missatge clàssic mitjançant un canal quàntic.
A la dècada de 1970 es van començar a desenvolupar tècniques de manipulació d'estats quàntics d'un sol àtom, com ara la trampa d'àtoms i el microscopi de túnel d'escaneig, que van permetre aïllar àtoms individuals i disposar-los en matrius. Abans d'aquests desenvolupaments, no era possible un control precís sobre sistemes quàntics únics, i els experiments utilitzaven un control simultani més gruixut sobre un gran nombre de sistemes quàntics. El desenvolupament de tècniques viables de manipulació d'un sol estat va provocar un interès creixent en el camp de la informació i la computació quàntica.
A la dècada de 1980, va sorgir l'interès per saber si podria ser possible utilitzar efectes quàntics per refutar la teoria de la relativitat d'Einstein. Si fos possible clonar un estat quàntic desconegut, seria possible utilitzar estats quàntics entrellaçats per transmetre informació més ràpid que la velocitat de la llum, desmentint la teoria d'Einstein. Tanmateix, el teorema de la no clonació va demostrar que aquesta clonació és impossible. El teorema va ser un dels primers resultats de la teoria de la informació quàntica.
Desenvolupament a partir de la criptografia
Malgrat tota l'emoció i l'interès per estudiar sistemes quàntics aïllats i intentar trobar una manera d'eludir la teoria de la relativitat, la investigació en teoria de la informació quàntica es va estancar als anys vuitanta. Tanmateix, al mateix temps, una altra via va començar a incursionar en la informació i la computació quàntica: la criptografia. En un sentit general, la criptografia és el problema de fer comunicació o càlcul en què participen dues o més parts que potser no confien entre elles.
Bennett i Brassard van desenvolupar un canal de comunicació en el qual és impossible escoltar sense ser detectat, una manera de comunicar-se en secret a llargues distàncies mitjançant el protocol criptogràfic quàntic BB84. La idea clau era l'ús del principi fonamental de la mecànica quàntica que l'observació pertorba l'observat, i la introducció d'un escolta en una línia de comunicació segura permetrà immediatament que les dues parts que intentin comunicar-se sàpiguen de la presència de l'escolta.
Desenvolupament des de la informàtica i les matemàtiques
Amb l'arribada de les idees revolucionàries d'Alan Turing d'un ordinador programable, o màquina de Turing, va demostrar que qualsevol càlcul del món real es pot traduir en un càlcul equivalent que implicava una màquina de Turing. Això es coneix com la tesi Church-Turing.
Ben aviat, es van fabricar els primers ordinadors i el maquinari informàtic va créixer a un ritme tan ràpid que el creixement, a través de l'experiència en la producció, es va codificar en una relació empírica anomenada llei de Moore. Aquesta "llei" és una tendència projectiva que estableix que el nombre de transistors en un circuit integrat es duplica cada dos anys. A mesura que els transistors van començar a fer-se cada cop més petits per tal d'acumular més potència per àrea de superfície, els efectes quàntics van començar a aparèixer a l'electrònica, donant lloc a interferències inadvertides. Això va provocar l'aparició de la computació quàntica, que utilitzava la mecànica quàntica per dissenyar algorismes.
En aquest punt, els ordinadors quàntics prometien ser molt més ràpids que els ordinadors clàssics per a certs problemes específics. Un d'aquests exemples de problemes el van desenvolupar David Deutsch i Richard Jozsa, conegut com l'algoritme Deutsch–Jozsa. Aquest problema, però, tenia poques o cap aplicació pràctica. Peter Shor l'any 1994 va plantejar un problema molt important i pràctic, el de trobar els factors primers d'un nombre enter. El problema del logaritme discret, com es deia, es podria resoldre de manera eficient en un ordinador quàntic, però no en un ordinador clàssic, per tant, demostrant que els ordinadors quàntics són més potents que les màquines de Turing.
Desenvolupament a partir de la teoria de la informació
Al voltant de l'època en què la informàtica estava fent una revolució, també ho van fer la teoria de la informació i la comunicació, a través de Claude Shannon. Shannon va desenvolupar dos teoremes fonamentals de la teoria de la informació: el teorema de codificació de canals sorollosos i el teorema de codificació de canals sorollosos. També va mostrar que els codis de correcció d'errors es podrien utilitzar per protegir la informació que s'envia.
La teoria de la informació quàntica també va seguir una trajectòria similar, Ben Schumacher el 1995 va fer un anàleg al teorema de codificació sense soroll de Shannon utilitzant el qubit. També es va desenvolupar una teoria de correcció d'errors, que permet als ordinadors quàntics fer càlculs eficients independentment del soroll i fer una comunicació fiable a través de canals quàntics sorollosos.
Qubits i teoria de la informació
La informació quàntica difereix fortament de la informació clàssica, resumida pel bit, de moltes maneres sorprenents i desconegudes. Mentre que la unitat fonamental de la informació clàssica és el bit, la unitat més bàsica d'informació quàntica és el qubit. La informació clàssica es mesura mitjançant l'entropia de Shannon, mentre que l'anàleg de la mecànica quàntica és l'entropia de Von Neumann. Un conjunt estadístic de sistemes de mecànica quàntica es caracteritza per la matriu de densitat. Moltes mesures d'entropia en la teoria clàssica de la informació també es poden generalitzar al cas quàntic, com l'entropia Holevo i l'entropia quàntica condicional.
A diferència dels estats digitals clàssics (que són discrets), un qubit té un valor continu, es pot descriure per una direcció a l'esfera de Bloch. Tot i valorar-se contínuament d'aquesta manera, un qubit és la unitat més petita possible d'informació quàntica i, malgrat que l'estat del qubit té valors continus, és impossible mesurar el valor amb precisió. Cinc teoremes famosos descriuen els límits de la manipulació de la informació quàntica:
- teorema de no-teletransportació, que afirma que un qubit no es pot convertir (totalment) en bits clàssics; és a dir, no es pot "llegir" completament,
- teorema de no clonació, que impedeix que es copi un qubit arbitrari,
- teorema sense supressió, que evita que un qubit arbitrari s'elimini,
- teorema de no-difusió, que impedeix que un qubit arbitrari sigui lliurat a diversos destinataris, tot i que es pot transportar d'un lloc a un altre (per exemple, mitjançant la teletransportació quàntica),
- teorema de no ocultació, que demostra la conservació de la informació quàntica,Aquests teoremes demostren que la informació quàntica dins de l'univers es conserva i obren possibilitats úniques en el processament de la informació quàntica.
Processament quàntic d’informació
L'estat d'un qubit conté tota la seva informació. Aquest estat s'expressa sovint com un vector a l'esfera de Bloch. Aquest estat es pot canviar aplicant-hi transformacions lineals o portes quàntiques. Aquestes transformacions unitàries es descriuen com a rotacions a l'esfera de Bloch. Mentre que les portes clàssiques corresponen a les operacions familiars de la lògica booleana, les portes quàntiques són operadors físics unitaris.
A causa de la volatilitat dels sistemes quàntics i la impossibilitat de copiar estats, emmagatzemar la informació quàntica és molt més difícil que emmagatzemar la informació clàssica. No obstant això, amb l'ús de la correcció d'errors quàntics, la informació quàntica encara es pot emmagatzemar de manera fiable en principi. L'existència de codis de correcció d'errors quàntics també ha donat lloc a la possibilitat de càlcul quàntic tolerant a errors.
Els bits clàssics es poden codificar i, posteriorment, recuperar-se de configuracions de qubits, mitjançant l'ús de portes quàntiques. Per si mateix, un únic qubit no pot transmetre més d'un bit d'informació clàssica accessible sobre la seva preparació. Aquest és el teorema d'Holevo. Tanmateix, en la codificació superdensa, un emissor, actuant sobre un dels dos qubits entrellaçats, pot transmetre dos bits d'informació accessible sobre el seu estat conjunt a un receptor.
La informació quàntica es pot moure, en un canal quàntic, de manera anàloga al concepte de canal de comunicacions clàssic. Els missatges quàntics tenen una mida finita, mesurada en qubits; Els canals quàntics tenen una capacitat de canal finita, mesurada en qubits per segon.
La informació quàntica i els canvis en la informació quàntica es poden mesurar quantitativament utilitzant un anàleg de l'entropia de Shannon, anomenada entropia de von Neumann.
En alguns casos, els algorismes quàntics es poden utilitzar per realitzar càlculs més ràpid que en qualsevol algorisme clàssic conegut. L'exemple més famós d'això és l'algorisme de Shor que pot factoritzar nombres en temps polinomial, en comparació amb els millors algorismes clàssics que prenen temps subexponencial. Com que la factorització és una part important de la seguretat del xifratge RSA, l'algoritme de Shor va desencadenar el nou camp de la criptografia postquàntica que intenta trobar esquemes de xifratge que romanguin segurs fins i tot quan hi ha ordinadors quàntics en joc. Altres exemples d'algoritmes que demostren la supremacia quàntica inclouen l'algoritme de cerca de Grover, on l'algoritme quàntic ofereix una acceleració quadràtica sobre el millor algorisme clàssic possible. La classe de complexitat de problemes solucionables de manera eficient per un ordinador quàntic es coneix com BQP.
La distribució de claus quàntiques (QKD) permet la transmissió incondicionalment segura de la informació clàssica, a diferència del xifratge clàssic, que sempre es pot trencar en principi, si no a la pràctica. Tingueu en compte que certs punts subtils sobre la seguretat de QKD encara es debat a fons.
L'estudi de tots els temes i diferències anteriors inclou la teoria de la informació quàntica.
Relació amb la mecànica quàntica
La mecànica quàntica és l'estudi de com els sistemes físics microscòpics canvien dinàmicament a la natura. En el camp de la teoria de la informació quàntica, els sistemes quàntics estudiats s'abstreuen de qualsevol contrapart del món real. Per exemple, un qubit podria ser físicament un fotó en un ordinador quàntic òptic lineal, un ió en un ordinador quàntic d'ions atrapats, o podria ser una gran col·lecció d'àtoms com en un ordinador quàntic superconductor. Independentment de la implementació física, els límits i les característiques dels qubits implicats per la teoria de la informació quàntica es mantenen, ja que tots aquests sistemes es descriuen matemàticament pel mateix aparell de matrius de densitat sobre els nombres complexos. Una altra diferència important amb la mecànica quàntica és que, mentre que la mecànica quàntica sovint estudia sistemes de dimensions infinites com un oscil·lador harmònic, la teoria de la informació quàntica es refereix tant als sistemes de variable contínua com als sistemes de dimensions finites.
Càlcul quàntic
La computació quàntica és un tipus de càlcul que aprofita les propietats col·lectives dels estats quàntics, com ara la superposició, la interferència i l'entrellaçament, per realitzar càlculs. Els dispositius que realitzen càlculs quàntics es coneixen com a ordinadors quàntics.: I-5 Tot i que els ordinadors quàntics actuals són massa petits per superar els ordinadors habituals (clàssics) per a aplicacions pràctiques, es creu que són capaços de resoldre certs problemes computacionals, com ara la factorització de nombres enters. (que subjau al xifratge RSA), substancialment més ràpid que els ordinadors clàssics. L'estudi de la computació quàntica és un subcamp de la ciència de la informació quàntica.
La computació quàntica va començar l'any 1980 quan el físic Paul Benioff va proposar un model de mecànica quàntica de la màquina de Turing. Richard Feynman i Yuri Manin van suggerir més tard que un ordinador quàntic tenia el potencial de simular coses que un ordinador clàssic no podia fer de manera viable. El 1994, Peter Shor va desenvolupar un algorisme quàntic per factoritzar nombres enters amb el potencial de desxifrar comunicacions xifrades amb RSA. El 1998 Isaac Chuang, Neil Gershenfeld i Mark Kubinec van crear el primer ordinador quàntic de dos qubits que podia realitzar càlculs. Malgrat el progrés experimental continuat des de finals de la dècada de 1990, la majoria dels investigadors creuen que "la computació quàntica tolerant a errors [és] encara un somni força llunyà". En els darrers anys, la inversió en recerca en computació quàntica ha augmentat en els sectors públic i privat. El 23 d'octubre de 2019, Google AI, en col·laboració amb la National Aeronautics and Space Administration (NASA) dels EUA, va afirmar haver realitzat un càlcul quàntic que era inviable en qualsevol ordinador clàssic, però si aquesta afirmació era o encara és vàlida és un tema de recerca activa.
Hi ha diversos tipus d'ordinadors quàntics (també coneguts com a sistemes de computació quàntica), incloent el model de circuit quàntic, la màquina quàntica de Turing, l'ordinador quàntic adiabàtic, l'ordinador quàntic unidireccional i diversos autòmats cel·lulars quàntics. El model més utilitzat és el circuit quàntic, basat en el bit quàntic, o "qubit", que és una mica anàleg al bit en la computació clàssica. Un qubit pot estar en un estat quàntic 1 o 0, o en una superposició dels estats 1 i 0. Quan es mesura, però, sempre és 0 o 1; la probabilitat de qualsevol resultat depèn de l'estat quàntic del qubit immediatament abans de la mesura.
Els esforços per construir un ordinador quàntic físic se centren en tecnologies com transmons, trampes d'ions i ordinadors quàntics topològics, que tenen com a objectiu crear qubits d'alta qualitat.: 2–13 Aquests qubits es poden dissenyar de manera diferent, depenent del model informàtic complet de l'ordinador quàntic, ja siguin portes de lògica quàntica, recuit quàntic o càlcul quàntic adiabàtic. Actualment hi ha una sèrie d'obstacles importants per construir ordinadors quàntics útils. És especialment difícil mantenir els estats quàntics dels qubits, ja que pateixen decoherència quàntica i fidelitat d'estat. Per tant, els ordinadors quàntics requereixen correcció d'errors.
Qualsevol problema computacional que es pugui resoldre amb un ordinador clàssic també es pot resoldre amb un ordinador quàntic. Per contra, qualsevol problema que es pugui resoldre amb un ordinador quàntic també es pot resoldre amb un ordinador clàssic, almenys en principi amb el temps suficient. En altres paraules, els ordinadors quàntics obeeixen la tesi Church-Turing. Això vol dir que, mentre que els ordinadors quàntics no ofereixen avantatges addicionals sobre els ordinadors clàssics en termes de computabilitat, els algorismes quàntics per a determinats problemes tenen complexitats temporals significativament més baixes que els corresponents algorismes clàssics coneguts. En particular, es creu que els ordinadors quàntics són capaços de resoldre ràpidament certs problemes que cap ordinador clàssic podria resoldre en qualsevol període de temps factible, una gesta coneguda com a "supremacia quàntica". L'estudi de la complexitat computacional dels problemes respecte als ordinadors quàntics es coneix com a teoria de la complexitat quàntica.
El model predominant de càlcul quàntic descriu el càlcul en termes d'una xarxa de portes de lògica quàntica. Aquest model es pot pensar com una generalització lineal-algebraica abstracta d'un circuit clàssic. Com que aquest model de circuit obeeix a la mecànica quàntica, es creu que un ordinador quàntic capaç d'executar aquests circuits de manera eficient es pot realitzar físicament.
Una memòria que consta de n bits d'informació té 2^n estats possibles. Per tant, un vector que representa tots els estats de memòria té 2^n entrades (una per a cada estat). Aquest vector es veu com un vector de probabilitat i representa el fet que la memòria es troba en un estat particular.
En la visió clàssica, una entrada tindria un valor d'1 (és a dir, una probabilitat del 100% d'estar en aquest estat) i totes les altres entrades serien zero.
En mecànica quàntica, els vectors de probabilitat es poden generalitzar a operadors de densitat. El formalisme vectorial d'estat quàntic s'introdueix primer perquè és conceptualment més senzill i perquè es pot utilitzar en lloc del formalisme de la matriu de densitat per als estats purs, on es coneix tot el sistema quàntic.
un càlcul quàntic es pot descriure com una xarxa de portes i mesures de lògica quàntica. Tanmateix, qualsevol mesura es pot ajornar fins al final del càlcul quàntic, tot i que aquest ajornament pot tenir un cost computacional, de manera que la majoria dels circuits quàntics representen una xarxa que consisteix només en portes lògiques quàntiques i sense mesures.
Qualsevol càlcul quàntic (que és, en el formalisme anterior, qualsevol matriu unitària sobre n qubits) es pot representar com una xarxa de portes de lògica quàntica d'una família de portes força petita. Una selecció de la família de portes que permet aquesta construcció es coneix com a conjunt de portes universal, ja que un ordinador que pot executar aquests circuits és un ordinador quàntic universal. Un d'aquests conjunts comú inclou totes les portes d'un sol qubit així com la porta CNOT des de dalt. Això significa que qualsevol càlcul quàntic es pot realitzar executant una seqüència de portes d'un sol qubit juntament amb portes CNOT. Tot i que aquest conjunt de portes és infinit, es pot substituir per un conjunt de portes finit apel·lant al teorema de Solovay-Kitaev.
Algorismes quàntics
El progrés en la recerca d'algorismes quàntics normalment se centra en aquest model de circuit quàntic, tot i que existeixen excepcions com l'algoritme adiabàtic quàntic. Els algorismes quàntics es poden classificar aproximadament segons el tipus d'acceleració aconseguit sobre els algorismes clàssics corresponents.
Els algorismes quàntics que ofereixen més que una acceleració polinomial respecte a l'algoritme clàssic més conegut inclouen l'algoritme de Shor per factoritzar i els algorismes quàntics relacionats per calcular logaritmes discrets, resoldre l'equació de Pell i, de manera més general, resoldre el problema del subgrup ocult per a grups finits abelians. Aquests algorismes depenen de la primitiva de la transformada quàntica de Fourier. No s'ha trobat cap prova matemàtica que mostri que no es pugui descobrir un algorisme clàssic igual de ràpid, tot i que això es considera poc probable. [font autopublicada?] Alguns problemes d'oracle com el problema de Simon i el problema de Bernstein-Vazirani donen acceleracions demostrables, tot i que això es troba en el model de consulta quàntica, que és un model restringit on els límits inferiors són molt més fàcils de demostrar i no necessàriament es tradueixen en acceleracions per a problemes pràctics.
Altres problemes, inclosa la simulació de processos físics quàntics des de la química i la física de l'estat sòlid, l'aproximació de certs polinomis de Jones i l'algorisme quàntic per a sistemes d'equacions lineals, tenen algorismes quàntics que semblen donar acceleracions superpolinomials i són BQP-complets. Com que aquests problemes són BQP complets, un algorisme clàssic igualment ràpid per a ells implicaria que cap algorisme quàntic ofereix una acceleració superpolinomial, cosa que es creu que és poc probable.
Alguns algorismes quàntics, com l'algoritme de Grover i l'amplificació d'amplitud, donen acceleracions polinomials sobre els algorismes clàssics corresponents. Tot i que aquests algorismes donen una acceleració quadràtica comparablement modesta, són àmpliament aplicables i, per tant, proporcionen acceleracions per a una àmplia gamma de problemes. Molts exemples d'acceleració quàntica demostrable per a problemes de consulta estan relacionats amb l'algoritme de Grover, inclòs l'algoritme de Brassard, Høyer i Tapp per trobar col·lisions en funcions de dos a un, que utilitza l'algoritme de Grover i l'algoritme de Farhi, Goldstone i Gutmann per avaluar NAND arbres, que és una variant del problema de cerca.
Aplicacions criptogràfiques
Una aplicació notable de la computació quàntica és per als atacs a sistemes criptogràfics que s'utilitzen actualment. La factorització de nombres enters, que sustenta la seguretat dels sistemes criptogràfics de clau pública, es creu que és computacionalment inviable amb un ordinador normal per a nombres enters grans si són el producte de pocs nombres primers (per exemple, productes de dos nombres primers de 300 dígits). En comparació, un ordinador quàntic podria resoldre aquest problema de manera eficient utilitzant l'algoritme de Shor per trobar els seus factors. Aquesta capacitat permetria a un ordinador quàntic trencar molts dels sistemes criptogràfics que s'utilitzen actualment, en el sentit que hi hauria un algorisme de temps polinomial (en el nombre de dígits de l'enter) per resoldre el problema. En particular, la majoria dels xifratges de clau pública populars es basen en la dificultat de factoritzar nombres enters o el problema del logaritme discret, tots dos es poden resoldre amb l'algorisme de Shor. En particular, es podrien trencar els algorismes RSA, Diffie–Hellman i de corba el·líptica Diffie–Hellman. S'utilitzen per protegir pàgines web segures, correu electrònic encriptat i molts altres tipus de dades. Trencar-los tindria ramificacions importants per a la privadesa i la seguretat electròniques.
La identificació de sistemes criptogràfics que poden ser segurs contra els algorismes quàntics és un tema investigat activament en el camp de la criptografia postquàntica. Alguns algorismes de clau pública es basen en problemes diferents de la factorització de nombres enters i problemes de logaritmes discrets als quals s'aplica l'algorisme de Shor, com el criptosistema McEliece basat en un problema en la teoria de la codificació. Tampoc se sap que els ordinadors quàntics trenquin els criptosistemes basats en gelosia, i trobar un algorisme de temps polinomial per resoldre el problema del subgrup ocult del diedre, que trencaria molts criptosistemes basats en gelosia, és un problema obert ben estudiat. S'ha demostrat que l'aplicació de l'algoritme de Grover per trencar un algorisme simètric (clau secreta) per força bruta requereix un temps aproximadament igual a 2n/2 invocacions de l'algoritme criptogràfic subjacent, en comparació amb aproximadament 2n en el cas clàssic, el que significa que les longituds de clau simètriques són efectivament reduït a la meitat: AES-256 tindria la mateixa seguretat contra un atac amb l'algoritme de Grover que AES-128 contra la cerca clàssica de força bruta (vegeu Mida de la clau).
La criptografia quàntica podria complir algunes de les funcions de la criptografia de clau pública. Per tant, els sistemes criptogràfics basats en quàntics podrien ser més segurs que els sistemes tradicionals contra la pirateria quàntica.
Problemes de cerca
L'exemple més conegut d'un problema que admet una acceleració quàntica polinomial és la cerca no estructurada, trobant un element marcat d'una llista de n elements en una base de dades. Això es pot resoldre mitjançant l'algorisme de Grover utilitzant consultes O(sqrt(n)) a la base de dades, quadràticament menys que les consultes Omega(n) necessàries per als algorismes clàssics. En aquest cas, l'avantatge no només és demostrable sinó també òptim: s'ha demostrat que l'algoritme de Grover dóna la màxima probabilitat possible de trobar l'element desitjat per a qualsevol nombre de cerques d'oracles.
Els problemes que es poden solucionar amb l'algorisme de Grover tenen les propietats següents:
- No hi ha cap estructura de cerca a la col·lecció de possibles respostes,
- El nombre de respostes possibles a comprovar és el mateix que el nombre d'entrades a l'algorisme, i
- Hi ha una funció booleana que avalua cada entrada i determina si és la resposta correcta
Per a problemes amb totes aquestes propietats, el temps d'execució de l'algorisme de Grover en un ordinador quàntic s'escala com l'arrel quadrada del nombre d'entrades (o elements de la base de dades), a diferència de l'escala lineal dels algorismes clàssics. Una classe general de problemes als quals es pot aplicar l'algorisme de Grover és el problema de satisfacció booleà, on la base de dades a través de la qual itera l'algorisme és la de totes les respostes possibles. Un exemple i (possible) aplicació d'això és un cracker de contrasenyes que intenta endevinar una contrasenya. Els xifratges simètrics com el Triple DES i l'AES són especialment vulnerables a aquest tipus d'atac.
Simulació de sistemes quàntics
Com que la química i la nanotecnologia es basen en la comprensió dels sistemes quàntics, i aquests sistemes són impossibles de simular d'una manera eficient clàssicament, molts creuen que la simulació quàntica serà una de les aplicacions més importants de la computació quàntica. La simulació quàntica també es podria utilitzar per simular el comportament d'àtoms i partícules en condicions inusuals, com ara les reaccions dins d'un col·lisionador. Les simulacions quàntiques es podrien utilitzar per predir camins futurs de partícules i protons en superposició en l'experiment de doble escletxa. [Cita necessària] Al voltant del 2% de la producció anual d'energia global s'utilitza per a la fixació de nitrogen per produir amoníac per al procés Haber en l'agricultura. indústria de fertilitzants, mentre que els organismes naturals també produeixen amoníac. Es podrien utilitzar simulacions quàntiques per entendre aquest procés augmentant la producció.
Recuit quàntic i optimització adiabàtica
El recuit quàntic o càlcul quàntic adiabàtic es basa en el teorema adiabàtic per realitzar càlculs. Un sistema es col·loca en l'estat fonamental d'un hamiltonià simple, que s'evoluciona lentament cap a un hamiltonià més complicat l'estat fonamental del qual representa la solució del problema en qüestió. El teorema adiabàtic estableix que si l'evolució és prou lenta el sistema es mantindrà en el seu estat fonamental en tot moment durant el procés.
L'aprenentatge automàtic
Com que els ordinadors quàntics poden produir sortides que els ordinadors clàssics no poden produir de manera eficient, i com que la computació quàntica és fonamentalment algebraica lineal, alguns expressen l'esperança de desenvolupar algorismes quàntics que puguin accelerar les tasques d'aprenentatge automàtic. Per exemple, es creu que l'algoritme quàntic per a sistemes d'equacions lineals, o "Algoritme HHL", que porta el nom dels seus descobridors Harrow, Hassidim i Lloyd, proporciona una acceleració respecte a les seves contraparts clàssiques. Alguns grups de recerca han explorat recentment l'ús de maquinari de recuit quàntic per entrenar màquines Boltzmann i xarxes neuronals profundes.
Biologia computacional
En el camp de la biologia computacional, la computació quàntica ha jugat un paper important en la resolució de molts problemes biològics. Un dels exemples coneguts seria la genòmica computacional i com la informàtica ha reduït dràsticament el temps per seqüenciar un genoma humà. Tenint en compte com la biologia computacional utilitza el modelatge i l'emmagatzematge de dades genèriques, també s'espera que sorgeixin les seves aplicacions a la biologia computacional.
Disseny de fàrmacs assistit per ordinador i química generativa
Els models de química generativa profunda sorgeixen com a eines poderoses per accelerar el descobriment de fàrmacs. Tanmateix, la immensa mida i la complexitat de l'espai estructural de totes les possibles molècules semblants a fàrmacs plantegen obstacles importants, que podrien ser superats en el futur mitjançant ordinadors quàntics. Els ordinadors quàntics són naturalment bons per resoldre problemes complexos de molts cossos quàntics i, per tant, poden ser fonamentals en aplicacions que impliquen la química quàntica. Per tant, es pot esperar que els models generatius millorats quàntics, inclosos els GAN quàntics, es puguin desenvolupar finalment en algorismes de química generativa finals. Les arquitectures híbrides que combinen ordinadors quàntics amb xarxes clàssiques profundes, com ara els autoencoders de variació quàntica, ja es poden entrenar amb recuits disponibles comercialment i utilitzar-se per generar noves estructures moleculars semblants a fàrmacs.
Desenvolupament d'ordinadors quàntics físics
Challenges
Hi ha una sèrie de reptes tècnics en la construcció d'un ordinador quàntic a gran escala. El físic David DiVincenzo ha enumerat aquests requisits per a un ordinador quàntic pràctic:
- Físicament escalable per augmentar el nombre de qubits,
- Qubits que es poden inicialitzar a valors arbitraris,
- Portes quàntiques que són més ràpides que el temps de decoherència,
- Conjunt de porta universal,
- Qubits que es poden llegir fàcilment.
També és molt difícil obtenir peces per a ordinadors quàntics. Molts ordinadors quàntics, com els construïts per Google i IBM, necessiten heli-3, un subproducte de la investigació nuclear, i cables superconductors especials fabricats només per l'empresa japonesa Coax Co.
El control de sistemes multi-qubit requereix la generació i coordinació d'un gran nombre de senyals elèctrics amb una resolució de temps ajustada i determinista. Això ha donat lloc al desenvolupament de controladors quàntics que permeten la interfície amb els qubits. Escalar aquests sistemes per suportar un nombre creixent de qubits és un repte addicional.
Descoherència quàntica
Un dels majors reptes que implica la construcció d'ordinadors quàntics és controlar o eliminar la decoherència quàntica. Normalment, això significa aïllar el sistema del seu entorn, ja que les interaccions amb el món extern fan que el sistema es decoheri. Tanmateix, també existeixen altres fonts de decoherència. Alguns exemples inclouen les portes quàntiques i les vibracions de la gelosia i el gir termonuclear de fons del sistema físic utilitzat per implementar els qubits. La decoherència és irreversible, ja que efectivament no és unitària, i sol ser una cosa que s'hauria de controlar molt, si no evitar-la. Els temps de decoherència per als sistemes candidats en particular, el temps de relaxació transversal T2 (per a la tecnologia RMN i MRI, també anomenat temps de desfasament), solen oscil·lar entre nanosegons i segons a baixa temperatura. Actualment, alguns ordinadors quàntics requereixen que els seus qubits es refredin a 20 milikelvins (normalment utilitzant un refrigerador de dilució) per evitar una decoherència significativa. Un estudi del 2020 argumenta que les radiacions ionitzants com els raigs còsmics poden, tanmateix, provocar que determinats sistemes es decoherin en mil·lisegons.
Com a resultat, les tasques que requereixen temps poden fer que alguns algorismes quàntics siguin inoperables, ja que mantenir l'estat dels qubits durant una durada prou llarga acabarà corrompent les superposicions.
Aquests problemes són més difícils per als enfocaments òptics, ja que les escales de temps són ordres de magnitud més curtes i un enfocament sovint citat per superar-los és la conformació del pols òptic. Les taxes d'error solen ser proporcionals a la relació entre el temps de funcionament i el temps de decoherència, per tant, qualsevol operació s'ha de completar molt més ràpidament que el temps de decoherència.
Tal com es descriu al teorema del llindar quàntic, si la taxa d'error és prou petita, es creu que és possible utilitzar la correcció d'errors quàntics per suprimir els errors i la decoherència. Això permet que el temps total de càlcul sigui més llarg que el temps de decoherència si l'esquema de correcció d'errors pot corregir errors més ràpidament del que la decoherència els introdueix. Una xifra citada sovint per a la taxa d'error requerida a cada porta per al càlcul tolerant a errors és 10−3, suposant que el soroll s'està despolaritzant.
El compliment d'aquesta condició d'escalabilitat és possible per a una àmplia gamma de sistemes. Tanmateix, l'ús de la correcció d'errors comporta el cost d'un nombre molt augmentat de qubits necessaris. El nombre necessari per factoritzar nombres enters utilitzant l'algorisme de Shor encara és polinomial, i es creu que està entre L i L2, on L és el nombre de dígits del nombre que cal factoritzar; els algorismes de correcció d'errors inflarien aquesta xifra en un factor addicional de L. Per a un nombre de 1000 bits, això implica la necessitat d'uns 104 bits sense correcció d'errors. Amb la correcció d'errors, la xifra augmentaria a uns 107 bits. El temps de càlcul és d'uns L2 o uns 107 passos i a 1 MHz, uns 10 segons.
Un enfocament molt diferent del problema d'estabilitat-decoherència és crear un ordinador quàntic topològic amb anyons, quasi-partícules utilitzades com a fils i basant-se en la teoria de trenes per formar portes lògiques estables.
Supremacia quàntica
La supremacia quàntica és un terme encunyat per John Preskill que fa referència a la gesta d'enginyeria de demostrar que un dispositiu quàntic programable pot resoldre un problema més enllà de les capacitats dels ordinadors clàssics d'última generació. El problema no ha de ser útil, de manera que alguns veuen la prova de supremacia quàntica només com una referència futura potencial.
L'octubre de 2019, Google AI Quantum, amb l'ajuda de la NASA, es va convertir en el primer a afirmar haver aconseguit la supremacia quàntica realitzant càlculs a l'ordinador quàntic Sycamore més de 3,000,000 de vegades més ràpid del que es podien fer a Summit, generalment considerat el més ràpid del món. ordinador. Aquesta afirmació s'ha qüestionat posteriorment: IBM ha afirmat que Summit pot realitzar mostres molt més ràpid del que s'afirma, i des de llavors els investigadors han desenvolupat millors algorismes per al problema de mostreig utilitzat per reclamar la supremacia quàntica, donant reduccions substancials o tancant la bretxa entre Sycamore i Sycamore. superordinadors clàssics.
El desembre de 2020, un grup de l'USTC va implementar un tipus de mostreig de bosons en 76 fotons amb un ordinador quàntic fotònic Jiuzhang per demostrar la supremacia quàntica. Els autors afirmen que un superordinador clàssic contemporani requeriria un temps computacional de 600 milions d'anys per generar el nombre de mostres que el seu processador quàntic pot generar en 20 segons. El 16 de novembre de 2021, a la cimera de la informàtica quàntica, IBM va presentar un microprocessador de 127 qubits anomenat IBM Eagle.
Implementacions físiques
Per implementar físicament un ordinador quàntic, s'estan buscant molts candidats diferents, entre ells (distinguts pel sistema físic utilitzat per realitzar els qubits):
- Informàtica quàntica superconductora (qubit implementat per l'estat de petits circuits superconductors, unions Josephson)
- Ordinador quàntic d'ions atrapats (qubit implementat per l'estat intern dels ions atrapats)
- Àtoms neutres a les xarxes òptiques (qubit implementat per estats interns d'àtoms neutres atrapats en una xarxa òptica)
- Ordinador de punts quàntics, basat en espín (per exemple, l'ordinador quàntic Loss-DiVincenzo) (qubit donat pels estats de spin dels electrons atrapats)
- Ordinador de punt quàntic, basat en l'espai (qubit donat per la posició de l'electró en el punt quàntic doble)
- Informàtica quàntica utilitzant pous quàntics dissenyats, que en principi podrien permetre la construcció d'ordinadors quàntics que funcionin a temperatura ambient
- Cable quàntic acoblat (qubit implementat per un parell de cables quàntics acoblats per un contacte de punt quàntic)
- Ordinador quàntic de ressonància magnètica nuclear (NMRQC) implementat amb la ressonància magnètica nuclear de molècules en solució, on els qubits són proporcionats per spins nuclears dins de la molècula dissolta i sondejats amb ones de ràdio
- Ordinadors quàntics Kane de RMN d'estat sòlid (qubit realitzat per l'estat de spin nuclear dels donants de fòsfor en silici)
- Ordinadors quàntics d'electrons sobre heli (qubit és l'espín d'electrons)
- Electrodinàmica quàntica de cavitats (CQED) (qubit proporcionat per l'estat intern dels àtoms atrapats acoblats a cavitats d'alta finura)
- Imant molecular (qubit donat pels estats de spin)
- Ordinador quàntic ESR basat en fullerene (qubit basat en el gir electrònic d'àtoms o molècules encaixades en fullerenes)
- Ordinador quàntic òptic no lineal (qubits realitzats mitjançant el processament d'estats de diferents modes de llum a través d'elements lineals i no lineals)
- Ordinador quàntic òptic lineal (qubits realitzats mitjançant el processament d'estats de diferents modes de llum a través d'elements lineals, com ara miralls, divisors de feix i desplaçadors de fase)
- Ordinador quàntic basat en diamants (qubit realitzat mitjançant el gir electrònic o nuclear dels centres de vacant de nitrogen al diamant)
- Ordinador quàntic basat en condensats de Bose-Einstein
- Ordinador quàntic basat en transistors: ordinadors quàntics de corda amb arrastre de forats positius mitjançant una trampa electrostàtica
- Ordinadors quàntics basats en cristalls inorgànics dopats amb ions de metalls de terres rares (qubit realitzat per l'estat electrònic intern dels dopants en fibres òptiques)
- Ordinadors quàntics basats en nanosferes de carboni semblants a metàl·liques
- El gran nombre de candidats demostra que la informàtica quàntica, malgrat el ràpid progrés, encara està en la seva infància.
Hi ha una sèrie de models de computació quàntica, distingits pels elements bàsics en què es descompon el càlcul. Per a les implementacions pràctiques, els quatre models rellevants de càlcul són:
- Matriu de portes quàntiques (càlcul descompost en una seqüència de portes quàntiques de pocs qubits)
- Ordinador quàntic unidireccional (càlcul descompost en una seqüència de mesures d'un qubit aplicades a un estat inicial molt entrellaçat o estat de clúster)
- Ordinador quàntic adiabàtic, basat en el recuit quàntic (càlcul descompost en una transformació lenta i contínua d'un hamiltonià inicial en un hamiltonià final, els estats fonamentals del qual contenen la solució)
- Ordinador quàntic topològic (computació descomposta en el trenat d'anyons en una gelosia 2D)
La màquina quàntica de Turing és teòricament important, però la implementació física d'aquest model no és factible. S'ha demostrat que els quatre models de càlcul són equivalents; cadascun pot simular l'altre sense més que una sobrecàrrega polinomial.
Per familiaritzar-vos en detall amb el pla d'estudis de certificació podeu ampliar i analitzar la taula següent.
El currículum de certificació dels fonaments de la informació quàntica EITC/QI/QIF fa referència a materials didàctics d'accés obert en forma de vídeo. El procés d'aprenentatge es divideix en una estructura pas a pas (programes -> lliçons -> temes) que cobreix les parts rellevants del currículum. També s'ofereix assessorament il·limitat amb experts del domini.
Per obtenir més informació sobre el procediment de certificació, consulteu Com funciona?.
Notes principals de la conferència
Notes de la conferència U. Vazirani:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Notes de conferència de suport
L. Jacak et al. apunts de classe (amb materials suplementaris):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Llibre de text de suport principal
Llibre de text de càlcul quàntic i informació quàntica (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Notes addicionals de conferència
J. Notes de la conferència de preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Notes de la conferència infantil:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Notes de la conferència de S. Aaronson:
https://scottaaronson.blog/?p=3943
Notes de la conferència de R. de Wolf:
https://arxiv.org/abs/1907.09415
Altres llibres de text recomanats
Càlcul clàssic i quàntic (Kitaev, Shen, Vyalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Informàtica quàntica des de Demòcrit (Aaronson)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
La teoria de la informació quàntica (Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Teoria de la informació quàntica (Wilde)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Baixeu els materials preparatoris d'autoaprenentatge fora de línia complets per al programa EITC/QI/QIF Quantum Information Fundamentals en un fitxer PDF
Materials preparatoris EITC/QI/QIF - versió estàndard
Materials preparatoris EITC/QI/QIF: versió ampliada amb preguntes de revisió