Skip to content

TensorBFS/OMEinsumContractionOrders.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

OMEinsumContractionOrders

This package provides optimize_code function for finding tensor network contraction orders.

Build Status codecov

Installation

OMEinsumContractionOrders is a Julia Language package. To install OMEinsumContractionOrders, please open Julia's interactive session (known as REPL) and press ] key in the REPL to use the package mode, then type the following command

For stable release

pkg> add OMEinsumContractionOrders
pkg> add KaHyPar

The KaHyPar package (used in KaHyParBipartite optimizer) is optional because some one may have the binary issue, check this and this.

Example

Contract a tensor network

julia> using OMEinsum, OMEinsumContractionOrders, Graphs, KaHyPar

julia> function random_regular_eincode(n, k; optimize=nothing)
	    g = Graphs.random_regular_graph(n, k)
	    ixs = [minmax(e.src,e.dst) for e in Graphs.edges(g)]
	    return EinCode((ixs..., [(i,) for i in Graphs.vertices(g)]...), ())
    end
    
julia> code = random_regular_eincode(200, 3);

julia> optcode_tree = optimize_code(code, uniformsize(code, 2), TreeSA(sc_target=28, βs=0.1:0.1:10,
								ntrials=2, niters=100, sc_weight=3.0));

julia> optcode_tree_with_slice = optimize_code(code, uniformsize(code, 2), TreeSA(sc_target=28, βs=0.1:0.1:10, 
							ntrials=2, niters=100, sc_weight=3.0, nslices=5));

julia> optcode_kahypar = optimize_code(code, uniformsize(code, 2), KaHyParBipartite(sc_target=30, max_group_size=50));

julia> optcode_sa = optimize_code(code, uniformsize(code, 2), SABipartite(sc_target=30, max_group_size=50));

julia> OMEinsum.timespace_complexity(code, uniformsize(code, 2))
(200.0, 0.0)

julia> OMEinsum.timespace_complexity(optcode_kahypar, uniformsize(code, 2))
(39.00774639886569, 28.0)

julia> OMEinsum.timespace_complexity(optcode_sa, uniformsize(code, 2))
(39.09524927371961, 28.0)

julia> tc, sc = OMEinsum.timespace_complexity(optcode_tree, uniformsize(code, 2))
(31.13883492534964, 27.0)

julia> tc, sc = OMEinsum.timespace_complexity(optcode_tree_with_slice, uniformsize(code, 2))
(31.292828948918775, 22.0)

Acknowledge OMEinsum/OMEinsumContractionOrders

Since we do not have a paper to cite, we wish anyone who finds this package useful in his research can post a comment under this issue: #21

References

If you find this package useful in your research, please cite the following papers

To credit the KaHyParBipartite and SABipartite method,

@misc{Pan2021,
      title={Simulating the Sycamore quantum supremacy circuits}, 
      author={Feng Pan and Pan Zhang},
      year={2021},
      eprint={2103.03074},
      archivePrefix={arXiv},
      primaryClass={quant-ph}
}

To credit the KaHyParBipartite method,

@Article{10.21468/SciPostPhys.7.5.060,
	title={{Fast counting with tensor networks}},
	author={Stefanos Kourtis and Claudio Chamon and Eduardo R. Mucciolo and Andrei E. Ruckenstein},
	journal={SciPost Phys.},
	volume={7},
	issue={5},
	pages={60},
	year={2019},
	publisher={SciPost},
	doi={10.21468/SciPostPhys.7.5.060},
	url={https://scipost.org/10.21468/SciPostPhys.7.5.060},
}
@article{Gray2021,
   title={Hyper-optimized tensor network contraction},
   volume={5},
   ISSN={2521-327X},
   url={http://dx.doi.org/10.22331/q-2021-03-15-410},
   DOI={10.22331/q-2021-03-15-410},
   journal={Quantum},
   publisher={Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften},
   author={Gray, Johnnie and Kourtis, Stefanos},
   year={2021},
   month={Mar},
   pages={410}
}

To credit the TreeSA method,

@misc{kalachev2021recursive,
      title={Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits}, 
      author={Gleb Kalachev and Pavel Panteleev and Man-Hong Yung},
      year={2021},
      eprint={2108.05665},
      archivePrefix={arXiv},
      primaryClass={quant-ph}
}

Multi-GPU computation

Check this Gist:

https://gist.github.com/GiggleLiu/d5b66c9883f0c5df41a440589983ab99

Authors

Jin-Guo Liu and Pan Zhang