Quantum computers could solve a number of problems substantially faster than their conventional counterparts. However, all known quantum algorithms exhibiting speedups use one of a small number of techniques that are responsible for their success.
This project pursues novel quantum methods for problem solving, particularly for optimization and simulation of quantum systems. The methods for optimization will include linear transformations in signal analysis and filter design that generalize the Fourier transform, which is key in quantum computing. Special interest will be given to the fractional Fourier transform and wavelet transforms, and to their applications in quantum black-box algorithms that compute specific properties of a function. Efficient quantum circuits that implement these transformations will be developed and their impact in quantum-algorithmic design will be analyzed.
The methods for the simulation of quantum systems will use adiabatic state transformation, which is a key tool for accessing energy states in physics via slow evolution. Adiabatic quantum algorithms to compute finite-temperature properties will be designed, and their computational cost will be compared to that of conventional Monte Carlo methods. Complexity lower bounds will also be obtained. In addition, the impact of the devised quantum methods in other areas of quantum information, especially in quantum metrology and parameter estimation, will be explored.
Quantum computers can theoretically solve certain problems at speeds that would be otherwise impossible. Our project pursued the design of novel and fast quantum algorithmic tools with applications in optimization and for the simulation of physical systems. These problems are intractable with conventional computers even for relatively small problem sizes; fast and novel algorithms are highly desirable. We developed several new techniques that can be implemented on quantum computers for fast problem solving. The first class of techniques were based on the idea of adiabatic state transformations. Here the goal is to prepare the low-energy state of a quantum system by slowly, or adiabatically transforming a given initial state towards the desired one. Such a state encodes the solution to the problem we want to solve, which can be obtained after a simple measurement. The complexity of the method is given by the total evolution time to prepare the state. We showed that this time depends on spectral properties of the Hamiltonians, including its spectral gap, as well as the length of the path traversed by the state. By making explicit such dependencies, we were able to improve upon the complexity of all other known methods for adiabatic state transformations. We also constructed a technique called spectral gap amplification that can be used to improve the complexity and showed that, for several problem instances, spectral gap amplification provides provable quantum speedups with respect to conventional methods for the same problems. As an example, spectral gap amplification can be used to speedup conventional Monte-Carlo algorithms that are widely used in computer science, physics, and beyond. The second class of techniques considered a version of the so-called fractional Fourier transform (frFT), so that it can be implemented on a quantum computer. In the past, conventional implementations of the frFT were successfully implemented in a number of problems in signal analysis. Our quantum version of the frFT can be implemented on a quantum computer almost exponentially faster than the conventional one. This brings a number of quantum speedups for problems were the frFT is useful. As an example, we showed that the complexity of certain noise filtering tasks in signal analysis can be highly reduced if large quantum computers were available. Also, our quantum frFT provides very efficient means for simulating a variety of continuous-variable quantum physical systems, of infinte dimensions, on quantum computers. Our results open the door to a new world of applications where our transformations could have an impact. Our discoveries provided further results that, although not directly addressing the goals of the project, have a demonstrated impact in quantum information science, many-body physics, and beyond. As an example, we showed that continuous-time models of quantum computing are equivalent to more standard models, based on quantum circuits, even if the time-dependencies are arbitrary. Also, we provided a conventional exact real-space renormalization method to compute properties of low-energy states significantly faster than other well-known methods, which are based on exact diagonalization. Several graduate students at the University of New Mexico and one postdoc at the New Mexico Consortium professionally developed during the course of this project. Our results were published in several peer-reviewed journals, book chapters, and presented at international conferences and seminars. The public has open access to our publications.
