Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create Bucket elimination algorithm #50

Closed
chaserileyroberts opened this issue May 15, 2019 · 1 comment
Closed

Create Bucket elimination algorithm #50

chaserileyroberts opened this issue May 15, 2019 · 1 comment
Assignees
Labels
enhancement New feature or request

Comments

@chaserileyroberts
Copy link
Contributor

Bucket elimination is a fast algorithm that works well for networks with small "tree width".

Positive examples include: TTN, quantum circuits, MPS, and MERA.

Negative examples include: SAT TensorNetwork.

Seeing how most of our work involves the former, we should implement this algorithm asap. @viathor has been working on a first version.

@viathor
Copy link
Collaborator

viathor commented Jun 3, 2019

Note that BE contractor exploits sparsity in the tensors by reducing the number of indices to range over in cases where terms corresponding to most index combinations are zero. This arises very often in quantum circuits where a lot of tensors are diagonal.

Treewidth sets the lower bound for contraction complexity.

This should work fairly well on quantum circuits and SAT tensor network. For the other types, a lot depends on the tensors, but note that performing SVD on an edge does introduce a diagonal tensor that BE contractor can exploit.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants