3 ms·
What’s the Big-O factor for the initialization step? Seems it’s at least o(# qubits) which should be O(log n) where N is the database size, but the story acts l
by cromwellian 9y ago
What’s the Big-O factor for the initialization step? Seems it’s at least o(# qubits) which should be O(log n) where N is the database size, but the story acts like it it’s O(1) overall.
- ChrisLomont 9y agoIf I remember from when I worked on this, Grover allows searching N=2^n items with complexity O(sqrt(N)). Even if init was O(log N), this would be much smaller than O(sqrt(N)) for large N, so can be (almost) ignored.
- red75prime 9y agoO(sqrt(N) + log N) = O(sqrt(N)) by definition