Algorithmic strategies for seizing quantum computing

Abstract

Quantum computing is an emergent technology with prospects to solve problems nowadays intractable. For this purpose it is a requirement to build computers capable to store and control quantum systems without losing their quantum properties. However, these computers are hard to achieve, and in the near term there will only be Noisy Intermediate-Scale Quantum (NISQ) computers with limited performance. In order to seize quantum computing during the NISQ era, algorithms with low resource demands and capable to return approximate solutions are explored. This thesis presents two different algorithmic strategies aiming to contribute to the plethora of algorithms available for NISQ devices, namely re-uploading and strategy. Each strategy takes advantage of different features of quantum computing, namely the superposition and the density of the Hilbert space in re-uploading, and entanglement among different partitions of the system in unary, to overcome a variety of obstacles. In both cases, the strategies are general and can be applied in a range of scenarios. Some examples are also provided in this thesis. First, the re-uploading is designed as a meeting point between quantum computing and machine learning. Machine learning is a set of techniques to build computer programs capable to learn how to solve a problem through experience, without being explicitly programmed for it. Even though the re-uploading is not the first attempt to join quantum computers and machine learning, this approach has certain properties that make it different from other methods. In particular, the re-uploading approach consists in introducing data into a classical algorithms in different stages along the process. This is a main difference with respect to standard methods, where data is uploaded at the beginning of the procedure. In the re-uploading, data is accompanied by tunable classical parameters that are optimized by a classical method according to a cost function defining the problem. The joint action of data and tunable parameters grant the quantum algorithm a great flexibility to learn a given behavior from sampling target data. The more re- uploadings are used, the better results can be obtained. In this thesis, re-uploading is presented by means of a set of theoretical results supporting its capabilities, and simulations and experiments to benchmark its performance in a variety of problems. The second algorithmic strategy is unary. This strategy describes a problem making use of only a small part of the available computational space. Thus, the computational capabilites of the computer are not optimal. In exchange, the operations required to execute a certain task become simpler. As a consequence, the retrieved results are more resilient to noise and decoherence, and meaningful. Therefore, a trade-off between efficiency and resillience against noise arises. NISQ computers benefit from this circumstance, especially in the case of small problems, where even quantum advantage and advantage over standard algorithms can be achieved. In this thesis, unary is used to solve a typical problem in finance called option pricing, which is of interest for real world applications. Options are contracts to buy the right to buy/sell a given asset at certain time and price. The holder of the option will only exercise this right in case of profit. Option pricing concists in estimating this profit by handling stochastic evolution models. This thesis aims to contribute to the growing number of algorithms available for NISQ computers and pave the way towards new quantum technologies.

La computación cuántica es una tecnología emergente con potencial para resolver problemas hoy impracticables. Para ello son necesarios ordenadores capaces de mantener sistemas cuánticos y controlarlos con precisión. Sin embargo, construir estos ordenadores es complejo y a corto plazo solo habrá ordenadores pequeños afectados por el ruido y sujetos a ruido (NISQ). Para aprovechar los ordenadores NISQ se exploran algoritmos que requieran pocos recursos cuánticos mientras proporcionan soluciones aproximadas a los problemas que enfrentan. En esta tesis se estudian dos propuestas para algoritmos NISQ: re-uploading y unary. Cada estrategia busca tomar ventaja de diferentes características de la computación cuántica para superar diferentes obstáculos. Ambas estrategias son generales y aplicables en diversos escenarios. En primer lugar, re-uploading está diseñado como un puente entre la computación cuántica y el aprendizaje automático (Machine Learning). Aunque no es el primer intento de aplicar la cuántica al aprendizaje automático, re-uploading tiene ciertas características que lo distinguen de otros métodos. En concreto, re-uploading consiste en introducir datos en un algoritmo cuántico en diferentes puntos a lo largo del proceso. Junto a los datos se utilizan también parámetros optimizables clásicamente que permiten al circuito aprender cualquier comportamiento. Los resultados mejoran cuantas más veces se introducen los datos. El re-uploading cuenta con teoremas matemáticos que sustentan sus capacidades, y ha sido comprobado con éxito en diferentes situaciones tanto simuladas como experimentales. La segunda estrategia algorítmica es unary. Consiste en describir los problemas utilizando solo parte del espacio de computación disponible dentro del ordenador. Así, las capacidades computacionales del ordenador no son óptimas, pero a cambio las operaciones necesarias para una cierta tarea se simplifican. Los resultados obtenidos son resistentes al ruido, y mantienen su significado, y se produce una compensación entre eficiencia y resistencia a errores. Los ordenadores NISQ se ven beneficiados de esta situación para problemas pequeños. En esta tesis, unary se utiliza para resolver un problema tíıpico de finanzas, incluso obteniendo ventajas cuánticas en un problema aplicable al mundo real. Con esta tesis se espera contribuir al crecimiento de los algoritmos disponibles para ordenadores cuánticos NISQ y allanar el camino para las tecnologías venideras.