sublinear 0.3.1

High-performance sublinear-time solver for asymmetric diagonally dominant systems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

# Quantum Algorithms for Sublinear Linear Systems

## Executive Summary

Quantum computing offers potential exponential speedups for linear system solving through algorithms that exploit quantum superposition and entanglement. This research plan explores the intersection of quantum algorithms with our sublinear-time classical solvers.

## Core Research Areas

### 1. HHL Algorithm (Harrow-Hassidim-Lloyd)
- **Complexity**: O(log n · κ² · 1/ε) where κ is condition number
- **Key insight**: Exponential speedup for sparse, well-conditioned matrices
- **Challenge**: Quantum state preparation and measurement

### 2. Quantum-Inspired Classical Algorithms
Recent breakthroughs show classical algorithms can achieve similar speedups:
- Tang 2018: Dequantized recommendation systems
- Gilyén et al. 2018: Quantum-inspired sublinear algorithms
- **Our opportunity**: Combine with diagonal dominance for enhanced performance

### 3. Variational Quantum Linear Solver (VQLS)
- Near-term quantum devices (NISQ era)
- Hybrid quantum-classical approach
- **Application**: Small subproblems in our solver hierarchy

## Implementation Plan

### Phase 1: Theoretical Foundation
1. Map diagonal dominance to quantum advantage regimes
2. Identify quantum speedup boundaries
3. Develop hybrid quantum-classical protocols

### Phase 2: Quantum-Inspired Classical
1. Implement sampling-based linear solvers
2. Use quantum-inspired techniques for:
   - Matrix inversion via sampling
   - Low-rank approximations
   - Spectral sparsification

### Phase 3: Actual Quantum Implementation
1. VQLS for small dense subproblems
2. HHL for sparse components
3. Error mitigation strategies

## Key Papers

1. **Harrow, Hassidim, Lloyd (2009)**: "Quantum algorithm for linear systems of equations"
   - Original HHL algorithm
   - arXiv:0811.3171

2. **Tang (2018)**: "A quantum-inspired classical algorithm for recommendation systems"
   - Dequantization breakthrough
   - arXiv:1807.04271

3. **Chakraborty et al. (2018)**: "The power of block-encoded matrix powers"
   - Block encoding techniques
   - arXiv:1804.01973

4. **Bravo-Prieto et al. (2019)**: "Variational Quantum Linear Solver"
   - NISQ-friendly approach
   - arXiv:1909.05820

5. **Childs et al. (2017)**: "Quantum algorithm for systems of linear equations with exponentially improved dependence on precision"
   - Improved HHL
   - arXiv:1511.02306

## Performance Projections

### Classical Sublinear (Current)
- Complexity: O(poly(1/ε, 1/δ, log n))
- 1000×1000 matrix: ~1ms

### Quantum-Inspired (Projected)
- Complexity: O(poly(log n, 1/ε))
- 1000×1000 matrix: ~0.1ms
- **10x improvement** over current

### True Quantum (Future)
- Complexity: O(log n · poly(κ, 1/ε))
- 1000×1000 matrix: ~0.001ms
- **1000x improvement** (with quantum hardware)

## Integration Strategy

```python
class QuantumInspiredSolver:
    def __init__(self, matrix, epsilon=1e-6):
        self.matrix = matrix
        self.epsilon = epsilon

    def solve_via_sampling(self, b):
        """
        Quantum-inspired sampling approach
        Based on Tang 2018 dequantization
        """
        # 1. Approximate matrix via sampling
        rank = self.estimate_rank()
        samples = self.importance_sample(rank)

        # 2. Low-rank approximation
        U, S, V = self.randomized_svd(samples)

        # 3. Solve in low-rank space
        return self.low_rank_solve(U, S, V, b)
```

## Next Steps

1. **Immediate**: Implement quantum-inspired sampling techniques
2. **Q1 2025**: Develop VQLS prototype for GPU simulation
3. **Q2 2025**: Test on IBM Quantum / Google Cirq
4. **Q3 2025**: Benchmark vs classical on real quantum hardware