Computational complexity (WIP)

Input: A $n$ bit integer $x$.

Question: Is there a non-trivial factoring of $x$? i.e. $p \times q = x$ where $p>1$ and $q>1$ are integers.

Given a number and its factors, it is easy to verify that the factors are correct. However, finding the factors in the first place can be very difficult.

Example Given that $x > 1$ and $y > 1$ such that

\[x \times y = 2033\]

find $x$ and $y$.

Solving this problem is not easy. One simple algorithm is to iterate over all possible factors of $x$ and check if they are factors of $n$. The following Julia code shows how to factorize a number using this algorithm:

julia> function factorize(n)
           for x in 2:floor(Int, sqrt(n))
               if n % x == 0
                   return x, n ÷ x
               end
           end
           return nothing   # no factors found
       endfactorize (generic function with 1 method)
julia> factorize(2033)(19, 107)

This algorithm has a time complexity of $O(\sqrt{n})$. In terms of the number of bits of the input $m \approx \log_2(n)$, the time complexity is $O(2^{m/2})$, which is exponential in the input size.

Input: A Boolean circuit $C$.

Question: Is there an assignment of the inputs to the circuit that makes the output true?

Example Given a Boolean circuit

\[x_3 = (x_1 \lor x_2) \land (\neg (x_1 \land x_2))\]

where $\lor$ is the logical OR, $\land$ is the logical AND, and $\neg$ is the logical NOT. Find an assignment of the inputs $(x_1, x_2)$ that makes the output $x_3 = 1$.

It is easy to verify that the solution is given by the assignment $(x_1, x_2) = (1, 0)$ or $(x_1, x_2) = (0, 1)$. For larger circuits, the problem becomes harder to solve.

Input: A graph $G = (V, E)$ and a set of integer coupling strengths $J_{ij}$ for each edge $(i, j) \in E$.

Question: Is there a configuration of spins $\sigma_i \in \{-1, 1\}$ that has an energy below a certain threshold $E_t$? The energy of the system is given by

\[E(\sigma) = \sum_{(i,j)\in E} J_{ij} \sigma_i \sigma_j\]

The spin-glass problem is a problem in statistical mechanics and combinatorial optimization. It is a generalization of the Ising model, where the interactions between the spins are random. The goal is to find the ground state of the system, which is the configuration of spins that minimizes the energy of the system. This problem could be decomposed into finite yes/no questions - the decision problem above.

Example Given a spin-glass that defined on a Petersen graph, the coupling strength is 1. Consider that we use integer variables to store the coupling strength, the size of input is $O(n^2)$ for a general graph of size $n$. Determine whether the energy of the system is below -8?

Method 1: Generic tensor networks In the following, we use the generic tensor network approach to solve this problem.

julia> using GenericTensorNetworks, Graphs
julia> g = smallgraph(:petersen){10, 15} undirected simple Int64 graph
julia> J = ones(Int, 15)15-element Vector{Int64}:
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
julia> problem = SpinGlass(g, J)  # problem instanceGenericTensorNetworks.SpinGlass{Vector{Int64}}(10, [[1, 2], [1, 5], [1, 6], [2, 3], [2, 7], [3, 4], [3, 8], [4, 5], [4, 9], [5, 10]  …  [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1  …  0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
julia> tensor_network = GenericTensorNetwork(problem)  # the tensor network with optimized contraction orderGenericTensorNetworks.GenericTensorNetwork{GenericTensorNetworks.SpinGlass{Vector{Int64}}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}(GenericTensorNetworks.SpinGlass{Vector{Int64}}(10, [[1, 2], [1, 5], [1, 6], [2, 3], [2, 7], [3, 4], [3, 8], [4, 5], [4, 9], [5, 10]  …  [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1  …  0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3∘6∘8, 3∘6∘8 ->
├─ 3∘7∘5∘6, 5∘7∘8 -> 3∘6∘8
│  ├─ 3∘7∘5∘6, 3∘5∘6∘7 -> 3∘7∘5∘6
│  │  ├─ 1∘3∘7, 5∘6∘1 -> 3∘7∘5∘6
│  │  │  ├─ 1∘2, 3∘7∘2 -> 1∘3∘7
│  │  │  │  ├─ 2, 2∘1 -> 1∘2
│  │  │  │  │  ⋮
│  │  │  │  │
│  │  │  │  └─ 2∘3, 2∘7 -> 3∘7∘2
│  │  │  │     ⋮
│  │  │  │
│  │  │  └─ 1∘5, 1∘6 -> 5∘6∘1
│  │  │     ├─ 5, 1∘5 -> 1∘5
│  │  │     │  ⋮
│  │  │     │
│  │  │     └─ 6, 1∘6 -> 1∘6
│  │  │        ⋮
│  │  │
│  │  └─ 3∘5∘4, 4∘6∘7 -> 3∘5∘6∘7
│  │     ├─ 3∘4, 4∘5 -> 3∘5∘4
│  │     │  ├─ 4, 3∘4 -> 3∘4
│  │     │  │  ⋮
│  │     │  │
│  │     │  └─ 4∘5
│  │     └─ 4∘6∘9, 7∘9 -> 4∘6∘7
│  │        ├─ 4∘9, 6∘9 -> 4∘6∘9
│  │        │  ⋮
│  │        │
│  │        └─ 7∘9
│  └─ 5∘10, 7∘8∘10 -> 5∘7∘8
│     ├─ 10, 5∘10 -> 5∘10
│     │  ├─ 10
│     │  └─ 10, 5∘10 -> 5∘10
│     │     ├─ 10
│     │     └─ 5∘10
│     └─ 7∘10, 8∘10 -> 7∘8∘10
│        ├─ 7∘10
│        └─ 8∘10
└─ 3∘8, 6∘8 -> 3∘6∘8
   ├─ 8, 3∘8 -> 3∘8
   │  ├─ 8
   │  └─ 8, 3∘8 -> 3∘8
   │     ├─ 8
   │     └─ 3∘8
   └─ 6∘8
, Dict{Int64, Int64}())
julia> minimum_energy = solve(tensor_network, SizeMin())[]-9.0ₜ
julia> optimal_config = solve(tensor_network, SingleConfigMin())[](-9.0, GenericTensorNetworks.ConfigSampler{10, 1, 1}(0101111100))ₜ

The tensor network based algorithm has a time complexity of $O(2^{{\rm tw}(G)})$, which is exponential in the treewidth of the graph $G$ - a quantity that upper bounded by the number of vertices. For the Petersen graph, the treewidth is 4. Since in the worst case, the treewidth is $O(n)$, the time complexity is $O(2^n)$, which is exponential in the input size.

Method 2: Integer programming In the following, we use the integer programming approach to solve this problem.

# To be added

Many other algorithms can be used to solve the spin-glass problem. One good reference is the challenge in the GitGub repo: Deep Learning and Quantum Programming: A Spring School

Input: A graph $G = (V, E)$ and weights associated with vertices $\{\mu_{i} \mid i\in V\}$.

Question: Is there a configuration of particles $n_i \in \{0, 1\}$ that has a hard-core lattice gas energy below a certain threshold $E_t$? The hard-core lattice gas energy is given by

\[E(\mathbf n) = \sum_{(i,j)\in E} U_{ij} n_i n_j + \sum_{i\in V} \mu_i n_i\]

where $\mathbf n$ is the configuration of the particles, $n_i$ is the occupation number of site $i$, $U_{ij} \rightarrow \infty$ is the interaction strength between sites $i$ and $j$, and $\mu_i$ is the chemical potential at site $i$.

The hard-core lattice gas energy model describes a gas of particles on a lattice that interact via hard-core repulsion. Each lattice site $i \in V$ can be occupied by at most one particle, and two particles cannot occupy adjacent vertices.

It is a special case of the independent set problem, which asks what is the maximum set of mutually non-adjacent vertices on a graph. The only extra constraint is that the graph is a lattice graph. It turns out that the hard-core lattice gas model is also in NP-complete.

Example

Given a statement and a proof of the statement, it is easy to verify that the proof is correct. However, finding the proof in the first place can be very difficult. This is an example of a problem that can be verified in polynomial time, but may not be solvable in polynomial time.

Please check the demo package: https://github.com/GiggleLiu/ScientificComputingDemos/tree/main/Spinglass ^[Glover2019]. We first formulate the logic gates into QUBO penalty functions:

\[\begin{align*} &z = \neg x & \Leftrightarrow & \;2xy - x - z +1\\ &z = x_1 \lor x_2 & \Leftrightarrow & \;x_1x_2 + (x_1 + x_2)(1-2z) + z\\ &z = x_1 \land x_2 & \Leftrightarrow & \;x_1x_2 - 2(x_1 + x_2)z + 3z \end{align*}\]

Each variable can have boolean values $0$ or $1$. The ground state of the QUBO model corresponds to the solution of the original logic gates. The boolean variables can be mapped to spin variables $s_i = 1-2x_i$. The QUBO penalty functions can be mapped to the Ising model:

\[\begin{align*} &z = \neg x & \Leftrightarrow & \;s_1s_2\\ &z = x_1 \lor x_2 & \Leftrightarrow & \;s_1s_2 - (s_1 + s_2)(2s_z - 1) - 2s_z\\ &z = x_1 \land x_2 & \Leftrightarrow & \;s_1s_2 - (s_1 + s_2)(2s_z + 1) + 2s_z \end{align*}\]

In Ref.^[Nguyen2023], a universal set of weighted MIS gadgets are designed, which enables us to encode any Boolean constraint satisfaction problem to a weighted MIS problem. To further reduce the weighted MIS problem to that on a KSG, a pair of connected vertices must be made physically close to each other. This constraint can be fulfilled by introducing a crossing lattice, in which a vertex in the original graph is mapped to a chain or a tri-branched tree, namely the copy gadget. Copy gadgets are designed to copy the information of a vertex to the vicinity of other vertices, which enables us to equivalently add an edge between any two vertices. To further remove the non-unit-disk subgraphs like crossings from the crossing lattice, weighted crossing gadgets are introduced.

Given a graph $G$ with vertices and edges, find the largest independent set in the graph.

Solution

julia> using Graphs
julia> function mis1(g::SimpleGraph)
           N = nv(g)
           if N == 0
               return 0
           else
               dmin, vmin = findmin(v->degree(g, v), vertices(g))
               return 1 + mapreduce(y->mis1((gi = copy(g); rem_vertices!(gi, neighbors(g, y) ∪ [y]); gi)), max, neighbors(g, vmin) ∪ [vmin])
           end
       endmis1 (generic function with 1 method)
julia> mis1(smallgraph(:petersen))4

The algorithm has a time complexity of $O(2^n)$, which is exponential in the number of vertices in the graph. In the worst case, the algorithm may need to explore all possible subsets of vertices to find the largest independent set.