qiskit-textbook
qiskit-textbook copied to clipboard
qiskit-community
Oracle Design Pull Request
I inserted into ch-gates/ subdirectory a tutorial concerning oracle design. After an introduction to Boolean algebra and functions, an elementary methodology for the design of Boolean oracles is presented with four examples. Boolean oracles are then exploited for designing phase oracles. In this case, five examples are proposed. The quantum circuit of the oracle for triangle coloring is written in QASM, so a qasm file has been added too.
Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.
You have signed the CLA already but the status is still pending? Let us recheck it.
Hi @giovanniamedeocirillo, thank you for your contribution! You have clearly put a lot of work into this. Can we please work with you in making some changes we think would make it more appropriate for the textbook?
Hi @frankharkins for sure! I have never updated it since october. If you have suggestions for increasing the quality of this work please let me know. Thank you!
Firstly, we believe it belongs after the articles on Grover/Deutsch etc. and not in the ch-gates chapter. We are considering adding an 'advanced' sub-section in ch-algorithms which would be perfect for this.
In terms of code, you should try and separate more chunks into functions to improve readability. You may find it useful to know that qiskit does provide some multi-control-toffoli functionality (link) and I believe this will help reduce the size of the diagrams and the article in general. It would be better to avoid building from QASM if possible.
I thought this notebook as a way for learning how to exploit Grover's algorithm for solving "complex" search problems where the solution is not known a priori. Since the methodology from designing oracles starts from exploiting quantum gates, I proposed its insertion in ch-gates, but I agree with You that an "advanced algorithms" section would be better for it.
Thank you for the suggestions on multi-controlled gates and QASM.
Hi @frankharkins I updated the notebooks according to your suggestions. Now it is in a new subdirectory of ch-algorithms/ called advanced. I avoided QASM and I used functions and mct as much as possible. Please let me know if the current version could be OK. Thanks in advance.
P.S. I am going to write another notebook in which examples of problems solvable with Grover's search are provided. Moreover, I would like to add another section concerning "optimization problems" solvable with the proposed methodology for oracle design and Grover's search, where the full oracle is implemented as combination of smaller oracles (one for each constraint), each one increasing the phase kickback of the probability amplitudes (if a solution satisfies all constrains its probability amplitude will acquire phase pi, thus we have a sign flip, otherwise it will acquire a phase between 0 and pi). If the first notebook was OK, I would insert this proposal in the issues of the textbook on Github.
Depending on where this is inserted in the textbook, I think a section on hardware implementation might be important here. That is to say that many of these gates become quite deep when running on actual devices.
@nonhermitian do you think that I have to insert another section at the end of the notebook? Is it sufficient a simulation with noise models of real hardware?
I am not sure if one really needs to run these against a noisy simulator, although that does provide some insight. The thing with ccx gates or cccx etc. is that they decompose poorly into standard gate sets. So a reader might be confused when they see the qasm simulator results here are not what the real devices return. In some cases by a large amount. I think this needs to be explained a bit so that the reader is aware of what is going on.
I think the purpose of this article should be to help users understand how a useful oracle can be desinged (as @giovanniamedeocirillo mentioned earlier in this thread).
At the moment this article explains boolean functions and circuit decomposition from mct-gates, both of which are quite big topics in their own right. I think these need to be split up and covered separately because the article is already very large. Maybe something like "creating multi-control toffoli gates is a well researched topic, you can find out more about this in (references) but for now we will use qiskits mct function that takes care of this for us. It is worth mentioning that this can quickly create complex and deep circuits which often don't run well on real hardware" could replace a large chunk of this article that could then go elsewhere?
Let me know what you think, I'm happy to help do this.
Hi @frankharkins @nonhermitian, according to what You wrote in the previous messages I think that the best things to do are:
- separating Boolean and Phase oracles into two different notebooks;
- inserting in the Boolean oracle notebook a preliminary section, let's say between the part concerning the oracles of NOT, AND2, OR2 and XOR2 and the first exercise, with a premise about the implementation of multi-qubit Toffoli gates and the limitations of their real hardware implementations, providing some reference code, each one containing a quantum circuit with Hadamard gates (in order to evaluate simultaneously the mct on all basis states) followed by a mct (with different number of control qubits) and measure to be executed on two real backends (preferably two which differ in terms of qubits connectivity graph) or on qasm simulator with noise models (in order to avoid credits consumption).
What do You think about that? Thank You in advance.
@giovanniamedeocirillo I think both types of oracle belong together, we are currently discussing reorganising the textbook and migrating to IBMQX. I think once we have done this the problem of where this belongs will be more obvious. Secondly, being on IBMQX will allow us to use accordians and other web formatting that will make larger articles more readable.
In terms of hardware, I think we should make it clear from the start that these oracles cannot be run on current machines, but this shouldn't become a hardware article. My preference would be to ignore hardware completely. We are working on other chapters on transpiling which cover toffoli decomposition and that can explain exactly why mcts etc. are currently unfeasible.
Let me know what you think.
When I wrote the first version of the notebook in october, I was not going to consider real hardware (even though it is quite unusual for me, since I am an electronics engineer), because I was going to generalize the methodology already exploited for solving complex problems solvable with Qiskit Aqua's Grover (e.g. the 3-SAT), which were not executed on real hardware. It is clear that my notebook would be OK for a new arrangement of the textbook, where algorithms are mainly (not exclusively, because the consciousness of the limitations of NISQ devices is important) analyzed in "ideal" conditions. If you think that a premise like "creating multi-control toffoli gates is a well researched topic, you can find out more about this in (references) but for now we will use qiskits mct function that takes care of this for us. It is worth mentioning that this can quickly create complex and deep circuits which often don't run well on real hardware" (I copied what you wrote previously) would be sufficient, please let me know.
@giovanniamedeocirillo, I believe that would be sufficient. I'll get some opinions from my colleagues, but I think either way it might be best to sit on this for a bit until the structure is decided. Then we can work out exactly how it fits in and what we need to change.
Thanks for your contribution. I'm closing this pull request as this repository is no longer used and is being archived. You can find the latest version of the Qiskit Textbook online at https://qiskit.org/learn/, and the new content repository at Qiskit/textbook. Please feel free to re-open this pull request there if it's still relevant.