# Quantum Software

#### Quantum phase estimation and its applications

We review the circuit model of quantum computation with which quantum algorithms are formulated. At the core of many quantum algorithms, including the factoring algorithm and algorithms for physics and chemistry problems, lies the subroutine of quantum phase estimation. We discuss what problem quantum phase estimation solves and how it does this. We review some of the variants of phase estimation and show how phase estimation can be simplified in some cases. Such simplification can be viewed as a form of hybrid quantum-classical computation, leading to a saving of quantum resources.

#### Quantum gradient estimation

Estimating the gradient of a real-valued function is used as a building block in many classical algorithms. Frequently, the objective functions whose gradients are to be estimated are not differentiable in closed form analytically, and hence the estimate of the gradient is usually based on evaluations of the function around the point at which the gradient is to be evaluated. In the classical case, the number of function evaluations necessary to estimate a d-dimensional gradient is easily seen to be at least d+1. Gilyen et al. investigated whether this number of function evaluations can be reduced using a quantum algorithm. It turns out that under some smoothness condition, the number of function evaluations can be reduced to O(sqrt{d}), and I proved this method to be optimal even under a somewhat stronger smoothness condition. This algorithm could lead to algorithmic speed-ups, especially in applications where the domain of the function is high-dimensional, as often happens in machine learning.

#### Quantum computational speed-ups with small quantum computers

Theory shows that arbitrary-sized quantum computers may offer computational advantages for many problems. However, quantum computers we are likely to have in the foreseeable future will be restricted in many ways, including size. Motivated by this, we investigate whether a small quantum computer (limited to $$M$$ qubits) can genuinely speed up interesting algorithms, even when the problem size is much larger than the computer itself. We show that this is possible. We present a specific hybrid quantum-classical algorithm to solve 3SAT problems involving $$n\gg M$$ variables, that significantly speeds up its fully classical counterpart. Finally, we provide a more abstract characterization of the criteria which allow such speed-ups with smaller quantum computers, and discuss the broader applicability of our approach.