By name: quantum-linear-algebra-block-encoding description: "Design and implement quantum algorithms using block encoding methodology for quantum linear algebra. Block encoding embeds a matrix as a sub-block of a larger unitary, enabling quantum singular value transformation (QSVT), quantum linear system solvers, and Hamiltonian simulation. Use when implementing quantum linear algebra algorithms, building matrix arithmetic circuits, or working with QSVT/HHL-style algorithms. Trigger words: block encoding, quantum linear algebra, QSVT, quantum singular value transformation, matrix encoding quantum, quantum matrix arithmetic."
Quantum Linear Algebra via Block Encoding
Design quantum algorithms using block encoding methodology. Block encoding embeds a non-unitary matrix A as a sub-block of a larger unitary U, enabling composition of matrix operations without low-level circuit construction.
Core Concept
A block encoding of matrix A is a unitary U where:
U = [A/α · ]
[ · · ]
α is the normalization factor (subnormalization), ensuring ||A|| ≤ α.
Key Operations
1. Arithmetic Composition
Block encodings compose via standard operations:
| Operation | Subnormalization | Qubit Overhead |
|---|---|---|
| Addition A + B | α + β | O(1) ancilla |
| Multiplication A·B | α·β | O(1) ancilla |
| Tensor product A⊗B | α·β | 0 ancilla |
| Linear combination Σ cᵢAᵢ | Σ | cᵢ |
2. Quantum Singular Value Transformation (QSVT)
Apply polynomial P to singular values of A:
QSVT: U → polynomial(P, U) = [P(A/α) ·]
[ · ·]
Common polynomials:
- Matrix inversion: P(x) ≈ 1/x (for HHL-style solvers)
- Matrix exponential: P(x) ≈ e^{ixt} (Hamiltonian simulation)
- Projection: P(x) ≈ step function (eigenvalue filtering)
3. Input Models
| Input Model | Block Encoding Cost | Use Case |
|---|---|---|
| Sparse matrix | O(1) queries | Sparse linear systems |
| LCU (Linear Combination of Unitaries) | O(1) state prep | Hamiltonian simulation |
| QRAM access | O(1) queries | Dense matrix operations |
| Quantum RAM state prep | O(log n) | Data loading |
Design Patterns
Pattern 1: Quantum Linear System Solver
To solve Ax = b:
- Block encode A with normalization α
- Use QSVT with polynomial P(x) ≈ 1/x
- Apply to state |b⟩
- Result: |x⟩ ∝ A⁻¹|b⟩
Complexity: O(κ·α·polylog(n)/ε) where κ = condition number
Pattern 2: Hamiltonian Simulation
To simulate e^{-iHt}:
- Block encode H with normalization α
- Use QSVT with polynomial approximating e^{-iαtx}
- Query complexity: O(αt + log(1/ε))
Pattern 3: Matrix Function Evaluation
For any function f:
- Block encode A
- Construct polynomial approximation of f
- Apply QSVT
Pattern 4: Resource Estimation
Before circuit execution:
- Gate count: Track per composition step
- Qubit count: log(d) + ancilla per operation
- Normalization: Product of α factors (critical for success probability)
Implementation Checklist
- Identify input model (sparse, LCU, QRAM)
- Determine block encoding construction
- Compute subnormalization α
- Design polynomial approximation for target function
- Estimate resource requirements (qubits, gates, depth)
- Verify normalization factors at each composition step
- Account for amplitude amplification overhead (probability ~ 1/α²)
Common Pitfalls
- Normalization blowup: Each composition multiplies α → track carefully
- Polynomial degree: Higher accuracy → higher degree → more queries
- Condition number dependence: Linear system solving scales with κ
- Ancilla qubits: Composition requires fresh ancilla per step
References
- Unitaria: Python library for block encoding composition (arXiv: 2605.10768)
- Gilyén et al.: Quantum Singular Value Transformation (2019)
- Childs et al.: Quantum Linear Systems algorithms
Activation
- block encoding quantum
- quantum linear algebra
- QSVT quantum singular value transformation
- quantum matrix arithmetic
- quantum HHL algorithm
- quantum linear system solver
- Hamiltonian simulation block encoding