Winning submission for QRISE 2024 - Microsoft Challenge

Video Description

In this research challenge you will implement one or several quantum algorithms and obtain and analyze the estimates of resources required for running them on fault tolerant quantum computers using the Microsoft Azure Quantum Resource Estimator.

Implementation of Regev’s algorithm for prime factorization and discrete logarithms. This project focuses on the quantum circuit for resource estimation purposes.

This repository contains some key primitives of Regev's algorithm:

• Gaussian state preperation
  • gaussian.qs: Simplest implementation that calls Q# library PreparePureStateD()
  • gaussian_mot.qs: Arbitrary state preparation by Möttönen et al.
  • gaussian_gr.qs: Uses Grover-Rudolph state preparation which is meant specifically for probability distributions
• Quantum modular exponentiation
  • binary_exp.qs: Binary exponentiation used in the original paper
  • fib_exp.qs: Fibonacci exponentiation introduced as an optimization by Ragavan et. al.