Algorithm Comparison

Detailed comparison of GreedyMethod vs TreeSA.

Quick Summary

Performance Benchmarks

Based on benchmark results from the Julia implementation (OMEinsumContractionOrders.jl):

3-Regular Graph (50 vertices, bond dim 2)

Result: TreeSA finds 1.5x faster, 40% less memory solution, taking 40-170x longer to optimize.

Matrix Chain (20 matrices)

Result: TreeSA is 1.2x faster, using 30x more optimization time.

Speed vs Quality Trade-off

                Quality
                   ↑
                   │
         TreeSA    │
        (thorough) │
                   │
         TreeSA    │
         (fast)    │
                   │
        Greedy     │
       (stochastic)│
                   │
        Greedy     │
      (default)    │
                   │
                   └──────────────→ Speed

When Each Algorithm Shines

GreedyMethod Excels

Problem Type: Chains and trees

# Chain: A×B×C×D×E
ixs = [[0,1], [1,2], [2,3], [3,4]]
out = [0,4]

# Greedy finds optimal order in O(n²)
tree = optimize_code(ixs, out, sizes, GreedyMethod())

Characteristics:

• Sequential structure
• No cycles
• Clear optimal pairing strategy

TreeSA Excels

Problem Type: Cycles and complex graphs

# Cycle graph (much harder!)
ixs = [[0,1,2], [2,3,4], [4,5,6], [6,7,0]]
out = [1,3,5,7]

# TreeSA explores better orderings
tree = optimize_code(ixs, out, sizes, TreeSA.fast())

Characteristics:

• Irregular connectivity
• Hyperedges (indices in 3+ tensors)
• Multiple reasonable orderings

Real-World Example: Quantum Circuit

Problem: 30-qubit quantum circuit, 50 gates

# Greedy result
tree_greedy = optimize_code(circuit_ixs, out, sizes, GreedyMethod())
comp_greedy = contraction_complexity(tree_greedy, circuit_ixs, sizes)
# tc: 2^42.3, sc: 2^28.1, time: 0.2s

# TreeSA result
tree_sa = optimize_code(circuit_ixs, out, sizes, TreeSA(ntrials=10, niters=50))
comp_sa = contraction_complexity(tree_sa, circuit_ixs, sizes)
# tc: 2^40.1, sc: 2^26.8, time: 15s

# Improvement
speedup = 2 ** (comp_greedy.tc - comp_sa.tc)  # 4.6x faster execution
memory_reduction = 2 ** (comp_greedy.sc - comp_sa.sc)  # 2.5x less memory

Verdict: TreeSA took 75x longer to optimize but found a solution that’s 4.6x faster to execute. If you’ll run the circuit 100+ times, TreeSA pays for itself.

Optimization Time vs Problem Size

GreedyMethod Scaling

Complexity: O(n² log n)

TreeSA Scaling

Complexity: O(ntrials × niters × n²)

Decision Guide

Start
  │
  ├─ Need results in <1 second? ──→ GreedyMethod
  │
  ├─ Problem is a chain/tree? ──→ GreedyMethod
  │
  ├─ Greedy result good enough? ──→ GreedyMethod
  │
  ├─ Have >1 minute to optimize? ──→ TreeSA
  │
  ├─ Complex graph structure? ──→ TreeSA
  │
  └─ Need best possible solution? ──→ TreeSA (thorough)

Hybrid Approach

Use both in sequence:

# 1. Quick baseline with greedy
tree_greedy = optimize_code(ixs, out, sizes, GreedyMethod())
comp_greedy = tree_greedy.complexity(ixs, sizes)
print(f"Greedy baseline: tc={comp_greedy.tc:.2f}")

# 2. If not good enough, refine with TreeSA
if comp_greedy.tc > 35.0:  # Too slow
    print("Refining with TreeSA...")
    tree_sa = optimize_code(ixs, out, sizes, TreeSA.fast())
    comp_sa = tree_sa.complexity(ixs, sizes)
    print(f"TreeSA result: tc={comp_sa.tc:.2f}")

    improvement = 2 ** (comp_greedy.tc - comp_sa.tc)
    print(f"Improvement: {improvement:.1f}x speedup")

Summary Recommendations

Next Steps

• Greedy Method - Details on greedy algorithm
• TreeSA - Details on simulated annealing
• Score Function - Tune for your hardware