Quantum Mean-Value Approximator for Hard Integer-Value Problems


May 29, 2021


Pub Type:



American Physical Society


David Joseph, Antonio Martinez, Cong Ling, Florian Mintert


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.

Download Paper
Back to all publications