ApplyPermutationUsingDecomposition operation

  • Article

Warning

This documentation refers to the Classic QDK, which has been replaced by the Modern QDK.

Please see https://aka.ms/qdk.api for the API documentation for the Modern QDK.

Namespace: Microsoft.Quantum.Synthesis

Package: Microsoft.Quantum.Standard

Permutes the amplitudes in a quantum state given a permutation using decomposition-based synthesis.

operation ApplyPermutationUsingDecomposition (perm : Int[], qubits : Microsoft.Quantum.Arithmetic.LittleEndian) : Unit is Adj + Ctl

Description

This procedure implements the decomposition based synthesis approach. The input is a permutation $\pi$ over $2^n$ elements ${0, \dots, 2^n-1}$, which represents an $n$-variable reversible Boolean function. The algorithm iteratively performs the following steps for each variable index $i$:

  1. Compute $((\pi_l, \pi_r), \pi')$ such that the images of $\pi_l$ and $\pi_r$ do not change bits in their elements at indexes other than $i$ and images of $\pi'$ do not change bit $i$ in their elements.
  2. Set $\pi \leftarrow \pi'$, and derive truth tables from $\pi_l$ and $\pi_r$ based on elements that are not fixed-points.

After applying these steps for all variable indexes, the remaining permutation $\pi$ will be the identity, and based on the collected truth tables and indexes, one can apply truth-table controlled X operation operations using the ApplyXControlledOnTruthTable operation operation.

The variable order is $0, \dots, n - 1$. A custom variable order can be specified in the operation ApplyPermutationUsingDecompositionWithVariableOrder operation.

Input

perm : Int[]

A permutation of $2^n$ elements starting from 0.

qubits : LittleEndian

A list of $n$ qubits to which the permutation is applied to.

Output : Unit

Example

To synthesize a SWAP operation:

using (qubits = Qubit[2]) {
  ApplyPermutationUsingDecomposition([0, 2, 1, 3], LittleEndian(qubits));
}

References

See Also