Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits

Abstract

Quantum phase estimation is a corner-stone in quantum algorithm design, al-lowing for the inference of eigenvalues of exponentially-large sparse matrices. The maximum rate at which these eigenvalues may be learned, -known as the Heisen-berg limit-, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estima-tion that do not require coherence between experiments have garnered interest in re-cent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, also when one is un-able to prepare eigenstates of the system. Given a quantum subroutine which pro-vides samples of a 'phase function' g(k) = sigma(j) A(j)e(i Phi)j(k) with unknown eigenphases phi(j )and overlaps A(j )at quantum cost O(k), we show how to estimate the phases {phi(j}) with (root-mean-square) error delta for total quantum cost T = O(delta(-1)). Our scheme com-bines the idea of Heisenberg-limited multi -order quantum phase estimation for a single eigenvalue phase [1, 2] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [3] or the matrix pencil method. For our algorithm which adaptively fixes the choice for k in g(k) we prove Heisenberg -limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.