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.

Figure 1

Each violin plot shows the distribution of $\mu \left(\gamma \right)/\mu \left(0\right)$ over $\gamma$ obtained from 45 two-dimensional lattices, numerically simulated using TensorFlow Quantum [34]. With growing system size $k$, the distributions get increasingly narrow, and the centers of the distributions lie above the classical baseline (red dashed line). The tail of the distributions, however, extend substantially below this baseline, indicating clear improvement over classical sampling for rare values of $\gamma$.

Figure 2

Pearson correlation coefficient $r_A$ for $A=1,2,3,k/2$, and $k$ averaged over 45 two-dimensional lattices. Even approximations ${\mu }_A$ based on a few most-significant qubits, i.e., small values of $A$, result in an excellent approximation of the exact energy expectation value $\mu$ as indicated by a value of $r_A$ close to unity.

Figure 3

Distribution of the ratio between the approximated expectation and the exact expectation for a fixed $\gamma$. Low $A$ gives a wider spread of errors and a large systematic error, whereas higher $A$ gives sharper peaks centered closer to the ideal value of 1.0. All results are for $k=7$.

Figure 4

Histogram for the ratio $\mu \left({\gamma }_A\right)/\mu \left({\gamma }_{\text{opt}}\right)$ where ${\gamma }_A$ and ${\gamma }_{\text{opt}}$ are the values of $\gamma$ that minimze ${\mu }_A$ and $\mu$, respectively. Each distribution contains datapoints for 45 lattices with $k=5,6,7$. The bin width is 0.04 for $A=1$ and $1.5\times {10}^{-3}$ for $A=2$ and $A=3$. The black dashed vertical in the left-hand plot denotes $\mu \left(0\right)/\mu \left({\gamma }_{\text{opt}}\right)$, but this value is too large to be shown for $A=2,3$. The actual minimum of $\mu$ is approximated increasingly well by ${\gamma }_A$ with increasing value of $A$, and even coarse approximations ($A\ll k$) yield excellent results.