Editing Quantum Volume Estimation

[https://journals.aps.org/pra/abstract/10.1103/PhysRevA.100.032328 Quantum Volume (QV)] is a single-number metric that can be measured using a concrete protocol on near-term quantum computers of modest size. The QV method quantifies the largest random circuit of equal width and depth that the computer successfully implements. The quantum volume protocol is strongly related to gate error rate and is influenced by underlying qubit connectivity and gate parallelism. This protocol is based on the performance of random model circuits with a fixed but generic form.

'''Tags:''' [[Certification protocol]], [[Quantum Volume estimation protocol]]

==Assumptions==

* The transpiler is free to use all available tricks and hardware resources to implement the model circuit.
* The transpiler should make an honest attempt to implement the model circuit, and not merely choose a relatively simple operation far from the model circuit that nevertheless produces the heavy outputs for it.

==Outline==
The quantum volume protocol is strongly related to gate error rate and is influenced by underlying qubit connectivity and gate parallelism. This protocol is based on the performance of random model circuits with a fixed but generic form. 

A model circuit is consists of <math>d</math> layers of random permutations of the <math>m</math> different qubit labels, followed by random two-qubit gates. When the circuit width m is odd, one of the qubits is idle in each layer. Each two-qubit gate used in the previous step is sampled from the [[Haar measure on SU(4)]].

Heavy output generation problem is used to define if the model circuit mentioned above is fully implemented in practice. From the outputs of all the implementations of the model circuit, we get an ideal output distribution. From this, we get the set of output probabilities and we can obtain the median of this set. The heavy outputs are the outputs for which the output probability will be greater than the median of the set of probabilities. The heavy output generation problem is to produce a
set of output strings such that more than two-thirds are
heavy.

To evaluate heavy output generation, we implement model circuits using the gate set provided by the target system, using the available hardware. For this purpose, a quantum circuit-to-circuit transpiler is used, which finds an implementation of the model circuit, where the approximation error.

This method to compute the quantum volume of a device consists of the following steps:

* The Quantum transpiler tries to implement the model circuit such that the approximation error is limited. From here, we get the distribution for the implementation of the model circuit, which we use to calculate the probability of sampling a heavy output.
* The heavy outputs are also computed using the ideal output distribution of the model circuit.
* The probability of observing a heavy output by implementing a randomly selected depth <math>d</math> model circuit is also computed using the probability of sampling a heavy output computed in the step above.
* We define the achievable depth <math>d(m)</math> to be the largest <math>d</math> such that we are confident that the probability of observing a heavy output is greater than <math>2/3</math> (as the heavy output generation problem is to produce a set of output strings such that more than two-thirds are heavy.)
* The data of achievable depth is gathered by sweeping over values of width <math>m</math> and depth <math>d</math> of the model circuit.
* Using all the data gathered, the quantum volume is computed. The quantum volume treats the width and depth of a model circuit with equal importance and measures the largest square shaped (i.e., <math>m = d</math>) model circuit a quantum computer can implement successfully on average.