Departamento de Computación

La Computación Cuántica apareció hace cerca de 30 años motivada por la ideas de Richard Feyman, quien se preguntaba si era posible simular un sistema cuántico por medio de una máquina cuántica universal o computadora cuántica. Aunque todavía no existe una implementación física de una computadora cuántica, se han hecho grandes progresos teóricos en el diseño de algoritmos cuánticos, por ejemplo el algoritmo cuántico de Shor para factorizar números enteros en sus factores primos [76]. Un algoritmo cuántico recibe como entrada un estado inicial, sobre el cual se aplican sucesivamente matrices unitarias, obteniendo así un estado final, la salida del algoritmo se obtiene llevando a cabo una medición cuántica sobre el estado final. Este tipo de algoritmos cuánticos pertenecen al Modelo de Circuitos Cuánticos (MCC) [61]. Recientemente, se propuso la Computación Cuántica Adiabática (CCA) [37, 35] que se basa en el Teorema Adiabático [58, 42] para aproximar soluciones de la ecuación de Schrödinger. El diseño de un algoritmo en CCA involucra la construcción de un hamiltoniano que describe el comportamiento del sistema cuántico, este hamiltoniano se expresa como una interpolación lineal de un hamiltoniano inicial cuyo estado firme sea fácil de calcular, y un hamiltoniano final cuyo estado firme corresponde a la solución de un problema de optimización dado. El Teorema Adiabático establece que si el tiempo de evolución de un sistema cuántico, descrito por un hamiltoniano, es lo suficientemente grande, entonces el sistema se mantiene cerca de su estado firme. Así, dado un problema de optimización, un algoritmo en CCA emplea el Teorema Adiabático para aproximar el estado firme del hamiltoniano final, que corresponde a la solución del problema de optimización. Se considera a la complejidad en tiempo de un algoritmo en CCA como al mínimo tiempo tal que se satisfaga el Teorema Adiabático. La CCA se ha empleado para resolver problemas de optimización, en [35] los autores creen que el problema MAX-SAT puede ser resuelto en complejidad de tiempo polinomial por un algoritmo en CCA. En [2] se probó que el MCC es equivalente a la CCA. Desde el punto de vista computacional, es importante calcular el espectro del hamiltoniano a lo largo del tiempo de evolución de un algoritmo en CCA, esto ayudaría a conocer su complejidad en tiempo. En general, conocer la complejidad en tiempo de un algoritmo en CCA es un problema difícil [37]. Investigamos la simulación computacional de los algoritmos en CCA para el problema de optimización MAX-SAT, proponemos un análisis simbólico de la solución en CCA con el fin de entender la complejidad computacional de los algoritmos en CCA. Este enfoque se puede extender a otros problemas de optimización combinatorios. En la practica, la simulación computacional de un algoritmo en CCA requiere la construcción de una matriz de dimensión 2n  2n donde n es la dimensión del sistema cuántico, en general esta matriz corresponde a una matriz dispersa, y se construye usando el producto tensorial de matrices. Proponemos una construcción eficiente de los hamiltonianos en CCA para el problema MAX-SAT que evita el uso de productos tensoriales. El diseño de algoritmos en CCA tiene consecuencias en su complejidad en tiempo y también en su posible implementación física. En la Mecánica Cuántica es conveniente describir un hamiltoniano como una suma de hamiltonianos locales i.e., hamiltonianos que actúan sobre un subconjunto de estados en el sistema cuántico. Por otro lado, el modelo de optimización de funciones pseudo-booleanas ha sido usado para modelar problemas de optimización combinatorios por medio de funciones pseudobooleanas. Proponemos un esquema general para el diseño de algoritmos en CCA por medio de funciones pseudo-booleanas para problemas de optimización combinatorios. Probamos que para cada problema de optimización que se exprese en el modelo de optimización de funciones pseudo-booleanas, se puede diseñar un algoritmo en CCA con hamiltonianos locales. En Complejidad Descriptiva la clase de problemas NP se puede describir como expresiones en la Lógica de Segundo Orden (LSO) [47]. En [27] se demuestra que todas las instancias de problemas sobre gráficas que se expresan en la Lógica Monádica de Segundo Orden (LMSO) con ancho de árbol acotado, se pueden resolver en complejidad de tiempo polinomial. La solución algorítmica propuesta en [27] se basa en un esquema de programación dinámica sobre descomposiciones en árbol de gráficas [13, 18]. Demostramos que cada expresión en LMSO tiene asociada funciones pseudo-booleanas que se obtienen expandiendo la expresión en LMSO, y que se pueden reducir a formas cuadráticas. Esta equivalencia entre expresiones en LMSO y funciones cuadráticas pseudo-booleanas se puede considerar como un esquema general para diseñar algoritmos en CCA, ya que cada función cuadrática pseudo-booleana puede ser optimizada por un algoritmo en CCA. Mostramos también un esquema de composición de hamiltonianos locales que se basa en el enfoque de programación dinámica sobre descomposiciones en árbol de gráficas.

Abstract

Quantum Computing appeared about 30 years ago motivated by the ideas of Richard Feynman. He wondered whether it is possible to simulate a quantum system by means of a universal quantum machine or quantum computer. Although, there is no yet a practical implementation of a quantum computer, researches have done impressive theoretical results in the design of quantum algorithms, an important quantum algorithm is the Shor algorithm to factorize an integer number into its prime factors [76]. A quantum algorithm has as input an initial state, and then a series of unitary matrices are applied over the initial state in order to produce a final state, the output of the algorithm is obtained by performing a quantum measurement over the final state. This kind of quantum algorithms belong to the Quantum Circuit Model (QCM) [61]. Recently, it was proposed the Adiabatic Quantum Computation (AQC) [37, 35] that is based on the Adiabatic Theorem [58, 42] to approximate solutions of the Schrödinger equation. The design of an AQC algorithm involves the construction of a Hamiltonian that describes the behavior of the quantum system, this Hamiltonian is expressed as a linear interpolation of an initial Hamiltonian whose ground state is easy to compute, and a final Hamiltonian whose ground state corresponds to the solution of a given optimization problem. The Adiabatic Theorem asserts that if the time evolution of a quantum system described by a Hamiltonian is large enough, then the system remains close to its ground state. Thus, given an optimization problem, an AQC algorithm uses the Adiabatic Theorem to approximate the ground state of the final Hamiltonian that corresponds to the solution of the given optimization problem. The time complexity of an AQC algorithm is the minimum time that satisfies the Adiabatic Theorem. AQC has been used to solve optimization problems, in [35] the authors claim that the optimization problem MAX-SAT can be solved in polynomial time complexity by an AQC algorithm. In [2] it was proved that QCM is equivalent to AQC. From the computational point of view it is important to compute the spectrum of the Hamiltonian in an AQC algorithm along the integration time in order to estimate its time complexity. In general, it is a hard problem to know the time complexity of an AQC algorithm. We investigate the computational simulation of AQC algorithms for the MAXSAT optimization problem, we propose a symbolic analysis of the AQC solution in order to understand the involved computational complexity of the AQC algorithms. This approach can be extended to others combinatorial optimization problems. The computational simulation of an AQC algorithm requires the construction of a matrix of dimension 2n2n where n is the dimension of the quantum system, that in general corresponds to a sparse matrix, this matrix is constructed using matrix tensor products. We propose an efficient construction of the Hamiltonian for AQC algorithms that avoid the matrix tensor products. The design of AQC algorithms has important consequences in its time complexity and also for its possible physical implementation. In Quantum Mechanics it is convenient to describe a Hamiltonian as an addition of local Hamiltonians i.e., Hamiltonians that only act on a subset of states in the quantum system. On the other hand, the pseudo-Boolean optimization model has been used to model combinatorial optimization problems into pseudo-Boolean maps. We propose a general scheme to design AQC algorithms based on pseudo-Boolean maps for combinatorial optimization problems, and we show that for a given optimization problem expressed in the pseudo-Boolean optimization model, then it is possible to construct an AQC algorithm with local Hamiltonians. In [47] it was proved that NP-problems can be expressed in Second Order Logic (SOL). In [27] it was shown that all instances of graph problems expressed in Monadic Second Order Logic (MSOL) with bounded treewidth can be solved in polynomial time complexity. The algorithmic solution proposed in [27] is based on a Dynamic Programming approach over tree-decompositions of graphs [13, 18]. We show that every MSOL expression has associated pseudo-Boolean maps that can be obtained by expanding the given MSOL expression, and also can be reduced to quadratic forms. The equivalence between MSOL expressions and quadratic pseudo-Boolean maps can be considered as a general scheme to design AQC algorithms, since every quadratic pseudo-Boolean map can be optimized by an AQC algorithm. We also show a composition scheme for local Hamiltonians based on the dynamic programming approach over tree-decompositions of graphs.