Ordinador quàntic

IBM Q System One (2019), el primer ordinador quàntic comercial basat en circuits.

Un ordinador quàntic és un dispositiu de càlcul que fa ús dels fenòmens específics de la mecànica quàntica, tals com la superposició i l'entrellaçament, per executar operacions sobre dades. Els ordinadors quàntics aprofiten la capacitat dels sistemes quàntics d'estar en dos estats simultàniament. En comptes de fer servir bits que tenen el valor 0 o 1, fan servir qubits (bits quàntics) que tenen una superposició dels dos valors. Processant simultàniament aquestes dades, un ordinador quàntic podria resultar exponencialment més ràpid que un de clàssic. Els ordinadors quàntics de suficient capacitat seran capaços de resoldre càlculs de complexitat intractable per a un ordinador convencional.

Així com un ordinador clàssic equival a una màquina de Turing, un ordinador quàntic equival a una màquina de Turing no determinista, en oferir, per a una determinada operació elemental, tot el conjunt de transicions possibles simultàniament.

El 13 de febrer del 2007, l'empresa canadenca D-Wave Systems presentà la primera oferta comercial d'aquest tipus amb un ordinador de 16 qubits com a mostra, amb la intenció de construir-ne un de 1024 qubits a final del 2008. Així mateix n'oferirà pròximament el servei en línia. La realitat de l'ordinador de D-Wave ha estat posada en dubte i sembla que la companyia hauria admès que es tracta d'un ordinador clàssic que fa servir la mecànica quàntica puntualment. L'agost del 2016 la universitat de Maryland va construir el primer ordinador quàntic programable. El maig del 2017 l'empresa IBM va implementar un ordinador quàntic de 16 qubits. El març del 2018 l'empresa Google va anunciar un ordinador quàntic anomenat Bristlecone i format per una matriu 9x8 de 72 bits.

L'esfera de Bloch és una representació d'un qubit, el bloc de construcció fonamental dels ordinadors quàntics.

La computació quàntica és un paradigma de computació diferent del de la computació clàssica. Es basa en l'ús de qubits en lloc de bits, i dona lloc a noves portes lògiques que fan possibles nous algorismes. Una mateixa tasca pot tenir diferent complexitat en computació clàssica i en computació quàntica, el que ha donat lloc a una gran expectació, ja que alguns problemes intractables passen a ser tractables. Mentre un ordinador clàssic equival a una màquina de Turing, un ordinador quàntic equival a una màquina de turing indeterminista.

Història

Planck i Einstein, van proposar que la llum no era una ona contínua, sinó que estava dividida en petits paquets o quàntums (en anglès quanta). Aquestes dues idees, en aparença molt simples, van fer que arribés la catàstrofe ultraviolada.

Diversos científics van desenvolupar aquestes idees, per veure que serien capaços d'aconseguir. Llavors van sorgir dues conclusions: la superposició d'estat i l'entrellaçament.

La superposició d'estat va resultar ser un problema. Alexander Holevo, el 1973 va demostrar que la superposició no era cent per cent confiable. Aquesta idea deia que els ordinadors quàntics no funcionarien amb 0 i 1 (com els ordinadors digitals), sinó que funcionaria amb percentatges. Per exemple, tindríem un 80% d'1 i un 20% de 0. El problema  era que a la pràctica i amb els sistemes dels quals es disposava, no es podia veure si veritablement aquests 0 i 1 es comportarien amb percentatges, i només a això, quant mesures les quantitats d'1 i 0 que hi ha, en mesurar els valors, també els modifiques, per això, seria impossible mesurar els percentatges dels 0 i 1.

Donada aquesta suposició, científics com Charles Benioff o Richard Feynman van demostrar que un ordinador clàssic no podria simular un sistema quàntic.

Tot això va canviar quan es va posar en marxa el segon concepte, l'entrellaçament. Aquesta idea va permetre crear dos algorismes: El temple quàntic (1989) i l'algorisme de Shor (1994).

El primer algorisme va permetre trobar valors funcionals, aplicats a la intel·ligència artificial i l'aprenentatge de l'automàtic.

El segon algorisme, ens va servir per descompondre els números en els seus factors primers amb molta més velocitat que un ordinador normal. Per exemple, RSA, un dels algorismes de protecció i xifrats, factoritza els seus números d'una forma molt lenta, amb l'algorisme de Shor, la velocitat de protecció i xifrat es dispararia.

Gràcies a aquests dos algorismes, es va començar a parlar de computació quàntica, un tipus de computació que podia deixar obsolets als sistemes digitals.

Comunicació

La criptografia quàntica permet noves maneres de transmetre dades de manera segura; per exemple, la distribució de claus quàntiques utilitza estats quàntics entrellaçats per establir claus criptogràfiques segures. Quan un emissor i un receptor intercanvien estats quàntics, poden garantir que un adversari no intercepti el missatge, ja que qualsevol escolta no autoritzat alteraria el delicat sistema quàntic i introduiria un canvi detectable. Amb els protocols criptogràfics adequats, l'emissor i el receptor poden establir informació privada compartida resistent a l'escolta.

Els cables de fibra òptica moderns poden transmetre informació quàntica a distàncies relativament curtes. La investigació experimental en curs té com a objectiu desenvolupar un maquinari més fiable (com ara repetidors quàntics), amb l'esperança d'escalar aquesta tecnologia a xarxes quàntiques de llarga distància d'extrem a extrem. Teòricament, això podria permetre noves aplicacions tecnològiques, com ara la computació quàntica distribuïda i la detecció quàntica millorada.

Teoria

Calculabilitat

Qualsevol problema computacional solucionable amb un ordinador clàssic també es pot resoldre amb un ordinador quàntic. Intuïtivament, això es deu al fet que es creu que tots els fenòmens físics, inclòs el funcionament dels ordinadors clàssics, es poden descriure mitjançant la mecànica quàntica, que és la base del funcionament dels ordinadors quàntics.

Per contra, qualsevol problema solucionable amb un ordinador quàntic també ho és amb un ordinador clàssic. És possible simular tant ordinadors quàntics com clàssics manualment amb només una mica de paper i un bolígraf, si se'ls dona el temps suficient. Més formalment, qualsevol ordinador quàntic pot ser simulat per una màquina de Turing. En altres paraules, els ordinadors quàntics no proporcionen cap potència addicional sobre els ordinadors clàssics en termes de computabilitat. Això vol dir que els ordinadors quàntics no poden resoldre problemes indecidibles com el problema de l'aturada, i l'existència d'ordinadors quàntics no refuta la tesi Church-Turing.

Complexitat

La sospita de relació de BQP amb diverses classes de complexitat clàssiques

Tot i que els ordinadors quàntics no poden resoldre cap problema que els ordinadors clàssics ja no puguin resoldre, se sospita que poden resoldre certs problemes més ràpidament que els ordinadors clàssics. Per exemple, se sap que els ordinadors quàntics poden factoritzar de manera eficient nombres enters, mentre que no es creu que aquest sigui el cas dels ordinadors clàssics.

La classe de problemes que es poden resoldre de manera eficient amb un ordinador quàntic amb error acotat s'anomena BQP, per "error acotat, temps quàntic, polinomi". Més formalment, BQP és la classe de problemes que es poden resoldre amb una màquina quàntica de Turing en temps polinomial amb una probabilitat d'error de com a màxim 1/3. Com a classe de problemes probabilístics, BQP és la contrapartida quàntica de BPP ("error acotat, probabilista, temps polinomial"), la classe de problemes que es poden resoldre mitjançant màquines de Turing probabilistes en temps polinomial amb error acotat. Se sap que ${\mathsf {BPP\subseteq BQP}}$ i és àmpliament provable que ${\mathsf {BQP\subsetneq BPP}}$, que intuïtivament significaria que els ordinadors quàntics són més potents que els ordinadors clàssics en termes de complexitat temporal.

No es coneix la relació exacta de BQP amb P, NP i PSPACE. No obstant això, se sap que ${\mathsf {P\subseteq BQP\subseteq PSPACE}}$; és a dir, tots els problemes que es poden resoldre de manera eficient amb un ordinador clàssic determinista també es poden resoldre de manera eficient amb un ordinador quàntic, i tots els problemes que es poden resoldre de manera eficient amb un ordinador quàntic també es poden resoldre amb un ordinador clàssic determinista amb recursos espacials polinomials. A més, se sospita que BQP és un superconjunt estricte de P, el que significa que hi ha problemes que es poden resoldre de manera eficient amb ordinadors quàntics que no es poden resoldre de manera eficient amb ordinadors clàssics deterministes. Per exemple, se sap que la factorització de nombres enters i el problema del logaritme discret estan en BQP i se sospita que estan fora de P. Sobre la relació de BQP amb NP, se sap poc més enllà del fet que alguns problemes de NP que es creu que no estan en P. P també estan en BQP (la factorització de nombres enters i el problema del logaritme discret estan tots dos en NP, per exemple). Se sospita que ${\mathsf {NP\nsubseteq BQP}}$; és a dir, es creu que hi ha problemes comprovables de manera eficient que no es poden resoldre de manera eficient amb un ordinador quàntic. Com a conseqüència directa d'aquesta creença, també se sospita que la BQP està disjunta de la classe de problemes NP-complets (si un problema NP-complet estigués a BQP, llavors de la duresa NP es derivaria que tots els problemes de NP estan en BQP).

Vegeu també

• Criptografia quàntica
• Teleportació quàntica
• Fotònica

Bibliografia

• Aaronson, Scott. Quantum Computing Since Democritus. Cambridge University Press, 2013. DOI 10.1017/CBO9780511979309. ISBN 978-0-521-19956-8. OCLC 829706638. 
• Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press, 2019. DOI 10.17226/25196. ISBN 978-0-309-47970-7. OCLC 1091904777. 
• Mermin, N. David. Quantum Computer Science: An Introduction, 2007. DOI 10.1017/CBO9780511813870. ISBN 978-0-511-34258-5. OCLC 422727925. 
• Nielsen, Michael; Chuang, Isaac. Quantum Computation and Quantum Information. 10th anniversary, 2010. DOI 10.1017/CBO9780511976667. ISBN 978-0-511-99277-3. OCLC 700706156. 
• Shor, Peter W. (1994). "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" a Symposium on Foundations of Computer Science. : 124Plantilla:En dash134, Santa Fe, New Mexico: IEEE. DOI:10.1109/SFCS.1994.365700 

Enllaços externs

• «Centre for Quantum Computation» (en anglès). Qubit.org. Arxivat de l'original el 2005-02-13. [Consulta: 21 octubre 2012].
• «Institute for Quantum Computing» (en anglès).
• «Blog sobre computació quàntica» (en espanyol).