2
$\begingroup$

I'm trying to maximize a QUBO function f(x,y,z) = 3xy + 4xz - 3yz + 11y + z. How can I use Grover's algorithm to do this?

I've been told to encode this cost function which I'm not sure of. And to use quantum annealing to maximize the cost function. I'm not sure if this is the right way to proceed. Where does Grover's algorithm comes in this? Thanks in advance!

$\endgroup$

2 Answers 2

2
$\begingroup$

It seems that you confused two approaches. First one is quantum annealing which can be implemented in single purpose quantum processor like those offered by D-Wave. Moreover, variational algorithms VQE and QAOA implements the annealing approach on gate-based computer.

Concerning the Grover algorithm, there is a modification of the algorithm for QUBO tasks called Grover adaptive search and it is described in this paper. In short, it is based on amplification of state representing the optimum. To do so, it iterates several time and each time adapts it's oracle to take into account new "best solution". In the last iteration the solution is revealed.

Just to add that annealing has unguaranteed speed-up whereas Grover has proven quadratic speed up.

Note that VQE, QAOA and Grover search are implemented in Qiskit libraries, so you can use them immediately on IBM Quantum. Concerning the annealer, it is possible to subscribe for free to D-Wave Leap environment and solve your task here.

$\endgroup$
1
  • 1
    $\begingroup$ +1 you beat me to it by 10 minutes it seems. This answer wasn't here when I started typing, so evidently it took me longer than 10 minutes for me to type my answer! $\endgroup$ Feb 4, 2023 at 8:07
1
$\begingroup$

"I've been told to encode this cost function which I'm not sure of. And to use quantum annealing to maximize the cost function."

Grover's algorithm is a circruit-based algorithm. It uses quantum gates, not quantum annealing.

"I'm not sure if this is the right way to proceed."

It is not the correct way to proceed if you want to use Grover's algorithm.

"Where does Grover's algorithm comes in this?"

It does not.

"I'm trying to maximize a QUBO function f(x,y,z) = 3xy + 4xz - 3yz + 11y + z. How can I use Grover's algorithm to do this?"

Based on the following lines in MATLAB/Octave:

b= dec2bin(2^3-1:-1:0)-'0';
3*b(:,1).*b(:,2) + 4*b(:,1).*b(:,3) - 3*b(:,2).*b(:,3) + 11*b(:,2) + b(:,3)

we can see that the ground state is degenerate with (x,y,z)=(0,0,0) and (x,y,z)=(1,0,0) both giving the minimum energy.

The most common way of describing Grover's algorithm, involves looking for one "unique" input for which the function has a particular output value. For example, Wikipedia says:

"We additionally assume that only one index satisfies f(x) = 1, and we call this index ω. Our goal is to identify ω."

In your case you're looking for two function inputs, so you would have to modify the "textbook Grover algorithm", but if you were only looking for (x,y,z) = (0,0,0), you would make a function "g(x,y,z)" and set g(0,0,0)=1 and g(x,y,z) = 0 for all other (x,y,z) triplets. Then you can use Grover's algorithm as it's described in many textbooks and in many questions that have already been answered here at QCSE.

Also if you k now that the minimum will have 0 energy but don't know where it is, you can implement Grover's algorithm using f(x,y,z) instead of g(x,y,z), but with all non-zero f(x,y,z) divided by their absolute value, so that your outputs are only 0s and 1s.

$\endgroup$
1
  • 1
    $\begingroup$ +1 as well, you provided additional information, so are answers are nice complements. $\endgroup$ Feb 4, 2023 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.