We develop a purely functional quantum circuit simulator that represents quantum circuits by composing circuits inductively with quantum gates as basic circuits. We devise a straightforward denotational-semantics based simulator where we employ canonical polyadic tensor decompositions to represent quantum states.

We develop general efficiently run-time implementable rank reductions based on tensor algebra equalities to represent quantum states compactly on low-entanglement circuits. We show that the states encountered during conventional circuit encodings of Quantum Fourier Transform (QFT) on base vectors and Grover’s algorithm with phase coded single-solution oracles are kept at their theoretical constant-bounded rank (ranks 1 and 2, respectively). We illustrate that this results in simulation of these circuits that exhibits practically and asymptotically superior performance on QFT circuits compared to both state vector (exponential speed-up) and matrix-product state (linear speed-up) based simulators.

These results suggest that symbolic tensor state representations harbor a large design space for efficient quantum program simulation that automatically adapts to the degree of entanglement by judiciously exploiting tensor algebra equalities of monoidal categories at run time.