No quantum speedup with Grover-Rudolph state preparation for quantum Monte Carlo integration

We prove that there is no quantum speedup when using quantum Monte Carlo integration to estimate the mean (and other moments) of analytically defined log-concave probability distributions prepared as quantum states using the Grover-Rudolph method.

Figure 1

Quantum circuits for the Grover-Rudolph method: (a) for the first iteration and (b) for subsequent iterations, where ${|0\rangle }^{\otimes l}|i\rangle \stackrel{U_{\theta }}{\to }|{\theta }_i\rangle |i\rangle$. Note that $l$ is the number of qubits needed to represent $\theta$ to appropriate accuracy and also that the controlled $R_y\left(\theta \right)$ gate shown is shorthand for a series of $R_y$ gates with fixed rotation angles, each conditionally controlled by the various qubits in the $\theta$ register, such that the overall action is a rotation by $\theta$.

Figure 2

Grover-Rudolph state preparation for trivariate distribution. GR(1) denotes the preparation of the marginal distribution of the first dimension of the multivariate distribution (as per normal univariate case of Grover-Rudolph); GR(2) denotes the use of Grover-Rudolph to prepare the conditional distribution of the second dimension given the first (with the third dimension marginalised out)—the conditioning in the integral achieved by the quantum control; and GR(3) denotes the use of Grover-Rudolph to prepare the conditional distribution of the third dimension given the first and second.