Ensuring that an operation takes a relatively specific amount of time, but easily verify the result
Timelock puzzles solve this problem.

For instance, consider the function $f(x) = x^{2^t} \bmod n$, where $n$ is a RSA modulus and $t$ is large.  For people who don't know the factorization of $n$, computing $f$ takes $t$ squarings modulo $n$.  If you do know the factorization of $n$ (the private key), then computing $f$ can be done with $O(\lg n)$ squarings, regardless of how large $t$ is, by first reducing $t$ modulo $\varphi(n)$.  This lets you create a puzzle that will take a controllable amount of time for someone else to solve, and where you can very efficiently verify the answer: e.g., choose $n$ to be a 2048-bit prime and $t$ to be a million, or whatever you want $t$ to be to make computing $f$ take exactly as long as you want for the other person.

See, e.g., Time Capsule cryptography? and Parallel-resistant proof-of-work scheme? and What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?



If you want a proof of work puzzle that requires the other person to do 30 seconds of work, I don't see any practical reason to worry much about quantum computers.  Right now there are no quantum computers that could pose a serious threat to this scheme.  If they ever become possible, you can always change the scheme out.  The scheme only needs to be secure for 30 seconds, not for 30 years....