Randomized Quantum Algorithm for Statistical Phase Estimation

Phase estimation is a quantum algorithm for measuring the eigenvalues of a Hamiltonian. We propose and rigorously analyze a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms $L$ in the Hamiltonian. Second, unlike previous $L$-independent approaches, such as those based on qDRIFT, all algorithmic errors in our method can be suppressed by collecting more data samples, without increasing the circuit depth.

Figure 1

(a) Hadamard test on $\rho$ and $U$: setting $G=\mathbb{1}$ (respectively $G=S^{†}≔|0⟩⟨0|-i|1⟩⟨1|$) and associating the measurement outcomes $(|0⟩,|1⟩)$ with $(+1,-1)$ produces an unbiased estimator for $\mathrm{Re}(\mathrm{tr}[\rho U])$ [respectively $\mathrm{Im}(\mathrm{tr}[\rho U])$]. (b) Schematic depiction of the randomly compiled circuits in our algorithm. For $\widehat{H}={\sum }_{\ell }{p}_{\ell }{P}_{\ell }$, the squares represent Pauli operators randomly drawn from $\{P_{\ell }{\}}_{\ell }$ according to $\{p_{\ell }{\}}_{\ell }$, while circles denote multiqubit Pauli rotations; see the proof of Lemma 2 for details.

Figure 2

Log-log plot of ${\mathcal{C}}_{\text{sample}}(\overrightarrow{r})/\ln ({\vartheta }^{-1})$ vs ${\mathcal{C}}_{\mathrm{gate}}(\overrightarrow{r})$, for $\lambda =1511$ (FeMoco [37, 38]), $\mathrm{\Delta }=0.0016$ (chemical accuracy), $\eta =1$, and $ϵ\in \{0.05,0.1,0.2,0.3\}$, for various choices of the optimized runtime vector $\overrightarrow{r}$. Dots indicate the values that minimize the total expected complexity $2{\mathcal{C}}_{\text{sample}}·{\mathcal{C}}_{\mathrm{gate}}$, while curves are obtained by fixing ${\mathcal{C}}_{\mathrm{gate}}$ and minimizing ${\mathcal{C}}_{\text{sample}}$. To calculate the number of samples needed to guarantee an overall failure probability $\le \xi$ for ground state energy estimation (Theorem 1), one would multiply the $y$ axis by $\ln ({\vartheta }^{-1})=\mathcal{O}(\log ({\xi }^{-1})+\log \log ({\delta }^{-1}))$ (see Ref. [6] for the explicit constants). As an example, $\xi =0.1$ would give a multiplier of approximately 6.