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:2609.40128

Optimal Resource Scaling for Early Fault Tolerant Iterative Quantum Phase Estimation under Cost Error Tradeoffs

Mrudula A Mahindrakar, Avhishek Chatterjee

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

The iterative quantum phase estimation algorithm (IPEA) is better suited for NISQ and early fault-tolerant hardware compared to the original algorithm, which requires the inverse quantum Fourier transform. However, current error mitigation and correction implementations lead to imperfect unitaries, causing erroneous phase feedback in IPEA. To improve the reliability of phase bits is to repeat the k^th iteration for the 2^k-th power of the unitary $N_k^*$ times, followed by a majority decision. However, due to variations in their circuit complexities, different iterations incur varying resource costs ($w_k$) and different per-shot error probabilities ($q_k$). Given tight resource constraints, we ask what the optimal number $\{N_k^*: 1\le k \le L\}$ of shots per bit is: $$\arg \max_{\{N_k\}} \mathbb{P}(\text{all } L \text{ bits correct}) \text{ s.t.} \sum_{k=1}^L w_k N_k \le W$$ We obtain closed-form expressions for $N^*_k$ under the conditions: $W \gg \sum_k w_k $(enough for at least one shot per iteration), $w_k$ increases with $k$, $q_k$ are small enough and $L$ is large. We do so by analyzing tractable upper and lower surrogate problems derived via tight concentration and anti-concentration bounds and showing that their solutions converge when $q_k\ll 1$. We observe that when $W\gg \sum_k w_k \ln\! \left(\sum_k w_k\right)$, the optimal $N_k^*$ is proportional to $\frac{\ln\! \left(\sum_k w_k\right)}{c_k}$ and does not depend on individual $w_k$, where $c_k=-\ln\left(2\sqrt{\left(1-\frac{q_k}{2} \right) \frac{q_k}{2}}\right) \propto \ln\frac{1}{q_k}$. However, when $\sum_k w_k \ll W\ll\sum_k w_k \ln\! \left(\sum_k w_k\right)$, the allocation is also (additively) influenced by $\frac{1}{c_k}\ln\frac{1}{w_k}$ for larger values of $k$, i.e., higher powers of unitary. These results lead to simple rules of thumb for resource allocation that may benefit the design of practical systems.

AI Summary

The paper asks how to allocate repeated measurements across iterative quantum phase-estimation (IPEA) bits to maximize the probability that the entire $L$-bit phase is correct under a budget $\sum_k w_kN_k\le W$, with iteration-dependent shot costs $w_k$ and noise strengths $q_k$. It assumes an exactly $L$-bit phase, independent shots, majority-vote decoding, and output depolarizing noise giving conditional single-shot error $q_k/2$ when previous bits are correct. Conditioning on correct prior feedback factorizes full-string success into per-bit majority-success probabilities. For even $N_k$, the per-bit failure probability is bounded between $e^{-c_kN_k}/(N_k+1)^2$ and $e^{-c_kN_k}$, where $c_k=-\ln[2\sqrt{(1-q_k/2)q_k/2}]$. Optimizing the lower-bound surrogate by continuous convex optimization gives $N_k^*=c_k^{-1}\ln[1+c_k/(\lambda w_k)]$, with $\lambda$ fixed by the budget. An upper-bound surrogate is also analyzed; their allocations are argued to approach one another for $q_k\ll1$. For polynomially or exponentially growing costs and bounded $c_k$, asymptotic analysis yields allocation rules. When $W\gg(\sum_k w_k)\ln(\sum_k w_k)$, allocations are approximately proportional to $1/c_k$, normalized to exhaust the budget. At smaller budgets still satisfying $W\gg\sum_k w_k$, individual costs enter through an additive $-\ln(w_k)/c_k$ contribution. The stated scope is low noise, large $L$, and budgets allowing repeated execution of every iteration. The analysis optimizes surrogate objectives rather than the exact binomial success probability, relaxes integer shot counts, and treats rounding effects as negligible in the large-budget regime.

Little sign of AI-generated textIncrementalStrong assumptionsOverclaimsPossible error

Central claim may not hold: The abstract's abundant-budget allocation scales as ln(Σ_k w_k)/c_k, whereas the budget-normalized leading allocation scales as W/[c_k Σ_j(w_j/c_j)]. For costs w_k=2^k and constant noise parameter c, the paper's exponential-cost formula exceeds the available budget asymptotically by a factor 2 ln 2 in its stated abundant-budget regime. The paper establishes an exact optimizer only for a lower-bound surrogate and does not adequately establish the asserted optimality for the original success probability across its stated asymptotic regimes.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum Circuit Optimization for the Fault-Tolerance Era: Do We Have to Start from Scratch?

Tobias V. Forster, Nils Quetschlich, Robert Wille

Quantum computing has made significant advancements in the last years in both hardware and software. Unfortunately, the currently available Noisy Intermediate-Scale Quantum (NISQ) hardware is still heavily affected by noise. Many optimization techniques have been developed to reduce the negative effects thereof, which, however, only works up to a certain point. Therefore, scaling quantum applications from currently considered small research examples to industrial applications requires error-correction techniques to execute quantum circuits in a fault-tolerant fashion and enter the Fault-Tolerant Quantum Computing (FTQC) era. These error-correction techniques introduce dramatic qubit overheads, leading to the requirement of tens of thousands of qubits already for toy-sized examples. Hence, quantum circuit optimization that reduces qubit overheads when shifting from the NISQ to the FTQC era is essential. This raises the question, whether we need to start from scratch, or whether current state-of-the-art optimization techniques can be used as a basis for this. To approach this question, this work investigates the effects of different optimization passes on a representative selection of quantum circuits. Since hardly any tools to automatically design and evaluate FTQC quantum circuits exist yet, we utilize resource estimation to compare the (potential) benefits gained by applying NISQ quantum circuit optimization to estimated FTQC resource requirements. The Results indicate that, indeed, the estimated resource requirements for FTQC can be improved by applying NISQ quantum circuit optimization techniques. At the same time, more detailed investigations show what techniques lead to more benefits for FTQC compared to others, providing guidelines for the transfer of NISQ optimization techniques to the FTQC era.

arXiv:2509.02668•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•3 citations

Error Mitigation and Circuit Division for Early Fault-Tolerant Quantum Phase Estimation

Alicja Dutkiewicz, Stefano Polla, Maximilian Scheurer +3 more

As fully fault-tolerant quantum computers capable of solving useful problems remain a distant goal, we anticipate an era of during which limited error correction is available. We propose a framework for designing early fault-tolerant algorithms by trading between error-correction overhead and residual logical noise, and apply it to quantum phase estimation (QPE). We develop a quantum-Fourier-transform- (QFT) based QPE technique that is robust to global depolarizing noise and outperforms the previous state of the art at low and moderate noise rates. We further introduce the explicitly unbiased maximum-likelihood estimator (EUMLE), a data-processing technique that mitigates errors in QFT-based QPE schemes. EUMLE provides consistent asymptotically normal error-mitigated estimates, addressing the open problem of extending error mitigation beyond expectation-value estimation. Applying this scheme to the ground-state problem of the two-dimensional Hubbard model and various molecular Hamiltonians, we find that we can roughly halve the number of physical qubits with a ∼ 10 times wall-clock time overhead, but that further reduction causes a steep run-time increase. This work provides an end-to-end analysis of early fault-tolerance cost reductions and space-time trade-offs, and identifies which areas can be improved in the future.

arXiv:2410.05369•PRX Quantum•Sep 11, 2025•24 citations

Methods for parallel quantum circuit synthesis, fault-tolerant quantum RAM, and quantum state tomography

Olivia Di Matteo

The pace of innovation in quantum information science has recently exploded due to the hope that a quantum computer will be able to solve a multitude of problems that are intractable using classical hardware. Current quantum devices are in what has been termed the ``noisy intermediate-scale quantum'', or NISQ stage. Quantum hardware available today with 50-100 physical qubits may be among the first to demonstrate a quantum advantage. However, there are many challenges to overcome, such as dealing with noise, lowering error rates, improving coherence times, and scalability. \n \nWe are at a time in the field where minimization of resources is critical so that we can run our algorithms sooner rather than later. Running quantum algorithms ``at scale'' incurs a massive amount of resources, from the number of qubits required to the circuit depth. A large amount of this is due to the need to implement operations fault-tolerantly using error-correcting codes. \n \nFor one, to run an algorithm we must be able to efficiently read in and output data. Fault-tolerantly implementing quantum memories may become an input bottleneck for quantum algorithms, including many which would otherwise yield massive improvements in algorithm complexity. We will also need efficient methods for tomography to characterize and verify our processes and outputs. Researchers will require tools to automate the design of large quantum algorithms, to compile, optimize, and verify their circuits, and to do so in a way that minimizes operations that are expensive in a fault-tolerant setting. Finally, we will also need overarching frameworks to characterize the resource requirements themselves. Such tools must be easily adaptable to new developments in the field, and allow users to explore tradeoffs between their parameters of interest. \n \nThis thesis contains three contributions to this effort: improving circuit synthesis using large-scale parallelization; designing circuits for quantum random-access memories and analyzing various time/space tradeoffs; using the mathematical structure of discrete phase space to select subsets of tomographic measurements. For each topic the theoretical work is supplemented by a software package intended to allow others researchers to easily verify, use, and expand upon the techniques herein.

•Jan 18, 2019•4 citations

Algorithmic error mitigation for quantum eigenvalues estimation

Adam C. Siegel, Kosuke Mitarai, Keisuke Fujii

When estimating the eigenvalues of a given observable, even fault-tolerant quantum computers will be subject to errors, namely algorithmic errors. These stem from approximations in the algorithms implementing the unitary passed to phase estimation to extract the eigenvalues, e.g. Trotterisation or qubitisation. These errors can be tamed by increasing the circuit complexity, which may be unfeasible in early-stage fault-tolerant devices. Rather, we propose in this work an error mitigation strategy that enables a reduction of the algorithmic errors up to any order, at the cost of evaluating the eigenvalues of a set of observables implementable with limited resources. The number of required observables is estimated and is shown to only grow polynomially with the number of terms in the Hamiltonian, and in some cases, linearly with the desired order of error mitigation. Our results show error reduction of several orders of magnitude in physically relevant cases, thus promise accurate eigenvalue estimation even in early fault-tolerant devices with limited number of qubits.

arXiv:2308.03879•Aug 7, 2023•2 citations

Modeling the performance of early fault-tolerant quantum algorithms

Qiyao Liang, Yiqing Zhou, Archismita Dalal +1 more

Progress in fault-tolerant quantum computation (FTQC) has driven the pursuit of practical applications with (EFTQC). These devices, limited in their qubit counts and fault-tolerance capabilities, require algorithms that can accommodate some degrees of error, which are known as EFTQC algorithms. To predict the onset of early quantum advantage, a comprehensive methodology is needed to develop and analyze EFTQC algorithms, drawing insights from both the methodologies of noisy intermediate-scale quantum and traditional FTQC. To address this need, we propose such a methodology for modeling algorithm performance on EFTQC devices under varying degrees of error. As a case study, we apply our methodology to analyze the performance of randomized Fourier estimation (RFE) [Kshirsagar, Katabarwa, and Johnson, ], an EFTQC algorithm for phase estimation. We investigate the runtime performance and the fault-tolerant overhead of RFE in comparison to the traditional quantum phase estimation algorithm. Our analysis reveals that RFE achieves significant savings in physical qubit counts while having a much higher runtime upper bound. We anticipate even greater physical qubit savings when considering more realistic assumptions about the performance of EFTQC devices. By providing insights into the performance trade-offs and resource requirements of EFTQC algorithms, our work contributes to the development of practical and efficient quantum computing solutions on the path to quantum advantage. Published by the American Physical Society 2024

arXiv:2306.17235•Physical Review Research•May 2, 2024•18 citations

Iterative quantum-phase-estimation protocol for shallow circuits

Joseph G. Smith, C. H. W. Barnes, David R. M. Arvidsson-Shukur

Given ${N}_{\text{tot}}$ applications of a unitary operation, parametrized by an unknown phase, a phase-estimation protocol on a large-scale fault-tolerant quantum system can reduce the standard deviation of an estimate of the phase from scaling as $O[1/\sqrt{{N}_{\text{tot}}}]$ to scaling as $O[1/{N}_{\text{tot}}]$. Owing to the limited resources available to near-term quantum devices, protocols that do not entangle probes have been developed. Their mean absolute error scales as $O[log({N}_{\text{tot}})/{N}_{\text{tot}}]$. Here, we propose a two-step protocol for near-term phase estimation, with an improved error scaling. Our protocol's first step produces several low-standard-deviation estimates of $\ensuremath{\theta}$, within $\ensuremath{\theta}$'s parameter range. The second step iteratively homes in on one of these estimates. Our protocol achieves a mean-absolute-error scaling of $O[\sqrt{log(log{N}_{\text{tot}})}/{N}_{\text{tot}}]$ and a root-mean-square-error scaling of $O[\sqrt{log{N}_{\text{tot}}}/{N}_{\text{tot}}]$. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths. This allows our protocol to outperform the asymptotically optimal quantum-phase-estimation algorithm for realistic values of ${N}_{\text{tot}}$.

arXiv:2206.06392•Physical Review A•Dec 19, 2022•20 citations
The iterative quantum phase estimation algorithm (IPEA) is better suited for NISQ and early fault-tolerant hardware compared to the original algorithm, which requires the inverse quantum Fourier transform. However, current error mitigation and correction implementations lead to imperfect unitaries, causing erroneous phase feedback in IPEA. To improve the reliability of phase bits is to repeat the k^th iteration for the 2^k-th power of the unitary Nk∗N_k^*Nk∗​ times, followed by a majority decision. However, due to variations in their circuit complexities, different iterations incur varying resource costs (wkw_kwk​) and different per-shot error probabilities (qkq_kqk​). Given tight resource constraints, we ask what the optimal number {Nk∗:1≤k≤L}\{N_k^*: 1\le k \le L\}{Nk∗​:1≤k≤L} of shots per bit is: arg⁡max⁡{Nk}P(all L bits correct) s.t.∑k=1LwkNk≤W\arg \max_{\{N_k\}} \mathbb{P}(\text{all } L \text{ bits correct}) \text{ s.t.} \sum_{k=1}^L w_k N_k \le Wargmax{Nk​}​P(all L bits correct) s.t.∑k=1L​wk​Nk​≤W We obtain closed-form expressions for Nk∗N^*_kNk∗​ under the conditions: W≫∑kwkW \gg \sum_k w_k W≫∑k​wk​(enough for at least one shot per iteration), wkw_kwk​ increases with kkk, qkq_kqk​ are small enough and LLL is large. We do so by analyzing tractable upper and lower surrogate problems derived via tight concentration and anti-concentration bounds and showing that their solutions converge when qk≪1q_k\ll 1qk​≪1.
We observe that when W≫∑kwkln⁡ ⁣(∑kwk)W\gg \sum_k w_k \ln\! \left(\sum_k w_k\right)W≫∑k​wk​ln(∑k​wk​), the optimal Nk∗N_k^*Nk∗​ is proportional to ln⁡ ⁣(∑kwk)ck\frac{\ln\! \left(\sum_k w_k\right)}{c_k}ck​ln(∑k​wk​)​ and does not depend on individual wkw_kwk​, where ck=−ln⁡(2(1−qk2)qk2)∝ln⁡1qkc_k=-\ln\left(2\sqrt{\left(1-\frac{q_k}{2} \right) \frac{q_k}{2}}\right) \propto \ln\frac{1}{q_k}ck​=−ln(2(1−2qk​​)2qk​​​)∝lnqk​1​. However, when ∑kwk≪W≪∑kwkln⁡ ⁣(∑kwk)\sum_k w_k \ll W\ll\sum_k w_k \ln\! \left(\sum_k w_k\right)∑k​wk​≪W≪∑k​wk​ln(∑k​wk​), the allocation is also (additively) influenced by 1ckln⁡1wk\frac{1}{c_k}\ln\frac{1}{w_k}ck​1​lnwk​1​ for larger values of kkk, i.e., higher powers of unitary. These results lead to simple rules of thumb for resource allocation that may benefit the design of practical systems.
The paper asks how to allocate repeated measurements across iterative quantum phase-estimation (IPEA) bits to maximize the probability that the entire LLL-bit phase is correct under a budget ∑kwkNk≤W\sum_k w_kN_k\le W∑k​wk​Nk​≤W, with iteration-dependent shot costs wkw_kwk​ and noise strengths qkq_kqk​. It assumes an exactly LLL-bit phase, independent shots, majority-vote decoding, and output depolarizing noise giving conditional single-shot error qk/2q_k/2qk​/2 when previous bits are correct.
Conditioning on correct prior feedback factorizes full-string success into per-bit majority-success probabilities. For even NkN_kNk​, the per-bit failure probability is bounded between e−ckNk/(Nk+1)2e^{-c_kN_k}/(N_k+1)^2e−ck​Nk​/(Nk​+1)2 and e−ckNke^{-c_kN_k}e−ck​Nk​, where ck=−ln⁡[2(1−qk/2)qk/2]c_k=-\ln[2\sqrt{(1-q_k/2)q_k/2}]ck​=−ln[2(1−qk​/2)qk​/2​]. Optimizing the lower-bound surrogate by continuous convex optimization gives Nk∗=ck−1ln⁡[1+ck/(λwk)]N_k^*=c_k^{-1}\ln[1+c_k/(\lambda w_k)]Nk∗​=ck−1​ln[1+ck​/(λwk​)], with λ\lambdaλ fixed by the budget. An upper-bound surrogate is also analyzed; their allocations are argued to approach one another for qk≪1q_k\ll1qk​≪1.
For polynomially or exponentially growing costs and bounded ckc_kck​, asymptotic analysis yields allocation rules. When W≫(∑kwk)ln⁡(∑kwk)W\gg(\sum_k w_k)\ln(\sum_k w_k)W≫(∑k​wk​)ln(∑k​wk​), allocations are approximately proportional to 1/ck1/c_k1/ck​, normalized to exhaust the budget. At smaller budgets still satisfying W≫∑kwkW\gg\sum_k w_kW≫∑k​wk​, individual costs enter through an additive −ln⁡(wk)/ck-\ln(w_k)/c_k−ln(wk​)/ck​ contribution.
The stated scope is low noise, large LLL, and budgets allowing repeated execution of every iteration. The analysis optimizes surrogate objectives rather than the exact binomial success probability, relaxes integer shot counts, and treats rounding effects as negligible in the large-budget regime.
Quantum computing has made significant advancements in the last years in both hardware and software. Unfortunately, the currently available Noisy Intermediate-Scale Quantum (NISQ) hardware is still heavily affected by noise. Many optimization techniques have been developed to reduce the negative effects thereof, which, however, only works up to a certain point. Therefore, scaling quantum applications from currently considered small research examples to industrial applications requires error-correction techniques to execute quantum circuits in a fault-tolerant fashion and enter the Fault-Tolerant Quantum Computing (FTQC) era. These error-correction techniques introduce dramatic qubit overheads, leading to the requirement of tens of thousands of qubits already for toy-sized examples. Hence, quantum circuit optimization that reduces qubit overheads when shifting from the NISQ to the FTQC era is essential. This raises the question, whether we need to start from scratch, or whether current state-of-the-art optimization techniques can be used as a basis for this. To approach this question, this work investigates the effects of different optimization passes on a representative selection of quantum circuits. Since hardly any tools to automatically design and evaluate FTQC quantum circuits exist yet, we utilize resource estimation to compare the (potential) benefits gained by applying NISQ quantum circuit optimization to estimated FTQC resource requirements. The Results indicate that, indeed, the estimated resource requirements for FTQC can be improved by applying NISQ quantum circuit optimization techniques. At the same time, more detailed investigations show what techniques lead to more benefits for FTQC compared to others, providing guidelines for the transfer of NISQ optimization techniques to the FTQC era.
As fully fault-tolerant quantum computers capable of solving useful problems remain a distant goal, we anticipate an era of during which limited error correction is available. We propose a framework for designing early fault-tolerant algorithms by trading between error-correction overhead and residual logical noise, and apply it to quantum phase estimation (QPE). We develop a quantum-Fourier-transform- (QFT) based QPE technique that is robust to global depolarizing noise and outperforms the previous state of the art at low and moderate noise rates. We further introduce the explicitly unbiased maximum-likelihood estimator (EUMLE), a data-processing technique that mitigates errors in QFT-based QPE schemes. EUMLE provides consistent asymptotically normal error-mitigated estimates, addressing the open problem of extending error mitigation beyond expectation-value estimation. Applying this scheme to the ground-state problem of the two-dimensional Hubbard model and various molecular Hamiltonians, we find that we can roughly halve the number of physical qubits with a ∼ 10 times wall-clock time overhead, but that further reduction causes a steep run-time increase. This work provides an end-to-end analysis of early fault-tolerance cost reductions and space-time trade-offs, and identifies which areas can be improved in the future.
The pace of innovation in quantum information science has recently exploded due to the hope that a quantum computer will be able to solve a multitude of problems that are intractable using classical hardware. Current quantum devices are in what has been termed the ``noisy intermediate-scale quantum'', or NISQ stage. Quantum hardware available today with 50-100 physical qubits may be among the first to demonstrate a quantum advantage. However, there are many challenges to overcome, such as dealing with noise, lowering error rates, improving coherence times, and scalability. \n \nWe are at a time in the field where minimization of resources is critical so that we can run our algorithms sooner rather than later. Running quantum algorithms ``at scale'' incurs a massive amount of resources, from the number of qubits required to the circuit depth. A large amount of this is due to the need to implement operations fault-tolerantly using error-correcting codes. \n \nFor one, to run an algorithm we must be able to efficiently read in and output data. Fault-tolerantly implementing quantum memories may become an input bottleneck for quantum algorithms, including many which would otherwise yield massive improvements in algorithm complexity. We will also need efficient methods for tomography to characterize and verify our processes and outputs. Researchers will require tools to automate the design of large quantum algorithms, to compile, optimize, and verify their circuits, and to do so in a way that minimizes operations that are expensive in a fault-tolerant setting. Finally, we will also need overarching frameworks to characterize the resource requirements themselves. Such tools must be easily adaptable to new developments in the field, and allow users to explore tradeoffs between their parameters of interest. \n \nThis thesis contains three contributions to this effort: improving circuit synthesis using large-scale parallelization; designing circuits for quantum random-access memories and analyzing various time/space tradeoffs; using the mathematical structure of discrete phase space to select subsets of tomographic measurements. For each topic the theoretical work is supplemented by a software package intended to allow others researchers to easily verify, use, and expand upon the techniques herein.
When estimating the eigenvalues of a given observable, even fault-tolerant quantum computers will be subject to errors, namely algorithmic errors. These stem from approximations in the algorithms implementing the unitary passed to phase estimation to extract the eigenvalues, e.g. Trotterisation or qubitisation. These errors can be tamed by increasing the circuit complexity, which may be unfeasible in early-stage fault-tolerant devices. Rather, we propose in this work an error mitigation strategy that enables a reduction of the algorithmic errors up to any order, at the cost of evaluating the eigenvalues of a set of observables implementable with limited resources. The number of required observables is estimated and is shown to only grow polynomially with the number of terms in the Hamiltonian, and in some cases, linearly with the desired order of error mitigation. Our results show error reduction of several orders of magnitude in physically relevant cases, thus promise accurate eigenvalue estimation even in early fault-tolerant devices with limited number of qubits.
Progress in fault-tolerant quantum computation (FTQC) has driven the pursuit of practical applications with (EFTQC). These devices, limited in their qubit counts and fault-tolerance capabilities, require algorithms that can accommodate some degrees of error, which are known as EFTQC algorithms. To predict the onset of early quantum advantage, a comprehensive methodology is needed to develop and analyze EFTQC algorithms, drawing insights from both the methodologies of noisy intermediate-scale quantum and traditional FTQC. To address this need, we propose such a methodology for modeling algorithm performance on EFTQC devices under varying degrees of error. As a case study, we apply our methodology to analyze the performance of randomized Fourier estimation (RFE) [Kshirsagar, Katabarwa, and Johnson, ], an EFTQC algorithm for phase estimation. We investigate the runtime performance and the fault-tolerant overhead of RFE in comparison to the traditional quantum phase estimation algorithm. Our analysis reveals that RFE achieves significant savings in physical qubit counts while having a much higher runtime upper bound. We anticipate even greater physical qubit savings when considering more realistic assumptions about the performance of EFTQC devices. By providing insights into the performance trade-offs and resource requirements of EFTQC algorithms, our work contributes to the development of practical and efficient quantum computing solutions on the path to quantum advantage. Published by the American Physical Society 2024
Given Ntot{N}_{\text{tot}}Ntot​ applications of a unitary operation, parametrized by an unknown phase, a phase-estimation protocol on a large-scale fault-tolerant quantum system can reduce the standard deviation of an estimate of the phase from scaling as O[1/Ntot]O[1/\sqrt{{N}_{\text{tot}}}]O[1/Ntot​​] to scaling as O[1/Ntot]O[1/{N}_{\text{tot}}]O[1/Ntot​]. Owing to the limited resources available to near-term quantum devices, protocols that do not entangle probes have been developed. Their mean absolute error scales as O[log(Ntot)/Ntot]O[log({N}_{\text{tot}})/{N}_{\text{tot}}]O[log(Ntot​)/Ntot​]. Here, we propose a two-step protocol for near-term phase estimation, with an improved error scaling. Our protocol's first step produces several low-standard-deviation estimates of $\ensuremath{\theta}$, within $\ensuremath{\theta}$'s parameter range. The second step iteratively homes in on one of these estimates. Our protocol achieves a mean-absolute-error scaling of O[log(logNtot)/Ntot]O[\sqrt{log(log{N}_{\text{tot}})}/{N}_{\text{tot}}]O[log(logNtot​)​/Ntot​] and a root-mean-square-error scaling of O[logNtot/Ntot]O[\sqrt{log{N}_{\text{tot}}}/{N}_{\text{tot}}]O[logNtot​​/Ntot​]. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths. This allows our protocol to outperform the asymptotically optimal quantum-phase-estimation algorithm for realistic values of Ntot{N}_{\text{tot}}Ntot​.