Quantum_phase_estimation_algorithm Knowpia

In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, 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 in 1995.^[1]^[2]^: 246

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm,^[2]^: 131 the quantum algorithm for linear systems of equations, and the quantum counting algorithm.

Formal description of the problem edit

Let $U$ be a unitary operator acting on an $m$ -qubit register. Unitarity implies that all the eigenvalues of $U$ have unit modulus, and can therefore be characterized by their phase. Thus if $|\psi \rangle$ is an eigenvector of $U$ , then $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle$ for some $\theta \in \mathbb {R}$ . Due to the periodicity of the complex exponential, we can always assume $0\leq \theta <1$ .

Our goal is to find a good approximation to $\theta$ with a small number of gates and with high probability. The quantum phase estimation algorithm achieves this under the assumptions of having oracular access to $U$ , and having $|\psi \rangle$ available as a quantum state.

More precisely, the algorithm returns an approximation for $\theta$ , with high probability within additive error $\varepsilon$ , using $O(\log(1/\varepsilon ))$ qubits (without counting the ones used to encode the eigenvector state) and $O(1/\varepsilon )$ controlled-U operations. Furthermore, we can improve the success probability to $1-\Delta$ for any $\Delta >0$ by using a total of $O(\log(1/\Delta )/\varepsilon )$ uses of controlled-U, and this is optimal.^[3]

The algorithm edit

The circuit for quantum phase estimation.

Setup edit

The input consists of two registers (namely, two parts): the upper $n$ qubits comprise the first register, and the lower $m$ qubits are the second register.

The initial state of the system is:

|0\rangle ^{\otimes n}|\psi \rangle .

After applying n-bit Hadamard gate operation $H^{\otimes n}$ on the first register, the state becomes:

{\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

.

Let $U$ be a unitary operator with eigenvector $|\psi \rangle$ such that $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$ . Thus,

U^{2^{j}}|\psi \rangle =e^{2\pi i2^{j}\theta }|\psi \rangle

.

Overall, the transformation implemented on the two registers by the controlled gates applying $U,U^{2},U^{2^{2}},\ldots ,U^{2^{n-1}}$ is

|k\rangle |\psi \rangle \mapsto |k\rangle U^{k}|\psi \rangle

This can be seen by the decomposition of

k

into its bitstring

k_{n-1}k_{n-2}\ldots k_{1}k_{0}

and binary representation

2^{n-1}k_{n-1}+2^{n-2}k_{n-2}+\ldots +2k_{1}+k_{0}

, where

k_{n-1},\ldots ,k_{1},k_{0}\in \{0,1\}

. Clearly,

U^{k}

becomes

U^{2^{n-1}k_{n-1}+\ldots +2^{2}k_{2}+2k_{1}+k_{0}}=U^{2^{n-1}k_{n-1}}\ldots U^{2^{2}k_{2}}U^{2k_{1}}U^{k_{0}}

Each

U^{2^{j}k_{j}}

will only apply if the qubit

k_{j}

is

1

, implying that it is controlled by that bit. Therefore the overall transformation to

|k\rangle U^{k}|\psi \rangle

is equivalent to the controlled

U^{2^{j}}

gates from each

j

-th qubit.

Therefore, the state will be transformed by the controlled $U^{2^{j}}$ gates like so:

{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle |\psi \rangle

At this point, the second register with the eigenvector is not needed. It can be reused again in another run of phase estimation. The state without

|\psi \rangle

is

${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle$

Apply inverse quantum Fourier transform edit

Applying the inverse quantum Fourier transform on

{\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle

yields

{\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 ikx}{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 ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .

We can approximate the value of $\theta \in [0,1]$ by rounding $2^{n}\theta$ to the nearest integer. This means that $2^{n}\theta =a+2^{n}\delta ,$ where $a$ is the nearest integer to $2^{n}\theta ,$ and the difference $2^{n}\delta$ satisfies $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$ .

Using this decomposition we can rewrite the state as ${\textstyle \sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$ where

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 ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}.

Measurement edit

Performing a measurement in the computational basis on the first register yields the outcome $|y\rangle$ with probability

\Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.

It follows that

\operatorname {Pr} (a)=1

if

\delta =0

, that is, when

\theta

can be written as

\theta =a/2^{n}

, one always finds the outcome

y=a

. On the other hand, if

\delta \neq 0

, the probability reads

\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 i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.

From this expression we can see that

\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405

when

\delta \neq 0

. To see this, we observe that from the definition of

\delta

we have the inequality

|\delta |\leqslant {\tfrac {1}{2^{n+1}}}

, and thus:^[4]^: 157^[5]^: 348

{\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\[6pt]&={\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}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\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 |\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}

We conclude that the algorithm provides the best $n$ -bit estimate (i.e., one that is within $1/2^{n}$ of the correct answer) of $\theta$ with probability at least $4/\pi ^{2}$ . By adding a number of extra qubits on the order of $O(\log(1/\epsilon ))$ and truncating the extra qubits the probability can increase to $1-\epsilon$ .^[5]

Toy examples edit

Consider the simplest possible instance of the algorithm, where only $n=1$ qubit, on top of the qubits required to encode $|\psi \rangle$ , is involved. Suppose the eigenvalue of $|\psi \rangle$ reads $\lambda =e^{2\pi i\theta }$ . The first part of the algorithm generates the one-qubit state ${\textstyle |\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )}$ . Applying the inverse QFT amounts in this case to applying a Hadamard gate. The final outcome probabilities are thus $p_{\pm }=|\langle \pm |\phi \rangle |^{2}$ where ${\textstyle |\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )}$ , or more explicitly,

p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.

Suppose

\lambda =1

, meaning

|\phi \rangle =|+\rangle

. Then

p_{+}=1

,

p_{-}=0

, and we recover deterministically the precise value of

\lambda

from the measurement outcomes. The same applies if

\lambda =-1

.

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

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

References edit

^ Kitaev, A. Yu (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.
^ ^a ^b Nielsen, Michael A. & Isaac L. Chuang (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035.
^ Mande, Nikhil S.; Ronald de Wolf (2023). "Tight Bounds for Quantum Phase Estimation and Related Problems". arXiv:2305.04908 [quant-ph].
^ Benenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN 978-9812388582.
^ ^a ^b Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 January 1998). "Quantum algorithms revisited". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969): 339–354. arXiv:quant-ph/9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098/rspa.1998.0164. S2CID 16128238.

[kitaev-1] Kitaev, A. Yu (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.

[nielchuan-2] Nielsen, Michael A. & Isaac L. Chuang (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035.

[optimality-3] Mande, Nikhil S.; Ronald de Wolf (2023). "Tight Bounds for Quantum Phase Estimation and Related Problems". arXiv:2305.04908 [quant-ph].

[benet-4] Benenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN 978-9812388582.

[ekert-5] Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 January 1998). "Quantum algorithms revisited". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969): 339–354. arXiv:quant-ph/9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098/rspa.1998.0164. S2CID 16128238.

[1]

[2]

[3]

[4]

[5]

Summary