[Feature Request] ApplyPermutationUnitary

[fedimser]

Q# already supports ApplyUnitary which takes $2^n \times 2^n$ Complex matrix.

I propose to support ApplyPermutationUnitary which would take Int array of size $2^n$ describing a permutation and implement a unitary matrix that is a permutation matrix.

Why?

• When working with arithmetic, we often use gates that apply reversible integer function on a target register. In other words, a permutation on basis states.
• On a real quantum computer, such gates need to be implemented using 1- and 2- qubit gates, often requiring ancillas. However, for debugging an testing, we might want to represent such a gate directly by the permutation it applies. This allows to debug the rest of algorithm (and later replace this matrix with real implementation). Also this allows to simulate algorithm using less qubits (because we don't need ancillas). This can make a difference between being able to simulate an algorithm or not.
• This already can be done by constructing the permutation unitary explicitly, which is very inefficient. It would be more efficient to store permutation without converting it to matrix. Then, in the simulator we can directly apply this permutation to wavefunction vector instead of doing matrix multiplication.

Below is example of inefficient implementation of ApplyPermutationUnitary in pure Q# by constructing the unitary:

operation ApplyPermutationUnitary(permutation : Int[], qubits : Qubit[]) : Unit {
    let n = Length(permutation);
    if (n != 1 <<< Length(qubits)) { fail "Size mismatch."; }
    mutable matrix = Repeated(Repeated(0.0 + 0.0i, n), n);
    for i in 0..n-1 {
        let j = permutation[i];
        set matrix w/= j <- (matrix[j] w/ i <- 1.0 + 0.0i);
    }
    ApplyUnitary(matrix, qubits);
}

I propose implementing it as intrinsic and pass the integer array to the simulator.

Additional context

• Note that this matrix permutes basis states, not qubits (so size of permutation is $2^n$, not $n$).
• Cirq already has equivalent feature, it's called ArithmeticGate. This feature request proposes to close a feature parity gap between Q# and Cirq.