I'm reading a paper on quantum pattern matching and here it talks about a unitary matrix U which represents the oracle that flips a state's amplitude as a permutation over the computational basis. See page 3 right side fourth paragraph under equation (7).
Can someone explain to me what that means?
The unitary defined by equation (7) is a permutation because it sends every computational basis state to another computational basis state (as opposed to some superposition of computational basis states). In the matrix form, every column of U is filled with zeros except for one entry equal to one (and similarly for rows by invertibility). In other words, it is a permutation matrix.
Specifically, U sends the computational basis state |x0, x1, ..., xn⟩ to the computational basis state |y, x1, ..., xn⟩ where y = f(x1, ..., xn) if x0 = 0 and y = 1-f(x1, ..., xn) if x0 = 1. See equation (6).
Note that U does not flip the phase of any state. However, if we act with U on the state
|0, x1, ..., xn⟩ - |1, x1, ..., xn⟩
(where we neglect normalization) then the result is
(-1)^f(x1, ..., xn) (|0, x1, ..., xn⟩ - |1, x1, ..., xn⟩)
where the phase is flipped if and only if f(x1, ..., xn) = 1. This is an example of phase kickback.