with any real runtime allowed. These algorithms are particularly suitable for early fault-tolerant quantum computers in the following senses: (1) a minimal number of ancilla qubits are used, (2) an imperfect initial state with a significant residual is allowed, (3) the prefactor in the maximum runtime can be arbitrarily small given that the residual is sufficiently small and a gap among the dominant eigenvalues is known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE algorithms can achieve the Heisenberg limit while maintaining (1) and (2).

DOI: 10.48550/arxiv.2303.08099

Related papers

Adaptive low-depth quantum algorithms for robust multiple-phase estimation

Haoya Li, Hongkang Ni, Lexing Ying B

This paper is an algorithmic study of quantum phase estimation with multiple eigenvalues. We present robust multiple-phase estimation (RMPE) algorithms with Heisenberg-limited scaling. The proposed algorithms improve significantly from the idea of single-phase estimation methods by combining carefully designed signal processing routines and an adaptive determination of runtime amplifying factors. They address both the integer-power model, where the unitary $U$ is given as a black box with only integer runtime accessible, and the real-power model, where $U$ is defined through a Hamiltonian $H$ by $U=exp(\ensuremath{-}2\ensuremath{\pi}\mathrm{i}H)$ with any real runtime allowed. These algorithms are particularly suitable for early fault-tolerant quantum computers in the following senses: (1) a minimal number of ancilla qubits are used, (2) an imperfect initial state with a significant residual is allowed, (3) the prefactor in the maximum runtime can be arbitrarily small given that the residual is sufficiently small and a gap among the dominant eigenvalues is known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE algorithms can achieve the Heisenberg limit while maintaining (1) and (2).This paper is an algorithmic study of quantum phase estimation with multiple eigenvalues. We present robust multiple-phase estimation (RMPE) algorithms with Heisenberg-limited scaling. The proposed algorithms improve significantly from the idea of single-phase estimation methods by combining carefully designed signal processing routines and an adaptive determination of runtime amplifying factors. They address both the integer-power model, where the unitary $U$ is given as a black box with only integer runtime accessible, and the real-power model, where $U$ is defined through a Hamiltonian $H$ by $U=exp(\ensuremath{-}2\ensuremath{\pi}\mathrm{i}H)$ with any real runtime allowed. These algorithms are particularly suitable for early fault-tolerant quantum computers in the following senses: (1) a minimal number of ancilla qubits are used, (2) an imperfect initial state with a significant residual is allowed, (3) the prefactor in the maximum runtime can be arbitrarily small given that the residual is sufficiently small and a gap among the dominant eigenvalues is known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE algorithms can achieve the Heisenberg limit while maintaining (1) and (2).

Physical Review ADec 11, 202319 citations

On low-depth algorithms for quantum phase estimation

Hongkang Ni, Haoya Li, Lexing Ying B

Quantum phase estimation is one of the critical building blocks of quantum computing. For early fault-tolerant quantum devices, it is desirable for a quantum phase estimation algorithm to (1) use a minimal number of ancilla qubits, (2) allow for inexact initial states with a significant mismatch, (3) achieve the Heisenberg limit for the total resource used, and (4) have a diminishing prefactor for the maximum circuit length when the overlap between the initial state and the target state approaches one. In this paper, we prove that an existing algorithm from quantum metrology can achieve the first three requirements. As a second contribution, we propose a modified version of the algorithm that also meets the fourth requirement, which makes it particularly attractive for early fault-tolerant quantum devices.Quantum phase estimation is one of the critical building blocks of quantum computing. For early fault-tolerant quantum devices, it is desirable for a quantum phase estimation algorithm to (1) use a minimal number of ancilla qubits, (2) allow for inexact initial states with a significant mismatch, (3) achieve the Heisenberg limit for the total resource used, and (4) have a diminishing prefactor for the maximum circuit length when the overlap between the initial state and the target state approaches one. In this paper, we prove that an existing algorithm from quantum metrology can achieve the first three requirements. As a second contribution, we propose a modified version of the algorithm that also meets the fourth requirement, which makes it particularly attractive for early fault-tolerant quantum devices.

arXiv:2302.02454QuantumNov 6, 202346 citations

Quantum Phase Estimation by Compressed Sensing

Changhao Yi, Cunlu Zhou, Jun Takahashi

As a signal recovery algorithm, compressed sensing is particularly effective when the data has low complexity and samples are scarce, which aligns natually with the task of quantum phase estimation (QPE) on early fault-tolerant quantum computers. In this work, we present a new Heisenberg-limited, robust QPE algorithm based on compressed sensing, which requires only sparse and discrete sampling of times. Specifically, given multiple copies of a suitable initial state and queries to a specific unitary matrix, our algorithm can recover the phase with a total runtime of O ( ϵ − 1 poly log ⁡ ( ϵ − 1 ) ) , where ϵ is the desired accuracy. Additionally, the maximum runtime satisfies T max ϵ ≪ π , making it comparable to state-of-the-art algorithms. Furthermore, our result resolves the basis mismatch problem in certain cases by introducing an additional parameter to the traditional compressed sensing framework.As a signal recovery algorithm, compressed sensing is particularly effective when the data has low complexity and samples are scarce, which aligns natually with the task of quantum phase estimation (QPE) on early fault-tolerant quantum computers. In this work, we present a new Heisenberg-limited, robust QPE algorithm based on compressed sensing, which requires only sparse and discrete sampling of times. Specifically, given multiple copies of a suitable initial state and queries to a specific unitary matrix, our algorithm can recover the phase with a total runtime of O ( ϵ − 1 poly log ⁡ ( ϵ − 1 ) ) , where ϵ is the desired accuracy. Additionally, the maximum runtime satisfies T max ϵ ≪ π , making it comparable to state-of-the-art algorithms. Furthermore, our result resolves the basis mismatch problem in certain cases by introducing an additional parameter to the traditional compressed sensing framework.

arXiv:2306.07008QuantumDec 27, 20246 citations

Adiabatic Quantum Phase Estimation

Alexander Schmidhuber, Seth Lloyd

Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $ε$ in Heisenberg-limited time $T=Θ(1/ε)$ . Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling $T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)$ in both the precision $ε$ and failure probability $δ$ . By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $ε$ in Heisenberg-limited time $T=Θ(1/ε)$. Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling $T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)$ in both the precision $ε$ and failure probability $δ$. By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.

quant-pharXiv:2605.22770May 22, 20260 citations

Heisenberg-limited quantum phase estimation of multiple eigenvalues with up to two control qubits

Alicja Dutkiewicz, Barbara M. Terhal, Thomas E. O’Brien

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 depth required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation 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 \phi_j k}$ with unknown eigenvalue phases $\phi_j$ and probabilities $A_j$ at quantum cost $O(k)$ , we show how to estimate the phases $\{\phi_j\}$ with accuracy (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 \cite{Higgins09Demonstrating,Kimmel15Robust} with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem \cite{Somma19Quantum} 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.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 depth required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation 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 \phi_j k}$ with unknown eigenvalue phases $\phi_j$ and probabilities $A_j$ at quantum cost $O(k)$, we show how to estimate the phases $\{\phi_j\}$ with accuracy (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 \cite{Higgins09Demonstrating,Kimmel15Robust} with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem \cite{Somma19Quantum} 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.

Jul 9, 20210 citations

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

Alicja Dutkiewicz, Barbara M. Terhal, Thomas E. O apos Brien

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, a l s o when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' g ( k ) = ∑ j A j e i ϕ j k with unknown eigenphases ϕ j and overlaps A j at quantum cost O ( k ) , we show how to estimate the phases { ϕ j } with (root-mean-square) error δ for total quantum cost T = O ( δ − 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.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, a l s o when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' g ( k ) = ∑ j A j e i ϕ j k with unknown eigenphases ϕ j and overlaps A j at quantum cost O ( k ) , we show how to estimate the phases { ϕ j } with (root-mean-square) error δ for total quantum cost T = O ( δ − 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.

arXiv:2107.04605QuantumOct 6, 202233 citations

U

is given as a black box with only integer runtime accessible, and the {\em real-power} model, where

U

is defined through a Hamiltonian

H

U = \exp(-2π\mathrm{i} H)

U

is given as a black box with only integer runtime accessible, and the real-power model, where

U

is defined through a Hamiltonian

H

by $U=exp(\ensuremath{-}2\ensuremath{\pi}\mathrm{i}H)$ with any real runtime allowed. These algorithms are particularly suitable for early fault-tolerant quantum computers in the following senses: (1) a minimal number of ancilla qubits are used, (2) an imperfect initial state with a significant residual is allowed, (3) the prefactor in the maximum runtime can be arbitrarily small given that the residual is sufficiently small and a gap among the dominant eigenvalues is known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE algorithms can achieve the Heisenberg limit while maintaining (1) and (2).

Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision

ε

in Heisenberg-limited time

T=Θ(1/ε)

. Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling

T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)

in both the precision

ε

and failure probability

δ

. By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.

g(k)=\sum_j A_j e^{i \phi_j k}

with unknown eigenvalue phases

\phi_j

and probabilities

A_j

at quantum cost

O(k)

, we show how to estimate the phases

\{\phi_j\}

with accuracy (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 \cite{Higgins09Demonstrating,Kimmel15Robust} with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem \cite{Somma19Quantum} or the matrix pencil method. For our algorithm which adaptively fixes the choice for

k

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.