Source-linked AI summary
Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
Yigit Subasi, Rolando D. Somma, Davide Orsucci
TL;DR
The paper studies Hamiltonian-based evolution for preparing the solution state of a linear system. It reports evolution times scaling as O(κ^2 log(κ)/ϵ) and O(κ log(κ)/ϵ), with the latter yielding gate-based complexities stated below.
Problem
The paper addresses preparing a solution state for a linear system using Hamiltonian-based evolution.
Method
The algorithms use Hamiltonian families whose evolution follows a unique zero-eigenvalue ground state, with an invertible A(s) and no ancilla qubit.
Results
O(κ^2 log(κ)/ϵ) is obtained for the first algorithm, while the second algorithm has evolution time O(κ log(κ)/ϵ).
Takeaways & Limitations
The second algorithm's evolution can be simulated with query complexity ˜O(dκ/ϵ) and gate complexity ˜O(dκ(n + CM)/ϵ).
Takeaways & Limitations
The approach assumes access to an oracle for A.
Abstract
from arXiv · showhide
We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state $\vert x \rangle$ that is proportional to the solution of the system of linear equations $A \vec{x}=\vec{b}$. The time complexities of our algorithms are $O(κ^2 \log(κ)/ε)$ and $O(κ\log(κ)/ε)$, where $κ$ is the condition number of $A$ and $ε$ is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of $A$, the projector onto the initial state $\vert b \rangle$, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of $κ$. Like previous methods, our techniques yield an exponential quantum speedup under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.
SUPPLEMENTARY MATERIAL
The supplementary material analyzes spectral gaps, eigenstate path lengths, time complexities, special cases, and gate-based implementation of the two randomization algorithms. It derives O(κ^2 log(κ)/ε) for the first algorithm and gives gate and query complexities for implementing the second.
- Spectral gap: The Hamiltonian H(s) has ground state |x(s)⟩ with eigenvalue zero, while its spectral gap is the second-smallest eigenvalue Δ(s).Under the stated assumptions, all other eigenvalues are positive and bounded above by 1.
- Path length: The eigenstate path-length analysis uses a phase choice satisfying ⟨x(s)|∂_s x(s)⟩ = 0 and bounds the derivative norm along the path.A natural parametrization makes the derivative norm at most 1, and the resulting upper bound on path length depends logarithmically on κ.
- Time complexity: O(κ^2 log(κ)/ε) is the time complexity obtained for the first algorithm using H(s).The derivation uses q = Θ(log^2(κ)/ε) steps and δ = Θ(ε/log(κ)).
- Spectral gap amplification: The amplified Hamiltonian H′(s) has a two-fold degenerate zero eigenvalue and paired nonzero eigenvalues with opposite signs.The positive and negative eigenvalues arise through the spectral-gap amplification construction and are illustrated in Fig. 2.
- Special case: A > 0: For A > 0, the construction makes A(s) invertible on [0, 1] without an ancilla qubit while preserving the general-case time complexities.The resulting Hamiltonian is also simpler and uses one fewer ancilla qubit.
- Gate-based implementation: Gate-based simulation of the second algorithm has query complexity ˜O(dκ/ε) and gate complexity ˜O(dκ(n + C_M)/ε).The implementation expresses the Hamiltonian as a linear combination of unitaries and uses oracles for the sparse matrix A.