Open SSoelvsten opened 1 year ago
As highlighted in the paper "Automated Reasoning in Quantum Circuit Compilation" (SPIN 24), the idea of QMDDs is actually (almost) the same as an even older idea: Edge-valued Decision Diagrams (EVDDs). In fact, these are versions of multi-terminal decision diagrams ( #438 ) that are strictly smaller (with respect to the number of nodes).
Hence, we may want to actually have this in mind, and implement instead(ish).
Decision Diagrams can also be used to reason about quantum computation. Here, one makes use of a lot of matrix computation, where the matrix itself is quite sparse, i.e. it has a lot of entries being 0. With Quantum Multiple-valued Decision Diagram (QMDD) [Miller06] we have a compact and canonical representation of these complex-valued matrices.
Definition of a QMDD
The paper [Li22] provides a comprehensive definition of this type of decision diagram.
A QMDD is defined in relation to a radix r. Usually, the value of r is 2 and does not change throughout computation (i.e. it can just be a compile time constant).
The out-degree of a QMDD node is r2.
Each edge from one QMDD node to another is associated with a complex-valued number.
From hereon forward, let us just assume r = 2 since that makes thinking about it much easier. At each vertex, we are looking at a square matrix power-of-two matrix and choosing which of the four quadrants to go into. The weight on the edge reflects the complex-valued number needed to multiply to each of the submatrices.
Adding Support for QMDDs
To add QMDDs to Adiar, one has to follow similar steps as for MTBDDs ( #438 ) .
[ ] Template
ptr
ptr_uint64
(and any other relevantptr_t
) to be given anOUTDEGREE
.ptr_data<ptr_t>
template class should inherit from a givenptr_t
class and extend it with adata
field which in this case is a complex-valued number.[ ] Template
node
A node should be variadic in (1) its
ptr_t
and (2) itsOUTDEGREE
.QMDD Reduce
node::OUTDEGREE
many edges from the priority queue instead of being hardcoded for a binary outdegree.QMDD Operations
The following operations are transcribed from [Miller06] and the actual source code of the QMDD package. These are defined on edges going to nodes, such that the weight of the in-going edge is available. There might be errors in this pseudocode, please read them critically.
Matrix Addition
Matrix Multiplication
We also should design/provide a variant of this, where the left or right-hand side is a vector (i.e. only use an outdegree of r rather than r2.
Kronecker Product
References
[Li22] Yonghong Li and Hao Miao. “*Quantum Multiple-Valued Decision Diagrams with Linear Transformations*”. In: arXiv*. (2022)
[Miller06] D. Michael Miller and Mitchell A. Thornton. “QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits”. In: *36th International Symposium on Multiple-Valued Logic (ISMVL'06)** (2006)