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.

==Notation==

* <math>U</math>: Model circuit
* <math>U'</math>: Implementation of the model circuit by the quantum transpiler
* <math>m</math>: width of the model circuit
* <math>d</math>: depth of the model circuit
* <math>F_{avg}(U, U')</math>: Average fidelity between <math>U</math> and <math>U'</math>
* <math>\epsilon</math>: approximation error
* <math>d(m)</math>: Achievable depth, which is 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>
* <math>V_Q</math>: Quantum Volume
* <math>H_U</math>: Set of heavy outputs for a model circuit <math>U</math>
* <math>x</math>: Outcome of executing <math>U'</math>, which is a observable bit string, <math>x \in \{0,1\}^m</math>
* <math>p_U(x)</math>: Ideal output distribution for <math>U</math>. <math>p_U(x) = |\langle x|U|0\rangle|^2</math>
* <math>p_{med}</math>: median of the set of probabilities
* <math>n_c</math>: Number of repetitions, <math>n_c>100</math>
* <math>n_s</math>: Number of repetitions

==Hardware Requirements==

* Quantum Computing device with a gate set
* Measurement device

==Properties==

* '''Figure of merit''': Quantum Volume
* Quantum computing systems with high-fidelity operations, high connectivity, large calibrated gate sets, and circuit rewriting tool chains are expected to have higher quantum volumes
* The protocol can be implemented with any universal programmable quantum computing device
* The method used to compute the heavy outputs from the ideal output distribution of the model circuit scales exponentially with the width <math>m</math>.
* Ideally, the probability of observing a heavy output would be estimated using all of the qubits of a large device, but NISQ devices have appreciable error rates, so we begin with small model circuits and progress to larger ones.
* 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.
* Given a model circuit <math>U</math>, a circuit-to-circuit transpiler finds an implementation <math>U'</math> for the target system such that <math>1- F_{avg}(U, U') \leq \epsilon \ll 1</math>

==Protocol Description==

'''Function''': ComputeHeavyOutputs<math>(U, m)</math>

'''Input''': <math>U, m</math>

'''Output''': <math>H_U</math>

* Obtain <math>p_U(x)</math> for <math>x \in \{0,1\}^m</math>
* Sort in ascending order <math>p_0 \leq p_1 ... \leq p_{2^m -1}</math>
* <math>p_{med}  = (p_{2^{m-1}} + p_{2^{m-1}-1})/2 </math>
* <math>H_U = \{x\in \{0,1\}^m</math> such that <math>p_U(x) > p_{med}\}</math>


'''Function''': ComputeQuantumVolume

'''Output''': Figure of merit: Quantum Volume, <math>V_Q</math>

* For <math>i = 1, 2, ..., m</math>:
** For <math>j = 1, 2, ..., d</math>:
*** <math>d(m) = 0</math>
*** <math>n_h = 0</math>
*** For <math>k = 1, 2, ..., n_c</math>:
**** Pick random model circuit <math>U</math>
**** <math>H_U =</math> ComputeHeavyOutputs<math>(U, m)</math>
**** Compile <math>U'</math>
**** For <math>l = 1, 2, ..., n_s</math>:
***** Get output <math>x</math>
***** If <math>x\in H_U</math> then <math>n_h = n_h + 1</math>
*** If <math>\frac{n_h-2\sqrt{n_h(n_s-n_h/n_c)}}{n_c n_S} > \frac{2}{3}</math>
**** <math>d(m) = </math>max<math>(d(m), d)</math>
**** Store data <math>(m, d(m))</math>
* Calculate <math>V_Q</math> from stored data, where log<math>_2 V_Q</math> = argmax<math>_m</math> min<math>(m, d(m))</math>

==Further Information==

== Related Papers ==
* Andrew W. Cross et al (2011) arXiv:1811.12926v3: Validating quantum computers using randomized model circuits

<div style='text-align: right;'>''*contributed by Rhea Parekh''</div>