Quantum Rejection Sampling

One of the main challenges in quantum computing is to come up with new quantum algorithms, ideally for problems with business value, i.e., ultimately leading to commercialization. While there have been quite a few successes in quantum algorithms during the past two decades, arguably not much progress has been made by the research community toward a) fundamentally new techniques and b) really compelling business cases. In this talk, I will review some of my efforts to finding new applications for quantum computers, focusing on exponential speedups between classical and quantum computation.

Quantum rejection sampling is an approach to quantum state generation that can be thought of as a quantum analog of the classical rejection sampling method (von Neumann, 1951). We assume that a black box is given that produces a coherent superposition of (possibly unknown) quantum states with some amplitudes. The problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. We exhibit a quantum algorithm for this problem and analyze its cost using semidefinite programming. As an application, we derive a quantum algorithm for the hidden shift problem for an arbitrary Boolean function. A bound on the runtime of this algorithm can be obtained by “water-filling” the Fourier spectrum.

I will also give a brief synopsis of some of my other work in quantum computing, including the software development project TORQUE which provides tools for resource estimation. One of the main use cases of the TORQUE tool-suite is to to estimate the overheads and costs of quantum algorithm implementations on actual physical hardware.