  Quantum computing is finding promising applications in optimization, machine
learning and physics, leading to the development of various models for
representing quantum information. Because these representations are often
studied in different contexts (many-body physics, machine learning, formal
verification, simulation), little is known about fundamental trade-offs between
their succinctness and the runtime of operations to update them. We therefore
analytically investigate three widely-used quantum state representations:
matrix product states (MPS), decision diagrams (DDs), and restricted Boltzmann
machines (RBMs). We map the relative succinctness of these data structures and
provide the complexity for relevant query and manipulation operations. Further,
to chart the balance between succinctness and operation efficiency, we extend
the concept of rapidity with support for the non-canonical data structures
studied in this work, showing in particular that MPS is at least as rapid as
some DDs.
  By providing a knowledge compilation map for quantum state representations,
this paper contributes to the understanding of the inherent time and space
efficiency trade-offs in this area.
