Motivated by Aaronson's call to find simple, verifiable proofs of quantumness, suppose we start off with a random polynomial-length circuit $U$ of, say, Hadamard+CCNOT (Toffoli) or CSWAP (Fredkin) gates, and attach $U^\dagger$ to it, can we then use a classical obfuscator to scramble $I=U^\dagger U$ beyond recognition, while still keeping the overall circuit size polynomial?
If we could do such scrambling easily enough, we can then provide a classical description of our obfuscated circuit for $I$, or alternatively of another random circuit $C$ from the same generating set of gates, to a quantum computer, who could determine which is which merely by executing the circuit on various basis states.
Indeed, we could insert a circuit such as $D=I+\epsilon$ that is exponentially close to the identity, and then run our circuit so obtained $U^\dagger D U$ through a Solovay-Kitaev compiler, to maybe add more spice to our circuit.
Are there enough known interesting relations to do such scrambling? After all, non-identity-checking is coQMA-complete.
