6.2 Quantum oracles for combinatorial optimization
As we have seen, the Dürr-Høyer algorithm can be used to find the minimum of a function with high probability and with a quadratic speedup over brute force search. However, in order to use it, we need a quantum oracle that, given binary strings and , checks whether .
In our case, we are interested in functions that can appear in QUBO and HOBO problems. This means that will be a polynomial with real coefficients and binary variables, and we could implement the quantum oracle with a straightforward approach: design a classical circuit for it using AND, OR, and NOT gates, and then simulate the classical gates with the Toffoli quantum gate, as we showed in Section 1.5.2.
However, in 2021, Gilliam, Woerner, and Gonciulea, introduced an improved way of implementing quantum oracles for QUBO and HOBO problems in a paper titled Grover adaptive search for constrained polynomial binary optimization [45].
In this section, we will...
