Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2507.23716

Sandwich test for Quantum Phase Estimation

Avatar Tulsi

Published Jul 31, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate $\langle ψ|U^{k}|ψ\rangle$ for a large integer $k$ for an efficiently preparable initial state $|ψ\rangle$ and an efficiently implementable unitary operator $U$. The Hadamard test is hard to implement because it requires controlled applications of $U^{k}$. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of $U$ only but its total run time $T_{\rm tot}$ scales as $\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})$ where $r_{\rm min}$ is the minimum value of $|\langle ψ|U^{k'}|ψ\rangle|$ among all integers $k' \leq k$. Typically $r_{\rm min}$ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state $|ψ\rangle$ to efficiently implement the SPROTIS operator $R_ψ^ϕ$ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between $U^{a}$ and $U^{b}$ for integers $\{a,b\} \leq k$ to estimate $\langle ψ|U^{k}|ψ\rangle$. The total run time $T_{\rm tot}$ is $\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})$. Here $s_{\rm min}$ is the minimum value of $|\langle ψ|U^{\hat{k}}|ψ\rangle$ among all integers $\hat{k}$ which are values of the nodes of a random binary sum tree whose root node value is $k$ and leaf nodes' values are $1$ or $0$. It can be reasonably expected that $s_{\rm min} \not\ll 1$ in typical cases because there is wide freedom in choosing the random binary sum tree.

DOI
10.48550/arxiv.2507.23716

Related papers

Efficient quantum phase estimation with adaptive entanglement-assisted Hadamard test

Hengzhun Chen, Benchi Zhao, Yingzhou Li

The entanglement-assisted Hadamard test (EHT) is a practical method for estimating a quantum phase by amplifying the phase signal. However, the feasible amplification is fundamentally limited by the accuracy of the reference phase, such that the method is inefficient in the high-precision regime. In this work, we propose an algorithm, called adaptive entanglement-assisted Hadamard test (AEHT), that iteratively refines the reference phase, enabling progressively stronger amplification as the iteration goes by. We further consider the imperfect eigenstate preparation scenario, where a systematic bias is unavoidable when estimating the quantum phase with the conventional EHT. Such a bias can be suppressed by the proposed AEHT. Moreover, taking physical implementation into consideration, we adopt device-restart count to measure the cost of quantum phase estimation, rather than shot count. The numerical experiments confirm the effectiveness of the proposed AEHT compared with conventional methods under this measure. By unlocking the full amplification power of large entangled states, this work offers an efficient method to estimate high-precision quantum phase on near-term quantum processors.

quant-pharXiv:2610.01772•Oct 2, 2026•0 citations

Parallel Hadamard Test

Soichiro Imamura, Synge Todo

The Hadamard test is a fundamental building block widely used in many quantum computing algorithms. It estimates the real or imaginary part of $\langle ψ\vert U \vert ψ\rangle$, where $\vert ψ\rangle$ is a quantum state and $U$ is a unitary operator. In many algorithms, however, many such quantities must be estimated, leading to a large number of distinct circuit types, long computational times, and high financial costs. In this work, we propose the parallel Hadamard test, which combines multiple Hadamard tests into a single circuit type. We demonstrate how the parallel Hadamard test applies to three structural classes of workloads: arbitrary sets of unitary operators, prefix-product arrays, and Gram-matrix elements. For each class, we compare the cost of the parallel Hadamard test with that of the conventional one. Our unified approach significantly reduces the number of distinct circuit types, and can lower both computational time and financial costs in regimes where fixed per-circuit overheads dominate the total cost. In Gram-matrix workloads, it can also reduce the total number of shots when typical off-diagonal overlaps are small.

quant-pharXiv:2607.12344•Jul 15, 2026•0 citations

A Practical Guide to Quantum Linear Algebra

Weiss, Alexander, Paul Bruzzi, Fabian M. Faulstich

We present a comprehensive and pedagogical study of two core quantum algorithms in quantum linear algebra: the Hadamard test (HT) and quantum phase estimation (QPE). Building on Prof. Lin's lecture notes on Quantum Algorithms for Scientific Computing, we detail their mathematical formulations, circuit implementations, and convergence behavior. Both algorithms are benchmarked on simulators and IBM's 127-qubit Eagle processor (ibm rensselaer) using a simple eigenvalue problem. While QPE performs well in simulation, its hardware performance degrades beyond t = 3 ancilla qubits due to circuit depth and two-qubit gate noise. In contrast, HT shows stable, sampling-based convergence and greater resilience to hardware noise. We further apply QPE to the transversefield Ising model (TFIM), demonstrating the importance of ansatz quality for accurate ground state energy estimation. These results provide a realistic baseline for implementing phase estimation on noisy intermediate-scale quantum (NISQ) era devices.

•May 29, 2025•0 citations

Statistical Quantum Phase Estimation: Extensions and Practical Considerations

Amit Surana, Brandon Allen

We present several refinements and extensions of the statistical quantum phase estimation (SQPE) framework to address some of its key practical limitations, improving its applicability to realistic cases. Recently, a family of statistical approaches for QPE have been proposed where each run uses only a few ancillae and shorter circuits than standard QPE and thus is better suited for early fault-tolerant quantum computers that are qubit-and depth-limited. SQPE method within that family estimates the cumulative distribution function (CDF) associated with spectral density of the Hamiltonian for a given trial state by using its Fourier approximation and then identifies the first jump discontinuity of the CDF to determine the ground state energy (GSE) of the Hamiltonian. It relies on random compilation procedure based on linear combination of unitaries (LCU) decomposition of the Hamiltonian assuming positive Pauli weights and requires a good estimate of lower bound on the overlap between the trial and true ground state, both of which may be difficult to achieve in practice. We address these limitations by generalizing the random compilation procedure for negative Pauli weights and employing a changepoint detection method for determining GSE which does not rely on an estimate of this overlap. We also show that by exploiting symmetry of the Fourier series one can reduce number of circuit runs/samples by a factor of 2x while keeping the GSE estimation accuracy the same. We illustrate these new developments numerically via a quantum simulator in Qiskit.

quant-pharXiv:2605.18876•May 19, 2026•0 citations

A Practical Guide to Model Problems in Quantum Linear Algebra: Theory and Experiment

Alexander Weiss, Paul Bruzzi

We present a comprehensive and pedagogical study of two core quantum algorithms in quantum linear algebra: the Hadamard test (HT) and quantum phase estimation (QPE).Building on the lecture notes on Quantum Algorithms for Scientific Computing [1] by Lin, we detail their mathematical formulations, circuit implementations, and convergence behavior.Both algorithms are benchmarked on simulators and IBM's 127-qubit Eagle processor (ibm rensselaer) using a simple eigenvalue problem.While QPE performs well in simulation, its hardware performance degrades beyond t = 3 ancilla qubits due to circuit depth and two-qubit gate error.In contrast, HT shows stable samplingbased convergence and greater resilience to hardware noise.These results provide a realistic baseline for implementing phase estimation on noisy intermediate-scale quantum (NISQ) era devices.

SIAM Undergraduate Research Online•Jan 1, 2026•0 citations

Quantum Phaselift

Dhrumil Patel, Laura Clinton, Steven T. Flammia +1 more

Estimating quantum time-series such as the Loschmidt amplitude $f(t)=\langleψ|\mathrm{e}^{-\mathrm{i}Ht}|ψ\rangle$ is central to spectroscopy, Hamiltonian analysis, and many phase-estimation algorithms. Direct estimation via the Hadamard test requires controlled implementations of $\mathrm{e}^{-\mathrm{i}Ht}$, and the depth of these controlled circuits grows with $t$, making long-time estimation challenging on near-term hardware. We introduce Quantum Phaselift, a lifting-based framework that estimates the rank-one matrix $Z = f f^\dagger$ rather than estimating $f$ directly. We propose simple quantum circuits for estimating the entries of $Z$ and show that measuring only a narrow band of this matrix around the diagonal is sufficient to uniquely recover $f$. Crucially, this reformulation decouples the controlled circuit depth from the maximum evolution time to scale instead with the width of the measured band. We prove that a $O(1)$ bandwidth suffices for generic signals, leading to substantial savings in controlled operations compared to direct estimation methods. We develop three recovery algorithms with provable exact recovery in the noiseless setting and stability under measurement noise. Finally, we numerically demonstrate that high-quality recovery is possible for the 2D Fermi-Hubbard and 2D transverse-field Ising model signals of size exceeding 100 time points using only a few million measurement shots and reasonable post-processing time, making our time-series estimation techniques efficient and effective for near-term implementations.

quant-pharXiv:2602.09119•Feb 11, 2026•0 citations
Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate ⟨ψ∣Uk∣ψ⟩\langle ψ|U^{k}|ψ\rangle⟨ψ∣Uk∣ψ⟩ for a large integer kkk for an efficiently preparable initial state ∣ψ⟩|ψ\rangle∣ψ⟩ and an efficiently implementable unitary operator UUU. The Hadamard test is hard to implement because it requires controlled applications of UkU^{k}Uk. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of UUU only but its total run time TtotT_{\rm tot}Ttot​ scales as O(k3/ε2rmin2)\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})O(k3/ε2rmin2​) where rminr_{\rm min}rmin​ is the minimum value of ∣⟨ψ∣Uk′∣ψ⟩∣|\langle ψ|U^{k'}|ψ\rangle|∣⟨ψ∣Uk′∣ψ⟩∣ among all integers k′≤kk' \leq kk′≤k. Typically rminr_{\rm min}rmin​ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state ∣ψ⟩|ψ\rangle∣ψ⟩ to efficiently implement the SPROTIS operator RψϕR_ψ^ϕRψϕ​ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between UaU^{a}Ua and UbU^{b}Ub for integers {a,b}≤k\{a,b\} \leq k{a,b}≤k to estimate ⟨ψ∣Uk∣ψ⟩\langle ψ|U^{k}|ψ\rangle⟨ψ∣Uk∣ψ⟩. The total run time TtotT_{\rm tot}Ttot​ is O(k2ln⁡k/ε2smin6)\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})O(k2lnk/ε2smin6​). Here smins_{\rm min}smin​ is the minimum value of ∣⟨ψ∣Uk^∣ψ⟩|\langle ψ|U^{\hat{k}}|ψ\rangle∣⟨ψ∣Uk^∣ψ⟩ among all integers k^\hat{k}k^ which are values of the nodes of a random binary sum tree whose root node value is kkk and leaf nodes' values are 111 or 000. It can be reasonably expected that smin≪̸1s_{\rm min} \not\ll 1smin​≪1 in typical cases because there is wide freedom in choosing the random binary sum tree.
The entanglement-assisted Hadamard test (EHT) is a practical method for estimating a quantum phase by amplifying the phase signal. However, the feasible amplification is fundamentally limited by the accuracy of the reference phase, such that the method is inefficient in the high-precision regime. In this work, we propose an algorithm, called adaptive entanglement-assisted Hadamard test (AEHT), that iteratively refines the reference phase, enabling progressively stronger amplification as the iteration goes by. We further consider the imperfect eigenstate preparation scenario, where a systematic bias is unavoidable when estimating the quantum phase with the conventional EHT. Such a bias can be suppressed by the proposed AEHT. Moreover, taking physical implementation into consideration, we adopt device-restart count to measure the cost of quantum phase estimation, rather than shot count. The numerical experiments confirm the effectiveness of the proposed AEHT compared with conventional methods under this measure. By unlocking the full amplification power of large entangled states, this work offers an efficient method to estimate high-precision quantum phase on near-term quantum processors.
The Hadamard test is a fundamental building block widely used in many quantum computing algorithms. It estimates the real or imaginary part of ⟨ψ∣U∣ψ⟩\langle ψ\vert U \vert ψ\rangle⟨ψ∣U∣ψ⟩, where ∣ψ⟩\vert ψ\rangle∣ψ⟩ is a quantum state and UUU is a unitary operator. In many algorithms, however, many such quantities must be estimated, leading to a large number of distinct circuit types, long computational times, and high financial costs. In this work, we propose the parallel Hadamard test, which combines multiple Hadamard tests into a single circuit type. We demonstrate how the parallel Hadamard test applies to three structural classes of workloads: arbitrary sets of unitary operators, prefix-product arrays, and Gram-matrix elements. For each class, we compare the cost of the parallel Hadamard test with that of the conventional one. Our unified approach significantly reduces the number of distinct circuit types, and can lower both computational time and financial costs in regimes where fixed per-circuit overheads dominate the total cost. In Gram-matrix workloads, it can also reduce the total number of shots when typical off-diagonal overlaps are small.
We present a comprehensive and pedagogical study of two core quantum algorithms in quantum linear algebra: the Hadamard test (HT) and quantum phase estimation (QPE). Building on Prof. Lin's lecture notes on Quantum Algorithms for Scientific Computing, we detail their mathematical formulations, circuit implementations, and convergence behavior. Both algorithms are benchmarked on simulators and IBM's 127-qubit Eagle processor (ibm rensselaer) using a simple eigenvalue problem. While QPE performs well in simulation, its hardware performance degrades beyond t = 3 ancilla qubits due to circuit depth and two-qubit gate noise. In contrast, HT shows stable, sampling-based convergence and greater resilience to hardware noise. We further apply QPE to the transversefield Ising model (TFIM), demonstrating the importance of ansatz quality for accurate ground state energy estimation. These results provide a realistic baseline for implementing phase estimation on noisy intermediate-scale quantum (NISQ) era devices.
We present several refinements and extensions of the statistical quantum phase estimation (SQPE) framework to address some of its key practical limitations, improving its applicability to realistic cases. Recently, a family of statistical approaches for QPE have been proposed where each run uses only a few ancillae and shorter circuits than standard QPE and thus is better suited for early fault-tolerant quantum computers that are qubit-and depth-limited. SQPE method within that family estimates the cumulative distribution function (CDF) associated with spectral density of the Hamiltonian for a given trial state by using its Fourier approximation and then identifies the first jump discontinuity of the CDF to determine the ground state energy (GSE) of the Hamiltonian. It relies on random compilation procedure based on linear combination of unitaries (LCU) decomposition of the Hamiltonian assuming positive Pauli weights and requires a good estimate of lower bound on the overlap between the trial and true ground state, both of which may be difficult to achieve in practice. We address these limitations by generalizing the random compilation procedure for negative Pauli weights and employing a changepoint detection method for determining GSE which does not rely on an estimate of this overlap. We also show that by exploiting symmetry of the Fourier series one can reduce number of circuit runs/samples by a factor of 2x while keeping the GSE estimation accuracy the same. We illustrate these new developments numerically via a quantum simulator in Qiskit.
We present a comprehensive and pedagogical study of two core quantum algorithms in quantum linear algebra: the Hadamard test (HT) and quantum phase estimation (QPE).Building on the lecture notes on Quantum Algorithms for Scientific Computing [1] by Lin, we detail their mathematical formulations, circuit implementations, and convergence behavior.Both algorithms are benchmarked on simulators and IBM's 127-qubit Eagle processor (ibm rensselaer) using a simple eigenvalue problem.While QPE performs well in simulation, its hardware performance degrades beyond t = 3 ancilla qubits due to circuit depth and two-qubit gate error.In contrast, HT shows stable samplingbased convergence and greater resilience to hardware noise.These results provide a realistic baseline for implementing phase estimation on noisy intermediate-scale quantum (NISQ) era devices.
Estimating quantum time-series such as the Loschmidt amplitude f(t)=⟨ψ∣e−iHt∣ψ⟩f(t)=\langleψ|\mathrm{e}^{-\mathrm{i}Ht}|ψ\ranglef(t)=⟨ψ∣e−iHt∣ψ⟩ is central to spectroscopy, Hamiltonian analysis, and many phase-estimation algorithms. Direct estimation via the Hadamard test requires controlled implementations of e−iHt\mathrm{e}^{-\mathrm{i}Ht}e−iHt, and the depth of these controlled circuits grows with ttt, making long-time estimation challenging on near-term hardware. We introduce Quantum Phaselift, a lifting-based framework that estimates the rank-one matrix Z=ff†Z = f f^\daggerZ=ff† rather than estimating fff directly. We propose simple quantum circuits for estimating the entries of ZZZ and show that measuring only a narrow band of this matrix around the diagonal is sufficient to uniquely recover fff. Crucially, this reformulation decouples the controlled circuit depth from the maximum evolution time to scale instead with the width of the measured band. We prove that a O(1)O(1)O(1) bandwidth suffices for generic signals, leading to substantial savings in controlled operations compared to direct estimation methods. We develop three recovery algorithms with provable exact recovery in the noiseless setting and stability under measurement noise. Finally, we numerically demonstrate that high-quality recovery is possible for the 2D Fermi-Hubbard and 2D transverse-field Ising model signals of size exceeding 100 time points using only a few million measurement shots and reasonable post-processing time, making our time-series estimation techniques efficient and effective for near-term implementations.