Reference

Properties

• size
• cross_location
• source: (locs, graph, pins/auto)
• mapped: (locs, graph/auto, pins/auto)

Requires

1. equivalence in MIS-compact tropical tensor (you can check it with tests),
2. the size is <= [-2, 2] x [-2, 2] at the cross (not checked, requires cross offset information),
3. ancillas does not appear at the boundary (not checked),

Provides

1. visualization of mapping
2. the script for generating backward mapping (project/createmap.jl)
3. the script for tikz visualization (project/vizgadget.jl)

Properties

• size
• source: (locs, graph/auto, pins/auto)
• mapped: (locs, graph/auto, pins/auto)

Requires

1. equivalence in MIS-compact tropical tensor (you can check it with tests),
2. ancillas does not appear at the boundary (not checked),

embed_graph([mode,] g::SimpleGraph; vertex_order=MinhThiTrick())

Embed graph g into a unit disk grid, where the optional argument mode can be Weighted() or UnWeighted. The vertex_order can be a vector or one of the following inputs

* `Greedy()` fast but non-optimal.
* `MinhThiTrick()` slow but optimal.

map_config_back(map_result, config)

Map a solution config for the mapped MIS problem to a solution for the source problem.

map_configs_back(res::MappingResult, configs::AbstractVector)

Map MIS solutions for the mapped graph to a solution for the source graph.

map_factoring(M::Int, N::Int)

Setup a factoring circuit with M-bit q register (second input) and N-bit p register (first input). The m register size is (M+N-1), which stores the output. Call solve_factoring to solve a factoring problem with the mapping result.

map_graph([mode=UnWeighted(),] g::SimpleGraph; vertex_order=MinhThiTrick(), ruleset=[...])

Map a graph to a unit disk grid graph that being "equivalent" to the original graph, and return a MappingResult instance. Here "equivalent" means a maximum independent set in the grid graph can be mapped back to a maximum independent set of the original graph in polynomial time.

Positional Arguments

• mode is optional, it can be Weighted() (default) or UnWeighted().
• g is a graph instance, check the documentation of Graphs for details.

Keyword Arguments

• vertex_order specifies the order finding algorithm for vertices.

Different vertex orders have different path width, i.e. different depth of mapped grid graph. It can be a vector or one of the following inputs * Greedy() fast but not optimal. * MinhThiTrick() slow but optimal.

• ruleset specifies and extra set of optimization patterns (not the crossing patterns).

map_qubo(J::AbstractMatrix, h::AbstractVector) -> QUBOResult

Map a QUBO problem to a weighted MIS problem on a defected King's graph, where a QUBO problem is defined by the following Hamiltonian

\[E(z) = -\sum_{i<j} J_{ij} z_i z_j + \sum_i h_i z_i\]

A QUBO gadget is

⋅ ⋅ ● ⋅
● A B ⋅
⋅ C D ●
⋅ ● ⋅ ⋅

where A, B, C and D are weights of nodes that defined as

\[\begin{align} A = -J_{ij} + 4\\ B = J_{ij} + 4\\ C = J_{ij} + 4\\ D = -J_{ij} + 4 \end{align}\]

The rest nodes: ● have weights 2 (boundary nodes have weights $1 - h_i$).

map_qubo_restricted(coupling::AbstractVector) -> RestrictedQUBOResult

Map a nearest-neighbor restricted QUBO problem to a weighted MIS problem on a grid graph, where the QUBO problem can be specified by a vector of (i, j, i', j', J).

\[E(z) = -\sum_{(i,j)\in E} J_{ij} z_i z_j\]

A FM gadget is

- ⋅ + ⋅ ⋅ ⋅ + ⋅ -
⋅ ⋅ ⋅ ⋅ 4 ⋅ ⋅ ⋅ ⋅ 
+ ⋅ - ⋅ ⋅ ⋅ - ⋅ +

where +, - and 4 are weights of nodes +J, -J and 4J.

- ⋅ + ⋅ ⋅ ⋅ + ⋅ -
⋅ ⋅ ⋅ 4 ⋅ 4 ⋅ ⋅ ⋅ 
+ ⋅ - ⋅ ⋅ ⋅ - ⋅ +

map_qubo_square(coupling::AbstractVector, onsite::AbstractVector) -> SquareQUBOResult

Map a QUBO problem on square lattice to a weighted MIS problem on a grid graph, where the QUBO problem can be specified by

• a vector coupling of (i, j, i', j', J), s.t. (i', j') == (i, j+1) or (i', j') = (i+1, j).
• a vector of onsite term (i, j, h).

\[E(z) = -\sum_{(i,j)\in E} J_{ij} z_i z_j + h_i z_i\]

The gadget for suqare lattice QUBO problem is as follows

⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ 
○ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ○ 
⋅ ⋅ ⋅ ● ⋅ ● ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ○ ⋅ ⋅ ⋅ ⋅ 

where white circles have weight 1 and black circles have weight 2. The unit distance is 2.3.

map_simple_wmis(graph::SimpleGraph, weights::AbstractVector) -> WMISResult

Map a weighted MIS problem to a weighted MIS problem on a defected King's graph.

map_weights(r::MappingResult{WeightedNode}, source_weights)

Map the weights in the source graph to weights in the mapped graph, returns a vector.

multiplier()

Returns the multiplier as a SimpleGridGraph instance and a vector of pins. The logic gate constraints on pins are

• x1 + x2x3 + x4 == x5 + 2x7
• x2 == x6
• x3 == x8

solve_factoring(missolver, mres::FactoringResult, x::Int) -> (Int, Int)

Solve a factoring problem by solving the mapped weighted MIS problem on a unit disk grid graph. It returns (a, b) such that $a b = x$ holds. missolver(graph, weights) should return a vector of integers as the solution.

unit_disk_graph(locs::AbstractVector, unit::Real)

Create a unit disk graph with locations specified by locs and unit distance unit.