What do you mean that we cannot "represent an input to this oracle as a bitstring"?

For example we could have the basis states in our Hilbert space be the adjacency matrices over $N$ vertices, with $G$ being one of these states, while $\pi_i\in S_N$ being permutations of these vertices.

I claim it's easy to prepare the state:

$$\frac{1}{\sqrt {N!}}\sum_{i=1}^{N!}|i\rangle,\tag 1$$

for example where each $i$ is written as a number in the [factoradic number system](https://en.wikipedia.org/wiki/Factorial_number_system).

With $\pi_i\in S_N$, $G$ being an adjacency matrix on $N$ vertices of the test graph, and $\pi_i(G)$ being another adjacency matrix having the $i$th permutation applied to $G$, I then also claim that it's easy to prepare:

$$\frac{1}{\sqrt {N!}}\sum_{i=1}^{N!}|i\rangle|\pi_i(G)\rangle,\tag 2$$

by applying the $i$th permutation to the vertices on the test graph $G$.  If $G$ is given as an adjacency matrix on $N$ vertices in, say, some canonical form, and $\pi_i$ is a permutation, then we can easily come up with classical code, and hence with a quantum circuit, to permute the $N$ vertices in the adjacency matrix to find another adjacency matrix.

The problem, though, is that we cannot then easily disentangle the first register from the second register to prepare:

$$\frac{1}{\sqrt {N!}}\sum_{i=1}^{N!}|\pi_i(G)\rangle,\tag 3$$

because we need to uncompute the garbage that's picked up along the way, while computing $\pi_i(G)$.  For, if we had such a state, we could solve graph isomorphism in quantum polynomial time.

---

<sup>Note I'm using "easy" as synonymous with "polynomially", and not necessarily as meaning easy in the plain and ordinary interpretation of effortlessly or uncomplicated; it might indeed be actually be challenging to engineer the actual snippet of code to do the permutations, and to then convert the code into a quantum circuit.</sup>