Robust Quantum Algorithms for Early Fault-Tolerant Quantum Computing

Abstract

Current quantum computing research is divided into two eras: near-term intermediate scaling quantum (NISQ) and fault-tolerant quantum computing (FTQC). There is a significant gap in these both in terms of hardware and algorithms. An important question is “how to transition from NISQ to FTQC”? Some research looks at an intermediate third era of quantum computing, sometimes referred to as “early” fault-tolerant quantum computing (EFTQC). The idea is to establish a trade-off between hardware and algorithmic parameters such that we have limited size circuits, albeit large enough to allow some amount of error-correction at the cost of more number of samples and increased run-time. This also requires adjustment to algorithms for various tasks. One way to do this is to allow the algorithm to tolerate some level of noise in the input. These algorithms are called “robust” quantum algorithms. In this chapter, we will understand what EFTQC means and how we can distinguish between the three eras of quantum computing. Furthermore, we will look at the ideas behind algorithms suitable for EFTQC devices. Lastly, we will look at two examples of robust quantum algorithms for the task of quantum phase estimation.

1. Introduction

The field of quantum computing caught attention when it was shown to provide an exponential advantage over classical computations. For example, the Deutsch-Jozsa algorithm [1] is a deterministic quantum algorithm which determines whether a given binary function is a constant or a balanced function (outputs 0 for inputs from half of the domain and 1 for the remaining half) and achieves an exponential speed-up over its classical counterparts; Shor’s algorithm [2] prime factorizes an integer which also achieves an exponential speed-up over its classical counterparts; Grover’s algorithm [3] is an unstructured search algorithm where given an output of a function, the algorithm finds a corresponding unique input with high probability and achieves a polynomial speed-up. Practical implementations of these systems needed development of specific hardware. In particular, a system of error-free qubits. To this end, some early developments in the literature of quantum error-correction, such as Shor’s 9 qubit code [4], Steane code [5], Knill-Laflamme concatenated quantum codes [6], etc., seemed promising.

These results attracted a lot of people to the field of quantum computing. Tremendous amount of progress has been seen in various aspects of quantum computing from error-correction to algorithm development and from simulations to hardware development. In light of this research, the community has been broadly divided into two categories. First, where the devices are small and noisy. This is usually referred to as the near-term intermediate scale quantum (NISQ) era of quantum computing. While the exact scale of devices is not clearly determined, it is assumed that these devices have a couple of 100 qubits at most. Devices in this era of quantum computing are sensitive to noise, are large for simulations due to a large number of degrees of freedom as compared to a classical computer but not sufficiently large to perform error-correction. Furthermore, decoherence errors accumulate in NISQ devices over a period of time, and thus the quantum circuits are constrained by a limited depth.

Quantum algorithms developed for NISQ devices are usually classical-quantum hybrid algorithms, where speed-up is determined by the quantum part of the algorithm and some part of the algorithm includes classical processing. Variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) are two popular NISQ algorithms which have various applications. These algorithms require shorter-depth circuits and some amount of error-mitigation to produce accurate results. The VQE algorithm [7] is based on variational methods (approximately finds the ground-state energy), where the quantum computer computes the expectation value of a given system and a classical optimizer improves the guess to determine the ground-state energy of a physical system for a given input ansatz. The QAOA [8], as its name suggests, is an optimization algorithm with a wide range of applications. In most cases, the problem is modeled as a minimization problem to minimize the error. Several variations and applications of VQE and QAOA are studied by the community.

While NISQ era is at one end of the quantum spectrum, at the other end are quantum devices with large number of error-corrected qubits. This is called the fault-tolerant quantum computing (FTQC) era. The quantum circuits for algorithms in this regime have deep circuits and support large computations. The threshold theorem [9, 10, 11] provides a limit on the maximum physical error allowed in the system below which quantum error-correction schemes can reduce the logical errors exponentially. Some popular fault-tolerant quantum algorithms are quantum phase estimation (QPE) [12], quantum amplitude estimation (QAE) [3, 13], etc.

Currently, there is a large gap between the two eras of quantum computing, namely NISQ and FTQC. We find ourselves at a stage where, we as a quantum community need to bridge the gap between these two eras. The natural question that arises is how? There are several challenges in going from NISQ to FTQC, and therefore there is a new era of quantum computing that is coming up. This is called the early fault-tolerant quantum computing (EFTQC) era. Not all research in the literature use the term EFTQC, but the idea is to transition from NISQ to FTQC. This means, that number of physical qubits are still limited (albeit larger than NISQ) at the cost of allowing some amount of (potentially costly) error-correction or more measurements (as compared to FTQC) or other factors. Devices in this new era quantum computing call for a new set of algorithms with some resilience to noise. These algorithms are often called as Robust quantum algorithms.

In the next two sections, we will discuss the EFTQC era of quantum computing, robust quantum algorithms and look at some examples of robust quantum algorithms for phase estimation. The fault-tolerant phase estimation algorithm presented in Ref. [12] is discussed in Appendix A.

2. Early fault-tolerant quantum computing

In this section, we will try to understand what exactly determines early fault-tolerant quantum computing. In order to go beyond NISQ, we need larger systems, meaning that the number of physical qubits is large or the circuit has a larger depth. This means that some amount of error-correction is possible. However, the gates (or qubits) are not fully error-corrected. This means that there is still a restriction on the size of the circuit. Given the restriction on the depth of quantum circuits in the NISQ era, the number of measurements required for algorithms to output a “good” outcome is much larger than the number of measurements required by fault-tolerant algorithms run on deeper circuits.

It is therefore crucial to understand the trade-off between parameters of interest to determine how the three eras of quantum computing are separated from each other. One such definition can be found in Ref. [18]. Katabarwa et al. choose physical gate error-rate and physical qubit number as the parameters and define “scalability” as a trade-off between the two. That is, to determine how the error-rates are maintained below (a potentially lower) threshold value while the size of the circuit grows.

The “scalability” model defined in Ref. [18] can be modified to accommodate specific hardware as well as error-correction requirements in order to evaluate the utility of quantum devices. Furthermore, the requirements of algorithms suited for devices in each era of quantum computing may vary. In the next section, we will discuss one particular type of algorithms called robust quantum algorithms suited to early fault-tolerant devices.

3. Quantum algorithms for EFTQC

In the early fault-tolerant era of quantum computing, we have circuits deeper that can be deeper than the NISQ circuits with some amount of error-correction and slightly higher measurements as compared to fault-tolerance. Therefore, there arises a need to modify quantum algorithms and make them suitable for EFTQC. The idea is to improve on one or more parameters (reduce the number of logical qubits, reduce the number of gate operations, and increase noise accommodation levels of the algorithm) at the cost of increased number of measurements, complexity as well as classical processing.

Our main focus is one such category of algorithms called robust quantum algorithms. Robust quantum algorithms incorporate some amount of noise in the inputs. The idea here is to consider noise as a nuisance parameter to the input function and then run the algorithm. One way to achieve this is minimizing the quantum computation to what is absolutely necessary and offloading other computations to a classical system. However, the classical offloading means the quantum states must be mapped to classical states and back. Given that the quantum systems have more degrees of freedom as compared to their classical counterparts, this back-and-forth mapping of states will create an overhead. This will in turn lead to an increased number of measurements as well as re-initialization of quantum states.

In the next section, we will look at some examples of robust quantum algorithms.

4. Some examples of robust quantum algorithms for quantum phase estimation

In this section, we will look at a nonexhaustive list of robust quantum algorithms for the task of phase estimation. We will particularly focus on quantum phase estimation because the methodologies can be easily extended to develop algorithms for other tasks, such as amplitude estimation, ground-state energy estimation, ground-state property estimation, etc. Appendix A contains a summary of the fault-tolerant quantum phase estimation algorithm [12]. Appendix B contains a summary of the Hadamard test [14], which is used to develop the robust quantum algorithms discussed here.

4.1 Robust phase estimation

We will first look at the Robust Phase Estimation (RPE) algorithm [15] for phase estimation. It is a robust quantum algorithm, meaning it can accommodate for some errors. As long as the errors are below a certain threshold, the algorithm estimates the phase of an input state accurately. The RPE protocol requires application of a unitary $U$ repeatedly, such that given input $\left|0\right.⟩$ or $\left|+\right.⟩=\frac{\left|0\right.⟩+i\left|1\right.⟩}{\sqrt{2}}$, the quantum circuit used for measurement encodes the phase with a probability distribution as in Eqs. (1) and (2). Let the experiments be indexed by $k$, then in the $k$th generation $U$ is applied $N_k$ times. And, in each run, RPE estimates the rotation of $U$, ${\widehat{\theta }}_k$. The maximum ${\widehat{\theta }}_k$ is the required phase.

$${\mathit{Pr}}_{0,k}=\frac{1+cos\left(N_k\theta \right)}{2}$$E1

$${\mathit{Pr}}_{+,k}=\frac{1+sin\left(N_k\theta \right)}{2}$$E2

The algorithm accommodates some level of noise in the input, which is modeled as additive errors in the probability distribution. That is, Eqs. (1) and (2) are modified as Eqs. (3) and (4) for noise ${\delta }_0\left(k\right)$ when the input is $0$ and noise ${\delta }_{+}\left(k\right)$ when the input is +.

$${\mathit{Pr}}_{0,k}=\frac{1+cos\left(N_k\theta \right)}{2}+{\delta }_0\left(k\right)$$E3

$${\mathit{Pr}}_{+,k}=\frac{1+sin\left(N_k\theta \right)}{2}+{\delta }_{+}\left(k\right)$$E4

Therefore, under the assumption that perfect resources are not required for phase estimation, in the worst-case scenario depolarizing errors or amplitude sampling noise can be re-modeled as additive errors. Furthermore, the set-up allows control over gates (including gate errors) and upon characterization, systematic errors can be undone. This process is robust to state preparation and measurement errors. It may be noted that the algorithm works efficiently as long as the amount of noise is below a certain threshold. The algorithm is Heisenberg-limited, meaning given an accuracy $\epsilon$ the run-time scales as $O\left(1/\epsilon \right)$ in the case that the noise is below the threshold.

The main result of the paper [15] where RPE was introduced can be summarized as follows. Consider a nonadaptive experimental set-up. Given an input $0$ or $+$ with noise ${\delta }_0\left(k\right)$ and noise ${\delta }_{+}\left(k\right)$, respectively, RPE can be performed with probability of success as given in Eqs. (3) and (4). The $k$th experiment takes time proportional to $k$ and estimates ${\widehat{\theta }}_k\in \left(-\pi ,\pi \right]$ with a standard deviation $\sigma \left({\widehat{\theta }}_k\right)$. The run-time of the algorithm is $O\left(1/\sigma \left({\widehat{\theta }}_k\right)\right)$. Moreover, if $\mid {\delta }_0\left(k\right)\mid$ and $\mid {\delta }_{+}\left(k\right)\mid$ are less than $1/\sqrt{8}$ for all $k<k^{\ast }$ then $\sigma \left({\widehat{\theta }}_k\right)\sim O\left(1/k^{\ast }\right)$.

4.2 Randomized fourier estimation

In this subsection, we will look at the Randomized Fourier Estimation (RFE) [16] and modified RFE algorithms [17] for phase estimation. The RFE algorithm introduced in Ref. [16] works on a similar principal as the RPE, meaning that it estimates the phase of an input state accurately and efficiently in the presence of noise up to a threshold. While two types of noise models are considered in Ref. [16], another one is considered in Ref. [17]. The circuit used for (lower bounded number of) measurements is a modified Hadamard test (Appendix B) circuit as shown in Figure 5 (Figure 1).

Figure 1.

(figure 1 in [16]) circuit diagram of the Hadamard, where the application of phase gate $S=\left[\begin{array}{cc}1& 0\\ 0& i\end{array}\right]$ is toggled by $\mathrm{\ell }=0,1$.

Here, $S=\left[\begin{array}{cc}1& 0\\ 0& i\end{array}\right]$ is the phase gate. In the case that $\mathrm{\ell }=0$, the modified Hadamard test (real in this case) produces outcome $c=\pm 1$ with probability given in Eq. (5).

$$\mathit{Pr}\left(c|k\right)=\frac{1+ccos\left(\mathit{k\theta }\right)}{2}$$E5

In the case that $\mathrm{\ell }=1$, the modified Hadamard test (imaginary in this case) produces outcome $s=\pm 1$ with probability given in Eq. (6).

$$\mathit{Pr}\left(s|k\right)=\frac{1+scos\left(\mathit{k\theta }\right)}{2}$$E6

The outcome probabilites in Eqs. (5) and (6) change based on the noise model used to determine the noise in inputs. The analysis uses an analogy to a signal processing task due to similarity. Let us first consider the case where there is noise in the input state. The RFE algorithm can be summarized as follows. Given a maximum number of iterations (samples) $M$ and a maximum depth $K$ (which is analogously the maximum value of the time variable), initialize a Fourier estimate to 0, $\widehat{f}\leftarrow 0\in {\mathrm{ℂ}}^K$. Draw a sample of the time signal as in Eq. (7) for a time variable $k\in \left\{0,\dots ,K-1\right\}$ and call the real Hadamard test (output $c$) as well as the imaginary Hadamard test (output $s$).

$$g\left(k\right)=\left(\mathit{Pr}\left(c=1|k\right)-\mathit{Pr}\left(c=-1|k\right)\right)+e^{\mathit{ik\theta }}\left(\mathit{Pr}\left(s=1|k\right)-\mathit{Pr}\left(s=-1|k\right)\right)$$E7

Update the Fourier estimate $M$ times using Eq. (8). Let $j$ represent the iteration number.

$${\widehat{f}}_j\leftarrow \frac{{\widehat{f}}_j\left(c+\mathit{\text{is}}\right)e^{-2\mathit{\text{πikj}}/K}}{M}$$E8

This generates an array of $M$ Fourier estimates. The output phase corresponds to the maximum Fourier estimate. In the noiseless case, the algorithm efficiently estimates the accurate phase with high probability. Given an accuracy $\epsilon$, RFE estimates the accurate phase with high probability in $O\left(1/\left(\epsilon ln\epsilon \right)\right)$ time.

Now, we will look at how a noisy input affects the algorithm. There are two types of additive noise models used to determine the noise in the input in Ref. [16]. The first model called the bounded adversarial noise (BAN) model represents a worst-case analysis of the algorithm’s tolerance to noise. The second model called the Gaussian noise (GN) model represents a more realistic noise model where the additive noise is drawn from a Gaussian distribution. The GN model is a special case of the BAN model. In both these cases, given that the noise is below a certain threshold the number of samples required to accurately estimate the phase is slightly higher than that in the noiseless case. Moreover, the run-time of the algorithm is slightly longer. However, in both the cases given an accuracy $\epsilon$, RFE estimates the accurate phase with high probability in $O\left(1/\left(\epsilon ln\epsilon \right)\right)$ time.

A third noise model presented in Ref. [17] captures the effect of noise as a combination of exponential decay and random fluctuations in the algorithm. Let us call this the algorithmic noise (AN) model. The analysis requires a modified version of RFE, where the phase gate in modified Hadamard tests is replaced with a modified phase gate, $S\left(\varphi \right)=\left[\begin{array}{cc}1& 0\\ 0& e^{\mathit{i\varphi }}\end{array}\right]$. The circuit is presented in Figure 2.

Figure 2.

(figure 1 in [17]) circuit diagram of the modified Hadamard, where the application of modified phase gate $S\left(\varphi \right)=\left[\begin{array}{cc}1& 0\\ 0& e^{\mathit{i\varphi }}\end{array}\right]$ leads to a measurement ${\sigma }_{\varphi }=cos\left(\varphi \right){\sigma }_x-sin\left(\varphi \right){\sigma }_y$ of the region of the circuit comprising of the $S\left(\varphi \right),H^{†}$ gates and the meter; and ${\sigma }_x$, ${\sigma }_y$ are conventional Pauli operators.

Under this noise model, the time signal $g\left(k\right)$ in Eq. (7) decays exponentially. This means that identifying the largest Fourier estimate requires a more number of samples. We will not go into the details of the analysis here. Given that the noise is low, the algorithm is Heisenberg-limited. That is, given an accuracy $\epsilon$, the algorithm runs in $O\left(1/\epsilon \right)$ time. However, if the noise is high, the algorithm runs in $O\left(1/{\epsilon }^2\right)$ time.

We summarize the outcome probabilities of the real and imaginary modified Hadamard test noiseless cases and all three noise models are discussed in Table 1.

	Real Hadamard test	Imaginary Hadamard test	Special conditions
Noiseless input	$\mathit{Pr}\left(c|k;\theta \right)=\frac{1+ccos\left(\mathit{k\theta }\right)}{2}$	$\mathit{Pr}\left(s|k;\theta \right)=\frac{1+ssin\left(\mathit{k\theta }\right)}{2}$	None
BAN model	$\mathit{Pr}\left(c|k;\theta \right)=\frac{1+c\left(cos\left(\mathit{k\theta }\right)+{\eta }_{1,k}\right)}{2}$	$\mathit{Pr}\left(s|k;\theta \right)=\frac{1+s\left(sin\left(\mathit{k\theta }\right)+{\eta }_{2,k}\right)}{2}$	None
GN model	$\mathit{Pr}\left(c|k;\theta \right)=\frac{1+c\left(cos\left(\mathit{k\theta }\right)+{\eta }_{1,k}\right)}{2}$	$\mathit{Pr}\left(s|k;\theta \right)=\frac{1+s\left(sin\left(\mathit{k\theta }\right)+{\eta }_{2,k}\right)}{2}$	${\eta }_{1,k},{\eta }_{2,k}$ are drawn from a Gaussian distribution.
AN model	$\mathit{Pr}\left(c|k,\varphi ;\theta \right)=\frac{1+{\mathit{ce}}^{-\mathit{\lambda k}}cos\left(\mathit{k\theta }-\varphi \right)+{\eta }_{k,\varphi }}{2}$	$\mathit{Pr}\left(s|k,\varphi ;\theta \right)=\frac{1+{\mathit{se}}^{-\mathit{\lambda k}}sin\left(\mathit{k\theta }-\varphi \right)+{\eta }_{k,\varphi }}{2}$	None

Table 1.

Probability of outcomes of real and imaginary Hadamard tests for various models of RFE.

5. Discussion

The Robust Phase Estimation algorithm summarized in Section 4.1 estimates all systematic single-qubit gate errors simultaneously and represents these using additive errors in the measurement probabilities of experiments (see Eqs. (2) and (3)). However, this analysis can be extended further to multi-qubit operations. Furthermore, the additive noise model can be refined to include errors such as due to twirling occurring by repeated gate applications. The algorithm has been tested for robustness in Ref. [19]. We will not go into the analysis of these experiments here. The framework of the algorithm has also been extended to develop other robust quantum algorithms such as robust ground-state energy estimation [20].

Similarly, the Randomized Fourier Estimation algorithm summarized in Section 4.2 provides a framework to analyze quantum algorithms under different noise models. The noise models can be fine-tuned to accommodate a more practical scenario. Furthermore, the framework can be utilized to develop robust quantum algorithms for tasks, such as amplitude estimation, ground-state energy estimation, ground-state property estimation, etc.

6. Conclusions

The quantum community is currently divided between the near-term intermediate scaling quantum (NISQ) era and the fault-tolerant quantum computing (FTQC) era. In the NISQ era, the devices are small and highly sensitive to noise. The small sizes of circuits imply that error-correction is not possible. Algorithms developed for running on NISQ devices are hybrid classical-quantum algorithms. The quantum part of the algorithm requires a shorter-depth circuit, which means a large part of the process must be offloaded to classical systems for processing. Since error-correction is not possible, some error-mitigation techniques might be necessary. Here, we briefly touch upon two NISQ algorithms: VQE and QAOA.

In the FTQC era, the devices are large and resilient to noise. The larger sizes of circuits imply error-correction can be done efficiently. Algorithms developed for running on FTQC devices have deep circuits and support a large number of computations. We have discussed one FTQC algorithm: QPE. It may be noted that the hardware development of FTQC devices is not feasible currently.

In moving from NISQ to FTQC era, the size of circuits must increase to allow at least some amount of error-correction. This will come at some cost in terms of fault-tolerance. Some works in the literature call this the early fault-tolerant quantum computing (EFTQC) era. There are several ways in which the three eras of quantum computing can be distinguished from each other. We discuss one such model: namely the “scalability” model where the scalability is the measure of trade-off between the circuit size and number of samples required to run any algorithm successfully. The scalability model used to distinguish between the three eras of quantum computing can be improved by incorporating several hardware and algorithmic parameters into the model definition.

Devices in the EFTQC era of quantum computing are larger than their NISQ counterparts. This enables some amount of error-correction. This means that error-mitigation and error-correction techniques may be combined to deal with noise. New algorithms may be required to suit EFTQC devices, which could need deeper circuits. These deeper circuits will require a cost in the form of increased measurements and run-times. There are a few different techniques found in the literature to develop these new algorithms. One such technique incorporates some amount of noise in the algorithm input. This class of algorithms is called “robust” quantum algorithms. We discuss two types of robust quantum algorithms for the task of phase estimation: namely RPE and RFE. We do not discuss an exhaustive list of algorithms or development techniques in this work. Yet, there are several ways in which the algorithms can be improved in order to move toward fault-tolerance. All-in-all, we are still far-away from fault-tolerance. However, development of hardware as well as algorithms for this new era of quantum computing, namely EFTQC, might be a step in the direction of slowly achieving fault-tolerance.

Appendix A: Kitaev’s phase estimation algorithm

Here, we will look at the (fault-tolerant) QPE algorithm. Given a unitary matrix $U$ and its eigenvector $\left|\psi \right.⟩$, QPE [12] tries to estimate the angle ${\theta }_{\psi }$ by estimating $\left|\psi \right.⟩$ where $U\left|\psi \right.⟩=e^{i{\theta }_{\psi }}\left|\psi \right.⟩$. Given an additive error $\epsilon$, the algorithm needs $O\left(log\left(1/\epsilon \right)\right)$ qubits and $O\left(1/\epsilon \right)$ controlled-U operations. An important question to answer is what kind of information can we get by running QPE. Let us first look at the single (ancilla) qubit version of QPE. Consider the circuit in Figure 3, which is applied to implement (single-qubit) QPE.

Figure 3.

Circuit implemented for (single-qubit) QPE.

Given an input $\left|0\right.⟩\otimes \left|\psi \right.⟩$, applying the Hadamard gate to $\left|0\right.⟩$ yields

$$\frac{1}{\sqrt{2}}\left(\left|0\right.⟩+\left|1\right.⟩\right)\otimes \left|\psi \right.⟩=\frac{1}{\sqrt{2}}\left(\left|0\right.⟩\otimes \left|\psi \right.⟩+\left|1\right.⟩\otimes \left|\psi \right.⟩\right).$$E9

Then applying controlled-$U$ to $\left|\psi \right.⟩$ yields

$$\frac{1}{\sqrt{2}}\left(\left|0\right.⟩\otimes \left|\psi \right.⟩+e^{i{\theta }_{\psi }}\left|1\right.⟩\otimes \left|\psi \right.⟩\right).$$E10

Finally applying the Hadamard gate to the first qubit yields:

$$\frac{1}{\sqrt{2}}\left(\left(1+e^{i{\theta }_{\psi }}\right)\left|0\right.⟩\otimes \left|\psi \right.⟩+\left(1-e^{i{\theta }_{\psi }}\right)\left|1\right.⟩\otimes \left|\psi \right.⟩\right).$$E11

The probability of measuring the first qubit as $\left|0\right.⟩$ is

$${\left|\frac{1}{2}\left(1+e^{i{\theta }_{\psi }}\right)\right|}^2$$E12

and that of measuring the first qubit as $\left|1\right.⟩$ is

$${\left|\frac{1}{2}\left(1-e^{i{\theta }_{\psi }}\right)\right|}^2.$$E13

The algorithm can be extended to a multiple (ancilla) qubit system. This is the QPE algorithm presented in Ref. [12]. Given an input ${\left|0\right.⟩}^{\otimes n}\otimes \left|\psi \right.⟩$, consider the quantum circuit in Figure 4.

Figure 4.

Circuit implemented for (multiple qubit) QPE.

Applying the Hadamard gate to ${\left|0\right.⟩}^{\otimes n}$ yields

$$\frac{1}{2^{n/2}}{\left(\left|0\right.⟩+\left|1\right.⟩\right)}^{\otimes n}\otimes \left|\psi \right.⟩=\frac{1}{2^{n/2}}\sum _{j=0}^{2^n-1}\left|j\right.⟩\left|\psi \right.⟩.$$E14

Then applying controlled-$U^j$ to $\left|j\right.⟩\left|\psi \right.⟩$ yields

$$\frac{1}{\sqrt{2^n}}{e}^{2\mathit{\text{πijθ}}}\left|j\right.⟩\left|\psi \right.⟩.$$E15

Finally applying the inverse quantum Fourier transform yields

$$\frac{1}{2^{n/2}}\sum _{k=0}^{2^n-1}{e}^{2\mathit{\text{πiθk}}}\left(\frac{1}{2^{n/2}}\sum _{x=0}^{2^n-1}{e}^{-2\mathit{\text{πikx}}/2^n}\left|x\right.⟩\right)=\frac{1}{2^n}\sum _{x=0}^{2^n-1}\sum _{k=0}^{2^n-1}{e}^{\frac{-2\mathit{\pi ik}}{2^n}\left(x-2^n\theta \right)}\left|x\right.⟩.$$E16

This can be rewritten as follows:

$$\begin{array}{ll}\mathit{QPE}\left({\left|0\right.⟩}^{\otimes n}\otimes \left|\psi \right.⟩\right)=& \frac{1}{\sqrt{2^n}}\left(\left(\left(1+e^{i{\theta }_{\psi }{2}^{n-1}}\right)\left|0\right.⟩+\left(1-e^{i{\theta }_{\psi }{2}^{n-1}}\right)\left|1\right.⟩\right)\otimes \left(\left(1+e^{i{\theta }_{\psi }{2}^{n-2}}\right)\left|0\right.⟩+\left(1-e^{i{\theta }_{\psi }{2}^{n-2}}\right)\left|1\right.⟩\right)\right.\otimes \\ & \cdots \otimes \left.\left(\left(1+e^{i{\theta }_{\psi }{2}^0}\right)\left|0\right.⟩+\left(1-e^{i{\theta }_{\psi }{2}^0}\right)\left|1\right.⟩\right)\right)\otimes \left|\psi \right.⟩.\end{array}$$E17

Appendix B: Hadamard test

Here, we will look at the Hadamard test [14], a method used to create a random variable. Given a unitary matrix $U$ and a state $\left|\psi \right.⟩$, the Hadamard test provides an estimate of $\mathit{Re}\left(\left.⟨\psi \right|U\left|\psi \right.⟩\right)$. The circuit in Figure 5 is used for this purpose.

Figure 5.

Circuit implemented for Hadamard test and estimating the probability of $\left|0\right.⟩$ output.

The probability of measuring $\left|0\right.⟩$ is

$$P\left(\left|0\right.⟩\right)=\frac{1}{2}\left(1+\mathit{Re}\left(\left.⟨\psi \right|U\left|\psi \right.⟩\right)\right)$$E18

and the probability of measuring $\left|1\right.⟩$ is

$$P\left(\left|1\right.⟩\right)=\frac{1}{2}\left(1-\mathit{Re}\left(\left.⟨\psi \right|U\left|\psi \right.⟩\right)\right).$$E19

Thus, $\mathit{Re}\left(\left.⟨\psi \right|U\left|\psi \right.⟩\right)$ can be estimated by computing $P\left(\left|0\right.⟩\right)+P\left(\left|1\right.⟩\right)$, that is the same as $2P\left(\left|0\right.⟩\right)-1$. Moreover, $\mathit{Im}\left(\left.⟨\psi \right|U\left|\psi \right.⟩\right)$ can be estimated using a similar circuit in Figure 6.

Figure 6.

Circuit implemented for Hadamard test and estimating the probability of $\left|1\right.⟩$ output.

This test can also be thought of as a coin flip experiment. Assume $M$ samples with $K$ heads and $M-K$ tails. Then the probability of heads, $P\left(H\right)=\frac{K}{M}$. Note that $P\left(H\right)$ corresponds to the estimator, $\widehat{P\left(\left|0\right.⟩\right)}$ and thus the estimate of $\mathit{Re}\left(\left.⟨\psi \right|U\left|\psi \right.⟩\right)$ is $\frac{2K}{M}-1$.

Abbreviations

NISQ	Near-term intermediate scaling quantum
FTQC	Fault-tolerant quantum computing
EFTQC	Early fault-tolerant quantum computing
VQE	Variational quantum eigensolver
QAOA	Quantum approximate optimization algorithm
QPE	Quantum phase estimation
QAE	Quantum amplitude estimation
QFT	Quantum Fourier transform
RPE	Robust phase estimation
RFE	Randomized Fourier estimation
BAN	Bounded adversarial noise
GN	Gaussian noise
AN	Algorithmic noise