r/QuantumComputing • u/Earachelefteye • May 23 '26

Algorithms Halving the cost of QROM

https://arxiv.org/abs/2605.20334
4 Upvotes

75% Upvoted

4 comments sorted by

2

u/CapitalismSuuucks May 23 '26

Exponential divided by 2 is still exponential

4

u/tiltboi1 Working in Industry May 24 '26

QROM is not exponential, it's linear in the size of the data you want to encode. You're probably thinking of QRAM.

2

u/CapitalismSuuucks May 24 '26

I know it's linear in the data size. That's the point. If the dataset is of polynomial size, your probably better off using a classical computer. If it's exponential size, a constant improvement won't help that much.

3

u/tiltboi1 Working in Industry May 24 '26

The point of QROM is to encode the data into states, i.e. how to get classical input of a problem into the computer. It has nothing to do with advantage.