Transformation-based synthesis (TBS)

Header: tweedledum/algorithms/synthesis/tbs.hpp

Transformation-based synthesis algorithms modify the input permutation by adding gates to the input or output side of a circuit in a way that the permutation becomes the identity. The gates collected in this process construct a reversible circuit realizing the permutation.

Parameters

struct tbs_params

Parameters for tbs.

Public Types

enum behavior

Variants of transformation-based synthesis.

Values:

unidirectional

Only adds gates from the output side. (default)

bidirectional

adds gates from input or output side at each step.

multidirectional

adds gates from input and output side at each step

(for more information see [SDRM16])

Public Members

behavior behavior = behavior::unidirectional

Algorithm behavior.

cost_fn_type cost_fn = [](auto& permutation, auto x, auto z) { return __builtin_popcount(z ^ x) + __builtin_popcount(x ^ permutation[z]); }

Cost function in multi-directional synthesis.

By default the number of reversible gates is used as cost function.

bool verbose = false

Be verbose.

Algorithm

template<typename Network>
Network tweedledum::tbs(std::vector<uint32_t> permutation, tbs_params params = {})

Transformation-based reversible logic synthesis.

This algorithm implements various variants of the transformation-based synthesis algorithm originally proposed in [MMD03]. 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 = tbs<netlist<io3_gate>>(permutation);

Parameters

  • permutation: A vector of different integers

  • params: Parameters (see tbs_params)

template<typename Network>
void tweedledum::tbs(Network &network, std::vector<io_id> const &qubits, std::vector<uint32_t> permutation, tbs_params params = {})

Transformation-based reversible logic synthesis.

This is the in-place variant of tbs, in which the network is passed as a parameter and can potentially already contain some gates. The parameter qubits provides a qubit mapping to the existing qubits in the network.

Parameters

  • network: A quantum circuit

  • qubits: A qubit mapping

  • permutation: A vector of different integers

  • params: Parameters (see tbs_params)