microsoft / microsoft/qdk

Request for Durr Hoyer Library

Open
#1,928 13 comments 0 reactions 1 assignee View on GitHub

@mertall is already working on this.

Since Sep 24, 2024.

library
Dominant language
Rust
Stars
1k
Forks
212
Avg merge
3d 8h
Merged PRs (30d)
65

Description

**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](https://arxiv.org/pdf/1908.07943) which increase accuracy to nearly 100%. I replicated the logic for QESA [here](https://github.com/mertall/DurrHoyerLibrary/blob/master/library/QMSA.py), 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](https://github.com/user-attachments/files/17107727/DurrHoyerImplementation.ipynb.zip)

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.