The 'database' can be a function implemented as a quantum circuit, e.g. a function that takes a candidate private key (and noise inputs) and computes a public k

The 'database' can be a function implemented as a quantum circuit, e.g. a function that takes a candidate private key (and noise inputs) and computes a public key from it and compares it to the target's key. Grover gets handed this function as an oracle and asked to find the input that makes it return 1, which it can do with sqrt(|key|) operations. Of course, the circuit for reversibly computing a public key ends up ginormous... but it's still vastly smaller than the keyspace. And if we were limiting ourselves to the practical we wouldn't be talking about quantum computers. :P