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

Abstract

Quantum phase estimation is a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices.The maximum rate at which these eigenvalues may be learned, --known as the Heisenberg limit--, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, {\em also} when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' $g(k)={\sum }_j{A}_j{e}^{i{\varphi }_{j}k}$ with unknown eigenphases ${\varphi }_j$ and overlaps $A_j$ at quantum cost $O(k)$, we show how to estimate the phases $\{{\varphi }_j\}$ with (root-mean-square) error $\delta$ for total quantum cost $T=O({\delta }^{-1})$. Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [Higgins et al (2009) and Kimmel et al (2015)] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [Somma (2019)] 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.

25 pages + 5 page appendix, 3 figures, accepted in Quantum

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Algorithms for quantum simulation at finite energies
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• Error mitigation via verified phase estimation
• Spectral density estimation with the Gaussian Integral Transform
• Bayesian Quantum Multiphase Estimation Algorithm
• Several natural BQP-Complete problems
• Efficient Bayesian phase estimation using mixed priors

Cited by in corpus (25)

• Early Fault-Tolerant Quantum Computing
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Towards quantum advantage via topological data analysis
• Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
• Statistical phase estimation and error mitigation on a superconducting quantum processor
• Noise-resilient phase estimation with randomized compiling
• Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
• The advantage of quantum control in many-body Hamiltonian learning
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
• Error estimation in current noisy quantum computers
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Quantum Phase Estimation by Compressed Sensing
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Quantum-enhanced mean value estimation via adaptive measurement
• Hardware-efficient quantum phase estimation via local control
• Calculating response functions of coupled oscillators using quantum phase estimation
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Channel-based framework for phase esimation of multiple eigenvalues
• Dissipative ground state preparation in ab initio electronic structure theory
• Preparing low-variance states using a distributed quantum algorithm
• Quantum memory assisted observable estimation
• Tensor-based phase difference estimation on time series analysis
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation
• Hermitian Matrix Definiteness from Quantum Phase Estimation