# Quantum phase estimation algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Quantum_phase_estimation_algorithm
> Markdown URL: https://mediated.wiki/source/Quantum_phase_estimation_algorithm.md
> Source: https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm
> Source revision: 1326463885
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Use American English|date=January 2019}}{{Short description|Quantum algorithm for eigenvalue estimation
}}
In [quantum computing](/source/quantum_computing), the '''quantum phase estimation algorithm''' is a [quantum algorithm](/source/quantum_algorithm) to estimate the phase corresponding to an eigenvalue of a given [unitary operator](/source/Unitary_matrix). Because the eigenvalues of a unitary operator always have [unit modulus](/source/Absolute_value_of_a_complex_number), they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. The algorithm was initially introduced by [Alexei Kitaev](/source/Alexei_Kitaev) in 1995.<ref name="kitaev">{{Cite arXiv|last=Kitaev|first=A. Yu|date=1995-11-20|title=Quantum measurements and the Abelian Stabilizer Problem|eprint=quant-ph/9511026}}</ref><ref name="nielchuan" />{{rp|246}}

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as [Shor's algorithm](/source/Shor's_algorithm),<ref name=nielchuan>{{cite book|last1=Nielsen|first1=Michael A. & Isaac L. Chuang|title=Quantum computation and quantum information|date=2001|publisher=Cambridge Univ. Press|location=Cambridge [u.a.]|isbn=978-0521635035|edition=Repr.}}</ref>{{rp|131}} the [quantum algorithm for linear systems of equations](/source/quantum_algorithm_for_linear_systems_of_equations), and the [quantum counting algorithm](/source/quantum_counting_algorithm).

==Overview of the algorithm==
The algorithm operates on two sets of qubits, referred to in this context as [registers](/source/Quantum_register). The two registers contain <math> n </math> and <math> m </math> qubits, respectively. Let <math>U</math> be a [unitary operator](/source/unitary_operator) acting on the <math>m</math>-[qubit](/source/qubit) register. The eigenvalues of a unitary operator have unit modulus, and are therefore characterized by their phase. Thus if <math>| \psi \rangle</math> is an [eigenvector](/source/Eigenvalues_and_eigenvectors) of <math>U</math>, then <math>U| \psi\rangle =  e^{ 2\pi i \theta}\left|\psi \right\rangle </math> for some <math>\theta\in\mathbb{R} </math>. Due to the periodicity of the complex exponential, we can always assume <math>0 \leq \theta < 1 </math>.

The goal is producing a good approximation for <math>\theta </math> with a small number of gates and a high probability of success. The [quantum phase](/source/Phase-space_formulation) estimation algorithm achieves this assuming oracular access to <math>U </math>, and having <math>|\psi\rangle </math> available as a [quantum state](/source/quantum_state). This means that when discussing the efficiency of the algorithm we only worry about the number of times <math>U </math> needs to be used, but not about the cost of implementing <math>U </math> itself.

More precisely, the algorithm returns [with high probability](/source/with_high_probability) an approximation for <math>\theta</math>, within additive error <math>\varepsilon</math>, using <math>n=O(\log(1/\varepsilon))</math> qubits in the first register, and <math>O(1/\varepsilon)</math> [controlled-''U''](/source/quantum_logic_gate) operations. Furthermore, we can improve the success probability to <math>1-\Delta</math> for any <math>\Delta>0</math> by using a total of <math>O(\log(1/\Delta)/\varepsilon)</math> uses of controlled-U, and this is optimal.<ref name="optimality">{{cite arXiv | eprint = 2305.04908| last1 = Mande| first1 = Nikhil S.| author2 = Ronald de Wolf| title = Tight Bounds for Quantum Phase Estimation and Related Problems| date = 2023| class = quant-ph}}</ref>

==Detailed description of the algorithm==
thumb|500x500px|The circuit for quantum phase estimation.

===State preparation===
The initial state of the system is:
:<math> |\Psi_0\rangle = |0\rangle^{\otimes n}|\psi\rangle ,</math>

where <math> |\psi\rangle</math> is the <math> m</math>-qubit state that evolves through <math> U</math>. We first apply the ''n-qubit'' [Hadamard gate operation](/source/Hadamard_transform) <math> H^{\otimes n} </math> on the first register, which produces the state:<math display="block">|\Psi_1\rangle = (H^{\otimes n}\otimes I_m)|\Psi_0\rangle = \frac{1}{2^{\frac{n}{2}}}(|0\rangle + |1\rangle)^{\otimes n}|\psi\rangle = \frac{1}{2^{n/2}} \sum_{j = 0}^{2^n - 1} |j\rangle |\psi\rangle.</math>Note that here we are switching between binary and <math>n</math>-ary representation for the <math>n</math>-qubit register: the ket <math>|j\rangle</math> on the right-hand side is shorthand for the <math>n</math>-qubit state <math>|j\rangle\equiv \bigotimes_{\ell=0}^{n-1} |j_\ell\rangle</math>, where <math>j=\sum_{\ell=0}^{n-1} j_\ell 2^\ell</math> is the binary decomposition of <math>j</math>.

=== Controlled-U operations ===
This state <math>|\Psi_1\rangle</math> is then evolved through the controlled-unitary evolution <math>U_C</math> whose action can be written as<math display="block"> U_C(|k\rangle\otimes|\psi\rangle) = |k\rangle\otimes( U^{k}|\psi\rangle),</math> for all <math> k=0,...,2^n-1</math>. This evolution can also be written concisely as<math display="block">U_C = \sum_{k=0}^{2^n-1} |k\rangle\!\langle k|\otimes U^k,</math> which highlights its controlled nature: it applies <math>U^k</math> to the second register conditionally to the first register being <math>|k\rangle</math>. Remembering the eigenvalue condition holding for <math>|\psi\rangle</math>, applying <math>U_C</math> to <math>|\Psi_1\rangle</math> thus gives<math display="block">|\Psi_2\rangle \equiv U_C|\Psi_1\rangle
= \left(\frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1} e^{2\pi i \theta k}|k\rangle\right)\otimes |\psi\rangle,</math> where we used <math>U^{k}| \psi\rangle = e^{ 2\pi i k\theta}|\psi \rangle</math>. 

To show that <math>U_C</math> can also be implemented efficiently, observe that we can write <math>U_C = \prod_{\ell=0}^{n-1} C_\ell(U^{2^\ell})</math>, where <math>C_\ell(U^{2^\ell})</math> denotes the operation of applying <math>U^{2^\ell}</math> to the second register conditionally to the <math>\ell</math>-th qubit of the first register being <math>|1\rangle</math>. Formally, these gates can be characterized by their action as<math display="block">C_\ell(U^k) (|j\rangle\otimes |\psi\rangle)
= |j\rangle\otimes ( U^{j_\ell k}|\psi\rangle).</math>This equation can be interpreted as saying that the state is left unchanged when <math>j_\ell=0</math>, that is, when the <math>\ell</math>-th qubit is <math>|0\rangle</math>, while the gate <math>U^k</math> is applied to the second register when the <math>\ell</math>-th qubit is <math>|1\rangle</math>. The composition of these controlled-gates thus gives<math display="block">\prod_{\ell=0}^{n-1} C_\ell(U^{2^\ell})(|j\rangle\otimes|\psi\rangle)
= |j\rangle\otimes\left(U^{\sum_{\ell=0}^{n-1} j_\ell 2^\ell} |\psi\rangle\right)= U_C \left( |j\rangle\otimes |\psi\rangle\right),</math> with the last step directly following from the binary decomposition <math>j=\sum_{\ell=0}^{n-1} j_\ell 2^\ell</math>.

From this point onwards, the second register is left untouched, and thus it is convenient to write <math>|\Psi_2\rangle=|\tilde\Psi_2\rangle\otimes|\psi\rangle</math>, with <math>|\tilde\Psi_2\rangle</math> the state of the <math>n</math>-qubit register, which is the only one we need to consider for the rest of the algorithm.

=== Apply inverse quantum Fourier transform ===
The final part of the circuit involves applying the inverse [quantum Fourier transform](/source/quantum_Fourier_transform) (QFT) <math>\mathcal{QFT}</math> on the first register of <math>|\Psi_2\rangle</math>:<math display="block">|\tilde\Psi_3\rangle = \mathcal{QFT}^{-1}_{2^n} |\tilde\Psi_2\rangle.</math>The QFT and its inverse are characterized by their action on basis states as<math display="block">\begin{align}
\mathcal{QFT}_N|k\rangle &= N^{-1/2}\sum_{j=0}^{N-1} e^{\frac{2\pi i}{N}jk}|j\rangle, \\
\mathcal{QFT}_N^{-1}|k\rangle &= N^{-1/2}\sum_{j=0}^{N-1} e^{-\frac{2\pi i}{N}jk}|j\rangle.
\end{align}</math> It follows that 

:<math>|\tilde\Psi_3\rangle = \frac{1}{2^{\frac{n}{2}}}\sum_{k=0}^{2^n - 1} e^{2\pi i \theta k} \left( \frac{1}{2^{\frac{n}{2}}}\sum_{x=0}^{2^n - 1} e^{\frac{-2\pi i k x}{2^n}}|x\rangle \right) = \frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{2\pi i k}{2^n} \left ( x - 2^n \theta \right )}  |x\rangle.</math>
Decomposing the state in the computational basis as <math display="inline">|\tilde\Psi_3\rangle = \sum_{x=0}^{2^n-1} c_x |x\rangle,</math> the coefficients thus equal<math display="block"> c_x \equiv 
\frac{1}{2^n} \sum_{k=0}^{2^n-1} e^{-\frac{2\pi ik}{2^n}(x-2^n \theta) } =
 \frac{1}{2^{n}}  \sum_{k=0}^{2^n - 1} e^{-\frac{2\pi i k}{2^n} \left ( x-a \right )} e^{2 \pi i \delta k},</math>where we wrote <math>2^n \theta = a + 2^n \delta,</math> with <math>a</math> is the nearest integer to <math>2^n \theta</math>. The difference <math>2^n\delta</math>  must by definition satisfy <math>0 \leqslant |2^n\delta| \leqslant \tfrac{1}{2}</math>. This amounts to approximating the value of <math>\theta \in [0, 1]</math> by rounding <math>2^n \theta</math> to the nearest integer.

=== Measurement ===
The final step involves performing a [measurement](/source/Measurement_in_quantum_mechanics) in the computational basis on the first register. This yields the outcome <math> |y\rangle </math> with probability<math display="block">\Pr(y) = |c_y|^2 =  \left| \frac{1}{2^{n}} \sum_{k=0}^{2^n-1} e^{\frac{-2\pi i k}{2^n}(y-a)} e^{2 \pi i \delta k} \right |^2.
</math> It follows that <math>\operatorname{Pr}(a)=1</math> if <math>\delta=0</math>, that is, when <math>\theta</math> can be written as <math>\theta=a/2^n</math>, one always finds the outcome <math>y=a</math>. On the other hand, if <math>\delta\neq0</math>, the probability reads<math display="block">\operatorname{Pr}(a)=\frac{1}{2^{2n}} \left | \sum_{k=0}^{2^n-1} e^{2 \pi i \delta k} \right |^2 = \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right|^2.
</math> From this expression we can see that <math>\Pr(a) \geqslant \frac{4}{\pi^2} \approx 0.405</math> when <math>\delta\neq0</math>. To see this, we observe that from the definition of <math>\delta</math> we have the inequality <math>|\delta| \leqslant \tfrac{1}{2^{n+1}}</math>, and thus:<ref name="benet">{{cite book|last1=Benenti|first1=Guiliano|last2=Casati|first2=Giulio|last3=Strini|first3=Giuliano|title=Principles of quantum computation and information|date=2004|publisher=World Scientific| location=New Jersey [u.a.]|isbn=978-9812388582|edition=Reprinted.}}</ref>{{rp|157}}<ref name="ekert">{{cite journal| last1=Cleve| first1=R.| last2=Ekert |first2=A. |last3=Macchiavello| first3=C.| last4=Mosca|first4=M.|title=Quantum algorithms revisited|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences|date=8 January 1998| volume=454| issue=1969| pages=339–354|doi=10.1098/rspa.1998.0164|arxiv=quant-ph/9708016|bibcode=1998RSPSA.454..339C| s2cid=16128238}}</ref>{{rp|348}}<math display="block">\begin{align} 
\Pr(a) &=  \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right |^2 && \text{for } \delta \neq 0 \\ 
&= \frac{1}{2^{2n}} \left | \frac{2 \sin \left ( \pi 2^n \delta\right)}{ 2\sin( \pi \delta)} \right |^2 && \left| 1-e^{2ix}\right|^2 = 4\left| \sin (x)\right|^2 \\ 
&= \frac{1}{2^{2n}}  \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \sin( \pi \delta) |^2} \\ 
&\geqslant \frac{1}{2^{2n}}  \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \pi \delta |^2} && | \sin(\pi \delta) | \leqslant | \pi \delta | \\
&\geqslant \frac{1}{2^{2n}}  \frac {|2 \cdot 2^n \delta|^2}{| \pi \delta |^2} &&  | 2\cdot2^n \delta | \leqslant | \sin(\pi 2^n\delta) |  \text{ for }  |\delta| \leqslant \frac{1}{2^{n+1}} \\ 
&\geqslant \frac {4}{\pi^2} 
.\end{align}</math>

We conclude that the algorithm provides the best <math>n</math>-bit estimate (i.e., one that is within <math>1/2^n</math> of the correct answer) of <math>\theta</math> with probability at least <math>4/\pi^2</math>. By adding a number of extra qubits on the order of <math>O(\log(1/\epsilon))</math> and truncating the extra qubits the probability can increase to <math>1 - \epsilon</math>.<ref name="ekert" />

== Toy examples ==
Consider the simplest possible instance of the algorithm, where only <math>n=1</math> qubit, on top of the qubits required to encode <math>|\psi\rangle</math>, is involved. Suppose the eigenvalue of <math>|\psi\rangle</math> reads <math>\lambda=e^{2\pi i \theta}</math>, <math>\theta\in[0,1)</math>. The first part of the algorithm generates the one-qubit state <math display="inline">|\phi\rangle\equiv \frac{1}{\sqrt2}(|0\rangle+\lambda |1\rangle)</math>. Applying the inverse QFT amounts in this case to applying a [Hadamard gate](/source/Hadamard_gate). The final outcome probabilities are thus <math>p_\pm = |\langle\pm|\phi\rangle|^2</math> where <math display="inline">|\pm\rangle\equiv\frac{1}{\sqrt2}(|0\rangle\pm|1\rangle)</math>, or more explicitly,<math display="block">p_\pm = \frac{|1\pm\lambda|^2}{4}
=\frac{1 \pm \cos(2\pi \theta)}{2}.</math> Suppose <math>\lambda=1</math>, meaning <math>|\phi\rangle=|+\rangle</math>. Then <math>p_+=1</math>, <math>p_-=0</math>, and we recover deterministically the precise value of <math>\lambda</math> from the measurement outcomes. The same applies if <math>\lambda=-1</math>.

If on the other hand <math>\lambda=e^{2\pi i/3}</math>, then <math>p_\pm = [1 \pm \cos(2\pi/3)]/2</math>, that is, <math>p_+=1/4</math> and <math>p_-=3/4</math>. In this case the result is not deterministic, but we still find the outcome <math>|-\rangle</math> as more likely, compatibly with the fact that <math>2/3</math> is closer to 1 than to 0.

More generally, if <math>\lambda=e^{2\pi i\theta}</math>, then <math>p_+\ge 1/2 </math> if and only if <math>|\theta|\le 1/4 </math>. This is consistent with the results above because in the cases <math>\lambda=\pm1</math>, corresponding to <math>\theta=0,1/2</math>, the phase is retrieved deterministically, and the other phases are retrieved with higher accuracy the closer they are to these two.

== See also ==
* [Shor's algorithm](/source/Shor's_algorithm)
* [Quantum counting algorithm](/source/Quantum_counting)
* [Parity measurement](/source/Parity_measurement)

==References==
{{Reflist}}

{{Quantum information}}
{{DEFAULTSORT:Quantum Phase Estimation Algorithm}}
Category:Quantum algorithms

---
Adapted from the Wikipedia article [Quantum phase estimation algorithm](https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.