<jupyter_start><jupyter_text>prepared by <NAME> (QTurkey)                 This cell contains some macros. If there is a problem with displaying mathematical formulas, please run this cell to load these macros. $ \newcommand{\bra}[1]{\langle 1|} $$ \newcommand{\ket}[1]{|1\rangle} $$ \newcommand{\braket}[2]{\langle 1|2\rangle} $$ \newcommand{\dot}[2]{ 1 \cdot 2} $$ \newcommand{\biginner}[2]{\left\langle 1,2\right\rangle} $$ \newcommand{\mymatrix}[2]{\left( \begin{array}{1} 2\end{array} \right)} $$ \newcommand{\myvector}[1]{\mymatrix{c}{1}} $$ \newcommand{\myrvector}[1]{\mymatrix{r}{1}} $$ \newcommand{\mypar}[1]{\left( 1 \right)} $$ \newcommand{\mybigpar}[1]{ \Big( 1 \Big)} $$ \newcommand{\sqrttwo}{\frac{1}{\sqrt{2}}} $$ \newcommand{\dsqrttwo}{\dfrac{1}{\sqrt{2}}} $$ \newcommand{\onehalf}{\frac{1}{2}} $$ \newcommand{\donehalf}{\dfrac{1}{2}} $$ \newcommand{\hadamard}{ \mymatrix{rr}{ \sqrttwo & \sqrttwo \\ \sqrttwo & -\sqrttwo }} $$ \newcommand{\vzero}{\myvector{1\\0}} $$ \newcommand{\vone}{\myvector{0\\1}} $$ \newcommand{\stateplus}{\myvector{ \sqrttwo \\  \sqrttwo } } $$ \newcommand{\stateminus}{ \myrvector{ \sqrttwo \\ -\sqrttwo } } $$ \newcommand{\myarray}[2]{ \begin{array}{1}2\end{array}} $$ \newcommand{\X}{ \mymatrix{cc}{0 & 1 \\ 1 & 0}  } $$ \newcommand{\Z}{ \mymatrix{rr}{1 & 0 \\ 0 & -1}  } $$ \newcommand{\Htwo}{ \mymatrix{rrrr}{ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} & \frac{1}{2} } } $$ \newcommand{\CNOT}{ \mymatrix{cccc}{1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0} } $$ \newcommand{\norm}[1]{ \left\lVert 1 \right\rVert } $$ \newcommand{\pstate}[1]{ \lceil \mspace{-1mu} 1 \mspace{-1.5mu} \rfloor } $  Phase Estimation  In this section we will talk about an application of Quantum Fourier Transform, which will lead us in the way to Shor's Algorithm. Suppose that unitary operator $ U $ has an eigenvector (eigenstate) $\ket{\psi}$ with eigenvalue $ e^{2{\pi}i{\phi}} $where ${\phi}$ is unknown, that is, $U\ket{\psi}$ = $ e^{2{\pi}i{\phi}}$ $\ket{\psi} $. Our goal is to estimate ${\phi}$. Remarks:    - $ v $ is an eigenvector for matrix $ A  $ with eigenvalue $ \lambda $ if $Av = {\lambda}v$. - When $ U $ is a unitary operator, then all of its eigenvalues have length 1 and can be expressed in the form $ e^{2{\pi}i{\phi}}$ where $\phi$ is between 0 and 1. - One can define power of the operator $ U $, $ U^k $ for some $ k $. In that case, check that  $U^k \ket{\psi} = e^{2\pi i \phi k}\ket{\psi}$ Task 1 (on paper)Show that $\ket{-}$ and $\ket{+}$ are eigenvectors for the $X$ operator with eigenvalues -1 and 1 respectively. click for our solution  Some observations  Let $ U $ be a unitary operator with eigenstate $ \ket{\psi} $ and eigenvalue $ e^{2\pi i \phi} $ such that $ U\ket{\psi} =  e^{2{\pi}i{\phi}} \ket{\psi}$. Let's check the effect of controlled-$ U $ ($CU$) operator on a two qubit system where second qubit is set to $ \ket{\psi} $. In general, for any unitary operator $U$ with $U \ket{\psi} = e^{2\pi i \phi}\ket{\psi}$, and its controlled version $CU$ the following is true. $$ CU(\ket{0}\ket{\psi}) \rightarrow \ket{0}\ket{\psi} ~~\mbox{   and   }~~ CU(\ket{1}\ket{\psi}) \rightarrow  e^{2{\pi}i{\phi}}\ket{1}\ket{\psi} $$  $ CU $ operator puts a phase of $ e^{2\pi i \phi} $ in front of state $ \ket{1} $ when the first qubit is in superposition of the states $ \ket{0} $ and $ \ket{1} $. $$ CU~\left (\frac {\ket{0} + \ket{1}} {\sqrt{2}}\ket{\psi} \right ) \rightarrow\frac {\ket{0} + e^{2{\pi}i{\phi}} \ket{1}} {\sqrt{2}}\ket{\psi} $$ Hence, for an arbitrary state, $\alpha \ket{0}\ket{\psi} + \beta \ket{1}\ket{\psi} \xrightarrow{CU} \alpha \ket{0}\ket{\psi} ~+~ e^{2{\pi}i{\phi}}  \beta \ket{1}\ket{\psi} = (\alpha \ket{0} ~+~ e^{2{\pi}i{\phi}} \beta \ket{1})\ket{\psi}$.  Task 2Consider the following quantum state where $ x=0 $ or $ 1 $. How can you find out the value of $x$ by applying a single operator?$$ \frac {\ket{0} + (-1)^x \ket{1}} {\sqrt{2}}$$ click for our solution  Estimating eigenvalues of the $X$ operator  Recall that $ \ket{+} $ and $ \ket{-} $ are the eigenstates of the operator $X$. If we apply $ CX $ operator to the following quantum state where $ \ket{\psi} $ is either $ \ket{+} $ or $ \ket{-} $, then by Task 2 we know how to find out the value of $x$.\begin{align*}CX \left(\frac {\ket{0} + \ket{1}} {\sqrt{2}} \ket{\psi} \right) \rightarrow \frac {\ket{0} + (-1)^x \ket{1}} {\sqrt{2}}\ket{\psi}\end{align*} Note that this is a special case of the phase estimation problem where we are trying to estimate eigenvalues of the operator $ X $. In this case, $ \phi $ is either $ 0 $ or $ \frac{1}{2} $ which can be determined by an Hadamard operator. Next we will see how to accomplish this in general. AlgorithmWe need two registers where first register contains $ t $ qubits which are in state $ \ket{0} $. $ t $ depends on the number of digits of accuracy and the probability of success while estimating $ \phi $. We will come to details of $ t $ later on. Suppose that the qubits in the first register are numbered from 1 to $ t $. Second register stores $ \ket{\psi} $. Suppose that we are given controlled $ U^{2^j} $ operators as black-box functions.  - Apply Hadamard to first register. The new quantum state is     $\frac {1}{2^{t/2}} \bigl (\ket{0}+\ket{1}\bigr ) \otimes \cdots \otimes  \bigl (\ket{0}+\ket{1}\bigr)\ket{\psi}.$      - Apply $CU^{2^j}$ gate where qubit $t-j$ is the control for $j = 0, \dots ,t-1$.    - $j=0$   , Apply $CU^{2^0}$ where qubit $t$ is the control qubit.      $ \frac {1}{2^{t/2}}\bigl (\ket{0}+\ket{1}\bigr ) \otimes  \cdots \otimes \bigl (\ket{0}+\ket{1}\bigr ) \otimes \bigl(\ket{0}+ {} e^{2{\pi}i\phi 2^0}\ket{1}\bigr )\ket{\psi} $            - $j=1$   , Apply $CU^{2^1}$ where qubit $t-1$ is the control qubit.      $\frac {1}{2^{t/2}}\bigl (\ket{0}+\ket{1} \bigr )\otimes \cdots \otimes \bigl(\ket{0}+ e^{2\pi i \phi 2^1}\ket{1}\bigr ) \otimes \bigl (\ket{0}+ e^{2\pi i\phi 2^0}\ket{1} \bigr )\ket{\psi}$    - $\cdots$        - $j=t - 1$   ,  Apply $CU^{2^{t-1}}$ where qubit $1$ is the control qubit      $\frac {1}{2^{t/2}}\bigl (\ket{0}+e^{2\pi i \phi 2^{t-1}}\ket{1}\bigr ) \otimes\cdots \otimes \bigl(\ket{0}+ {} e^{2{\pi}i\phi 2^1}\ket{1} \bigr) \otimes \bigl(\ket{0}+ e^{2\pi i \phi 2^0}\ket{1}\bigr)\ket{\psi}$      We have succussfully encoded $\phi$ into the phase of state $\ket{1}$ for each one of the $t$ qubits in the first register. Now let's express the above state in a different formulation. \begin{align*}&\frac {1}{2^{t/2}}\bigotimes_{l=1}^{t}\bigl(\ket{0}+e^{2{\pi}i{\phi}2^{t-l}}\ket{1} \bigr)\ket{\psi}\\=&\frac {1}{2^{t/2}}\bigotimes_{l=1}^{t}\sum_{k_l=0}^{1}e^{2{\pi}i k_l {\phi}2^{t-1}}\ket{k_l}\ket{\psi} \\=&\frac {1}{2^{t/2}}\sum_{k_1=0}^{1}\cdots\sum_{k_t=0}^{1}e^{2{\pi}i\sum_{1=1}^{t}k_l2^{t-l}	\phi} \ket{k_1 \dots k_t} \ket{\psi} \\   =&\frac {1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}e^{2{\pi}i k{\phi}}\ket{k}\ket{\psi}\end{align*} - If $\phi$ is of the form $\frac{x}{N}$ for some $ x $ and $ N=2^t $ or equivalently if $ \phi $ can be expressed using exactly $ t $ bits as $$    \phi= 0.\phi_1 \dots \phi_t = \frac{\phi_1 \dots \phi_t}{N},$$ then we can reexpress the state of first register as $$    \frac {1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}e^{\frac{2{\pi}i k{x}}{N}}\ket{k}.$$ Recall the $QFT$ of a basis state $\ket{j}$: $$     \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1}e^{\frac{2\pi i j k }{N}} \ket{k}.$$ Hence after applying $QFT^{\dagger}$ to the first register, we exactly measure $\ket{x}\ket{\psi}=\ket{\phi_1 \dots \phi_t}{\ket{\psi}}$. This can be easily seen as the expression we have obtained is the state obtained after applying $QFT$ to the state $ \ket{x} $. - If not, then choosing $ t = n + \left \lceil \log \left (2 + \frac{1}{2\varepsilon} \right) \right \rceil $, we can still approximate $\phi$ accurate to $ n $ bits with probability of success at least $1 - \epsilon$. As we know how to implement $QFT^{\dagger}$ efficiently, we have obtained an efficient algorithm for phase estimation as well. Many interesting problems reduce to phase estimation problem.  Here is the circuit for overall representation for phase estimation algorithm. Remarks- Need $O(t^2)$ operations and $t$ calls to $CU^{2^j}$ blackbox.- If you take any arbitrary state instead of $\ket{\psi}$, then you obtain an approximation to one of the eigenvalues with some probability. The reason behind is that you can express any quantum state as the linear combination of the eigenvectors.<jupyter_code>from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, Aer, execute
from qiskit.circuit.library import PhaseGate
from math import pi

qasm_simulator = Aer.get_backend('qasm_simulator')<jupyter_output><empty_output><jupyter_text>>  Using gates from 'qiskit.circuit.library'>> Using the default methods of `QuantumCircuit` is not the only way of applying a gate in qiskit. `qiskit.circuit.library` provides a wide range of quantum gates that can be used with the `apply` method of `QuantumCircuits`.>> ```python> from qiskit.circuit.library import CPhaseGate>>  Construct the gate> my_phase_ate = CPhaseGate(pi/2)> >  Apply it to the 1st and 3rd qubits of>  some circuit> qubits = [0, 2]> circuit.append(my_phase_ate, qubits)> circuit.draw()> ```>> ``` > > q_0: ─■───────>       │       > q_1: ─┼───────>       │P(π/2) > q_2: ─■───────>```  Task 3Consider the unitary operator $U$ with eigenvector $\ket{1}$ and eigenvalue $e^{2\pi i \phi}$ where $\phi = \frac{5}{16}$. $CU$ operator can be realized via a `PhaseGate` gate. Pick $t=4$ and implement the phase estimation circuit to estimate $\phi$. Write a function named qpe which takes as parameters t, control qubits, target qubits, circuit and the operator CU.Note that you will get an exact result since $t=4$ is precise enough. _Remarks:_- You can apply arithmetical operations to gates, such as taking powers or inverses. - To apply $QFT^{\dagger}$, you can use the function `iQFT` from our `silver` module. Create a `iQFT` operator by providing the number of qubits, and apply it like any other gate provided by `qiskit.circuit.library`.- To create a controlled $U^{2^k}$ gate from any $U$ in `qiskit.circuit.library`, you can use the `CUPowFactory` function in our module.              ──────■────── ┌───┐        ┌────┴────┐ ─┤ U ├─  to  ─┤ U^(2^k) ├─ └───┘        └─────────┘<jupyter_code>from silver import CUPowFactory

CPhasePowGate = CUPowFactory(PhaseGate(2*pi*5/16)) # Do not forget the 2π factor
from silver import iQFT
def qpe(circuit, CU, control, target):
    
    # Your code here
    pass
CONTROL_QUBIT_NUM = 4

# Create a cirucit
circuit = QuantumCircuit(
    control_register   := QuantumRegister(CONTROL_QUBIT_NUM),
    target_register    := QuantumRegister(1),
    classical_register := ClassicalRegister(CONTROL_QUBIT_NUM),
)

# Set target qubit to store eigenvector

# Apply QPE

# Mesaure and print the results
    
# Select the maximum outcome as the current estimation<jupyter_output><empty_output><jupyter_text>click for our solution Task 4Try Task 3 this time by setting $t=3$. What do you expect to see?<jupyter_code>CONTROL_QUBIT_NUM = 3

# Create a cirucit
circuit = QuantumCircuit(
    control_register   := QuantumRegister(CONTROL_QUBIT_NUM),
    target_register    := QuantumRegister(1),
    classical_register := ClassicalRegister(CONTROL_QUBIT_NUM),
)

# Set target qubit to store eigenvector

# Apply QPE

# Mesaure and print the results

# Select the maximum outcome as the current estimation<jupyter_output><empty_output><jupyter_text>click for our solution Task 5Try Task 3 this time by setting $\phi=0.685$. Calculate and print the estimates for different $t$ values between 1 and 10.<jupyter_code># Create CU operator with phase 0.685
CPhasePowGate = CUPowFactory(PhaseGate(2*pi*0.685)) # Do not forget the 2π factor
for t in range (1,10):
    
    # Create a cirucit
    circuit = QuantumCircuit(
        control_register   := QuantumRegister(t),
        target_register    := QuantumRegister(1),
        classical_register := ClassicalRegister(t),
    )
    
    # Set target qubit to store eigenvector
    
    # Apply QPE
    
    # Mesaure and print the results
    
    # Select the maximum outcome as the current estimation<jupyter_output><empty_output><jupyter_text>click for our solution Task 6You are given an operator $U$ with eigenvector $\ket{11}$ and eigenvalue $\phi$, which is this time unknown to you. Use phase estimation to estimate $\phi$ by trying different $t$ values. Run the following cell to load operator $U$<jupyter_code>from silver import CUPowFactory
from silver.phaseEstimation import U

misteryGate = CUPowFactory(U)
for t in range (1,10):
    
    # Create a cirucit
    circuit = QuantumCircuit(
        control_register   := QuantumRegister(t),
        target_register    := QuantumRegister(2),
        classical_register := ClassicalRegister(t),
    )
    
    # Set target qubit to store eigenvector
    
    # Apply QPE
    
    # Mesaure and print the results
    
    # Select the maximum outcome as the current estimation<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17785994566857832, 'fraction_numerical': 0.02618472683368548, 'mean_word_length': 3.724777183600713, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 47, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '373267', 'license': 'Apache-2.0', 'n_tokens_mistral': 4643, 'n_tokens_neox': 4361, 'n_words': 1503, 'path': 'silver/D03_Phase_Estimation.ipynb', 'repo_name': 'kurabirko/silver-phys437', 'size': '13258'}