The Yamakawa-Zhandry algorithm is a breakthrough that has some properties similar to the other major quantum algorithms such as Shor's, and some that are quite a bit different. Apparently the algorithm and the breakthrough rely on at least (1) the presumed classical hardness of inverting SHA256, (2) the relationship between multiplication (in a primal domain) and convolution (in a dual domain), along with a quantum computer's capabilities to calculate the Fourier transform of a lattice to move therebetween, and (3) error correction in these lattices, so as to make this convolution reversible.
The Yamakawa-Zhandry problem is to find points on a lattice in a boolean cube, all of whose coordinates hash onto $1$.
It's straightforward enough to prepare a first register into a superposition of all points in the lattice:
$$|\psi\rangle=\alpha_i |x_i\rangle\tag 1.$$
It's also straightforward to prepare a second register into a superposition of all points in the cube all of whose coordinates hash onto $1$:
$$|\phi\rangle=\beta_j |y_j\rangle.\tag 2$$
We would like to multiple $\alpha_i\times\beta_j$, but these two registers start off unentangled:
$$|\psi\rangle\otimes|\phi\rangle=\alpha_i |x_i\rangle\otimes\beta_j |y_j\rangle.\tag 3$$
So although we can measure the first and second registers independently, we'll get a random lattice point and another independent random point satisfying the hashing constraint.
However, through the magic of Fourier transforms and decoding of errors, we can move/add the contents of the first register into the second register (and uncompute and throw away or ignore the first register):
$$|\phi\rangle=\alpha_i\beta_i |x_i+y_i\rangle.\tag 4$$
Measuring this register now gives us a lattice point (because of $\alpha$) that concurrently satisfies the hashing constraint (because of $\beta$).
In more detail, there's a lot of ideas in the paper, and it's hard to make a simple circuit now. To be honest I only understand portions of the algorithm, and only at a very high level. Nonetheless according to my limited understanding, based on Zhandry's presentation, we can refer to a marked-up version of Figure 1 of the paper as below.
The upper first register $|\psi\rangle$ of qubits is initially prepared, with the uppermost $n-k$ registers Hadamard'ed with a $\mathsf{QFT}_\Sigma$ gate, while the other $k$ registers remain at $|0\rangle$.
The map $x\mapsto M_{C^\perp}\cdot x$ prepares the upper register into the dual lattice of a uniform superposition over all codewords of a sufficiently nice code. The folded Reed-Solomon code has the requisite properties.
Concurrently in the second lower register $|\phi\rangle$, for each dimension, one half of all lattice points are randomly picked while in superposition. Post-selection with random oracles $H_1,\ldots, H_n$ are illustrated in the circuit. This can be instantiated with a SHA256 hash of the coordinate (salted with the index of the coordinate's axis, for example).
This second register is then Fourier-transformed. In each dimension, the amplitude of the Fourier transform of register $|\phi\rangle$ at $y=0$ is about $\frac{1}{2}$, because precisely half of the coordinates hash on to $1$. For other $y$, the amplitudes are roughly uniformly distributed. Note that up to this point, the first register and the second register are unentangled, and we can describe the state as $|x\rangle\otimes|y\rangle$.
Now, the first register is added into the second register as $|x\rangle\otimes|x+y\rangle$. The first and second registers are now entangled.
The random oracle step 3 induces errors in the code that are decodable in superposition from the dual lattice. This means we can uncompute the first register, and be left with the second register $|x+y\rangle$. The circuit $\mathsf{Decode}_{C^\perp}$ does this uncomputation. The upper register $|\psi\rangle$ is now done as it reverted back and the entanglement with the lower register $|\phi\rangle$ is removed. This upper register can thrown away.
An inverse Fourier transform is then done on the lower register to get from the dual lattice back to the primal lattice. Upon measuring this lower register one obtains a set of codes that all satisfy the SHA256 test.
I'm a bit fuzzy on how much of this I got this right. But I'm still interested in learning! I also seriously doubt whether the circuit can be implemented in short-order in the NISQ-era, as at least the decoding step likely involves fault-tolerance.
