Monte Carlo graph search for quantum circuit optimization

The building blocks of quantum algorithms and software are quantum gates, with the appropriate combination of quantum gates leading to a desired quantum circuit. Deep expert knowledge is necessary to discover effective combinations of quantum gates to achieve a desired quantum algorithm for solving a specific task. This is especially challenging for quantum machine learning and signal processing. For example, it is not trivial to design a quantum Fourier transform from scratch. This work proposes a quantum architecture search algorithm which is based on a Monte Carlo graph search and measures of importance sampling. It is applicable to the optimization of gate order for both discrete gates and gates containing continuous variables. Several numerical experiments demonstrate the applicability of the proposed method for the automatic discovery of quantum circuits.

Figure 1

Example graph of quantum circuits. The edges are labeled by possible elementary gates. The vertices are identified with the unitary operator built by taking the product of the gates along the shortest path. A trajectory on this graph directly corresponds to a quantum circuit.

Figure 2

Example graph of quantum circuits. The purpose of this visualization is to demonstrate the high degree of connectivity and the presence of multiple cycles in the generated quantum circuit graph. A large number of the cycles emerge from commuting local quantum gates. As products of gates are taken to build the unitary matrix representing the quantum circuit, one encounters a graph structure which is rapidly branching and merging. This branching and cycle structure indicates that the MCGS will likely supply superior performance relative to MCTS.

Figure 3

Basic steps of the MCGS quantum circuit optimization algorithm. The currently implemented gates and their invocations are tabulated in the Appendix.

Figure 4

Simple example to visualize the basic steps for the optimization of quantum circuits involving continuous variables.

Figure 5

Number of required samples for quantum circuit optimization for differing circuit lengths. Compared are random sampling, a genetic algorithm, a particle filter, simulated annealing, and the proposed MCGS model. The bars depict the standard deviation. The diagram is illustrated with respect to a logarithmic $y$-axis scale. One observes in this way that the MCGS already requires an order of magnitude fewer samples than the four baselines. (Quantities plotted are dimensionless.)

Figure 6

Optimal circuit length versus the circuit length of different architecture search algorithms. (Quantities plotted are dimensionless.)

Figure 7

Concept for a classical cellular automaton as a target for a quantum circuit. In this case the $M_{30}$ automaton is targeted: The binary eight-dimensional input vector encodes the three-dimensional binary state using the one-hot encoding. A quantum circuit is searched for that, when applied to $|000\rangle$, produces the corresponding eight-dimensional vector according to the rule that if the probability is larger than zero (or a small threshold), the bit is set to 1 and is otherwise set to 0.

Figure 8

Optimized quantum circuits for the wine, zoo, and iris datasets. (Images have been generated using quantum composer [48].)