Quantum State Preparation via Free Binary Decision Diagram

Quantum state preparation (QSP) is a fundamental task in quantum computation to prepare a quantum state for a given classical description of the quantum state. The classical description of an n-qubit quantum state may have (O (n) ) parameters in general, which are inherently inefficient to deal with in the worst case; however, in many practical cases, we may be able to employ suitable data structures to represent such large-scale data in a compressed way, e. g. , by using a free binary decision diagram (FBDD), a rooted directed acyclic graph with two terminal nodes to concisely represent a Boolean function. We here construct a quantum algorithm for QSP when the classical description of a quantum state is given by an FBDD with weighted edges, and analyze the space, and time complexity of QSP in this setting. We provide a nontrivial example of an n-qubit state that can be represented by a weighted FBDD with N=O (poly (n) ) nodes rather than exp (O (n) ). We show that any quantum state represented by the weighted FBDD with N nodes can be prepared by an O (N) -sized quantum circuit using N ancillary qubits, exponentially improving the required circuit size for QSP compared to other BDD-based QSPs. We also provide another example of an n-qubit state that can be represented by a weighted FBDD with N=O (n²) nodes, and O (n²) ancillary qubits, but cannot be prepared efficiently by a QSP based on the amplitude amplification. These results provide techniques to employ FBDDs as a tool for broadening the possibility of efficient QSP.