2
$\begingroup$

There are many data structures in classical computers, like Tree, HashSet, etc. These data structures give convenience to the performance (time complexity) of algorithms. I am wondering how to create a similar data structure on a quantum computer. Specifically, I want to know if there is a quantum HashSet that supports $\mathcal{O}(1)$ cost for adding and accessing elements. If not, how might one implement a hash function on a quantum computer?

I think a quantum computer can do at least the same as a classical computer, but I could not find a solution on Google.

$\endgroup$
0
$\begingroup$

A major problem with implementing a hash set on a quantum computer is that, if you are inserting a superposed item, it can go into a superposition of buckets. But if you don't operate on a bucket, you can't possibly have inserted an item into it. Therefore to insert (or query) a superposed item correctly, which goes into a superposition of all the buckets, you have to apply at least one operation per bucket. Therefore the number of operations scales like O(n) instead of O(1).

That being said, this is kind of unfair to the quantum computer. The classical logic circuit implementing a hash set also uses O(n) gates to perform a query, but in a CPU we hide almost all of that circuit behind an abstraction we call "querying memory". We only pay attention to the time cost instead of the hardware time cost. The quantum circuit model tends to highlight the hardware time cost.

So, in order for a quantum hash set to be efficient, you need quantum memory that's cheap enough compared to quantum computation that you think of querying across that memory as having constant cost instead of cost proportional to the size of the memory.

$\endgroup$

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.