User:Neospace125/sandbox

In the near era, there are several applications and adaptation of technology, especially, a computer and a computational technology. A development of these technologies are separated but they have the same destination. That is, how to improve an efficiency of computation ? In a scientific way, there are two significant ways, classical algorithm and quantum algorithm. In this article, we consider a quantum algorithm directly.

Quantum supremacy via Random circuit sampling

There was a promise of quantum computer since Richard P. Feynman said "A quantum computer might be exponentially better than a classical computer in a solving problems in physics and chemistry". Given this statement, A physicist and a computer scientist use more times to characterize a super algorithm that demonstrates a task to solve a computational problem in a quantum way. That is, a physicist tries to use quantum information theory together with quantum mechanics principles to demonstrate a better algorithm than classical algorithms immediately.

Literally, a quantum supremacy or quantum advantage, first announced by John Preskill, is a task to state that a quantum algorithm conquers a classical algorithm. That is, no classical algorithm can solve a problem without a quantum algorithm that we demonstrated. Here is the definition of quantum supremacy defined by John Preskill,

Definition of quantum supremacy

Quantum supremacy is a goal to find a problem that a quantum algorithm is better than every classical algorithms. A quantum computer is said to be better than classical computer for solving some problems whenever we can show that some parameters in quantum computer is better than classical computer (or algorithm).

One famous scenario is a use of quantum circuit. That is, a random circuit sampling (see also. ). Usually denote as $C$. From the definition, that is, we have to compare some parameters between quantum and classical.

Random circuit sampling

From the previous section, We already had a great tool to study quantum physics so - called quantum circuit, a circuit which has an input as a quantum state instead of classical bits, namely, qubits. A quantum circuit is represented by a unitary quantum gate using to operate an input state for each Hilbert space. We can graphically represent a quantum circuit like a classical circuit. Commonly, a random quantum circuit is a quantum circuit that randomly draws a unitary quantum gate from a gates set.

In this section, we will describe a task of a random circuit sampling. a random circuit chooses gates from a gates set and then applies them to register states.

In general, we fix a size of quantum circuit follow registers. For a circuit size $n$ ($n$ - qubits register). That is, A quantum system in $2^{n}$ dimensional Hilbert space $H^{\otimes n}$, we can denote a circuit family use in this circuit as $C_{n}$. Now we can demonstrate a task of random circuit sampling (quantum version) using this scenario directly,

Task : Random circuit sampling

Suppose the classical sample space $\Omega$ consists of the possible measurement outcomes of any quantum circuit $C$ with a fixed size $n$ which is chosen from a circuit family $C_{n}$ with the output distribution $p(C)$. The initial state of a circuit is $|0\rangle$. Hence, the probability of an outcome $x\in \Omega$, where $x$ is bitstrings with a length $n$,

$P_{C}(|x\rangle )=|\langle x|C|0\rangle |^{2}$

where $C$ is a circuit or the other name, unitary operator in a circuit. However, we can obtain this task more general. That is, set an initial state as an arbitrary state $|\psi \rangle$.

From above task, we may familiarized ourselves with a notation of circuit as a quantum gate. That is, a unitary operator $U$.

In term of quantum supremacy protocol, we have demonstrated a new assumption of random quantum circuit. From a task above, we can sketch a random quantum circuit from a uniform sampling of unitary operators. Hence, we may write a subscription of probability in a task in form $P_{U}(|\psi \rangle )$.

How to characterize a supremacy via random circuit sampling ?

There are several methods for characterizing a quantum supremacy. One of the most famous method is a cross entropy benchmarking via random circuit sampling method. In this section, we will dive into a demonstrating quantum supremacy step by step.

Characterized parameters

In the first step, we have to denote parameters to use in this consideration. From the previous task we demonstrated, we have to construct two algorithms. That is, one is a quantum algorithm and other classical algorithms.

From a task of random circuit sampling , we can construct a quantum algorithm generally by considering an initial state as $|\psi _{0}\rangle$ which is always evolved by a random unitary operator $U$. That is, $|\psi \rangle =U|\psi _{0}\rangle$. Set an attempt to set up a random circuit sampling generally; sample bitstrings like in a task. Then, denote a probability $P_{C}(|x\rangle )$ for each classical bitstrings. From a task, a quantum circuit has $n$ copy of qubits. Hence, we obtain a set of bitstrings $S=\{x_{1},x_{2},x_{3},...,x_{n}\}$. A nature of non - correlated quantum systems, independent Hilbert space, the bitstrings are exactly independent random variables. Hence, we can obtain a probability for a sample $S$ as follow,

$Pr(S)=\prod _{x\in S}|\langle x|\psi \rangle |^{2}=\prod _{x\in S}P_{U}(|x\rangle )$

This probability is a probability of measurement outcomes via quantum algorithms. That is, a classical algorithms we can do the same but in a classical way. Roughly speaking, obtain a state $|\psi _{cl}\rangle$ and a random unitary operator $U_{cl}$ from a classical simulation. So, $|\psi _{cl}\rangle =U_{cl}|\psi _{0,cl}\rangle$. Since we can obtain a set of bitstrings, classically we can obtain $S_{cl}=\{x_{1}^{cl},x_{2}^{cl},...,x_{n}^{cl}\}$. On the same way of considering probability, we obtain,

$Pr(S_{cl})=\prod _{x^{cl}\in S_{cl}}|\langle x^{cl}|\psi \rangle |^{2}$

Now, we have two probabilities of the outcomes of two difference version of algorithms. The fact of a quantum circuit is that a state space of a circuit is exponential in $n$. Thus, a perfect simulation in classical computer is a hard problem to solve. Hence, we assume a complexity of classical algorithm is polynomial in $n$. More clearly, the sample $S_{cl}$ is drawn from an approximation of the actual quantum circuit that does not scale appropriately as we increase the number of qubits exponentially.

The intuition is that what will happen if we obtain the sample $S_{cl}$ if we already had a perfect representation of the circuit's output state $|\psi \rangle$ ? This probability of measurement outcome is obtained by computing $|\langle x^{cl}|\psi \rangle |$, where $|\psi \rangle$ represents the perfect output state.

Hence, we can directly compare a probability $Pr(S_{cl})$ to the probability $Pr(S)$.

Now, from research article of Sergio Boixo , they obtain an equation to quantify a comparing of these two probabilities as follow,

$E_{U}[{\frac {Pr(S)}{Pr(S_{cl})}}]\approx e^{me^{-rg}}$ where $m$ is a number of sampled bitstrings and $E_{U}$ is an expectation value taken over an ensemble of random unitary operators which drawn effectively from the Haar measure. And, $r$ is an estimate of the effective per-gate error rate, $g\propto nd$ is the total number of gates where $d$ is a circuit depth. These parameters told us that why this formula can achieve a quantum supremacy themselves.

This equation told us that if a quantum algorithm has per - gate error rate low enough and perform the sampling experiments described above for a large set of random unitary operator $\{U_{\alpha }\}$, there exist an expectation value that $E_{U}[\log Pr(S)-\log Pr(S_{cl})]\approx m$. That is, this equation checks an (algorithm) efficiency between quantum algorithm and classical algorithm that we provided. Then we have to approximate a probability by using the Porter - Thomas distribution. Denote the probability density function $F(p)$ over the continuous variable $p=p(x)=|\langle x|\psi \rangle |^{2}$ for some state $|\psi \rangle$ obtained from a circuit, then,

$F(p)=Ne^{-Np}$

Hence, we got the expectation value in form of continuous variable,

$E[p(x)]=\int dp\ pNe^{-Np}$

You can see a full derive of Porter - Thomas distribution in and this is a sketch of proof,

A sketch of proof of Porter - Thomas distribution

• Write down a random wavefunction in Hilbert space $H$ in computational basis,

$|\psi \rangle =\sum _{x}(a_{x}+ib_{x})|x\rangle$

where the normalization condition is $\sum _{x}a_{x}^{2}+b_{x}^{2}=1$

• Count the number of normalized states with $p(x_{0})=a_{x_{0}}^{2}+b_{x_{0}}^{2}$ and consider a volume of Hilbert space where a state of volume satisfies only the number of normalized states and the normalization condition.

• Follow above condition, we can consider a subspace of Hilbert space via overall Hilbert space; the volume of the space of normalized states with $p(x)=a_{x_{0}}^{2}+b_{x_{0}}^{2}$ and dividing by the volume of the subspace with only normalized states. This give us a probability density function $F(p)$. Hence $F(p)={\frac {Vol(H_{p,1})}{Vol(H_{1})}}$

where $H_{p,1}$ is the subspace with normalized states of probability $p$ and $H_{1}$ is the subspace of normalized states.

• Compute integral form of these two volumes,

$Vol(H_{p,1})=\int _{-\infty }^{\infty }\prod _{x}da_{x}db_{x}\delta (\sum _{x}(a_{x}^{2}+b_{x}^{2}-1))\delta (a_{x_{0}}^{2}+b_{x_{0}}^{2}-p)$ $Vol(H_{p,1})=\int _{-\infty }^{\infty }\prod _{x}da_{x}db_{x}\delta (\sum _{x}(a_{x}^{2}+b_{x}^{2}-1))$

• Then, we got volumes,

$Vol(H_{1})={\frac {\pi ^{N}}{(N-1)!}}$

$Vol(H_{p,1})={\frac {\pi ^{N}}{(N-2)!}}(1-p)^{N-2}$

• Hence, we got a probability density function,

$F(p)=(N-1)(1-p)^{N-2}$

• Limit a large $N$, we finally got an approximation,

$F(p)\rightarrow Ne^{-Np}$

This is a form of Porter - Thomas distribution.

Then, a way to derive the expectation value we presented above is to use a property which called asymptotic equipartition property.

Asymptotic equipartition property

There is an exact definition of this property. We will describe below,

Definition of Asymptotic equipartition property

For any $\epsilon >0$, a set of bitstrings $S$ of size $m$ is epsilon - typical if holds :

$|-{\frac {1}{m}}\log Pr(S)-H(p(x))|<\epsilon$

where $H(p(x))$ is the information entropy.

However, there is another theorem in use for a proof,

Theorem

Let $\mathrm {E} _{n,\epsilon }$ denote the set of all $S$ (a set of samples) that are epsilon - typical. Then for all $\epsilon >0$, we have,

$P(S\in \mathrm {E} _{n,\epsilon })\rightarrow 1\ {\text{as}}\ m\rightarrow \infty$

where $P(S\in \mathrm {E} _{n,\epsilon })$ is the probability that $S$ is contained in the epsilon - typical set.

Use these scenarios we then obtain that,

$\log Pr(S)\approx -mH(p)$

For large $N$, the entropy can be evaluate into a form,

$H(p(x))=-\sum _{j=1}^{N}p(x_{j})\log p(x_{j})=-N\int _{0}^{\infty }dpNpe^{-Np}\log p$

That is,

$E_{U}[\log Pr(S)]=\log Pr(S)=-m(\log N-1+\gamma )$

where $\gamma$ is Euler's constant.

Then, we dive to a classical sampling, we will claim a useful definition and another theorem to evaluate it.

Definition

For any $\epsilon >0$, a set of bitstrings $S_{cl}$ of size $m$ is cross epsilon - typical (use the same name which denoted in ) if holds:

$|-{\frac {1}{m}}\log Pr(S_{cl})-H(p_{cl},p)|\leq \epsilon$

where $H(p_{cl},p)$ is the cross entropy, defined by:

$H(p_{cl},p)=-\sum _{j=1}^{N}p_{cl}(x_{j})\log p(x_{j})$

Similar like a quantum case, we first obtain,

Theorem

Let $C_{n,\epsilon }$ denote the set of all $S_{cl}$ that are cross epsilon - typical. Then for all $\epsilon >0$, obtain as follow,

$P(S_{cl}\in C_{n,\epsilon })\rightarrow 1\ {\text{as}}\ n\rightarrow \infty$

where $P(S_{cl}\in C_{n,\epsilon })$ is the probability that $S_{cl}$ is contained in the cross epsilon - typical set.

Again, use these scenarios to evaluate $E_{U}[\log Pr(S_{cl})]$. We obtain that,

$E_{U}[\log Pr(S_{cl})]=-m(\log N+\gamma )$

These results easily obtain a formula of quantum supremacy protocol we described above. Next, we will demonstrate quantum supremacy via these scenarios.

Characterized quantum supremacy

One of the most famous quantum supremacy benchmarking is cross entropy benchmarking. Suppose a classical algorithm has outputs from a uniform distribution over all bitstrings. That is, $P_{cl}(x_{j})={\frac {1}{N}}$. From a cross entropy benchmarking, we can directly consider this compare with a random quantum circuit in quantum algorithms,

$H=-\sum _{j=1}^{N}{\frac {1}{N}}\log p(x_{j})=-{\frac {1}{N}}N\int _{0}^{\infty }dpNe^{-Np}\log p=\log N+\gamma$

A comparison of algorithms we used in this scenario has to have a rigorous perfect sample. We have to suppose an algorithm $A$ with outputs distribution $p_{A}$ which we are testing and the outputs distribution $p$ for ideal outputs distribution Using the cross entropy difference.

$\Delta H(p_{A})=H-H(p_{A},p)$

Hence, we can write down a new form of cross entropy difference using formulas from above,

$\Delta H(p_{A})=\sum _{j=1}^{N}(p_{A}(x_{j})-{\frac {1}{N}})\log p(x_{j})$

If we consider a worst case of algorithm $A$,then the outputs distribution is $p_{A}={\frac {1}{N}}$ (uniform distribution). That is, we obtain $\Delta H=0$. However, the best case scenario can be easily verified, $p_{A}=p$. This case will give a result of cross entropy difference as $\Delta H=1$.<rev name = ":3" />

This scenario is called cross entropy benchmarking because two algorithms can be compared directly by this scenario and can be claimed which algorithm is better. Hence, if we suppose the best classical algorithm as $p^{*}$ then we use this scenario to compare with a quantum algorithm. That is, if a quantum algorithm is better than the best algorithm using this criteria, we can declare that this quantum algorithm is better than classical algorithm. The quantum supremacy is completed. However, in a mathematical term, we have to suppose the outputs distribution of a quantum algorithm as $p_{Q}$ and then compute the cross entropy difference of this outputs distribution and repeat this computation. After more enough, compute this parameter,

$\alpha =E_{U}[\Delta H(p_{Q})]$

Finally, we suppose an expectation value of the best possible classical algorithm $C=E_{U}[\Delta H(p^{*})]$. Quantum supremacy is completely achieved when,

$1\geq \alpha >C$

This is only one scenario of quantum supremacy protocol we recent use in quantum information and quantum computing research area.