SC20 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Logic Formulas as Program Abstractions for Quantum Circuits: A Case Study in Noisy Variational Algorithm Simulation


Workshop:First International Workshop on Quantum Computing Software

Authors: Yipeng Huang (Rutgers University); Steven Holtzen, Todd Millstein, and Guy Van den Broeck (University of California, Los Angeles (UCLA)); and Margaret Martonosi (Princeton University)


Abstract: Existing quantum circuit simulators do not address the traits of variational algorithms, namely:

1) their ability to work with noisy qubits and operations, 2) their repeated execution of the same circuits but with different parameters, and 3) the fact that they sample from circuit final wavefunctions to drive optimization routines.

Our key insight is that knowledge compilation—a technique for efficient repeated inference originating in AI research—can be generalized to work on complex-valued quantum amplitudes, such that the technique serves as the basis for a quantum circuit simulation toolchain geared for variational quantum algorithms. In knowledge compilation, AI models such as Bayesian networks encode probabilistic knowledge about the world in a factorized format. The Bayesian networks compile down to minimized logical formulas that enable repeated inference and sampling queries with different parameters and new pieces of evidence. The features of the knowledge compilation approach—namely,

1) the ability to represent probabilistic information, 2) the ability to compile probabilistic model structural information into minimized formats, and 3) the ability to efficiently sample from the same model but for varying parameters and evidence—match the requirements for variational quantum algorithm simulation.

Our approach offers performance advantages relative to simulation approaches based on state vectors, density matrices, and tensor networks. The advantages are due to the more compact representation, the circuit minimization and memoization capabilities of our approach, and due to the storage costs for conventional simulators based on matrix representations. The improved simulation performance facilitates studying variational algorithms in the NISQ era of quantum computing.





Back to First International Workshop on Quantum Computing Software Archive Listing



Back to Full Workshop Archive Listing