Eigenpath Traversal by Poisson-Distributed Phase Randomisation

Pedro C. S. Costa, Dong An, Ryan Babbush, Dominic W. BerryarXiv 2023 · DOI · arXiv

TL;DR

Theoretical upper bounds in quantum computing can be notoriously pessimistic. This paper demonstrates through numerical simulation that a state-of-the-art "discrete adiabatic" quantum linear system solver is actually 1,200 times more efficient in practice than its theoretical proof suggests, outperforming competing randomized methods by nearly an order of magnitude.

What Problem Does This Paper Address?

The Quantum Linear System Problem (QLSP)—solving $Ax = b$ on a quantum computer—is a cornerstone of quantum algorithms. While researchers have developed "asymptotically optimal" algorithms that scale linearly with the condition number ($\kappa$) and logarithmically with error ($\epsilon$), the constant factors (the "hidden" numbers in Big-O notation) determine whether an algorithm is actually runnable on near-term hardware.

A previous landmark paper (Costa et al., 2022) provided a rigorous upper bound for a discrete adiabatic solver, but the constant factor derived was a massive $\alpha \approx 2305$. This led the community to believe the method might be impractical, prompting a search for "randomized" alternatives that claimed to have smaller constants. This paper investigates whether that theoretical pessimism matches reality.

Methods

The authors compare two primary approaches to the QLSP:

  1. The Quantum Walk (QW) Method: This uses a discrete version of the adiabatic theorem. Instead of continuous Hamiltonian evolution, it uses a "quantum walk" operator to stay near the ground state (the solution) as the system parameters are slowly changed.
  2. The Randomized Method (RM): This approach evolves the system for random time intervals. This "randomization" effectively emulates the Quantum Zeno effect, suppressing transitions away from the desired solution state.

The researchers performed extensive numerical simulations, classically emulating quantum circuits for matrices of various sizes (up to $32 \times 32$) and condition numbers ($\kappa$ from 10 to 50). They measured complexity by counting the number of calls to the "block encoding" of the matrix $A$—the standard unit of cost for these algorithms.

Datasets

The study utilized two types of data for evaluation:

  • Synthetic Random Matrices: 100 independent samples for each condition number, covering both positive-definite Hermitian matrices and general non-Hermitian matrices.
  • SuiteSparse Matrix Collection: Two real-world sparse matrices from a standard benchmark set—one representing a directed graph problem (ID=168) and another from a circuit simulation problem (ID=1199). These provide a "sanity check" for how the algorithms perform on structured, non-random data.

Key Insights and Ideas

  • The "Loose Bound" Gap: The most striking insight is the massive gap between "provable" math and "practical" performance. Theoretical bounds often rely on a chain of inequalities (like the triangle inequality) where each step adds a layer of pessimism. In this case, those layers compounded into a 1,200x overestimation of the cost.
  • Discrete vs. Continuous: The QW method is inherently discrete, which maps more naturally to quantum gates. The Randomized Method requires simulating continuous-time Hamiltonian evolution, which adds significant overhead that the QW method avoids.
  • Robustness Across Dimensions: The authors found that the complexity depends very little on the dimension of the matrix ($N$), confirming that these quantum algorithms truly provide an exponential speedup over classical solvers in terms of system size.

Key Results

  • Massive Speedup over Theory: For the QW method, the practical constant factor was found to be $\alpha \approx 1.84$, compared to the theoretical upper bound of $2305$.
  • Dominance over Randomized Methods: The QW method was consistently 7 to 10 times more efficient than the Randomized Method across all random test cases.
  • Real-World Performance: On the circuit simulation benchmark (ID=1199), the QW method was a staggering 457 times faster than the Randomized Method.
  • Linear Scaling Confirmed: The results numerically confirmed the optimal $O(\kappa)$ scaling for both methods, but with the QW method having a much lower "slope."

Limitations and Future Work

  • Simulation Scale: Because the authors used classical computers to simulate quantum systems, they were limited to relatively small matrices ($N \le 32$). While the theory suggests these results scale to much larger systems, numerical verification at the scale of hundreds of qubits remains impossible for now.
  • Gate-Level Details: The paper measures cost in "calls to block encoding." While this is a standard metric, the actual gate-level implementation on specific hardware (like superconducting qubits vs. ion traps) will introduce additional hardware-specific overheads not captured here.
  • Future Directions: The authors suggest that future work could explore even more sophisticated "scheduling functions" (how fast to move along the adiabatic path) to further shrink these constants.

Summary updated

Abstract

The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number $κ$ and the allowable error $ε$ [PRX Quantum \textbf{3}, 040303 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,200 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is about an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.
BibTeX
@misc{costa2023eigenpath,
  author = {Pedro C. S. Costa and Dong An and Ryan Babbush and Dominic W. Berry},
  title = {{Eigenpath Traversal by Poisson-Distributed Phase Randomisation}},
  year = {2023},
  eprint = {2312.07690},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.07690},
}
Figure