Decomposition-based synthesis (DBS)

Header: tweedledum/algorithms/synthesis/dbs.hpp

This synthesis algorithm is based on the following property of reversible functions: Any reversible function \(f : \mathbb{B}^n \to \mathbb{B}^n\) can be decomposed into three reversible functions \(f_r \circ f' \circ f_l\), where \(f_l\) and \(f_r\) are single-target gates acting on target line \(x_i\) and \(f'\) is a reversible function that does not change in \(x_i\).

Parameters

struct dbs_params

Parameters for dbs.

Public Members

bool verbose = false

Be verbose.

Algorithm

template <class Network, class STGSynthesisFn>
Network tweedledum::dbs(std::vector<uint32_t> perm, STGSynthesisFn &&stg_synth, dbs_params params = {})

Reversible synthesis based on functional decomposition.

This algorithm implements the decomposition-based synthesis algorithm proposed in [DVVR08]. A permutation is specified as a vector of \(2^n\) different integers ranging from \(0\) to \(2^n-1\).

std::vector<uint32_t> permutation{{0, 2, 3, 5, 7, 1, 4, 6}};
auto network = dbs<netlist<mcst_gate>>(permutation, stg_from_spectrum());

Parameters

• perm: A permutation
• stg_synth: Synthesis function for single-target gates
• params: Parameters (see dbs_params)