search

microsoft / qsharp

Azure Quantum Development Kit, including the Q# programming language, resource estimator, and Quantum Katas
https://microsoft.github.io/qsharp/
MIT License
459 stars 91 forks source link

Request for Durr Hoyer Library #1928

Open mertall opened 1 month ago

mertall commented 1 month ago

Is your feature request related to a problem? Please describe.

I haven't seen an implementation of Durr Hoyer that is ready to use. I would like to contribute to a Q# Durr Hoyer library. I started this project as a Junior in Undergrad, almost 4 years ago. Past 4 years have been working on my SWE skills and after continued thought and iteration I came up with a quick and dirty implementation of Durr Hoyer Algorithm to find Min and Max. At the very least I think the logic will be educational for many people, I understood MSB comparison and how it relates to quantum information which for me was really cool to see.

Describe the solution you'd like

Eventually I would like to take this algorithm and also implement finding range, and median of unsorted database. Also do some actual experiments on quantum computer. I already have an idea of the Oracle functions that we would use for range or median. Still need to implement, will work on that next in azure quantum workspace.

Describe alternatives you've considered

I am considering more optimized methods like QESA which increase accuracy to nearly 100%. I replicated the logic for QESA here, which was about 3 years ago. The quantum operations in this repo are correct but I did not understand the quantum information steps to transform lists of numbers to qubits-- as I have in my current implantation in the Jupyter notebook. Also in the QESA, you will notice I have little experience in building unit tests and was still learning about these concepts. I aim to fully flush out the current Jupyter notebook and recognize there are too many hard coded variables that will need to be set as configurable. Ideally I separate most of the quantum logic in Q#, bring up abstraction for steps like calculating Grovers steps and higher level logic in Python, accessing base operations stored in a namespace. For now, I was just trying to get something to go brrr.

Additional context I have attached my current Jupyter notebook file, which was ran in Azure quantum Workspace DurrHoyerImplementation.ipynb.zip

sezna commented 1 month ago

We would love to see this! If you encapsulate the algorithmic logic in a Q# project, we can certainly put together a Q# library for it, and I would be happy to assist you in that!

billti commented 1 month ago

FYI if not familiar, here's the docs and creating projects that reference other projects <https://learn.microsoft.com/en-us/azure/quantum/how-to-work-with-qsharp-projects?tabs=tabid-qsharp%2Ctabid-qsharp-run#example-external-project>>

mertall commented 1 month ago

@zesna I will begin work to encapsulate this in a Q# project. @billti that was my next question. Thank you!

Thank you so much for the opportunity!! This has been a long and rewarding journey. I'm excited to get this across for other users!

mertall commented 1 month ago

I created a Github repo with a Q# project. Please advise on next steps to integrate with Q#... should I be cloning Q# and finding a good place for this code? Thank you for your patience.

https://github.com/mertall/DurrHoyerLibrary/tree/main

EDIT: thinking out loud here. Clone Q#, find a good place (May be best if y'all tell me best place in your opinion), make sure unit tests run with code in Q# repo, and then create PR...

Manvi-Agrawal commented 1 month ago

Nice Addition to Q# library. Please feel free to reach out in case of any further questions.

Please advise on next steps to integrate with Q#... should I be cloning Q# and finding a good place for this code? Thank you for your patience.

Finding a good place: As per my current understanding official Q# samples are supposed to be hosted here in this repo. Although, users are welcome to host Q# samples in their own repositories too. This is being tracked currently by #1934

EDIT: thinking out loud here. Clone Q#, find a good place (May be best if y'all tell me best place in your opinion), make sure unit tests run with code in Q# repo, and then create PR...

Plan sounds good to me. I had a brief look at the tests in the github repo shared earlier. They are just printing evaluated values to the console. I think you might find the following folders helpful samples/testing, samples/python_interop.

@sezna, @billti Thoghts?

mertall commented 1 month ago

@Manvi-Agrawal I have created a branch and have a commit ready, but it is not allowing to me to push anything to my branch giving me access denied. How should I proceed?

Edit: is perferred pattern for committing me forking repo and then cloning?

Manvi-Agrawal commented 1 month ago

Edit: is perferred pattern for committing me forking repo and then cloning?

Yes @mertall , You got this right. This might help: forking a repo and create PR from fork.

mertall commented 1 month ago

Doh! Thanks for reminding me about PRs with forks, totally forgot about that. PR is up for review! Thank you all! Looking forward to the review process :D

mertall commented 1 month ago

Any thoughts on adding this algorithm as a sample in Q#?

sezna commented 1 month ago

Pinging @swernli, @billti, and @cesarzc for their thoughts on sample-hood

swernli commented 1 month ago

I think once we have #1932 merged, adding links there for both the library and the sample in your repo would be good. We could even provide the qsharp.json snippets for pulling in the library from a well-known commit that way folks have an easy way to copy-paste and build from your work. I think merging the usage samples into the samples folder under the qsharp repo might be better suited to part of the stabilization process if/when that takes places, so that the samples and code live together.

mertall commented 1 month ago

thank you for the feedback team!

curious, what does the process of stabilization entail? Are there tasks to be checked off? Or certain amount of time to pass?Thanks for your patience while I understand these dev standards.

sezna commented 1 week ago

Hi @mertall! I apologize for the delayed response here. There's not a particularly formal process (yet) as the Q# ecosystem is nascent. But what we'd like to see is:

  1. A working, tested, library with an API that you think is reasonable, published by you under your own GitHub name
  2. A PR adding your library to our markdown document listing known libraries.
  3. An issue detailing why it should be included in the standard library (significant ecosystem impact, generally necessary for quantum code, etc) Just today I filed #2013 which adds a new library to our repository. It is a good template for what a Q# library looks like, and you could even use Qtest to write tests for your library in Q#.

Feel free to respond to this issue and I can provide any clarification or help -- we also hang out in the #qdk channel in the Unitary Fund discord, if you'd prefer to chat that way.