Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy

Instantaneous quantum polynomial time (IQP) is a model of (probably) nonuniversal quantum computation. Since it has been proven that IQP circuits are unlikely to be simulated classically up to a multiplicative error and an error in the $l_1$ norm, IQP is considered as one of the promising classes that demonstrates quantum supremacy. Although IQP circuits can be realized more easily than a universal quantum computer, demonstrating quantum supremacy is still difficult. It is therefore desired to find subclasses of IQP that are easy to implement. In this paper, by imposing some restrictions on IQP, we propose ancilla-driven IQP (ADIQP) as the subclass of commuting quantum computation suitable for many experimental settings. We show that even though ADIQP circuits are strictly weaker than IQP circuits in a sense, they are also hard to simulate classically up to a multiplicative error and an error in the $l_1$ norm. Moreover, the properties of ADIQP make it easy to investigate the verifiability of ADIQP circuits and the difficulties in realizing ADIQP circuits.

Figure 1

The general IQP circuit. Each of the meter symbols represents the measurement in the $Z$ basis.

Figure 2

The general ADIQP circuit. $U_{\mathrm{CZ}}$ is a quantum gate composed of $\mathrm{\Lambda }\left(Z\right)$, and $U_z^{\left(2\right)}={\mathrm{\Pi }}_{l=1}^{n_b}{T}_l^{d_l}{U}_{\mathrm{CZ}}(0\le d_l\le 7)$.

Figure 3

The ADIQP circuit in the case where the input register is the same as the output register. Here, $U_z^{\left(2\right)}=W_z^{\left(2\right)}\left(\right|0\rangle \langle 0|\otimes I^{\otimes (n-1)}+|1\rangle \langle 1|\otimes V_z^{\left(2\right)})$.

Figure 4

(a)–(d) The equalities used to show lemma t7. (a) Bridge operation. Here, $S\equiv Z(\pi /2)$. (b) This equality is used to remove $S$ in (a). (c) $T$ used in ADQC. (d) Hadamard gadget. (e)–(g) The quantum gates on white qubits. In all cases, 0 is output as each of the measurement outcomes with probability $1/2$. (e) $H^{\otimes 2}\mathrm{\Lambda }\left(Z\right)H^{\otimes 2}$. Three black qubits are used as an ancillary qubit. (f) $H$. Three black qubits and one white qubit are used as ancillary qubits. The output qubit is different from the input qubit. (g) $HTH$. Three black qubits and one white qubit are used as ancillary qubits.