27 de Junio de 2018
Teoría de la computaciòn

Un problema que solo podría ser resuelto rápidamente por un ordenador cuántico

Un resultado matemático muestra que la computación cuántica es diferente incluso en principio: ni siquiera un ordenador clásico ideal podría resolver en un tiempo aceptable cierto problema resoluble por un ordenador cuántico.

Procesador de 128 cúbits de D-Wave Systems, de eficacia sujeta a discusión; pero, matemáticamente, se ha demostrado una determinada superioridad intrínseca de la computación cuántica, definida en términos abstractos, sobre la clásica [D-Wave Systems, Inc].

Dos matemáticos han descubierto un problema matemático que un ordenador clásico, por potente que fuese, no podría resolver rápidamente, pero que sí estaría al alcance de un ordenador cuántico, y con ello han mostrado que un ordenador cuántico no solo podría ser más eficiente, sino esencialmente superior. Como Ran Raz, del instituto Weizmann de Ciencia, en Rehovot, Israel, y Avishay Tal, de la Universidad Stanford, explican, que dos series de números aparentemente aleatorios tengan una relación oculta es algo que un computador cuántico podría determinar en un tiempo admisible, pero no uno clásico. Conforme a este resultado, la computación cuántica es algo fundamentalmente nuevo.

Desde principios de la década de 1990 se las han estado viendo los especialistas con esta cuestión. En su raíz están dos de las llamadas «clases de complejidad»: la PH y la BQP. La PH comprende, entre otras, las clases P, la de los problemas que un ordenador clásico puede resolver en un «tiempo polinómico», lo que se toma como equivalente a que el problema es resoluble rápidamente, y la clase NP, la de los problemas para los que se puede verificar que una respuesta dada es correcta en tiempo polinómico. La BQP es la clase de los problemas que se pueden resolver en tiempo polinómico con un computador cuántico. La pregunta era: ¿hay problemas que estén en BPQ, pero no en PH? Raz y Tal dicen que sí. Su nuevo artículo incluye la prueba de que el problema susodicho no es tratable rápidamente con un ordenador clásico, por potente o ideal que sea. Ya se había demostrado hace bastantes años que existe un algoritmo cuántico que sí puede hacerlo.

Determinar teóricamente el tiempo de cálculo necesario para resolver un problema es muy difícil. Estos dos matemáticos han podido abordarlo en este caso mediante un «truco» habitual: el de sustituir el problema original por otro, el de qué información adicional bastaría para resolver aquel, lo cual se plantea refiriéndose a un «oráculo» al que se piden «pistas» y preguntando cuántas hay que pedirle para llegar a la solución. El número de esas pistas es una forma de medir el tiempo de cálculo. Pues bien: el ordenador cuántico necesitaría una sola pista, mientras que el clásico no podría hacerlo ni con un número ilimitado. Un problema fundamental de la teoría de la computación es el de si las clases P y NP no serán en realidad la misma (hay problemas para los que se puede verificar rápidamente que una solución realmente lo es, pero para los que no se sabe si hay forma de hallar soluciones en tiempo polinómico). Pero conforme a este nuevo resultado, aunque ambas clases fuesen la misma habría problemas que un eventual ordenador cuántico podría resolver pero que serían inaccesibles para un ordenador clásico.

Lars Fischer / spektrum.de

Artículo traducido y adaptado por Investigación y Ciencia con permiso de Spektrum der Wissenschaft.

Referencia: «Oracle Separation of BQP and PH», de Ran Raz y Avishay Tal en Electronic Colloqium on Computational Complexity, Report núm. 107 (2018).

Más información en Quanta Magazine

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.