Quantum circuit synthesis via a random combinatorial search

We use a random search technique to find quantum gate sequences that implement perfect quantum state preparation or unitary operator synthesis with arbitrary targets. This approach is based on the recent discovery that there is a large multiplicity of quantum circuits that achieve unit fidelity in performing a given target operation, even at the minimum number of single-qubit and two-qubit gates needed to achieve unit fidelity. We show that the fraction of perfect-fidelity quantum circuits increases rapidly as soon as the circuit size exceeds the minimum circuit size required for achieving unit fidelity. This result implies that near-optimal quantum circuits for a variety of quantum information processing tasks can be identified relatively easily by trying only a few randomly chosen quantum circuits and optimizing their parameters. In addition to analyzing the case where the cnot gate is the elementary two-qubit gate, we consider the possibility of using alternative two-qubit gates. In particular, we analyze the case where the two-qubit gate is the $B$ gate, which is known to reduce the minimum quantum circuit size for two-qubit operations. We apply the random search method to the problem of decomposing the four-qubit Toffoli gate and find a 15-cnot-gate decomposition.

Figure 1

Probability $p$ that a random quantum circuit gives $F=1$ as a function of circuit size $N$ for the case of state preparation of an $n$-qubit system using the cnot gate as the entangling gate. The $F=1$ probability rises rapidly from zero to almost 1 even when $N$ corresponds to just a few gates more than the theoretical lower bound $N_{\mathrm{LB},\mathrm{SP},\mathrm{CNOT}}$. The error bars account for the uncertainty in inferring the probability $p$ from the fraction $p_{\mathrm{num}}$ obtained in the random sampling calculation.

Figure 2

Same as in Fig. 1, but for the case of unitary operator synthesis.

Figure 3

Threshold at which the success probability exceeds 50%. The different panels are identified by their legends: SP corresponds to state preparation, while U corresponds to unitary operator synthesis. Similarly, cnot corresponds to using the cnot gate, while B corresponds to using the $B$ gate, which is discussed in Sec. 3. The red circles show $N_{\mathrm{th}}-N_{\mathrm{LB}}$ ($y$ axis on the left-hand side), while the blue triangles show $(N_{\mathrm{th}}-N_{\mathrm{LB}})/N_{\mathrm{LB}}$ ($y$ axis on the right-hand side). In almost all cases, $(N_{\mathrm{th}}-N_{\mathrm{LB}})/N_{\mathrm{LB}}$ decreases with increasing $n$, which means that the ratio $N_{\mathrm{th}}/N_{\mathrm{LB}}$ gradually approaches 1, which means that in relative terms $N_{\mathrm{th}}$ approaches $N_{\mathrm{LB}}$ with increasing system size.

Figure 4

Maximum achievable fidelity $F$ as a function of the number of $B$ gates for state preparation with $n=2$ (red diamond), 3 (green circles), and 4 (blue squares). By comparing these results with those of Ref. [6], we can see that the $B$ gate allows achieving the same results as the cnot gate with smaller values of $N$. In the case of the cnot gate, $F=1$ is achieved for $N=1$, 3, and 6 instead of 1, 2, and 5, respectively.

Figure 5

Maximum achievable fidelity $F$ as a function of the number of $B$ gates for unitary operator synthesis with $n=2$ (red diamonds) and 3 (green circles). In the case of the cnot gate analyzed in Ref. [6], $F=1$ is achieved for $N=3$ and 14 instead of 2 and 9, respectively.

Figure 6

Same as in Fig. 1, but for the case where the $B$ gate is used as the entangling gate. The $B$ gate allows achieving the same results as the cnot gate with smaller values of $N$.

Figure 7

Same as in Fig. 2, but for the case where the $B$ gate is used as the entangling gate. The $B$ gate allows achieving the same results as the cnot gate with smaller values of $N$.

Figure 8

Maximum achievable fidelity $F$ as a function of the number of entangling (cnot or $B$) gates used to synthesize a four-qubit Toffoli gate. The green squares correspond to the results obtained in Ref. [6], where all possible cnot gate configurations were analyzed. The purple $\times$ symbols are obtained by analyzing all possible $B$ gate configurations. The red circles and blue $+$ symbols correspond to the random search approach for the cnot gate and $B$ gate, respectively. The four-qubit Toffoli gate can be perfectly synthesized using 15 cnot gates. Unlike what we found for the case of arbitrary $n$-qubit gate synthesis, the $B$ gate seems to be less efficient than the cnot gate in this case. At $N=20$, the $B$ gate gives $F=0.997$.

Figure 9

Histograms for the fidelity $F$ values for $N=20$ when using the cnot gate (red solid line) or the $B$ gate (blue dotted line) to synthesize a four-qubit Toffoli gate. The $y$-axis scale is not the same for the two curves. For the cnot gate there are special values of $F$ that dominate the distribution, while for the $B$ gate there is a continuous, broad distribution of $F$ values.