Abstract:  The problem of simulating quantum circuits that appear in variational algorithms offers distinct opportunities, when compared to simulating other types of quantum circuits. We focus on exploiting three characteristics common in variational algorithm quantum circuits. These properties are 1. circuits in variational algorithms such as VQE and QAOA are often wide but shallow, 2. the algorithms run circuits with the same topology many times, with only differences in gate parameters between runs, 3. the variational algorithm expects the quantum computer or simulator to return samples from a multi-modal wavefunction, and not the full high-dimensional wavefunction. These traits make this type of circuit simulation a distinctive workload compared to simulating Shor's, Grover's, or even random circuit sampling workloads.

In this ongoing work, we use knowledge compilation on Bayesian networks to aid simulating variational quantum algorithms. Knowledge compilation is a set of techniques we borrow from classical AI inference, which had been useful for repeated inference on AI models with different parameters, and for efficient stochastic simulation of those inference models. Those tricks may be useful here for quantum circuit simulation.

The toolchain begins by converting quantum circuits to complex-valued Bayesian networks. This transformation has been established by prior work that use probabilistic graphical models and tensor network contraction for quantum circuit simulation. From this transformation, our work strikes out on a new pathway to do simulation. We convert the Bayesian networks to conjunctive normal forms, and finally to arithmetic circuits for inference. These minimized arithmetic circuits can be reused across multiple simulations with different parameters. Furthermore, the arithmetic circuits allow for more efficient sampling of measurement outcomes from the final wavefunction.

We experimentally validate our simulation toolchain using Google Cirq for its QAOA benchmark, its simulator test harnesses, and its native simulator as a baseline. We are able to beat the native simulator for QAOA problem sizes beyond 16 qubits, where the native simulator starts to struggle with longer wavefunction vectors. Our proposed approach appears to be limited in terms of depth to about 33 steps, where the size of the compiled topology becomes a limiting factor. In all, the approach may be useful in simulating this wide but shallow range of quantum circuits.