Quantum State Preparation via Efficiently Represented Boolean Function

Abstract

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 exp(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(n2) nodes, and O(n2) 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.