Solving Factoring problem with Ising machine

Introduction

Ising machines are powerful tools for solving SpinGlass problem. Given that many NP problems can be reduced to SpinGlass, it's possible to solve these NP problems with Ising machines. Among these problems, the Factoring problem is one of the most important problems and it's the basis of RSA encryption system for its practical hardness.

Therefore, solving Factoring problem with Ising machine is a significant task. In this example, we will show how to reduce the Factoring problem to SpinGlass with ProblemReductions.jl and solve it with an Ising machine solver GenericTensorNetworks.jl

Factoring -> SpinGlass -> Ising machine

Consider a simple Factoring problem: $6 = p \times q$, we need to figure out the prime factors of 6. In our package, the Factoring problem is modeling under binary representation and when we initialize an instance, we need to offer the information of the number of bits for the two factors. Here, since 6 is a 3 bit number, the number of bits for the two factors are both 2.

Run the following code in Julia REPL:

using ProblemReductions
factoring = Factoring(2, 2, 6) # initialize the Factoring problem

Factoring(2, 2, 6)

Using reduction_graph and reduction_paths, we could obtain the way to reduce Factoring to SpinGlass.

g = reduction_graph()
paths = reduction_paths(g,Factoring,SpinGlass)

1-element Vector{Vector{Type}}:
 [Factoring, CircuitSAT, SpinGlass]

The input of reduction_paths is the reduction graph and the types of source and target problems. And the output is a nested vector, each element of the outer vector is a path from source to target problem.

Then we could use implement_reduction_path to obtain the corresponding SpinGlass problem.

reduction_result = implement_reduction_path(paths[1], factoring)
target = target_problem(reduction_result)

SpinGlass{HyperGraph, Vector{Int64}}(HyperGraph(44, [[1, 2], [1, 3], [2, 3], [1], [2], [3], [4], [3, 4], [3, 5], [3, 6]  …  [38, 42], [36, 42], [42], [37, 43], [25, 43], [43], [42, 43], [42, 44], [43, 44], [44]]), [1, -2, -2, 2, 2, 0, 0, 1, -1, -2  …  -2, -2, -3, -2, -2, -3, 1, -2, -2, 1])

Note that the output of implement_reduction_path is a AbstractReductionResult, which contains the target problem and reduction information. So we need to extract the target problem by target_problem function.

import GenericTensorNetworks # import Ising machine solver
gtn_problem = GenericTensorNetworks.SpinGlass(
                  target.graph.n,
                  target.graph.edges,
                  target.weights
                )
result = GenericTensorNetworks.solve(
                    GenericTensorNetworks.GenericTensorNetwork(gtn_problem),
                    GenericTensorNetworks.SingleConfigMin()
                  )[]

(-92.0, GenericTensorNetworks.ConfigSampler{44, 1, 1}(01000000000000100000000001110010000011010000))ₜ

Here we use GenericTensorNetworks.jl to solve the SpinGlass problem and obtain the result, we need to extract the solution for source problem from the result.

extract_solution(reduction_result, 1 .- 2 .* Int.(GenericTensorNetworks.read_config(result)))

4-element Vector{Int64}:
 0
 1
 1
 1

The result is 01 and 11, decimally 2 and 3, which yields the correct factors of 6.

Conclusion

In this example, we show how to reduce Factoring problem to SpinGlass and solve it with Ising machine solver. This shows the power of ProblemReductions.jl in helping Problem Reduction.

For your convenience, here is how to use ProblemReductions.jl to reduce source problem to target problem:

• Initialize the source problem source = SourceProblem(...), ... is the parameters of the source problem.
• Obtain the reduction paths paths = reduction_paths(reduction_graph(), SourceProblem, TargetProblem).
• Implement the reduction path reduction_result = implement_reduction_path(paths[1], source).
• Extract the target problem target = target_problem(reduction_result).

This page was generated using Literate.jl.