Even Shorter Quantum Circuit for Phase Estimation on Early Fault-Tolerant Quantum Computers with Applications to Ground-State Energy Estimation

We develop a phase-estimation method with a distinct feature: its maximal run time (which determines the circuit depth) is $\delta /ϵ$, where $ϵ$ is the target precision, and the preconstant $\delta$ can be arbitrarily close to $0$ as the initial state approaches the target eigenstate. The total cost of the algorithm satisfies the Heisenberg-limited scaling $\tilde{\mathcal{O}}({ϵ}^{-1})$. As a result, our algorithm may significantly reduce the circuit depth for performing phase-estimation tasks on early fault-tolerant quantum computers. The key technique is a simple subroutine called quantum complex exponential least squares (QCELS). Our algorithm can be readily applied to reduce the circuit depth for estimating the ground-state energy of a quantum Hamiltonian, when the overlap between the initial state and the ground state is large. If this initial overlap is small, we can combine our method with the Fourier-filtering method developed in [Lin and Tong, PRX Quantum 3, 010318, 2022], and the resulting algorithm provably reduces the circuit depth in the presence of a large relative overlap compared to $ϵ$. The relative-overlap condition is similar to a spectral-gap assumption but it is aware of the information in the initial state and is therefore applicable to certain Hamiltonians with small spectral gaps. We observe that the circuit depth can be reduced by around 2 orders of magnitude in numerical experiments under various settings.

Popular Summary

Phase estimation is one of the most important quantum primitives. This paper focuses on designing phase-estimation algorithms that are suitable for early fault-tolerant quantum computers. Compared with full fault-tolerant computers, early fault-tolerant quantum computers have a limited number of logical qubits and limited circuit depths. Thus, algorithms on early fault-tolerant quantum computers should have a small number of qubits and small circuit depths.

In our paper, we develop a phase-estimation method that requires only one ancilla qubit and a small maximal run time. In the meantime, the total cost of our algorithm still satisfies the Heisenberg-limited scaling and is similar to that of other phase-estimation methods. As a result, our algorithm can significantly reduce the circuit depth for performing phase-estimation tasks on early fault-tolerant quantum computers. The key technique is a simple subroutine called quantum complex exponential least squares. We first transfer the phase-estimation problem to a fitting problem and then approximate the phase by solving an optimization problem. As an application, we use the idea to estimate the ground-state energy of a quantum Hamiltonian and justify the efficiency of our methods theoretically and numerically.

Figure 1

The quantum circuit used for collecting the input data. $H$ is the Hadamard gate, $t_n=n\tau$. Choosing $W=I$ or $W=S^{†}$ ($S$ is the phase gate) allows us to estimate the real or the imaginary part of $⟨\psi |\exp (-i{t}_{n}H)|\psi ⟩$.

Figure 2

(a) Fitting the noisy input data with $p_0=0.8$ using a complex exponential function. The mismatch between the data and the best fit reflects that the input data are more complex than a single complex exponential function. Despite this mismatch even in the absence of any Monte Carlo sampling error, QCELS is able to accurately estimate the phase under proper conditions. (b) A comparison of the theoretical upper bound of $\delta =T_{max}ϵ$ for QCELS ($T_{max}$ is the maximal run time) with the lower bound of $\delta$ for QPE-type methods when $p_0\ge 0.71$. The Hadamard test is only applicable when $p_0=1$ and in this case $\delta$ can be chosen to be arbitrarily small.

Figure 3

The landscape of the objective function $f(\theta )$ in Eq. (13) and a number of possible choices of the initial guess ${\theta }_0$ with $T_{max}=80$ and the eight-site TFIM model (see details in Sec. 5a). Here, $p_0=0.8$ and the landscape for other values of $p_0$ is similar. The Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm is used to maximize the objective function $f(\theta )$ for different initial guesses ${\theta }_0$. The error threshold is set as $0.01$, meaning that the optimization problem is successfully solved if $|{\theta }^{\ast }-{\mathrm{argmax}}_{\theta }f(\theta )|<0.01$.

Figure 4

QPE versus QCELS in the TFIM model with eight sites. The initial overlap is large ($p_0=0.6,0.8$). (a) The depth ($T_{max}$). (b) The cost ($T_{\mathrm{total}}$). For QCELS, we choose $N=5$ and $N_s=100$. $J$ and ${\tau }_j$ are chosen according to Theorem 2. Both methods have the error scaling linearly in $1/T_{max}$. The constant factor $\delta =Tϵ$ of QCELS is much smaller than that of QPE.

Figure 5

QPE versus QCELS in the Hubbard model with four sites. The initial overlap is small ($p_0=0.1,0.4$). (a) The depth ($T_{max}$). (b) The cost ($T_{\mathrm{total}}$). For QCELS, we choose $N=5$ and $N_s=\lfloor 15p_0^{-2}\log (d)\rfloor$. $J,{\tau }_j$ are chosen according to Corollary 4. Compared with QPE, to achieve the same accuracy, QCELS requires a much smaller circuit depth.

Figure 6

QPE versus QCELS in the Hubbard model with eight sites. (a) The depth ($T_{max}$). (b) The cost ($T_{\mathrm{total}}$). For QCELS, we choose $N=5$ and $N_s=\lfloor 15p_0^{-2}\log (d)\rfloor$. $J$ and ${\tau }_j$ are chosen according to Corollary 4. Compared with QPE, to achieve the same accuracy, QCELS has a much smaller circuit depth.

Figure 7

Multilevel quantum complex exponential least squares

Figure 8

Multilevel QCELS based ground-state energy estimation with small initial overlap