In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of effort proportional to some parameter N, an eavesdropper cannot break into their communication without expending an effort proportional to N^2, which is quadratically more than the legitimate effort. However, Merkle's original scheme becomes completely insecure against a quantum adversary. Can its security be restored (at least partially) if the legitimate parties are also allowed to use quantum computation? We give two novel key agreement schemes in the spirit of Merkle's. The first one requires an effort proportional to N^{5/3} to be broken by a quantum adversary. In the second scheme, the legitimate parties are purely classical, yet it cannot be broken by a quantum eavesdropper who is not willing to work significantly harder than the legitimate parties, making it the first provably secure post-quantum cryptographic scheme in the random oracle model. In these schemes, as opposed to quantum key distribution, all communication is classical. No prior knowledge of cryptography will be assumed.