對手能否通過單個查詢將 QROM 與 ROM 區分開來？

我承認 QROM 與 ROM 不同（可以將其視為對輸入執行測量的特定 QROM）。例如，可以找到任意值的原像 $ O(N) $ 在使用時查詢 ROM $ O(\sqrt N) $ 通過 Grover 算法查詢 QROM。然而，這需要超過 $ O(\sqrt N) $ 查詢。只需要一個查詢的情況是什麼？更一般地說，區分它們的優勢是否與查詢的（多項式）數量有關 $ q $ ?

僅有的 $ O(1) $ 需要查詢來區分 QROM oracle 和 measure-and-ROM oracle。

無需對整個輸出空間執行 Grover 算法。我們可以在單個輸出位（例如前導位 1）上執行 Grover，並且在一次迭代之後，我們將以壓倒性的機率測量產生具有前導位 1 的輸出的輸入。

另一方面，如果我們有一個假預言機來測量輸入並返回經典輸出，我們將測量一個輸入，該輸入在一半的時間產生一個前導位為 0 的輸出。

引用自：https://crypto.stackexchange.com/questions/96494