Quantum Multiple-valued Decision Diagram

[SSoelvsten]

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 r².

• 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

  • Until now, since nodes were binary, we could store whether an edge was the false or the true edge of a node in a single bit. In this case, we need to use lg(r²) = 2 lg(r) bits instead. This was fixed in 2dd4875 for the nested sweeping framework.
  • Template ptr_uint64 (and any other relevant ptr_t) to be given an OUTDEGREE.
  • A new ptr_data<ptr_t> template class should inherit from a given ptr_t class and extend it with a data field which in this case is a complex-valued number.

• Template node

  A node should be variadic in (1) its ptr_t and (2) its OUTDEGREE.

QMDD Reduce

• The Reduce algorithm needs to be generalised to retrieve and use node::OUTDEGREE many edges from the priority queue instead of being hardcoded for a binary outdegree.
• Furthermore, the Reduce operation needs to include the normalization of the edges described in [Miller06]. This essentially is a sorting of the edges (done by the priority queue itself without any changes) followed by a division with the first non-zero value.

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

qmdd_add(x, y):
  if x.weight == 0:
    return y
  if y.weight == 0:
    return x

  if x.target == 1 and y.target == 1:
    return y with y.weight 'x.weight + y.weight;'

  out_label = min(x.target.label, y.target.label)
  if x.target.label != out_label:
    swap x and y
  
  rec_results = { ., ., ., . }
  for idx = 0 .. r*r-1:
    p = x.target.children[idx]
    p.weight *= x.weight
    
    if x.target.label == y.target.label:
      q = y.target.children[idx]
      q.weight *= y.weight
    else:
      q = y

    rec_results[idx] = qmdd_add(rec_x, rec_y)

  return (var, rec_results) # normalized

Matrix Multiplication

qmdd_mult(x, y):
  if y.target == 1:
    swap x and y
    
  if x.target == 1:
    if x.weight == 0:
      return x
    return y with y.weight x.weight * y.weight

  out_label = min(x.target.label, y.target.label)
  if x.target.label != out_label:
    swap x and y

  rec_result = { ., ., ., . }
  for i = 0, r, 2r, ..., (r-1)*r:
    for j = 0, 1, 2, ..., r-1:
    
    z[i+j] = edge to 1 with weight 0
    
    for k = 0, 1, ..., r-1:
      p = x.target.children[i+k]
      p.weight *= x.weight
      
      if x.target.label == y.target.label:
        q = y.target.children[j+r*k]
        q.weight *= y.weight
      else:
        q = y
    
      rec = qmdd_mult(p,q)
      z_[i+j] = qmdd_add(rec, z_[i+j])

  return (out_label, rec_results) # normalized

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 r².

Kronecker Product

qmdd_kronecker_prod(x,y):
  if x.target == 1:
    if x.weight == 0:
      return x
    return y with weight x.weight * y.weight

  rec_results = { ., ., ., . }
  for i = 0, 1, ..., r*r-1:
    rec_results = qmdd_kronecker_prod(x.target.children[i], y)

  return (out_label, rec_results) # normalized

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)

[SSoelvsten]

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).