dwavesystems / dwavesystems/dimod

Add `factoring_circuit` or similar to generators

Open
#1,073 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Python
Stars
143
Forks
91
Avg merge
1h 24m
Merged PRs (30d)
3

Description

I wrote
```python
from typing import Optional, Tuple

import dimod
import numpy as np

from dwave.system import LeapHybridSampler

def factor(p: int,
*,
shape: Optional[Tuple[int, int]] = None,
sampler: Optional[dimod.Sampler] = None,
**kwargs
) -> Tuple[int, int]:
"""Factor p using a BQM sampler.

Args:
p: The number to be factored
shape: The shape of the multiplication circuit. If `p` needing `n` bits
to represent it, this defaults to ``(n-1, n-1)``.
sampler: The bqm sampler. Defaults to `LeapHybridSampler`.
**kwargs: Additional keyword arguments are passed to the sampler's
sample method.

Returns:
The factors. If no factor was found, returns ``(1, p)``.

"""

# convert p into a little-endian array of bits
parray = np.fromiter((int(b) for b in reversed(format(p, 'b'))), dtype=np.int8)

num_product_bits = parray.shape[0]

if shape is not None:
num_multiplier_bits, num_multiplicand_bits = shape
else:
# the worst case
num_multiplier_bits = num_product_bits // 2
num_multiplicand_bits = num_product_bits - 1

# get the BQM
bqm = dimod.generators.multiplication_circuit(num_multiplier_bits, num_multiplicand_bits)

# fix the product variables
bqm.fix_variables({f'p{i}': b for i, b in enumerate(parray)})
bqm.fix_variables({f'p{i}': 0 for i in range(len(parray), num_multiplicand_bits + num_multiplier_bits)})

# get a sampler
if sampler is None:
sampler = LeapHybridSampler()

# solve!
sampleset = sampler.sample(bqm, **kwargs).change_vartype('BINARY', inplace=True)

# see if we found a solution, otherwise return 1 and p
factors = (1, p)
for sample in sampleset.samples():
multiplier = int(''.join(str(sample[f'a{i}']) for i in reversed(range(num_multiplier_bits))), 2)
multiplicand = int(''.join(str(sample[f'b{i}']) for i in reversed(range(num_multiplicand_bits))), 2)

if multiplier * multiplicand == p:
factors = (multiplier, multiplicand)
break

return factors
```

for something unrelated, but we could wrap this functionality up in a generator or something.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.