Code Monkey home page Code Monkey logo

quaspy's Introduction

Quaspy

Quaspy

The Quaspy (Quantum algorithm simulations in Python) library for Python3 contains modules that implement:

  • Simulators for the quantum part of Shor's order-finding algorithm [Shor94], modified as in [E22p], and the classical post-processing in [E22p] that recovers the order in a single run with very high success probability.

    Examples | Documentation | Open In Colab

  • Simulators for factoring general integers via order-finding, and the post-processing in [E21b] and [E22p] that factors any integer completely in a single order-finding run with very high success probability.

    Examples | Documentation | Open In Colab

  • Simulators for the quantum part of Shor's algorithm for computing general discrete logarithms [Shor94], modified as in [E19p], and the post-processing in [E19p] that recovers the logarithm given the order in a single run with very high probability of success.

    Examples | Documentation | Open In Colab

  • Simulators for the quantum part of Ekerå–Håstad's algorithm for computing short discrete logarithms [EH17], modified as in [E20] and [E23p], and the post-processing in [E23p] that recovers the logarithm in a single run with very high probability of success. This algorithm does not require the order to be known.

    Examples | Documentation | Open In Colab

  • Simulators for factoring RSA integers via short discrete logarithms, by using the reduction in [EH17], modified as in [E20] and [E23p], and the post-processing in [E23p] that factors random RSA integers in a single run with very high probability of success.

    Examples | Documentation | Open In Colab

All modules, classes, methods and functions in Quaspy are documented using Python3 docstrings.

Note that Quaspy does not implement support for tradeoffs in the aforementioned algorithms. Support for tradeoffs may potentially be added in the future. For the time being, see instead the Qunundrum repository with its suite of MPI programs. Note furthermore that portions of Quaspy are inherited from the Factoritall repository.

Quaspy is a work in progress, and may be subject to major changes without prior notice. Quaspy was developed for academic research purposes. It grew out of our research project in an organic manner as research questions were posed and answered. It is distributed "as is" without warranty of any kind, either expressed or implied. For further details, see the license.

Prerequisites

To install Python3 under Ubuntu 22.04 LTS, along with required dependencies, execute:

$ sudo apt install python3 python3-pip python3-venv
$ sudo apt install libgmp-dev libmpfr-dev libmpc-dev

For other Linux and Unix distributions, or operating systems, you may need to download Python3 and install it manually along with the required dependencies.

Installing the library

To install the Quaspy library, execute:

$ pip3 install dist/quaspy-0.9.3-py3-none-any.whl

You may also install Quaspy via Pip3 by executing:

$ pip3 install quaspy

Examples

For examples that illustrate how to use Quaspy, please see the examples directory.

See also the documentation for Quaspy for help on how to use the library.

About and acknowledgments

The Quaspy library was developed by Martin Ekerå, in part at KTH, the Royal Institute of Technology, in Stockholm, Sweden. Valuable comments and advice were provided by Johan Håstad throughout the development process.

Funding and support was provided by the Swedish NCSA that is a part of the Swedish Armed Forces.

quaspy's People

Contributors

ekera avatar

Stargazers

 avatar

Watchers

 avatar

quaspy's Issues

d = 0 when solving discrete logarithms with x = 1

Hi again,

when I try to solve DLPs with x = 1, e.g. 3^d = 1 mod 7 .

I would expect d = 6 as it is the smallest positive integer for r.

However, I receive d = 0.

Example output from my DLP circuit (3^d = 1 mod 7):
{'000 001': 125, '000 100': 209, '000 101': 122, '000 111': 130, '000 011': 127, '000 110': 52, '000 010': 67, '000 000': 168}

My code (it uses g^x = b convention):

from quaspy.logarithmfinding.general.postprocessing import solve_j_k_for_d_given_r

fail_count = 0
success_count = 0
x = -1

for (j, k, freq) in result_list: # note I converted it to [(j,k,freq)] correctly.
    x_cand = solve_j_k_for_d_given_r(j, k, n, 0, n, IntegerModRingMulSubgroupElement(g, p),
                                     IntegerModRingMulSubgroupElement(b, p), r)
    print(x_cand) # All solutions are 0 from Quaspy??
    if x_cand is not None and ((g ** x_cand) % p) == b:
        if x != -1:
            x = min(x, int(x_cand))
        else:
            x = int(x_cand)
        success_count += freq
    else:
        fail_count += freq

print("num_fail:", fail_count)
print("num_success:", success_count)
print({"x": x, "success_probability": success_count / shots})
print(f"x={x}")

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.