You'd need multiple verifications with the same (or similar) result ... but that isn't trustless since Sybil attacks would still be possible. ... and proof of work tends to be the solution to Sybil attacks.
And you'd need to be sure that the work being done wasn't some real-world scam... I see the point of how difficult it would be - I'm just saying that's tremendous value.
There have been very recent developments in homomorphic encryption - essentially doing addition and multiplication on encrypted data without revealing the inputs or outputs, and zero-knowledge proofs, thus enabling general trust-less computing.