# Illustration of importance sampling for GHZ states

The script [PurityImportanceSampling](PurityImportanceSampling.py) shows how to access the purity $p_2=\mathrm{Tr}(\rho^2)$ based on importance sampling of randomized Measurements [link to the paper](https://arxiv.org/pdf/2102.13524.pdf). 


### Description of the experimental situation
In this example we consider an experiment where we would like to implement a large $N$-qubit GHZ state
\begin{equation}
|\mathrm{GHZ}\rangle = \frac{1}{\sqrt{2}}\left(|0\dots 0\rangle + |1\dots 1\rangle \right)
\end{equation}
However, due to decoherence, we realize instead a mixed-state of the form
\begin{equation}
\rho = (1-p)|\mathrm{GHZ}\rangle \langle \mathrm{GHZ}| + p \mathbb{1}/2^N
\end{equation}
We would like here to measure the purity $p_2$ of the state $\rho$. 

### Measurement protocol with importance sampling of randomized measurements
The script is based on randomized measurements. The purity can be expressed as an average over randomized measurements
\begin{equation}
p_2=\int X(u) du \quad \mathrm{with}  \quad X(u) = 2^N\sum_{s,s'} (-2)^{-D[s,s']} P_u(s) P_u(s')
\end{equation}
with $P_u(s)=\langle s |u \rho u^\dagger |s \rangle$ measurements in the computational basis.  Each CUE local random unitary  $u = \otimes_i u_i = \otimes_i R_y(\theta_i)R_z(\phi_i)$ is made of single qubit gates.

In order to reduce the required number of measuremens, we can use importance sampling and sample unitaries non-uniformly. As we know that the state $\rho$ is closed to the pure state state $|\mathrm{GHZ}\rangle$, which was targeted, we can define a probability distribution
\begin{equation}
p_\mathrm{IS}(u) = \frac{|X_\mathrm{GHZ}(u)|}{\int |X_\mathrm{GHZ}(u)|} du \quad \mathrm{with} 
\quad
X_\mathrm{GHZ}(u)=2^N\sum_{s,s'} (-2)^{-D[s,s']} P^{\mathrm{GHZ}}_u(s) P^\mathrm{GHZ}_u(s')
\end{equation}
where the probabilities $P^\mathrm{GHZ}_u(s)=|\langle s u|\mathrm{GHZ}\rangle|^2$ can be calculated easily. Then the protocol consists first in sampling unitaries $u$ according to $p_\mathrm{IS}(u)$ from a Metropolis algorithm (before the experiment takes place).
where the probabilities $P_\mathrm{GHZ}(s)=|\langle s |u\mathrm{GHZ}\rangle|^2$ can be calculated easily. The protocol consists first then in sampling unitaries $u$ according to $p_\mathrm{IS}(u)$ from a Metropolis algorithm (before the experiment takes place).

These single qubit unitaries are then applied on the quantum computer on the state $\rho$. One measures for each unitary $u^{(r)}$ $N_M$ bistrings $\{s_m^{(r)}\}$ and access an estimation of $X(u)$ via 
\begin{equation}
X_e(u^{(r)}) = \frac{2^N}{N_M(N_M-1)}
    \sum_{m \neq m'} (-2) ^{-D[s_m^{(r)},s^{(r)}_{m'}]}
\end{equation}
We obtain the purity of the state $\rho$ based on the formula
\begin{equation}
[p_2]_\mathrm{IS} = \frac{ 1}{N_s}
    \sum_{r = 1}^{N_u} \frac{n^{(r)} X_e(u^{(r)}) }{p_\mathrm{IS}(u^{(r)})}
\end{equation}
 where $N_s$ is the total number of unitaries $u$ collected by the metropolis algorithm which contains $N_u$ distinct ones and $n^{(r)}$ takes into account the occurence of each of unitary $u^{(r)}$ of the $N_u$ distinct samples and satisfies $N_s=\sum_r n^{(r)}$.
 
 ### Example
 with $N=16$, $N_M=10\times 2^{16}$, $N_u=100$, $p=0.25$, the script returns for three different simulated experiments

Run 1----

p2 (uniform sampling) =  0.6197747395756498

p2 (Importance sampling) =  0.5633602285126839

Error uniform:  10.18 %

Error IS:  0.15 %

Run 2----

p2 (uniform sampling) =  0.5684924515878843

p2 (Importance sampling) =  0.5665709762430637

Error uniform:  1.06 %

Error IS:  0.72 %

Run 3----

p2 (uniform sampling) =  0.3738835630369831

p2 (Importance sampling) =  0.5560702642126601

Error uniform:  33.53 %

Error IS:  1.14 %

 



```python

```

3109ce9e86ba9ca0087069f9755b73db58d9679c
ipynb
Jupyter Notebook
TutorialImportanceSampling.ipynb
bvermersch/RandomMeas
e2029afe10afa7c2c5ba819463a3f880698a520e
Apache-2.0
2021-02-03T15:55:14.000Z
2022-02-22T11:01:34.000Z
TutorialImportanceSampling.ipynb
bvermersch/RandomMeas
e2029afe10afa7c2c5ba819463a3f880698a520e
Apache-2.0
TutorialImportanceSampling.ipynb
bvermersch/RandomMeas
e2029afe10afa7c2c5ba819463a3f880698a520e
Apache-2.0
2022-01-18T18:38:27.000Z
2022-01-20T04:07:15.000Z
Qwen/Qwen-72B
1. YES
2. YES