Can Grover's Algorithm be combined with a meet-in-the-middle attack? We all know and love the meet-in-the-middle attack, which basically makes double encryption pointless using a time-memory trade-off. Now, the NSA recently recommended to use double encryption to adequately protect sensitive data from quantum attackers.

This made me ask myself:

Can one combine Grover's algorithm with the MITM attack to make double encryption "pointless" in the quantum setting?

Example:
The classical strength of double AES-256 encryption is 257-bits and $2^{256}$ storage. Using Grover's algorithm to attack the full cipher would take $2^{256}$ time. Can this time be reduced using a MITM trade-off and a quantum computer?
You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption:


Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$.
For each partition generate the inner encryption table.
Run Grover's on the outer keyspace in $O(2^{n/2})$ time.
If you find the preimage in the table, you found both keys, otherwise return to 2.


You would get $O(2^{n})$ time and $O(2^{3n/4})$ storage, which is better than classical meet-in-the-middle and requires less quantum computations, $O(2^{3n/4})$, than just using Grover's on the whole combined keyspace in $O(2^{n})$ time.

The problem of the size of the quantum computer would probably apply (maybe $O(2^{3n/4})$ qubits here?).