9
$\begingroup$

Recently, popular sources (including Aaranson's blog and Quanta Magazine) have made it look like the recent Yamakawa-Zhandry algorithm is akin to Shor's algorithm, in the sense that it could demonstrate quantum advantage soon if done with sufficient qubits/volume. Allegedly, it is easy to verify classically. I went for the arXiv (linked above) but is very mathematical. Could somebody illustrate how does it work? I looked also at the paper presentation in Eurocrypt 2021 but it is not much better.

Could somebody provide a toy-version of the algorithm? Maybe with an exemplary circuit?

$\endgroup$

1 Answer 1

12
$\begingroup$

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.

Yamakawa-Zhandry Marked Up

  1. 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$.

  2. 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.

  3. 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).

  4. 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$.

  5. 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.

  6. 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.

  7. 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.

$\endgroup$
2
  • $\begingroup$ Thank you for the link! I had not seen that one $\endgroup$
    – Mauricio
    Aug 24 at 14:39
  • $\begingroup$ Excellent answer. $\endgroup$
    – Mauricio
    Aug 26 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.