[WIP] Introduce `partitioned_contract`

[LinjianMa]

This PR is mainly used for discussion. We need to break it into pieces to merge.

APIs:

Given a partition par and its partial contraction tree contraction_tree, the function below performs the approximate contraction based on given parameters:

• ansatz: can be mps or comb
• approx_itensornetwork_alg: can be density_matrix or ttn_svd
• linear_ordering_alg: can be top_down or bottom_up. This denotes the heuristic used to choose the MPS site ordering.

function partitioned_contract(
  par::DataGraph,
  contraction_tree::NamedDiGraph;
  ansatz="mps",
  approx_itensornetwork_alg="density_matrix",
  cutoff=1e-15,
  maxdim=10000,
  swap_size=1,
  contraction_sequence_alg,
  contraction_sequence_kwargs,
  linear_ordering_alg,
)

Instead of passing a partition and a contraction tree, one can also passing a contraction_sequence, which is a nested vector of ITensors. par and contraction_tree will then be produced internally.

function partitioned_contract(contraction_sequence::Vector; kwargs...)

One can also choose to let the package generate the partition and the contraction tree automatically. Given tn, the function below will generate a par and contraction_tree based on the recursive bisection algorithm, with each partition having approximately nvertices_per_partition number of vertices.

function contract(
  alg::Algorithm"partitioned_contract",
  tn::AbstractITensorNetwork;
  nvertices_per_partition::Integer=2,
  backend::String="KaHyPar",
  kwargs...,
)

Organization of the PR

• examples/partitioned_contract contains codes to benchmark the algorithm. The implementations contain experiments on top of 3D grids, random regular graphs, and random quantum circuits.
• src/contract.jl includes the new API for contract.
• src/mincut.jl includes a new algorithm/heuristic for generating the binary tree structure and path graph structure. In particular, the existing algorithm is a bottom-up greedy algorithm, and another greedy top-down algorithm based on recursive bisection is added. The top-down algorithm is standard since recursive bisection is a common algorithm. For now it is unclear which one is better.
• src/partitioned_contract/partitioned_contract.jl includes the implementations of partitioned_contract

[codecov-commenter]

Codecov Report

Merging #97 (7e9ce10) into main (d1e9ba6) will decrease coverage by 10.89%. The diff coverage is 13.39%.

:exclamation: Your organization is not using the GitHub App Integration. As a result you may experience degraded service beginning May 15th. Please install the Github App Integration for your organization. Read more.

@@             Coverage Diff             @@
##             main      #97       +/-   ##
===========================================
- Coverage   79.64%   68.75%   -10.89%     
===========================================
  Files          64       69        +5     
  Lines        3507     4276      +769     
===========================================
+ Hits         2793     2940      +147     
- Misses        714     1336      +622     

Impacted Files	Coverage Δ
src/ITensorNetworks.jl	77.77% <ø> (ø)
src/approx_itensornetwork/ttn_svd.jl	100.00% <ø> (ø)
src/approx_itensornetwork/utils.jl	94.11% <ø> (ø)
src/contract.jl	36.84% <0.00%> (-63.16%)	:arrow_down:
src/partitioned_contract/adjacency_tree.jl	0.00% <0.00%> (ø)
src/partitioned_contract/constrained_ordering.jl	0.00% <0.00%> (ø)
src/partitioned_contract/partitioned_contract.jl	0.00% <0.00%> (ø)
src/partitioned_contract/utils.jl	0.00% <0.00%> (ø)
src/mincut.jl	82.52% <62.79%> (-11.93%)	:arrow_down:
src/approx_itensornetwork/density_matrix.jl	91.24% <65.71%> (-8.76%)	:arrow_down:
... and 2 more

... and 9 files with indirect coverage changes

[mtfishman]

Sorry for the very long delay in reviewing this, finally finding some time to take a look.

In terms of the API, instead of the partitioned_contract you propose above, what if it was the following:

function contract(
  alg::Algorithm"partitioned_contract",
  tn::AbstractITensorNetwork;
  sequence,
  backend::String="KaHyPar",
  kwargs...,
)

sequence would be a partial contraction sequence, by which I mean if the vertices are 1:10, it could be something like:

[[[1, 2, 3], [4, 5, 6]], [7, 8, 9, 10]]

This would complement the version that accepts nvertices_per_partition::Integer, which would generate a sequence with that format.