The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver

Basic Information

• Paper ID: 2312.07690
• Title: The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Authors: Pedro C. S. Costa, Dong An, Ryan Babbush, Dominic W. Berry
• Classification: quant-ph (Quantum Physics)
• Publication Date: December 2023, Latest version October 11, 2025
• Paper Link: https://arxiv.org/abs/2312.07690

Abstract

Solving linear systems of equations is fundamental to many quantum algorithms. Recent research has provided algorithms with optimal complexity in both condition number κ and allowable error ε PRX Quantum 3, 040303 (2022). This work is based on the discrete adiabatic theorem and provides explicit constant factors for the complexity upper bound. Through numerical testing on random matrices, this paper demonstrates that the actual constant factors are approximately 1200 times smaller than the numerically derived upper bounds in previous results. This indicates that the method is far more efficient in practice than naively expected from the upper bounds. In particular, it is approximately one order of magnitude more efficient than the randomized method claiming superior efficiency arXiv:2305.11352.

Research Background and Motivation

Importance of the Problem

The quantum linear system problem (QLSP) is one of the core problems in quantum computing, aiming to efficiently produce a quantum state |x⟩ proportional to the solution of the linear equation Ax = b. Solving this problem is fundamental to many other quantum algorithms, including those in quantum machine learning and quantum optimization.

Development of Existing Methods

1. HHL Algorithm: Harrow, Hassidim, and Lloyd first proposed the quantum linear system algorithm with complexity O(poly(n)κ²/ε)
2. Adiabatic Quantum Computing Methods: Subsequent research based on adiabatic quantum computing (AQC) provided improvements, particularly Costa et al. in 6 achieved optimal complexity O(κlog(1/ε)) based on the discrete adiabatic theorem
3. Randomized Methods: An alternative approach uses randomized time evolution to simulate the quantum Zeno effect

Research Motivation

Although the discrete adiabatic method achieves optimal asymptotic complexity theoretically, the strict upper bound yields a very large constant factor α = 2305, raising questions about its practical efficiency. Meanwhile, the randomized method claims superior practical efficiency due to tighter upper bounds. This paper aims to verify the actual performance of these methods through numerical experiments.

Core Contributions

1. Revealed the actual constant factors of the discrete adiabatic method: Extensive numerical experiments discovered an actual constant factor α = 1.84, approximately 1200 times smaller than the theoretical upper bound
2. Demonstrated the practical superiority of the discrete adiabatic method: Numerical tests show the quantum walk method is on average approximately 7 times more efficient than the randomized method
3. Provided comprehensive performance comparison: Including cases for positive definite and general non-Hermitian matrices, with tests across different dimensions and condition numbers
4. Considered complete algorithm overhead: Analyzed total complexity including filtering steps, proving that the discrete adiabatic method maintains at least a 3-fold improvement even accounting for all overhead

Detailed Methodology

Task Definition

Given an invertible matrix A ∈ C^(N×N) with ∥A∥ = 1, and a normalized vector |b⟩ ∈ C^N, the goal is to prepare a normalized state |x̃⟩ that approximates |x⟩ = A^(-1)|b⟩/∥A^(-1)|b⟩∥ with precision ∥|x̃⟩ - |x⟩∥ ≤ ε.

Discrete Quantum Walk Method (QW)

Positive Definite Hermitian Matrix Case

For positive definite Hermitian matrices A, construct the Hamiltonian:

• H₀ := (0 Qb; Qb 0)
• H₁ := (0 AQb; QbA 0)

where Qb = I_N - |b⟩⟨b| is the projection operator.

The time-dependent Hamiltonian is: H(s) = (1 - f(s))H₀ + f(s)H₁

The scheduling function f(s) is designed according to the energy gap condition: f(s) = κ/(κ-1)1 - (1 + s(κ^(p-1) - 1))^(1/(1-p))

Non-Hermitian Matrix Case

Convert to Hermitian form by doubling the matrix dimension: A := (0 A; A† 0)

The corresponding Hamiltonian is: H(s) = (0 A(f(s))Qb; QbA(f(s)) 0)

where A(f) := (1-f)σz⊗I_N + fA.

Randomized Method (RM)

The randomized method implements the following operation: e^(-it_q H(v_q)) ⋯ e^(-it₂H(v₂))e^(-it₁H(v₁))

where:

• vⱼ = vₐ + j(vb - vₐ)/q are the discretized time points
• tⱼ are random variables selected according to a specific probability distribution

The probability density function is: p_j(t) ∝ (J_p(Δ(vⱼ)|t|/2)/(Δ^(p-1)(vⱼ)|t|^p))²

where J_p is the Bessel function of the first kind, p = 1.165.

Experimental Setup

Test Matrices

• Dimensions: 4×4, 8×8, 16×16 random matrices
• Condition Numbers: κ = 10, 20, 30, 40, 50
• Matrix Types: Positive definite Hermitian matrices and general non-Hermitian matrices
• Sample Size: 100 independent random matrices generated for each condition number

Evaluation Metrics

• Quantum Walk Method: Number of walk steps required to achieve target error Δ = 0.4
• Randomized Method: Total evolution time ∑|tⱼ| required to achieve the same error
• Error Definition: 2-norm error ∥|x̃⟩ - |x⟩∥

Implementation Details

• Scheduling function parameter p = 1.4
• Geometric mean used for complexity calculation
• Error bars including interquartile range and full data range
• 200 repetitions for each randomized method instance

Experimental Results

Main Results

Constant Factor Comparison

For the case κ = 50:

• Theoretical Upper Bound: α = 2305
• Actual Measurement: α = 1.84
• Improvement Factor: Approximately 1250 times

Method Performance Comparison

Real Application Testing

Using actual matrices from the SuiteSparse matrix collection:

• Directed Graph Problem (ID=168, κ=4.041×10²): QW is 9.58 times faster than RM
• Circuit Simulation Problem (ID=1199, κ=6.302×10⁵): QW is 457 times faster than RM

Dimension Dependency

Experiments show that complexity has minimal dependence on matrix dimension, consistent with theoretical expectations, as complexity primarily depends on condition number rather than dimension.

Complete Algorithm Overhead Analysis

Considering total complexity after filtering steps:

• For typical target errors ε > 0.0004, the adiabatic part dominates
• The QW method maintains significant advantages over the RM method even after including filtering overhead
• The optimal error threshold Δ is approximately 0.4, consistent with experimental settings

Related Work

Development of Quantum Linear System Algorithms

1. HHL Algorithm: Pioneering work with complexity O(κ²/ε)
2. Variational Time Amplitude Amplification: Improved dependence on precision
3. Adiabatic Quantum Computing Methods: Provided better complexity scaling
4. Optimal Polynomial Filtering: Further optimized implementation

Complexity Lower Bounds

Harrow and Kothari proved a lower bound of Ω(κlog(1/ε)) for the quantum linear system problem, which was first achieved in Costa et al.'s work.

Randomized Methods

The randomized method proposed by Subaşı et al. has complexity O(κlog(κ/ε)). Although it has an additional log κ factor, it claims superior practical efficiency due to smaller constant factors.

Conclusions and Discussion

Main Conclusions

1. Huge Gap Between Theory and Practice: The actual constant factors of the discrete adiabatic method are 1200 times smaller than the theoretical upper bound
2. Method Superiority: The quantum walk method outperforms the randomized method in all tested cases
3. Practical Value: The method is not only theoretically optimal but also highly efficient in practice

Limitations

1. Error Threshold: Uses a relatively large target error Δ = 0.4, which may lead to certain outlier cases
2. Matrix Types: Primarily tests random matrices; structured matrices in practical applications may show different performance
3. Comparison Fairness: The RM method comparison uses evolution time rather than specific quantum gate counts

Future Directions

1. More Precise Constant Factor Analysis: Develop tighter theoretical bounds
2. Structured Matrices: Investigate performance on matrices with special structures
3. Hardware Implementation: Verify these results on actual quantum hardware

In-Depth Evaluation

Strengths

1. High Practical Value: Addresses the important gap between theory and practice
2. Sufficient Experiments: Extensive testing on random matrices and real application cases
3. Comprehensive Analysis: Considers complete algorithm overhead including filtering steps
4. Reliable Results: All test instances demonstrate consistent advantages

Weaknesses

1. Insufficient Theoretical Explanation: Lacks deep analysis of why actual constant factors are so small
2. Comparison Baseline: Comparison with RM method may not be entirely direct (time vs. steps)
3. Scale Limitations: Tested matrix dimensions are relatively small (maximum 16×16)

Impact

This work has significant impact on the quantum algorithm community:

1. Reassessment of Algorithm Efficiency: Reminds researchers that theoretical upper bounds may be overly conservative
2. Algorithm Selection Guidance: Provides clear guidance for algorithm selection in practical applications
3. Future Research Direction: Stimulates demand for more precise complexity analysis

Applicable Scenarios

This method is particularly suitable for:

1. Quantum algorithms requiring high-precision linear solving
2. Practical problems with moderate condition numbers
3. Application scenarios sensitive to constant factors

References

This paper cites key literature in the field of quantum linear system solving, including:

• 1 Original HHL algorithm
• 6 Costa et al.'s discrete adiabatic method
• 10 Jennings et al.'s randomized method improvements
• 14 Berry et al.'s Hamiltonian simulation optimization