# Error rate vs Fidelity (Part 1): Unveil the mathematics behind quantum error rate

In the article of Bernsterin-Vazirani implementation, I’ve addressed one of the most crucial challenges of quantum computing. The field is yet to flourish because quantum gates aren’t constructed to be good enough. One major difference of quantum gates versus classical counterparts is that quantum gates have to be reversible, which means we’re able to retrieve a prior state of a qubit without loss of information. Scientists are now on their way to establish a proper scheme for building decent quantum gates. To be able to evaluate how good the gates are, several methods in determining error rates of quantum gates have been proposed, Quantum State Tomography and Randomized Benchmarking to name a few. To talk about these methods requires us some concrete understanding of the mathematical concept of quantum error rate and other related metrics. Error rate and fidelity, the two most essential notions, and their practical role will be our focus throughout this series. Due to being a topic of quantum computing theory, the analysis might be mathematically heavy.

#### Threshold theorem

As I don’t want to mesh up with your mind that early, so I’ll keep everything simple here. Essentially, the theorem demonstates that there exists a threshold error rate $\eta_0$ such that if a quantum computer has its average gate error rate $\eta < \eta_0$, the quantum computer can perform quantum computations efficiently with polylogarithm overhead.

#### The error rate of quantum gates

For deterministic processes, an error occurs when the result the process produces differs from the expected, correct outcome. However, there is no unique correct outcome in a random process like quantum computation. So, we define the error rate for a random process by comparing the realistically calculated result statistics to the ideal statistics.

For an error-free process there comes a probability distribution $p_{i}$ over the set of possible outcomes $X$. Processes subject to error results in a different distribution $p_{a}$ of actual outcomes. For any output $x \in X$, the corresponding ideal and actual probabilities of $x$ are $p_{i}(x)$ and $p_{a} (x)$ respectively. The total variation distance when the set $X$ is countable and finite is defined as
$$\delta (p_{a},p_{i}) = \frac{1}{2} \left \| p_{a} - p_{i} \right \|_1 = \frac{1}{2} \sum_{x \in X} |p_{a}(x) - p_{i}(x)|$$
Here’s the reason why the total distance variation can be interpreted equivalently to the error rate. We can sample the random process $N$ times and count the number $n(x)$ of occurences of each possible outcome $x$ in order to come up with an estimate of $p_a$: The fraction $n(x)/N$ approaches $p_a(x)$ as N approaches infinity. By changing a fraction of $r$ samples out of $N$, we can be able to adjust the distribution probability that $n’(x)/N \approx p_i(x)$ rather than $p_a(x)$. The value of $r$ is not unique, but the minimum $r_{min}$ must be greater than zero for sufficiently large $N$ if $p_a \neq p_i$. It’s proven that as $N \rightarrow \infty$, $r_{min} \rightarrow \delta (p_{a},p_{i})$. In other words, the total variation distance $\delta (p_{a},p_{i})$ is an approximation of $r_{min}$, which is the number of alteration (or the number of error correction) we made on our samples, to ensure that each outcome match the ideal distribution $p_i$.

TL;DR: $\delta (p_{a},p_{i})$ is approximately equal to the number of error in the random process.

###### Translated into the quantum language

First I want to give credit to the work of ‘Fuchs and van de Graff’ on the proof that the error rate of quantum states is determined by the trace distance between the quantum states, and the work of ‘Kitaev’ showing that trace norm can be extended to quantum channels through diamond norm $d_{\diamond}$.

I’m gonna write out a few standards for next steps later. Suppose we’re working on a quantum register that is a collection of $n$ qubits in $d = 2^n$ dimensional Hilbert space $\mathscr{H}$. $\mathscr{H}$ is canonically isomorphic with the n-fold tensor product of a single qubit’s Hilbert space, so $H \cong \left(\mathbb{C}^2\right)^{\otimes n}$.

While an ideal state in the system above is represented by a unit vector $\psi \in \mathscr{H}$, a realistc state is described by density operator $\rho \in \mathscr{H}$. A measurement of a quantum state as a density operator associates with the most general formulation of quantum measurement, a *Positive Operator-Valued Measure* (POVM). POVM shares some similarity with Projection-Valued Measure (PVM), which is the usual projective measurement scheme. In simple words, POVM to PVM is what a density matrix to a pure state. However, POVM only determines the probability (non-negative) of different outcomes while ignoring the postmeasurement state of the system. A POVM $\{E_m\}$ is a set of Hermitian positive semidefinite operators on $\mathscr{H}$ that sum to the identity operator $I$: $\sum_m E_m = I$.

For a state $\rho$, no matters whether it’s pure or mixed, the probability of obtaining the result labelled $m$ is $\text{Pr}(m) = \text{Tr}(E_m \rho)$, with $\sum_m \text{Pr}(m) = 1$. Therefore, it’s convenient to compare the ideal output $\rho_i$ to the actual outout $\rho_a$ with respect to some POVM. Following from the bottom line in the last section is the formula for evaluating quantum error rate: $\delta (\rho_{a},\rho_{i})$, where $\rho_{a} (m) = \text{Tr}(E_m \rho_{a})$ and $\rho_{i} (m) = \text{Tr}(E_m \rho_{i})$.

After maximizing $\delta (\rho_{a},\rho_{i})$ over all possible POVM choices, we get $$\Delta (\rho_{a},\rho_{i}) := \frac{1}{2} \| \rho_{a} -\rho_{i}\|_{\text{Tr}}$$ with $\|A\|_{\text{Tr}} := \text{Tr}\sqrt{A^{\dagger}A}$ for any linear operator $A$. From all the preceding, we can say $\Delta (\rho_{a},\rho_{i})$ is the error rate of the realistic outcome $\rho_a$. All of the above gives us the definition of the error rate of the output that results from a quantum logic gate. That’s really close to the error rate of the gate itself.

###### The error rate of quantum gates

The action of an ideal quantum gate $G$ acting upon a mixed state $\rho$ is a map:
$$\rho \mapsto G\rho G^{\dagger}$$
We define a quantum channel $\mathfrak{G}_{i}(\rho) := G\rho G^{\dagger}$ to explicitly describe the ideal action. Another quantum channel for the actual, errorneous employment of $G$, $\mathfrak{G}_{a}$ (just a letter ‘G’ in some convoluted script font, I’m sorry I can’t find a better font for my purpose), is also a map that is completely positive, trace-preserving on the space of density operators over $\mathscr{H}$, but not described unitary conjugation as $\mathfrak{G}_{i}$. Here we utilize the formula for the error rate of outcomes and employ it for evaluating the error rate of gates, given input state $\rho$:
$$\Delta \left(\mathfrak{G}_{a}(\rho),\mathfrak{G}_{i}(\rho) \right)$$.
It’s necessary to maximize $\Delta (\mathfrak{G}_{a}(\rho),\mathfrak{G}_{i})(\rho)$ over all possible inputs $\rho$ to find out the error rate of the realistic channel with respect to the ideal channel. In short, the desired calculation is
$$\underset{\rho}{\text{max }}\Delta \left(\mathfrak{G}_{a}(\rho),\mathfrak{G}_{i}(\rho) \right)$$
However the established formula becomes invalid because the error rate of $\mathfrak{G}_{a} \otimes \mathbb{I}$ ($\mathbb{I}$ is an identity matrix corresponding to the space of ancillary qubits $\mathscr{H’}$) differs from the error rate of $\mathfrak{G}_{a}$ in general. This is where *diamond norm* comes to correct the previous maximization by expanding it to the spaces of both input and ancillary qubits.
$$\|\mathfrak{A}\|_{\diamond} := \underset{\mathscr{H’}}{\text{sup}} \underset{\rho \in \text{ dens. op.}(\mathscr{H} \otimes \mathscr{H’})}{\text{sup}} \left \| \mathfrak{A} \otimes \mathbb{1} (\rho) \right\|_{\text{Tr}},$$
where $\mathfrak{A}$ is an arbitrary superoperator over $\mathscr{H}$, and the set of density operators over the joint space $\mathscr{H} \otimes \mathscr{H’}$. This gives us convenience to define to define the gate error rate $\eta$ via diamond norm as
$$\eta = \Delta_{\diamond} \left(\mathfrak{G}_{a},\mathfrak{G}_{i} \right) := \frac{1}{2} \|\mathfrak{G}_{a} - \mathfrak{G}_{i}\|_{\diamond}$$

The other side of this series, fidelity, will be discussed in the next part along with the dichotomy between gate error rate and gate fidelity.