Fixed-Point Grover Search

[atithi8]

Summary

It is the fixed point variant of Grover search which approaches quantum search without the risk of overshooting. The notebook contains the codes, short descriptions, and references. The most optimal algorithm for fixed-point search has been referred but the example contains only the non-optimal algorithm as originally written by Lov Grover himself.

Details and comments

[review-notebook-app[bot]]

Check out this pull request on 

See visual diffs & provide feedback on Jupyter Notebooks.

---

Powered by ReviewNB

[CLAassistant]

All committers have signed the CLA.

[woodsp-ibm]

HI, thanks for making this contribution.

However I will note that the algorithm tutorials here have so far been tutorials for the set of function in qiskit.algorithms. You can can see in the two existing Grover tutorials that they are based on the Grover implementation from there. They are intended to be a learning path for the aspects of the Qiskit code. As such this tutorial does not really fit that pattern.

@a-matsuo @Cryoris Is this fixed point search something that can be done based on the Grover we have; or a modification to it. Or perhaps we would need a seperate FixedPointGrover algorithm. Either way such a tutorial would then be more applicable in the set of algorithm tutorials since it would be covering an algorithm that was supplied. Otherwise I am thinking perhaps this type of content might be more applicable as a contribution to the qiskit textbook.

[atithi8]

Hi Steve, Thank you very much for your response. I agree with your suggestions. Should I wait for @Cryoris and @a-matsuo to comment? I can try to write it in the textbook format and see if it fits in there. Otherwise, if I can modify this into the existing Grover class in qiskit.algorithms, will it be acceptable inside qiskit tutorials?

[a-matsuo]

Hi Steve and @atithi8, The fixed-point Grover search is considerably different from the original Grover search. We can not realize it with the current Grover class. The tutorial itself is very useful and instructive. So, I suggest making a separate FixedPointGrover class, and then add this tutorial. If making a separate FixedPointGrover class is a heavy burden, we can just try to put this to Qiskit text book (I'm not an administrator of Qiskit textbook, so I can not promise though).

[atithi8]

Thank you for the response. Although, I would like to write a separate class. It is a difficult task considering that I am aiming for this contribution to count towards the advocate application. Do I need to re-upload to the textbook repository? Since you have read it and found it instructive, is there a way for the message to be passed on to the textbook admin?

[woodsp-ibm]

@aasfaw Do you have any thoughts on this as a textbook piece?

@atithi8 Maybe even if it ends up being submitted as textbook piece perhaps you would like to still consider making an algorithm of the code like we have for the regular Grover as a submission afterwards.

[woodsp-ibm]

@frankharkins I had tagged Abe above for his opinion on this as a textbook piece, but have seen no response. In the meanwhile do you have any thoughts in this regard.

[atithi8]

Thank you so much @woodsp-ibm . Updates: I had emailed Abe a week ago and haven't heard back from him either. I have finished implementing the optimal version of the fixed-point search by Yoder et al. (where the quadratic speedup isn't lost). Depending on what I hear from the textbook reviewers, I will add/remove the second batch of content. Also, I will start working on making it a separate class just in case it becomes more suitable here, rather than in the textbook.

[woodsp-ibm]

@atithi8 Sure you're welcome. When talking about a standalone algorithm class I was imagining it being added alongside our existing grover here https://github.com/Qiskit/qiskit-terra/tree/main/qiskit/algorithms/amplitude_amplifiers. Having it implemented similar to Grover would hopefully allow either to be used in the context where an amplitude_amplifier is needed for an amplification_problem. A tutorial here would then use that algorithm, to show its capabilities etc, like we have the existing tutorials for Grover.

If you like you can create an Issue in qiskit-terra to add a FixedPointGrover and maybe outline it. That way any intial discussion can take place etc around that.

[woodsp-ibm]

@atithi8 Not sure whether you made any progress with things in regards of this tutorial. Since the time when you created this issue a new category textbook has been been created in this repo here. So maybe it could go there - would still be nice for a separate class/algorithm added to Terra though - in which case this tutorial could be revised to use that and this would indeed then be the right place for it.

[atithi8]

Thanks @woodsp-ibm for checking in.

1. I have attempted to build a separate class modifying the existing ones before a week, but I failed after coming close. I can explain the issues I am facing via email or zoom? It will appear lengthy here. Comment: The Yoder et al algorithm fixed-point implementation is more compatible with the Amplification problem class, and then using something like "amplify" as a method.
2. What are the options moving forward? Should I try posting this existing notebook in the new textbook module you have mentioned? Or, should I reupload 1 notebook containing both the existing algorithm along with Yoder's version?

[a-matsuo]

@atithi8 For your first question, how about making a draft PR (WIP PR) in qiskit terra? Then we can discuss it in the PR. I think it's easer and we can have more information in that way.

[woodsp-ibm]

@atithi8 If you have looked at the Grover algo we have in Terra, then that implements amplify I had imagined that what you were doing would fit with that as a new amplitude_amplifier algorithm alongside the Grover one that is currently there. A Draft PR as @a-matsuo suggests will allow others to look at the code and offer help/advice - you mark it Draft via github.

Shall we see how it works out with the algorithm in Terra as to how to proceed with the notebook?

[Eric-Arellano]

Closing this because we're very soon archiving this repository and moving all the tutorials to Qiskit Terra to be built directly when building our docs.

Also, we've now migrated algorithms into a dedicated repository: https://github.com/qiskit-community/qiskit-algorithms. It looks like FixedPointGrover hasn't been added yet. If you or anyone is still interested, we'd want to first add the class to the code in qiskit-algorithms, and then land this tutorial in that repo.

Thank you for making Qiskit better @atithi8!