# US 2021/0334690 A1 · Methods and systems for tensor network contraction based on hypergraph decomposition and parameter optimization

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0334690 A1
- Document ID: US20210334690A1
- Status: Published application
- Kind: A1
- Application number: 17/238,870
- Filed: 2021-04-23
- Published: 2021-10-28
- Earliest claimed: 2020-04-24
- Assignees: Alibaba Group Holding Limited
- Applicants: Alibaba Group Holding Limited
- Inventors: Jiachen Huang; Jianxin Chen
- Web page: https://patentgrep.com/patent/US20210334690A1

## CPC

- G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
- G06F 18/214: Generating training patterns; Bootstrap methods, e.g. bagging or boosting
- G06F 18/2323: based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
- G06N 5/022: Knowledge engineering; Knowledge acquisition
- G06N 10/80: Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and systems for tensor network contraction are provided. A method implemented by a computing host includes obtaining a plurality of tensor nodes associated with a tensor network and a plurality of indices respectively associated with the plurality of tensor nodes; generating a graph associated with the tensor network, wherein the plurality of tensor nodes correspond to a plurality of vertices of the graph and the plurality of indices correspond to a plurality of edges of the graph, respectively; decomposing the graph into a plurality of sub-graphs; and for each sub-graph of the plurality of sub-graphs, iteratively decomposing a current sub-graph into a plurality of next-tier sub-graphs until a size of each of the plurality of next-tier sub-graphs is less than a pre-set threshold.

## Claims

### Claim 1

A method implemented by a computing host, the method comprising:
obtaining a plurality of tensor nodes associated with a tensor network and a plurality of indices respectively associated with the plurality of tensor nodes;
generating a graph associated with the tensor network, wherein the plurality of tensor nodes correspond to a plurality of vertices of the graph and the plurality of indices correspond to a plurality of edges of the graph, respectively;
decomposing the graph into a plurality of sub-graphs; and
for each sub-graph of the plurality of sub-graphs, iteratively decomposing a current sub-graph into a plurality of next-tier sub-graphs until a size of each of the plurality of next-tier sub-graphs is less than a pre-set threshold.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating a plurality of contraction trees associated with the tensor network based on the plurality of next-tier sub-graphs, wherein individual contraction tree includes a set of vertices being traversed in a respective next-tier sub-graph and indices associated with the set of vertices.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
decomposing the graph into the plurality of sub-graphs using a multi-partite decomposition algorithm.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
optimizing one or more first parameters associated with the multi-partite decomposition algorithm.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
iteratively decomposing the current sub-graph into a plurality of next-tier sub-graphs using a bipartition decomposition algorithm.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
optimizing one or more second parameters associated with the bipartition decomposition algorithm.

### Claim 7 (depends on 1)

The method of claim 1, wherein iteratively decomposing a current sub-graph into a plurality of next-tier sub-graphs until a size of each of the plurality of next-tier sub-graphs is less than a pre-set threshold further comprises:
determining that a first index of one or more first indices associated with a first node has a same dimension as a second index of one or more second indices associated with a second node in at least one of the plurality of next-tier sub-graphs;
contracting the first node and the second node to form a third node;
computing a count of nodes in the at least one of the plurality of next-tier sub-graphs; and
determining the count of nodes is less than the pre-set threshold.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
generating one or more third indices associated with the third node based on the one or more first indices and the one or more second indices.

### Claim 9 (depends on 2)

The method of claim 2, further comprising:
computing costs associated with the plurality of contraction trees;
determining whether the cost associated with at least one contraction tree satisfies a pre-set condition;
if the cost associated with at least one contraction tree satisfies the pre-set condition, outputting the at least one contraction tree as an optimal contraction tree; and
if the cost associated with at least one contraction tree does not satisfy the pre-set condition,
adjusting one or more parameters associated with decomposing the graph into a plurality of sub-graphs, iteratively decomposing the graph to generate at least one updated contraction tree until the pre-set condition is satisfied, and outputting the updated contraction tree as the optimal contraction tree.

### Claim 10 (depends on 9)

The method of claim 9, wherein the one or more parameters are associated with at least one of a multi-partite decomposition algorithm and a bipartition decomposition algorithm.

### Claim 11

A system comprising:
one or more processors, and
memory communicatively coupled to the one or more processors, the memory storing computer-executable modules executable by the one or more processors that, when executed by the one or more processors, perform actions including:
obtaining a plurality of tensor nodes associated with a tensor network and a plurality of indices respectively associated with the plurality of tensor nodes;
generating a graph associated with the tensor network, wherein the plurality of tensor nodes correspond to a plurality of vertices of the graph and the plurality of indices correspond to a plurality of edges of the graph, respectively;
decomposing the graph into a plurality of sub-graphs; and
for each sub-graph of the plurality of sub-graphs, iteratively decomposing a current sub-graph into a plurality of next-tier sub-graphs until a size of each of the plurality of next-tier sub-graphs is less than a pre-set threshold.

### Claim 12 (depends on 11)

The system of claim 11, wherein the actions further comprise:
generating a plurality of contraction trees associated with the tensor network based on the plurality of next-tier sub-graphs,
wherein individual contraction tree includes a set of vertices being traversed in a respective next-tier sub-graph and indices associated with the set of vertices.

### Claim 13 (depends on 12)

The system of claim 12, wherein the actions further comprise:
computing costs associated with the plurality of contraction trees;
determining whether the cost associated with at least one contraction tree satisfies a pre-set condition;
if the cost associated with at least one contraction tree satisfies the pre-set condition, outputting the at least one contraction tree as an optimal contraction tree; and
if the cost associated with at least one contraction tree does not satisfy the pre-set condition,
adjusting one or more parameters associated with decomposing the graph into a plurality of sub-graphs,
iteratively decomposing the graph to generate at least one updated contraction tree until the pre-set condition is satisfied, and
outputting the updated contraction tree as the optimal contraction tree.

### Claim 14 (depends on 13)

The system of claim 13, wherein the one or more parameters are associated with at least one of a multi-partite decomposition algorithm and a bipartition decomposition algorithm.

### Claim 15 (depends on 11)

The system of claim 11, wherein the actions further comprise:
decomposing the graph into the plurality of sub-graphs using a multi-partite decomposition algorithm; and
iteratively decomposing the current sub-graph into a plurality of next-tier sub-graphs using a bipartition decomposition algorithm.

### Claim 16

A computer-readable storage medium storing computer-readable instructions executable by one or more processors of a video compression system, that when executed by the one or more processors, cause the one or more processors to perform actions comprising:
obtaining a plurality of tensor nodes associated with a tensor network and a plurality of indices respectively associated with the plurality of tensor nodes;
generating a graph associated with the tensor network, wherein the plurality of tensor nodes correspond to a plurality of vertices of the graph and the plurality of indices correspond to a plurality of edges of the graph, respectively;
decomposing the graph into a plurality of sub-graphs; and
for each sub-graph of the plurality of sub-graphs, iteratively decomposing a current sub-graph into a plurality of next-tier sub-graphs until a size of each of the plurality of next-tier sub-graphs is less than a pre-set threshold.

### Claim 17 (depends on 16)

The computer—readable storage medium of claim 16, wherein the actions further comprise:
generating a plurality of contraction trees associated with the tensor network based on the plurality of next-tier sub-graphs,
wherein individual contraction tree includes a set of vertices being traversed in a respective next-tier sub-graph and indices associated with the set of vertices.

### Claim 18 (depends on 17)

The computer—readable storage medium of claim 17, wherein the actions further comprise:
computing costs associated with the plurality of contraction trees;
determining whether the cost associated with at least one contraction tree satisfies a pre-set condition;
if the cost associated with at least one contraction tree satisfies the pre-set condition, outputting the at least one contraction tree as an optimal contraction tree; and
if the cost associated with at least one contraction tree does not satisfy the pre-set condition,
adjusting one or more parameters associated with decomposing the graph into a plurality of sub-graphs,
iteratively decomposing the graph to generate at least one updated contraction tree until the pre-set condition is satisfied, and
outputting the updated contraction tree as the optimal contraction tree.

### Claim 19 (depends on 18)

The system of claim 18, wherein the one or more parameters are associated with at least one of a multi-partite decomposition algorithm and a bipartition decomposition algorithm.

### Claim 20 (depends on 16)

The system of claim 16, wherein the actions further comprise:
decomposing the graph into the plurality of sub-graphs using a multi-partite decomposition algorithm; and
iteratively decomposing the current sub-graph into a plurality of next-tier sub-graphs using a bipartition decomposition algorithm.
