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

Improve this question
$\endgroup$
1
  • $\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
    Commented May 16, 2020 at 7:05

2 Answers 2

Reset to default
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$
4
  • $\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
    Commented May 20, 2020 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
    Commented May 20, 2020 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
    Commented May 22, 2020 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
    Commented May 23, 2020 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$
1
  • $\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
    Commented May 17, 2020 at 2:26

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.