Expectation value estimation with parametrized quantum circuits

Basic Information

• Paper ID: 2407.19499
• Title: Expectation value estimation with parametrized quantum circuits
• Authors: Bujiao Wu, Lingyu Kong, Yuxuan Yan, Fuchuan Wei, Zhenhuan Liu
• Classification: quant-ph (Quantum Physics)
• Publication Date: July 2024 (arXiv preprint, v2 updated October 16, 2025)
• Paper Link: https://arxiv.org/abs/2407.19499

Abstract

Estimating properties of quantum states (such as fidelity, molecular energy, and correlation functions) is a fundamental task in quantum information science. Due to limitations of practical quantum devices, including finite circuit depth and connectivity constraints, even estimating linear properties encounters high sample complexity. To address this inefficiency, this paper proposes a framework that uses shallow parametrized quantum circuits to optimize sample complexity for estimating expectation values of arbitrary observables. Within this framework, two decomposition algorithms are introduced: a tensor network method and a greedy projection method, which decompose the target observable into linear combinations of multiple observables, each diagonalizable by shallow circuits. Based on this decomposition, importance sampling algorithms are applied to estimate the expectation value of the target observable.

Research Background and Motivation

Problem Definition

Estimating linear properties of quantum states Tr(ρH) is a core task in quantum information science, where ρ is a quantum state and H is an observable. This class of problems appears widely in:

1. Quantum Chemistry: Ground state energy calculations of molecules
2. Many-body Physics: Measurement of correlation functions
3. Quantum Information: State fidelity assessment

Limitations of Existing Methods

1. Classical Shadow (CS) Protocol:
   • Local CS protocol has sample complexity O(4^k) for k-local observables
   • Global CS protocol achieves O(1) complexity but requires logarithmic-depth circuits
   • Both are "measurement-agnostic," failing to exploit prior information about target observables
2. Pauli Decomposition Methods:
   • Limited to Clifford circuit implementations
   • Decomposition restricted to Pauli observables
   • May require deep circuits or high sample complexity

Research Motivation

Existing methods face the following challenges on near-term quantum devices:

• Limited circuit depth
• Connectivity constraints
• Noise effects
• Insufficient utilization of observable information

Core Contributions

1. Unified Framework: Proposes a general framework for estimating linear properties using parametrized quantum circuits, unifying existing Pauli decomposition protocols
2. Two Decomposition Algorithms:
   • Greedy Projection Decomposition (GPD): Applicable to general Hamiltonians
   • Tensor Network Decomposition (TND): Applicable to Hamiltonians with compact tensor network representations
3. Theoretical Lower Bounds: Derives fundamental lower bounds on sample complexity required for estimating target observables using given shallow quantum circuits
4. Numerical Verification: Validates algorithm advantages on sparse/dense Hamiltonians and Slater determinant inner product estimation

Methodology Details

Task Definition

Given:

• Unknown quantum state ρ
• Target observable H
• L-layer depth parametrized quantum circuit U_L(θ)
• Accuracy requirement ε and success probability 1-δ

Objective: Estimate Tr(ρH) with minimized sample complexity

Overall Framework

The framework consists of classical and quantum stages:

Classical Stage: Decompose the target observable as $H \approx \sum_{k=1}^K U_L(\theta^{(k)})^\dagger \Lambda_k U_L(\theta^{(k)})$ where Λ_k are real diagonal matrices

Quantum Stage: Use importance sampling to estimate expectation values

• Sample term k with probability p_k ∝ ||Λ_k||_2
• Execute U_L(θ^{(k)}) and measure in computational basis
• Apply median-of-means method to obtain final estimate

Greedy Projection Decomposition (GPD) Algorithm

Core Idea: Iteratively find the best approximating term U_L(θ)†ΛU_L(θ)

Algorithm Flow:

1. Initialize H^{(0)} = H, k = 0
2. While ||H^{(k)}||_2 ≥ ε:
   • Solve optimization problem: θ^{(k)} = argmin_θ ||U_L(θ)H^{(k)}U_L†(θ) - diagU_L(θ)H^{(k)}U_L†(θ)||_F
   • Set Λ_k = diagU_L(θ^{(k)})H^{(k)}U_L†(θ^{(k)})
   • Update H^{(k+1)} = H^{(k)} - U_L†(θ^{(k)})Λ_k U_L(θ^{(k)})
   • k = k + 1

Complexity Analysis: Classical processing time is O(poly(n)·2^{ωn}), where ω ≈ 2.37 is the matrix multiplication exponent

Tensor Network Decomposition (TND) Algorithm

Applicable Scenario: Target Hamiltonian possesses efficient matrix product operator (MPO) representation

Optimization Objective: Minimize loss function $L = ||H - \sum_k U_L(\theta_k)^\dagger \Lambda_k U_L(\theta_k)||_F^2$

Key Techniques:

• Represent U_L(θ_k) as unitary tensor network of depth L
• Represent Λ_k in MPO form
• Use tensor network contraction to compute loss function
• Gradient descent optimization of parameters {θ^{(k)}, Λ_k}

Sample Complexity Analysis

Upper Bound: Algorithm 1 requires T = O(||Λ||_1^2 log(1/δ)/ε_2^2) samples, where ||Λ||_1 is the sum of all ||Λ_k||_2

Lower Bound: Any single-copy adaptive strategy using parametrized circuit U_L(θ) requires $T = \Omega\left(\frac{\text{Tr}(H_0^2)^2}{\varepsilon^2 \delta(H_0) 4^n}\right)$ where H_0 is the traceless part of H, and δ(H_0) is the square of the maximum expectation value of H_0 on the reachable state set

Experimental Setup

Experimental Scenarios

1. Sparse Hamiltonian Ground State Energy Estimation: 8-qubit system with 64 nonzero elements
2. Dense Hamiltonian Expectation Value Estimation: 4-qubit random Hermitian matrix
3. Slater Determinant Inner Product Estimation: 3-qubit system, τ-Slater determinant inner product with pure state

Comparison Methods

• Classical Shadow Protocols: Global CS and local CS
• Pauli Decomposition Methods: Derandomized, C-LBCS, SG, Adaptive, OGM, etc.
• Specialized Methods: Fermionic classical shadow (FCS)

Implementation Details

• Parametrized gates: iSWAP gates + tensor product of two arbitrary single-qubit gates
• GPD algorithm: L=4 layers, K=20 or 80 decomposition terms
• TND algorithm: L=1 layer, K=3 decomposition terms

Experimental Results

Main Results

Sparse Hamiltonian (8 qubits):

• At 25,848 samples, GPD error is 0.030, significantly outperforming best comparison method OGM at 0.097
• GPD maintains lowest error as sample count increases

Dense Hamiltonian (4 qubits):

• At 25,848 samples, GPD error is 0.046, outperforming best comparison method OGM at 0.053
• Advantage more pronounced with fewer samples

Slater Determinant Inner Product (3 qubits):

• GPD achieves lowest error across all sample counts
• Error of 0.009 at 25,848 samples, compared to best comparison method at 0.012

Convergence Analysis

Numerical results show:

1. With fixed decomposition terms K, Frobenius distance decreases as circuit depth L increases
2. With fixed circuit depth, Frobenius distance decays exponentially with decomposition terms K

Tensor Network Method Performance

For low bond dimension Hamiltonians:

• TND method uses only 3 decomposition terms and 1-layer circuit depth
• Error of 0.050 at 18,000 steps, outperforming traditional methods

Related Work

Quantum State Learning

• Quantum Tomography: Complete state reconstruction with exponentially growing complexity
• Shadow Tomography: Provides classical description of state, supports multiple property estimation

Random Measurement Protocols

• Local Measurements: Single-qubit Clifford group, suitable for local observables
• Global Measurements: Global Clifford group, requires deep circuits
• Shallow Circuits: Compromise approach, but still underutilizes observable information

Pauli Decomposition Methods

• Based on Pauli expansion of observables
• Implemented via Clifford circuits and computational basis measurements
• This paper's framework unifies these methods

Conclusions and Discussion

Main Conclusions

1. The proposed framework successfully unifies existing measurement protocols and extends to general parametrized circuits
2. GPD and TND algorithms significantly outperform existing methods across multiple scenarios
3. Established theoretical lower bounds reveal fundamental limitations of shallow circuits in quantum learning tasks

Limitations

1. GPD Algorithm:
   • Classical optimization complexity remains high
   • Greedy strategy does not guarantee global optimality
   • Theoretical analysis of decomposition term count K is difficult
2. TND Algorithm:
   • Only applicable to Hamiltonians with efficient MPO representation
   • Requires additional tensor network optimization techniques
3. Theoretical Lower Bounds:
   • May not be tight for low-rank observables (e.g., fidelity)
   • Depends on accurate estimation of circuit capability parameter δ(H_0)

Future Directions

1. Algorithm Optimization:
   • Develop more efficient decomposition algorithms based on machine learning
   • Explore non-greedy global optimization strategies
2. Theoretical Refinement:
   • Establish tighter sample complexity lower bounds
   • Analyze relationship between decomposition term count K and circuit capability
3. Application Extension:
   • Extend to non-linear property estimation
   • Protocol design combining quantum memory
   • Reduce hardware configuration switching overhead

In-Depth Evaluation

Strengths

1. Theoretical Contributions:
   • Provides unified framework integrating multiple existing methods
   • Establishes important theoretical lower bounds, advancing understanding of shallow circuit capabilities
2. Methodological Innovation:
   • GPD algorithm applicable to general Hamiltonians with strong practicality
   • TND algorithm optimized for specific structures with high efficiency
   • Fully exploits observable prior information
3. Comprehensive Experiments:
   • Covers multiple application scenarios (sparse/dense Hamiltonians, inner product estimation)
   • Comparison with multiple mainstream methods yields convincing results
   • Provides convergence and average performance analysis

Weaknesses

1. Scalability Issues:
   • GPD classical optimization complexity grows exponentially with qubit count
   • Practical utility for large-scale systems remains to be verified
2. Experimental Limitations:
   • Numerical experiments at modest scale (maximum 8 qubits)
   • Lacks verification on actual quantum devices
   • Does not consider noise effects on algorithm performance
3. Theoretical Gaps:
   • Significant gap between upper and lower bounds
   • Convergence rate of decomposition term count K lacks rigorous theoretical guarantee

Impact

1. Academic Value:
   • Provides new theoretical framework for quantum state learning
   • Advances understanding of shallow quantum circuit capabilities
   • Offers practical tools for near-term quantum computing applications
2. Practical Value:
   • Algorithm design philosophy suited for NISQ devices
   • Potential applications in quantum chemistry and many-body physics
   • Provides benchmark tools for quantum advantage verification

Applicable Scenarios

1. Quantum Chemistry: Molecular ground state energy and property calculations
2. Quantum Simulation: Many-body system correlation function measurement
3. Quantum Machine Learning: Feature mapping and kernel methods
4. Quantum Optimization: Objective function expectation value estimation
5. Quantum Error Correction: Codeword fidelity and error correction performance assessment

References

The paper cites 66 relevant references covering core areas including quantum state learning, random measurements, classical shadows, and Pauli decomposition, providing solid theoretical foundation for the research.