Computación cuántica. QBSM, de la simulación restringida a la computación universal.

1. QIP (Quantum Information Processing) es una de las principales conferencias sobre información / computación cuántica. Este año ha sido en enero y en Beijing y aquí puedes ver la lista de papers presentados, la mayoría descargables  en PDF.

(Nota el margen: Viendo el header de la página web de QIP 2013 uno no puede si no confirmar lo que ya sospechaba: la estética, el Arte de algunas civilizaciones es atemporal, no pasa el tiempo para el. Me parece estar viendo los catálogos de productos industriales de los 90 dónde el Templo del Cielo era también cuántico, o sea ubicuo🙂. Creo que cuando estuve en Beijing lo visité pero sólo me quedan recuerdos brumosos. Tengo mejores recuerdos de otros palacios o templos).

2. En fin, de los publicados en QIP, quería hablar del siguiente paper que ya lleva varios meses publicado, pero que había escapado a mi radar que sólo lo ha detectado hace pocos días.

Viene a cuento además ya que está relacionado con los resultados comentados en la entrada anterior: de alguna manera presentan una manera de universalizar la máquina de muestro de bosones o QBSM.

Título.  Universal Computation by Multi-Particle Quantum Walk. 

We show that multi-particle quantum walk is capable of universal quantum computation. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. As in a previous single-particle construction, we use a discrete version of scattering theory to establish universality. However, we use a different encoding of quantum data and exploit interactions between particles to implement two-qubit gates.

In our scheme, an n-qubit circuit with g gates can be simulated by the dynamics of O(n) particles evolving for time poly(n,g) on a planar graph of maximum degree 4 with poly(n,g) vertices. Thus our graphs are exponentially smaller (as a function of n) than those used in the single-particle construction, offering the potential for efficient implementation by a system with a physical degree of freedom for each vertex of the graph. Our results apply to a broad class of multi-particle quantum walk Hamiltonians, including the Bose-Hubbard model and models with nearest-neighbor interactions for fermions and distinguishable particles. 

Leyendo el Abstract uno podría pensar que se trata de un modelo más de computación cuántica universal polinómicamente equivalente a otros modelos ya existentes (cómo el modelo de circuitos, topológico etc…), y en realidad así es.

Aunque no he leído el paper en detalle, este modelo me ha gustado:

–Primero, porque de alguna manera reducen el modelo de circuitos a otro en el que el “soporte” sobre el que se “mueven” las partículas son grafos de grado 4 (ya veremos que es problema abierto si el grado 3 es suficiente para la universalidad).

–Segundo, porque me recuerda (sólo de lejos, muy superficialmente) al modelo RH Systems del que hemos hablado aquí.

Whereas a standard quantum walk concerns a single walker moving (in superposition) on a graph, we consider the generalization to many interacting walkers. Since the state space of such a multi-particle quantum walk must record the locations of all the walkers, the dimension of the Hilbert space of the walk can be dramatically larger than the number of vertices of the graph. Thus it is possible in principle for a graph with relatively few vertices to describe a complex quantum process, and for the locality of the graph to correspond to locality of the physical system implementing the walk.

En el paper primero informan que ya existe un modelo universal de dispersión de una sola partícula:

In the single-particle universality construction reviewed in the previous section, the graph used to perform a computation is exponentially large as a function of the number of qubits n. This is necessary in order to encode the 2n computational basis states in the Hilbert space of the walk. In this section we describe our scheme for performing quantum computation using multiparticle scattering.

Luego desarrollan el modelo para múltiples partículas (sección 5) y dan detalles más concretos en la sección 6. Lo destacado es que ahora, no sé muy bien cómo, obtienen una transformación del modelo de circuitos a su modelo de caminos aleatorios eficiente (es decir polinómica) aunque no práctica, cómo veremos:

In this section we fill in the details of the scheme outlined above. We specify the initial state, the graph used to perform an n-qubit quantum computation, and the evolution time. These are all specified as a function of a single parameter L ∈ N. We show that by taking L = poly(n, g) we can achieve an arbitrarily small error in our simulation of a given g-gate quantum circuit. The resulting graph and evolution time are both polynomially large in n and g.

For simplicity, we discuss the case of indistinguishable particles and we concentrate on the nonplanar scheme using one mediator qubit, but similar results clearly apply to the planar scheme and for the case of distinguishable particles as discussed in Section 5.1 and Section 5.2.

También tiene sus defectos, ya que la reducción polínomica de los circuitos cuánticos a casos de este modelo no es muy práctica (hablamos a nivel teórico; no sé, y seguramente ellos tampoco, si desde el punto de vista ingenieril este modelo es viable):

Using this bound on L, the total number of vertices required in our construction is O(n^25 g^9) and the total evolution time is O(n^24 g^9). Although these bounds are sucient to establish universality with only polynomial overhead, we expect that they can be improved significantly.

Para más detalles debes de leer el paper completo. Los autores concluyen: 

We have shown how multi-particle quantum walk with indistinguishable or distinguishable particles can be used to perform ecient universal quantum computation.

We conclude by discussing some open problems.

–In our scheme we achieve universal computation using graphs with maximum degree 4. A natural question is whether multi-particle quantum walk on graphs with maximum degree 3 is suficient. 

–Another open problem is to improve our bounds on the time and space resources required for our scheme. Our bounds may not be practical, but we expect that tighter bounds should hold. For example, our analysis ensures that the shapes of the wave packets do not significantly change in the course of the computation, but it should be possible to obtain a useful output even with non-negligible dispersion.

Although the initial state for our scheme is simple, it could be even simpler. Ideally we would like to initialize each particle at a single vertex of the graph. This might be possible using momentum filters such as the one used in [11].

–Finally, another avenue for future research is to develop new quantum algorithms. We hope that some of the tools we have developed in this work can be used to design and analyze new algorithms based on multi-particle quantum walk.

4. Una aplicación: el problema del permanente.

Con respecto al último punto que señalan precisamente en la entrada anterior de este blog hemos desarrollado el tema. Puedes ver un comentario reciente sobre todo esto en este breve comentario de la revista Science titulado Beating Classical Computing without a Quantum Computer.

Encontrar un algoritmo cuántico para el permanente de una matriz binaria es una problema ya explorado. Aquí puedes ver un intento basado en otro modelo computacional cuántico:

Título. TOWARDS A QUANTUM ALGORITHM FOR THE PERMANENT

We resort to considerations based on topological quantum field theory to outline the development of a possible quantum algorithm for the evaluation of the permanent of a 0 − 1 matrix.

Such an algorithm might represent a breakthrough for quantum computation,  since computing the permanent is considered a “universal problem”, namely, one among the hardest problems that a quantum computer can efficiently handle. 

Y si te interesa la relación de las clases de complejidad de conteo (a la que pertenecería el problema del / de la permanente) con la computación cuántica puedes leer este paper ya antiguo, de Fenner. Finalmente si te interesa la complejidad computacional clásica del problema permanente puedes ver esta interesante entrada de Wikipedia.

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: