Quantum Mean-Value Approximator for Hard Integer-Value Problems

The quantum mean value (QMV) problem is a classically difficult problem that is the central part of many quantum algorithms. We show that using an approximation instead of the exact expectation results in a quadratic improvement in the efficiency of QMV and thus the underlying quantum algorithm.

Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of algorithms to solve general integer-value problems, such as the shortest vector problem investigated in this work.