I have just finished multiple readings of Applying Grover’s algorithm to AES: quantum resource estimates, a 2015 paper by Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt. There are many copies of it online; I used this one: https://arxiv.org/abs/1512.04965
The authors construct quantum gate implementations of AES-128, AES-192 and AES-256. They Do it with Clifford+T gates "as the underlying fault-tolerant logical quantum gate set." Table 1 has their gate estimates and qubit estimates for the key expansion.
Table 2 has the quantum resource estimates for the AES-128 implementation:
Table 3 has the resources for AES-192:
And Table 4 has the resource estimates for AES-256:
Cracking AES with Grover's algorithm requires a (plaintext, ciphertext) pair --- that is, you perform a known plaintext attack, which is easier than a ciphertext-only attack. In this case, Grover's algorithm is used find the key that produces the ciphertext from the plaintext (or vice-versa). One of the things that the authors note is that you actually need multiple blocks to perform the attack, since the block size is 128-bits, so for the vast majority of 128-bit blocks there will be multiple AES-192 and AES-256 bit keys that produce the same (plaintext,ciphertext) pair. (I had not realized this before reading the paper, but it is a straightforward application of the pigeonhole principle.)
The part of the paper that I do not understand is the time estimates, and this probably goes back to some confusion that I have regarding Grover's algorithm. The challenge in cracking AES with Grover is not the complexity of the circuit (which results primarily from unwinding the multiple rounds), but from the number of "Grover iterations" that are required.
The key paragraph is at the bottom of p. 10 and the top of p. 11:
What I'm confused about is how we actually implement a 'Grover iteration' on a suitably large quantum computer. If we were to use a scaled up version of the superconducting quantum computers with artificial atoms, then the qubits are the wires and the gates are radio pulses that are fed into the circuit, right? So does each "iteration" mean that we play the gates from beginning to end $1.19 \times 2^{86}$ times?
If we do need to play the gates $1.19 \times 2^{86}$ times, do we store the results of each of those iterations in a classical computer that's controlling the quantum computer, and then take the result that was selected the most number of times, or do the results accumulate in the quantum circuit itself? If we accumulate the results, then don't we also need to have room to store $2^{128}$ 128-bit solutions to see which one comes up the most times?
Here is Table 5, which computes the time resources required for attacking AES with Grover's algorithm:
The paper concludes "it seems prudent to move away from 128-bit keys when expecting the availability of at least a moderate size quantum computer." Presumably this is because we can perform $2^{86}$ iterations (even with today's technology!!!) but we won't be able to perform $2^{151}$ iterations of anything, ever. In fact, we won't ever be able to perform $2^{128}$ iterations of anything, ever.
But what exactly are we iterating?
