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.

Arjan Cornelissen (QuSoft, CWI)

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.