1
$\begingroup$

I am now practising using Qiskit. The example of Grover's algorithm in tutorials suggests using logical expression, truth table or circuit to construct the oracle. In most textbooks on quantum computation as far as I have read, they use a function $f$ mapping to 0 or 1 during constructing the oracle. So I want to know if there is any beautiful way to do this with Qiskit. For instance, to find 4 in the array of (3, 4, 5, 6, 8, 2, 7, 1), how to use some $f$ like returning 1 if matched, otherwise 0, to construct the oracle? I know I can obtain a truth table 01000000, but if it's too long to compute, how to use an $f$ directly, without calculating the truth table outside the part of quantum computation?

More generally, if elements in the array to search are obtained in iterations (e.g. in one iterate, I obtain one element $x_i$, which is sum of something else like $\sum_j y_j$), should I complete these iterations before doing Grover's algorithm? Or is it feasible to embed the iterations into quantum computation so that I do not need to traversal all the iterations?

In addition, I use the tutorial from https://github.com/Qiskit/qiskit-community-tutorials/blob/master/optimization/grover.ipynb

$\endgroup$
  • $\begingroup$ If any duplication, i'd apologize for that. Any related question may be helpful, but as far as I have searched, it seems there are few posts talking about code. $\endgroup$ – Zaragoss May 16 at 7:05
1
$\begingroup$

If your function is defined in a way that requires you to iterate over all possible inputs to implement the oracle, you clearly lose the advantage of using Grover's algorithm. This question goes into detail about using Grover's search for unordered database search, which is pretty much your example.

Instead, the function should be defined in a way that allows to recognize the answer much faster checking it against a table of all inputs. An excellent example of such functions are SAT problems: the number of operations you need to do to evaluate the given Boolean formula for an input depends on the size of the formula, rather than the size of the search space.

This paper discusses the practicality of using Grover's algorithm for solving various types of problems.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You got what I meant. So it seems not a programming issue. I know Oracles in aqua.components accepts logical expressions including CNF, which is quite decent. But to transform other problems into SAT, much extra work needs taking. So it couldn't be better if there are some built-in methods to make such transformations. $\endgroup$ – Zaragoss May 20 at 7:27
  • $\begingroup$ BTW I remember someone has talked about that paper in other posts, and the result shows Grover's algorithm is not that universally practical in speeding up a general problem at least for now. But I wonder whether quantum programming like in Qiskit could be more abstract without doing too much about circuits, even if there is not much speedup; I just want to demonstrate how a classical problem could be solved on quantum computers instead of how gates are combined. $\endgroup$ – Zaragoss May 20 at 7:28
  • $\begingroup$ Sorry, I'm not familiar with Qiskit enough to know about its high-level capabilities. I know how you could express this in Q# - github.com/microsoft/QuantumKatas/tree/master/tutorials/… and github.com/microsoft/QuantumKatas/tree/master/… $\endgroup$ – Mariia Mykhailova May 22 at 1:55
  • $\begingroup$ Oh, I have read tutorials about solving SAT in Qiskit, and that's why I said it's decent of the corresponding code. What I want is to see if there is any library reducing other problems e.g., set covering to SAT, however it seems currently invalid since in the tutorials you provided, extra manual work is required even for transforming SAT expressions to truth tables or something similar, which is really disappointing as Qiskit can accept logical expressions directly at least. If you know anything about reducing other problems to SAT in Q#, that couldn't be better. $\endgroup$ – Zaragoss May 23 at 5:45
0
$\begingroup$

The oracle of Grover's algorithm can be written as a phase oracle: for one computational basis state, induce a -1 phase, and do nothing for the other basis states. In Qiskit you can use a Diagonal operator for this.

In your example you are searching for the decimal 4 in 8 possibilities. You need 3 qubits for this problem, and the answer to search for would be 100 (little endian convention).

from qiskit.circuit.library import Diagonal
from qiskit.quantum_info import Statevector

mark_state = Statevector.from_label('100')
mark_circuit = Diagonal((-1)**mark_state.data)  # circuit that induces a -1 phase on the mark_state

You can see a complete Grover example in Qiskit with this approach here: https://github.com/ajavadia/qiskit-terra/blob/Demo/demo/Grover%20Interactive.ipynb

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your reply, but I request some further clarification. The marked state '100' indicates position/index of the target, does it? I have modified my example due to ambiguity, so for the current example, it's 001 or 110 (I am not so sure about little endian); but if I have known its position, why do I need Grover's search? If I misunderstand it, please tell me something more, especially about how to process elements obtained in iterations—should I finish all iterations before quantum search? If so, it seems quantum search doesn't speed up the problem. $\endgroup$ – Zaragoss May 17 at 2:26

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.