Giter VIP home page Giter VIP logo

factoring-notebook's Introduction

Open in GitHub Codespaces Linux/Mac/Windows build status

Factoring

This notebook explains the quantum processing unit (QPU) programming model used for factoring, and shows how to implement it.

The notebook has the following sections:

  1. Factoring as a Constraint Satisfaction Problem describes the factoring problem as an example CSP.
  2. Formulating the Problem for a D-Wave Quantum Computer shows how such CSPs can be formulated for solution on a quantum computer.
  3. A Simple Example codes a small CSP to clarify the solution technique.
  4. Factoring on the Quantum Computer codes a factoring problem for solution on a D-Wave quantum computer.
  5. Further Information details some points touched on in previous sections and examines more closely the results returned from the quantum computer.

Factoring as a Constraint Satisfaction Problem

The complexity class for classical integer factoring is believed to be between P and NP-hard. Although research has yielded algorithms that perform faster than the intuitive trial division, including Fermat's algorithm, Pollard's two algorithms, and sieve algorithms, it's still an open question whether a classical algorithm exists that can factor in polynomial time. For quantum computing, Shor's algorithm runs in polynomial time (D-Wave quantum computers do not run this algorithm).

This notebook solves factoring on a D-Wave quantum computer by formulating it as a constraint satisfaction problem. CSPs require that all a problem's variables be assigned values that result in the satisfying of all constraints. For factoring, the problem's constraints are that the two variables representing factors, a and b, be assigned only natural numbers and that their multiplication be equal to the factored number, P.

circuit

Installation

You can run this example without installation in cloud-based IDEs that support the Development Containers specification (aka "devcontainers").

For development environments that do not support devcontainers, install requirements:

pip install -r requirements.txt

If you are cloning the repo to your local system, working in a virtual environment is recommended.

Usage

Your development environment should be configured to access Leap’s Solvers. You can see information about supported IDEs and authorizing access to your Leap account here.

The notebook can be opened by clicking on the 01-factoring-overview.ipynb file in VS Code-based IDEs.

To run a locally installed notebook:

jupyter notebook

License

Released under the Apache License 2.0. See LICENSE file.

factoring-notebook's People

Contributors

arcondello avatar joelpasvolsky avatar randomir avatar tcnleung avatar tleungdwave avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar

factoring-notebook's Issues

Add tests

This repo needs tests, and to be hooked into circle-ci.

Requirements file

Needs bokeh:

dwave-ocean-sdk==2.1.1

jupyter
jupyter_contrib_nbextensions==0.5.1
autopep8==1.3.2
bokeh==0.12.15

dbc.stitch(and_csp)

On colab, I copy over the file dwave-examples/factoring-notebook/blob/master/01-factoring-overview.ipynb from your github, though the open menu.

I insert a code cell at the top with:

!pip install dwave-ocean-sdk
!pip install dwavebinarycsp[maxgap]

(the second line is suggested by an error if the notebook is run without it)

I restart the runtime from the cell on colab, as per instructions from pip.

When I run the rest of the notebook, it hangs on:
and_bqm = dbc.stitch(and_csp)

With the following messages:

VisibleDeprecationWarning Traceback (most recent call last)
in ()
----> 1 and_bqm = dbc.stitch(and_csp)
2 and_bqm.remove_offset()
3
4 print("Linear coefficients:\n\t{}".format(
5 {key: round(val, 2) for key, val in and_bqm.linear.items()}))

10 frames
/usr/local/lib/python3.7/dist-packages/dwavebinarycsp/compilers/stitcher.py in stitch(csp, min_classical_gap, max_graph_size)
180 # try to use the penaltymodel ecosystem
181 try:
--> 182 pmodel = pm.get_penalty_model(spec)
183 except pm.ImpossiblePenaltyModel:
184 # hopefully adding more variables will make it possible

/usr/local/lib/python3.7/dist-packages/penaltymodel/core/interface.py in get_penalty_model(specification)
71 for factory in iter_factories():
72 try:
---> 73 pm = factory(specification)
74 except ImpossiblePenaltyModel as e:
75 # information about impossible models should be propagated

/usr/local/lib/python3.7/dist-packages/penaltymodel/lp/interface.py in get_penalty_model(specification)
57 linear_energy_ranges=specification.ising_linear_ranges,
58 quadratic_energy_ranges=quadratic_ranges,
---> 59 min_classical_gap=specification.min_classical_gap)
60 except ValueError:
61 raise pm.exceptions.FactoryException("Specification is for too large of a model")

/usr/local/lib/python3.7/dist-packages/penaltymodel/lp/generation.py in generate_bqm(graph, table, decision_variables, linear_energy_ranges, quadratic_energy_ranges, min_classical_gap, catch_warnings)
176 try:
177 result = linprog(cost_weights.flatten(), A_eq=noted_matrix, b_eq=noted_bound,
--> 178 A_ub=unnoted_matrix, b_ub=unnoted_bound, bounds=bounds)
179 except (OptimizeWarning, LinAlgWarning) as e:
180 raise ValueError('Penaltymodel-lp has a bad matrix')

/usr/local/lib/python3.7/dist-packages/scipy/optimize/_linprog.py in linprog(c, A_ub, b_ub, A_eq, b_eq, bounds, method, callback, options, x0)
552 x, status, message, iteration = _linprog_ip(
553 c, c0=c0, A=A, b=b, callback=callback,
--> 554 postsolve_args=postsolve_args, **solver_options)
555 elif meth == 'revised simplex':
556 x, status, message, iteration = _linprog_rs(

/usr/local/lib/python3.7/dist-packages/scipy/optimize/_linprog_ip.py in _linprog_ip(c, c0, A, b, callback, postsolve_args, maxiter, tol, disp, alpha0, beta, sparse, lstsq, sym_pos, cholesky, pc, ip, permc_spec, **unknown_options)
1123 lstsq, sym_pos, cholesky,
1124 pc, ip, permc_spec, callback,
-> 1125 postsolve_args)
1126
1127 return x, status, message, iteration

/usr/local/lib/python3.7/dist-packages/scipy/optimize/_linprog_ip.py in _ip_hsd(A, b, c, c0, alpha0, beta, maxiter, disp, tol, sparse, lstsq, sym_pos, cholesky, pc, ip, permc_spec, callback, postsolve_args)
753 d_x, d_y, d_z, d_tau, d_kappa = _get_delta(
754 A, b, c, x, y, z, tau, kappa, gamma, eta,
--> 755 sparse, lstsq, sym_pos, cholesky, pc, ip, permc_spec)
756
757 if ip: # initial point

/usr/local/lib/python3.7/dist-packages/scipy/optimize/_linprog_ip.py in _get_delta(A, b, c, x, y, z, tau, kappa, gamma, eta, sparse, lstsq, sym_pos, cholesky, pc, ip, permc_spec)
319
320 # [4] 8.12 and "Let alpha be the maximal possible step..." before 8.23
--> 321 alpha = _get_step(x, d_x, z, d_z, tau, d_tau, kappa, d_kappa, 1)
322 if ip: # initial point - see [4] 4.4
323 gamma = 10

/usr/local/lib/python3.7/dist-packages/scipy/optimize/_linprog_ip.py in _get_step(x, d_x, z, d_z, tau, d_tau, kappa, d_kappa, alpha0)
372 alpha_z = alpha0 * np.min(z[i_z] / -d_z[i_z]) if np.any(i_z) else 1
373 alpha_kappa = alpha0 * kappa / -d_kappa if d_kappa < 0 else 1
--> 374 alpha = np.min([1, alpha_x, alpha_tau, alpha_z, alpha_kappa])
375 return alpha
376

<array_function internals> in amin(*args, **kwargs)

/usr/local/lib/python3.7/dist-packages/numpy/core/fromnumeric.py in amin(a, axis, out, keepdims, initial, where)
2829 """
2830 return _wrapreduction(a, np.minimum, 'min', axis, None, out,
-> 2831 keepdims=keepdims, initial=initial, where=where)
2832
2833

/usr/local/lib/python3.7/dist-packages/numpy/core/fromnumeric.py in _wrapreduction(obj, ufunc, method, axis, dtype, out, **kwargs)
85 return reduction(axis=axis, out=out, **passkwargs)
86
---> 87 return ufunc.reduce(obj, axis, dtype, out, **passkwargs)
88
89

VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray

** I get identical errors using dwavebinarycsp.stitch on my own PC as well.

Is this a code issue, or human error on my part?

Thanks!

Update to new bokeh version

Currently we pin to bokeh===0.12.15, it would be nice to update to the latest, 2.2.2.
However, 2.2.2 does not support Python 3.5. The previous version, which does support 3.5, is 1.4.0. Unfortunately, between 1.4.0 and 2.2.2 there is a deprecation that affects this JN: "Importing from_networkx from bokeh.models.graphs is deprecated. Import from bokeh.plotting instead."
So better to wait till after 3.5 is no longer supported.

See dwavesystems/dwave-ocean-sdk#91

I have the code change here for when we do: https://github.com/JoelPasvolsky/factoring-notebook/tree/bokeh

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.