Computación cuántica. Máquinas cuánticas de muestreo bosónico (QBSM), una nueva tendencia.

1. A finales de 2012 principios de 2013 ha emergido una nueva tendencia en computación cuántica: la computación mediante muestro bosónico (boson sampling en inglés).

Es una técnica de computación cuántica no universal (es decir del tipo simulación), que se ha demostrado eficiente para solucionar determinados problemas que se suponen un computador clásico no podría resolver de manera eficiente (método de momento probado experimentalmente para muy pequeños tamaños), que aparentemente presenta menos problemas para escalar que otras técnicas y que incluso incluiría una vía para la universalidad (sobre la que haremos  una entrada en breve ya que para nosotros tiene un interés independiente).

El nombre completo del  nuevo tipo de simulador o máquina de cómputo es Quantum Boson Sampling Machine (QBSM).

GaltonBoard_1000

Por lo visto todo nace de un paper teórico (aquí puedes leer una versión más corta) del ya conocido en este blog ingeniero cuántico computacional y profesor del MIT, Aaronson, conjuntamente con un colega, también del MIT  de nombre Arkhipov.

Teóricamente (teoría de complejidad computacional) llegan a un resultado interesante (pero muy matizado, muy condicional, sujeto a conjeturas):  si un computador clásico fuese capaz de simular de manera eficiente a uno cuántico, entonces la jerarquía polinómica (PH) colapsaría al tercer nivel.

Recordemos que:

–si P=NP entonces PH colapsa a al nivel 0,

–si NP=Co-NP entonces el colapso es al nivel 1,

–el teorema Karp-Lipton habla de un colapso al 2º nivel;

y aunque se piensa que la PH no colapsa, sino que tiene infinitos niveles, cuanto más alto sea el nivel de colapso menos sorprendente sería.

Hasta ahora ya se conocían algoritmos cuánticos más eficientes para algunos problemas, el más conocido el problema de encontrar los factores primos de un número entero dado. Pero una solución clásica eficiente para estos problemas no tenía serias consecuencias de complejidad computacional, cómo colapsos de jerarquías. El hecho de que exista un problema que  sí causaría estos colapsos aporta evidencia adicional de que el computador cuántico podría ser más eficiente que el clásico para determinados problemas. El problema implicado es el del permanente de una matriz, pero no tengo claro de momento si en el paper afirman que existe un algoritmo cuántico eficiente para este problema.

En un blog (el que aparece de vez en cuando asociado a mi nombre) parecen afirmar  explícitamente que según estos nuevos resultados, el problema del permanente estaría en BQP, pero me esto me choca. Aunque desde hace varios meses estoy viendo comentarios sobre esta tendencia, no los he seguido de momento ya que ahora dispongo de poco tiempo para dedicarle a estos temas; ahora voy a dedicarle algo de tiempo e intentaré aclarar que afirman exactamente.

Actualización:  ojo, si me he enterado bien el resultado no es para problemas de decisión, sino de muestreo.

Uno de los dos autores ha demostrado que los problemas de muestreo y búsqueda son de alguna manera equivalentes.

Pero la equivalencia de decisión y búsqueda depende:  However, what if A = L is not NP-complete? Well, in this case the search and decision problems might be of di erent complexities. For example, it could be that the decision problem is easy (ie. in P) yet the search problem is hard.

Y aquí nos estamos moviendo fuera de NP (This is because, unlike with (say) Factoring, neither BosonSampling nor any related problem seems to be in NP; relacionado y matizando esto un artículo de Arora). Pero, ¿y la otra dirección? ¿ Podría ser que el problema aproximado de muestreo sea fácil para un computador cuántico y el correspondiente problema de decisión sea difícil ? Concretamente:  que el problema de aproximación del Permanente que se contempla en este artículo esté incluido en SampBQP, pero que esto no implique necesariamente que esté incluida en la clase de decisión BQP. Resumiendo, si me he enterado bien, la situación es cómo sigue:

BosonSampling problem (calculo exacto o aproximado, con ruido, del Permanente de matrices según se define en el artículo) Decisión / Conteo (recordemos que decisión y conteo tampoco son equivalentes para todos los problemas: 2-sat por ejemplo) Muestreo
Computación Clásica Universal #P-completo Si SampP entonces Colapso de PH a nivel 3.
Simulación Cuántica (QBSM) o Computación Cuántica ¿? SampBQP

Los propios autores señalan cómo problemas abiertos (entre otros):

–In this work, we showed that unlikely complexity consequences would follow if classical computers could simulate quantum computers on all sampling or search problems: that is, that SampP = SampBQP or FBPP = FBQP. An obvious question that remains is, what about decision problems ? Can we derive some unlikely collapse of classical complexity classes from the assumption that P = BQP or PromiseP = PromiseBQP ?

— Is there any plausible candidate for a decision problem that is eficiently solvable by a boson computer, but not by a classical computer?

Reconozco que todo esto está confuso y ni yo mismo lo tengo claro 100% ahora mismo. Pero con esta actualización mi duda queda más o menos aclarada. Si quieres algo más claro, puedes ver esta otra entrada posterior.

Fin actualización. 

2. En cualquier caso, si te interesa profundizar puedes ver esta lista de noticias que es casi cómo una historia de la emergencia de esta nueva tendencia o esta entrada en el blog del citado profesor del MIT.  También un breve comentario en Science sobre esta nueva tendencia por parte de un especialista en computación cuántica.

El abstract del citado paper teórico es cómo sigue:

We give new evidence that quantum computers—moreover, rudimentary quantum computers built entirely out of linear-optical elements—cannot be eciently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of
photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. 

Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P = BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation.

Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy.

For this, we need two unproven conjectures: 

–the Permanent-of-Gaussians Conjecture, which says that it is #P-hard to approximate the permanent of a matrix A of independent N (0, 1) Gaussian entries, with high probability over A; 

–and the Permanent Anti-Concentration Conjecture, which says that |Per (A)| ≥ √n!/ poly (n) with high probability over A.

We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

 

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: