Quantum mean-value approximator for hard integer-value problems
David Joseph, Antonio Martinez, Cong Ling, Florian Mintert · Physical Review A · 2022
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.