Approximating the k -th spectral gap Δ k = | λ k − λ k + 1 | and the corresponding midpoint μ k = λ k + λ k + 1 2 of an N × N Hermitian matrix with eigenvalues λ 1 ≥ λ 2 ≥ … ≥ λ N , is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error ϵ Δ k using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by O ( N 2 ϵ 2 Δ k 2 p o l y l o g ( N , 1 Δ k , 1 ϵ , 1 δ ) ) , where ϵ , δ ∈ ( 0 , 1 ) are the accuracy and the failure probability, respectively. For large gaps Δ k , this provides a speed-up against the best-known complexities of classical algorithms, namely, O ( N ω p o l y l o g ( N , 1
Approximating the k -th spectral gap Δ k = | λ k − λ k + 1 | and the corresponding midpoint μ k = λ k + λ k + 1 2 of an N × N Hermitian matrix with eigenvalues λ 1 ≥ λ 2 ≥ … ≥ λ N , is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error ϵ Δ k using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by O ( N 2 ϵ 2 Δ k 2 p o l y l o g ( N , 1 Δ k , 1 ϵ , 1 δ ) ) , where ϵ , δ ∈ ( 0 , 1 ) are the accuracy and the failure probability, respectively. For large gaps Δ k , this provides a speed-up against the best-known complexities of classical algorithms, namely, O ( N ω p o l y l o g ( N , 1
Finding a good approximation of the top eigenvector of a given d x d matrix A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity Õ (d 1.75 ) and one with time complexity d 1.5+0(1) (the first algorithm has a slightly better dependence on the ℓ2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω (d 2) queries to entries of A, and hence Ω(d 2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd 1.5+o (1). We also prove a nearly-optimal lower bound of on the quantum query complexity of approximating the top eigenvector.
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given m Bernoulli distributions with unknown biases p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of O~(Δερ+Δε1) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2).
Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(ρ/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ερ+ε1) and Ω(ερ), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.
Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error ε with probability at least 1−pfail. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires O(κ2ε−(2m−1)log(1/pfail)) queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.
We determine the optimal query complexity of ground-state preparation to trace-distance error ε when an energy threshold in the spectral gap is known. Let UH be an α-block-encoding of a Hamiltonian with unique ground state ∣ψ0⟩, and suppose ∣⟨ψ0∣UI∣0⟩∣≥γ for a state-preparation oracle UI. The threshold lies at least Δ/2 above the ground-state energy and at least Δ/2 below every excited-state energy. We give two algorithms that prepare a state within trace distance ε of the ground state. One uses O((α/Δ)(γ−1+log(1/ε))) calls to UH in expectation; the other uses O((α/(γΔ))log(1/ε)) calls to UH in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to UI are O(1/γ) in expectation and O(γ−1log(1/ε)) in the worst case. On (N+1)-dimensional systems, these UI bounds are also optimal when the expected or worst-case count of UH calls, respectively, is o((α/Δ)N). Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.