Quantum computation capability verification protocol for noisy intermediate-scale quantum devices with the dihedral coset problem

In this article, we propose an interactive protocol for one party (the verifier) holding a quantum computer to verify the quantum computation power of another party's (the prover) device via a one-way quantum channel. This protocol is referred to as the dihedral coset problem (DCP) challenge. The verifier needs to prepare quantum states encoding secrets (DCP samples) and send them to the prover. The prover is then tasked with recovering those secrets with a certain accuracy. Numerical simulation demonstrates that this accuracy is sensitive to errors in quantum hardware. Additionally, the DCP challenge serves as a benchmarking protocol for locally fully connected quantum architecture and aims to be performed on current and near-future quantum resources. We conduct a 4-qubit experiment on one of the IBM Q devices.

Figure 1

A toy circuit for $m=2$, $n=3$, and $s=2$. The first four qubits correspond to the state when $x=0$, $|{\psi }_{0,2}\rangle =|0\rangle |000\rangle +|1\rangle |010\rangle$ and the second four qubits correspond to the state $x=2$, $|{\psi }_{2,2}\rangle =|0\rangle |010\rangle +|1\rangle |100\rangle$. The collision after QFT with ${\widehat{x}}_1=3$ and $\widehat{x_2}=7$ is chosen randomly.

Figure 2

A toy circuit for $m=2$, $n=3$, and $s=3$, first four qubits correspond to the state when $x=2$, $|{\psi }_{2,3}\rangle =|0\rangle |010\rangle +|1\rangle |101\rangle$ and the second four qubits correspond to the state $x=3$, $|{\psi }_{3,3}\rangle =|0\rangle |011\rangle +|1\rangle |110\rangle$. The collision after QFT with ${\widehat{x}}_1=6$ and $\widehat{x_2}=2$ is chosen randomly.

Figure 3

A toy circuit for the measurement method for $n=3$.

Figure 4

The DCP challenge in a diagram.

Figure 5

Combinations of $m$ and $n$ that we can have $p_{\mathrm{upper}}-p_B>g$ with a $t<25$ are plotted in blue (darker). These three figures show the situation of a small gap $g=0\%$, a medium gap $g=10\%$, and a big gap $g=25\%$ for less than 1600 qubits. (a) Smallest instance: $m=6$, $n=4$, $t=1$ with $p_B=66.05\%$ and $p_{\mathrm{upper}}=66.40\%$. (b) Smallest instance: $m=9$, $n=6$, $t=4$ with $p_B=71.64\%$ and $p_{\mathrm{upper}}=81.73\%$. and (c) Smallest instance: $m=21$, $n=9$, $t=9$ with $p_B=65.45\%$ and $p_{\mathrm{upper}}=90.66\%$.

Figure 6

Normalized probability distribution of ${\mathbf{p}}_{\mathrm{clean}}$ and ${\mathbf{p}}_{\mathrm{Hbasis}}$ over 100 trials, plotted with normal distribution $\mathcal{N}(\overline{{\mathbf{p}}_{\mathrm{clean}}},{\sigma }_{{\mathbf{p}}_{\mathrm{clean}}})$ and $\mathcal{N}(\overline{{\mathbf{p}}_{\mathrm{Hbasis}}},{\sigma }_{{\mathbf{p}}_{\mathrm{Hbasis}}})$.

Figure 7

Normalized probability distribution of ${\mathbf{p}}_{\mathrm{clean}}$ and ${\mathbf{p}}_{\mathrm{error}}$ over 100 trials, plotted with normal distribution $\mathcal{N}(\overline{{\mathbf{p}}_{\mathrm{clean}}},{\sigma }_{{\mathbf{p}}_{\mathrm{clean}}})$ and $\mathcal{N}(\overline{{\mathbf{p}}_{\mathrm{error}}},{\sigma }_{{\mathbf{p}}_{\mathrm{error}}})$.

Figure 8

Eight possible cases for two DCP samples of $n=1$. (a) Case A, with $s=0$, $x_0=0$ and $x_1=0$. (b) Case B, with $s=0$, $x_0=0$ and $x_1=1$. (c) Case C, with $s=0$, $x_0=1$ and $x_1=0$. (d) Case D, with $s=0$, $x_0=1$ and $x_1=1$. (e) Case E, with $s=1$, $x_0=0$ and $x_1=0$. (f) Case F, with $s=1$, $x_0=0$ and $x_1=1$. (g) Case G, with $s=1$, $x_0=1$ and $x_1=0$. and (h) Case H, with $s=1$, $x_0=1$ and $x_1=1$.

Figure 9

Normalized probability distribution of ${\mathbf{p}}_{\mathrm{clean}}$ and ${\mathbf{p}}_{\mathrm{IBM}}$ (reconstructed from experimental data) over 100 trials, plotted with normal distribution $\mathcal{N}(\overline{{\mathbf{p}}_{\mathrm{clean}}},{\sigma }_{{\mathbf{p}}_{\mathrm{clean}}})$ and $\mathcal{N}(\overline{{\mathbf{p}}_{\mathrm{IBM}}},{\sigma }_{{\mathbf{p}}_{\mathrm{IBM}}})$. The accuracy ${\mathbf{p}}_{\mathrm{IBM}}$ is very close to ${\mathbf{p}}_{\mathrm{clean}}$. A larger $r$ is needed to distinguish them. The quantum device is considered promising.