Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.23138

Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling

Byeongyong Park, Keunhong Jeong, Doyeol Ahn

quant-phSubmitted Oct 16, 2026• Announced Oct 19, 2026• 0 citations
arXivHTMLPDF

Abstract

To solve linear systems $Ax=b$, we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian $H_b(A)=A^\dagger(I-|b\rangle\langle b|)A$, we measure quantum Krylov states $e^{-iAT}|b\rangle$ generated by the original Hermitian operator $A$ in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of $A^{-1}|b\rangle$ as a linear combination of quantum Krylov states, we derive lower bounds on computational-basis sampling probabilities from solution amplitudes. We establish support-discovery guarantees for finite nonnegative-time grid sampling and signed-time sampling, which permits both positive and negative evolution times. The former bounds the maximum evolution time, whereas the latter improves ideal shot complexity at the cost of occasional long evolutions. For a condition-number bound $κ$ on $A$, a lower bound $β_L$ on the solution probability weight of each of $L$ target basis states, and failure probability $δ$, signed-time sampling achieves $O(κ^2β_L^{-1}\log(L/δ))$ shots, matching a worst-case lower bound up to constants within an evolution-only observation model in a specified parameter regime. Finally, we analyze the effects of finite-length qDRIFT compilation and circuit reuse on sampling and derive an infidelity bound for the reconstructed solution.

Comments
19 pages, including appendices

Related papers

Riemannian Formulation of Sample-Based Quantum Krylov Solvers for Elliptic Problems: Energy-Norm Guarantees and Duct-Flow Applications

Doyeol "David" Ahn, Byeongyong Park

Sample-based quantum linear solvers measure quantum Krylov states $e^{-iAT}|b\rangle$ and reconstruct the solution of $Ax=b$ classically on the observed basis states. We develop this approach for positive-definite systems that arise from elliptic partial differential equations. We show that the sampling guarantees hold in any fixed basis with an efficient transform. We then replace the variational reconstruction by a Galerkin solve on the sampled set. For this reconstruction we derive expected and high-probability energy-norm error bounds, a sample complexity in terms of the smallest sampling probability on an essential set, a computable residual certificate, and a support-completeness theorem for the dephased outcome law. We formulate the method for elliptic problems on Riemannian cross sections. In two dimensions the stiffness matrix is metric-independent in conformal coordinates, and curved vessels lead to the same matrix class. Killing symmetries of the cross section give selection rules for the measurement outcomes, and the Lie derivative of the metric gives first-order bounds for geometric perturbations. We separate operator approximations, whose effect we bound, from sampler approximations, which affect coverage but not the target. As examples we treat the implicit step of pulsatile flow in elliptic, lens-shaped, and curved ducts. In simulations of up to 12 qubits, the number of Fourier modes required for 1% error grows from 14 to 60 while the number of unknowns grows from 64 to 4096. A classical residual-greedy selection is nevertheless more efficient than quantum sampling in all cases studied, consistent with the low measured sampling efficiency. On a six-qubit trapped-ion processor, the measured outcome laws follow a replacement-noise model whose strength grows by about 0.6% per two-qubit gate, and a parity selection rule rejects shots at the predicted rate.

quant-pharXiv:2610.15586•Oct 13, 2026•0 citations

Extending Sample-based Quantum Diagonalization to Systems of Linear Equations

Taha Selim

Solving systems of linear equations, $Ax=b$, is a ubiquitous task in computational science. The Harrow-Hassidim-Lloyd algorithm requires phase estimation, controlled rotations, and post-selection, impractical on noisy intermediate-scale quantum hardware. We extend sample-based quantum diagonalization (SQD), developed for quantum chemistry, to linear systems. Following the sample-based Krylov variant, the Hermitian matrix $A$ is decomposed in the Pauli basis, the Trotterized time evolution of $|b\rangle$ is sampled at several times to select computational-basis configurations, and the system is solved classically by a Galerkin projection onto the selected subspace. We prove that the subspace solution is exact when the sampled configurations contain the Krylov support of $b$ and optimal in the energy norm for symmetric positive-definite matrices, so that noise-induced configurations cannot degrade it as long as they do not displace the ideal ones. On IBM Quantum hardware, the sampled distribution of a $4\times4$ example deviates from the exact one by eleven times the shot-noise level, yet the solution is recovered exactly. For a localized problem of dimension $N=1024$, SQD selects 33 configurations, reaches a relative error of $10^{-5}$, and its truncated subspaces coincide with the optimal choice; readout errors enlarge the subspace without degrading the accuracy. The tests also show the limitations: the selected subspace coincides with that of inexpensive classical selection, banded matrices require exponentially many Pauli terms in the binary encoding, and Trotter errors populate spurious configurations unless the circuits are deep. An MIT-licensed Python package and notebooks that reproduce the numerical results are provided.

quant-pharXiv:2610.41708•Nov 2, 2026

Mirror subspace diagonalization: A real-time quantum Krylov algorithm with near-optimal sampling cost

Shota Kanasugi, Yuya O. Nakagawa, Norifumi Matsumoto +3 more

Quantum Krylov algorithms are a promising approach for ground-state energy estimation on near-term quantum computers. However, their sampling cost is inherently high because each Hamiltonian term is measured individually. Despite various mitigation techniques, this overhead remains a bottleneck for large-scale electronic structure problems. We introduce mirror subspace diagonalization (MSD), which approaches the theoretical lower bound on the sampling cost for quantum Krylov algorithms built upon real-time evolution. MSD uses a finite-difference formula to express the Hamiltonian as a linear combination of time-evolution unitaries with symmetrically shifted timesteps, enabling efficient estimation of the Hamiltonian matrix within the Krylov subspace. By optimizing the timestep and shifting the energy spectrum, finite-difference and statistical errors are minimized simultaneously, allowing MSD to attain the sampling-cost lower bound up to a logarithmic factor. We further apply classical post-processing to infer Hamiltonian moments, which mitigate the ground-state energy error via the Lanczos scheme. Our analysis shows MSD is particularly effective when the Hamiltonian's spectral norm is much smaller than its 1-norm, as in high-accuracy molecular simulations with large basis sets and strong electronic correlations. Numerical results for various molecular models show sampling-cost reductions of roughly 10 to 10,000 times over the conventional quantum Krylov algorithm.

quant-pharXiv:2511.20998•npj Quantum Information•Nov 27, 2025•0 citations

Reducing quantum and classical resources for quantum-centric supercomputing workloads on near-term hardware

Maxence Grandadam, Vladyslav Bohun, Dikshant Dulal +1 more

Sample-based Krylov quantum diagonalization (SKQD) is a paradigmatic example of a quantum-centric supercomputing workflow that combines the convergence structure of Krylov quantum diagonalization with classical sampling-based post-processing. It provides convergence guarantees assuming that the important computational-basis configurations can be sampled from a set of Krylov states with sufficient probability. We analyze this assumption under depolarizing noise, deriving shot-count resource estimates that expose an exponential depth penalty, and perform experiments on current noisy hardware with the one-dimensional single-impurity Anderson model on a 20-site (40-qubit) instance. Device noise breaks the practical convergence predicted by the noiseless SKQD analysis, but approximate compilation techniques can compress the Krylov time-evolution circuits before execution. The compressed circuits accumulate less hardware noise, recover the expected energy convergence, and reduce both the quantum shot budget and the classical subspace dimension, remaining beneficial even when classical configuration recovery is applied.

quant-pharXiv:2609.05957•Sep 8, 2026•0 citations

Quantum chemistry with provable convergence via randomized sample-based Krylov quantum diagonalization

Samuele Piccinelli, Alberto Baiardi, Barison, Stefano +12 more

Quantum algorithms based on classical processing of individual samples have recently emerged as a promising route to perform large-scale quantum-chemical calculations on pre-fault-tolerant and early-fault-tolerant quantum devices. In these algorithms, the quantum computer acts as a sampling engine that generates the subspace in which the Hamiltonian is classically diagonalized. The recently proposed Sample-based Krylov Quantum Diagonalization (SKQD) uses quantum Krylov states as circuits from which samples are collected. Convergence guarantees can be derived for SKQD under assumptions similar to those of quantum phase estimation -- namely, a sufficiently large overlap between the reference and the target ground state -- with the additional requirement that the ground-state wave function be well approximated by a polynomial subset of the full Hilbert space. However, implementations of SKQD for complex many-body Hamiltonians, such as quantum chemistry ones, are limited by the depths of time-evolution circuits needed to generate Krylov vectors. In this work, we introduce a method that combines SKQD with a qDRIFT randomized compilation of the Hamiltonian propagator. The resulting algorithm, termed SqDRIFT, enables executing quantum chemistry experiments on present-day quantum processors while retaining provable convergence guarantees, which we extend to account for the error of the randomized compilation and of finite sampling. We demonstrate its viability by applying SqDRIFT to calculate the electronic ground-state energy of several polycyclic aromatic hydrocarbons, up to system sizes beyond the reach of exact diagonalization.

arXiv:2508.02578•Aug 4, 2025•4 citations

Generative Krylov Subspace Representations for Scalable Quantum Eigensolvers

Changwon Lee, Daniel K. Park

Predicting ground state energies of quantum many-body systems is one of the central computational challenges in quantum chemistry, physics, and materials science. Krylov subspace methods, such as Krylov Quantum Diagonalization and Sample-based Krylov Quantum Diagonalization, are promising approaches for this task on near-term quantum computers. However, both require repeated quantum circuit executions for each Krylov subspace and for every new Hamiltonian, posing a major bottleneck under noisy hardware constraints. We introduce Generative Krylov Subspace Representations (GenKSR), a framework that learns a classical generative representation of the entire Krylov diagonalization process. To enable effective modeling of quantum systems, GenKSR leverages a conditional generative model framework. We investigate two representative backbone architectures, the standard Transformer and the Mamba state-space model. By learning the distribution of measurement outcomes conditioned on Hamiltonian parameters and evolution time, GenKSR generates Krylov subspace samples for unseen Hamiltonians and for larger subspace dimensions than those used in training. This enables full energy reconstruction purely from the classical model, without additional quantum experiments. We validate our approach through simulations of 15-qubit 1D and 16-qubit 2D Heisenberg models, as well as a hardware experiment on a 20-qubit XXZ chain executed on an IBM quantum processor. Our model successfully learns the distribution from experimental data and generates a high-fidelity representation of the quantum process. This representation enables classical reproduction of experimental outcomes, supports reliable energy estimates for unseen Hamiltonians, and significantly reduces the need for further quantum computation.

quant-pharXiv:2512.19420•Dec 23, 2025•0 citations
To solve linear systems Ax=bAx=bAx=b, we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian Hb(A)=A†(I−∣b⟩⟨b∣)AH_b(A)=A^\dagger(I-|b\rangle\langle b|)AHb​(A)=A†(I−∣b⟩⟨b∣)A, we measure quantum Krylov states e−iAT∣b⟩e^{-iAT}|b\ranglee−iAT∣b⟩ generated by the original Hermitian operator AAA in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of A−1∣b⟩A^{-1}|b\rangleA−1∣b⟩ as a linear combination of quantum Krylov states, we derive lower bounds on computational-basis sampling probabilities from solution amplitudes. We establish support-discovery guarantees for finite nonnegative-time grid sampling and signed-time sampling, which permits both positive and negative evolution times. The former bounds the maximum evolution time, whereas the latter improves ideal shot complexity at the cost of occasional long evolutions. For a condition-number bound κκκ on AAA, a lower bound βLβ_LβL​ on the solution probability weight of each of LLL target basis states, and failure probability δδδ, signed-time sampling achieves O(κ2βL−1log⁡(L/δ))O(κ^2β_L^{-1}\log(L/δ))O(κ2βL−1​log(L/δ)) shots, matching a worst-case lower bound up to constants within an evolution-only observation model in a specified parameter regime. Finally, we analyze the effects of finite-length qDRIFT compilation and circuit reuse on sampling and derive an infidelity bound for the reconstructed solution.
Sample-based quantum linear solvers measure quantum Krylov states e−iAT∣b⟩e^{-iAT}|b\ranglee−iAT∣b⟩ and reconstruct the solution of Ax=bAx=bAx=b classically on the observed basis states. We develop this approach for positive-definite systems that arise from elliptic partial differential equations. We show that the sampling guarantees hold in any fixed basis with an efficient transform. We then replace the variational reconstruction by a Galerkin solve on the sampled set. For this reconstruction we derive expected and high-probability energy-norm error bounds, a sample complexity in terms of the smallest sampling probability on an essential set, a computable residual certificate, and a support-completeness theorem for the dephased outcome law. We formulate the method for elliptic problems on Riemannian cross sections. In two dimensions the stiffness matrix is metric-independent in conformal coordinates, and curved vessels lead to the same matrix class. Killing symmetries of the cross section give selection rules for the measurement outcomes, and the Lie derivative of the metric gives first-order bounds for geometric perturbations. We separate operator approximations, whose effect we bound, from sampler approximations, which affect coverage but not the target. As examples we treat the implicit step of pulsatile flow in elliptic, lens-shaped, and curved ducts. In simulations of up to 12 qubits, the number of Fourier modes required for 1% error grows from 14 to 60 while the number of unknowns grows from 64 to 4096. A classical residual-greedy selection is nevertheless more efficient than quantum sampling in all cases studied, consistent with the low measured sampling efficiency. On a six-qubit trapped-ion processor, the measured outcome laws follow a replacement-noise model whose strength grows by about 0.6% per two-qubit gate, and a parity selection rule rejects shots at the predicted rate.
Solving systems of linear equations, Ax=bAx=bAx=b, is a ubiquitous task in computational science. The Harrow-Hassidim-Lloyd algorithm requires phase estimation, controlled rotations, and post-selection, impractical on noisy intermediate-scale quantum hardware. We extend sample-based quantum diagonalization (SQD), developed for quantum chemistry, to linear systems. Following the sample-based Krylov variant, the Hermitian matrix AAA is decomposed in the Pauli basis, the Trotterized time evolution of ∣b⟩|b\rangle∣b⟩ is sampled at several times to select computational-basis configurations, and the system is solved classically by a Galerkin projection onto the selected subspace. We prove that the subspace solution is exact when the sampled configurations contain the Krylov support of bbb and optimal in the energy norm for symmetric positive-definite matrices, so that noise-induced configurations cannot degrade it as long as they do not displace the ideal ones. On IBM Quantum hardware, the sampled distribution of a 4×44\times44×4 example deviates from the exact one by eleven times the shot-noise level, yet the solution is recovered exactly. For a localized problem of dimension N=1024N=1024N=1024, SQD selects 33 configurations, reaches a relative error of 10−510^{-5}10−5, and its truncated subspaces coincide with the optimal choice; readout errors enlarge the subspace without degrading the accuracy. The tests also show the limitations: the selected subspace coincides with that of inexpensive classical selection, banded matrices require exponentially many Pauli terms in the binary encoding, and Trotter errors populate spurious configurations unless the circuits are deep. An MIT-licensed Python package and notebooks that reproduce the numerical results are provided.
Quantum Krylov algorithms are a promising approach for ground-state energy estimation on near-term quantum computers. However, their sampling cost is inherently high because each Hamiltonian term is measured individually. Despite various mitigation techniques, this overhead remains a bottleneck for large-scale electronic structure problems. We introduce mirror subspace diagonalization (MSD), which approaches the theoretical lower bound on the sampling cost for quantum Krylov algorithms built upon real-time evolution. MSD uses a finite-difference formula to express the Hamiltonian as a linear combination of time-evolution unitaries with symmetrically shifted timesteps, enabling efficient estimation of the Hamiltonian matrix within the Krylov subspace. By optimizing the timestep and shifting the energy spectrum, finite-difference and statistical errors are minimized simultaneously, allowing MSD to attain the sampling-cost lower bound up to a logarithmic factor. We further apply classical post-processing to infer Hamiltonian moments, which mitigate the ground-state energy error via the Lanczos scheme. Our analysis shows MSD is particularly effective when the Hamiltonian's spectral norm is much smaller than its 1-norm, as in high-accuracy molecular simulations with large basis sets and strong electronic correlations. Numerical results for various molecular models show sampling-cost reductions of roughly 10 to 10,000 times over the conventional quantum Krylov algorithm.
Sample-based Krylov quantum diagonalization (SKQD) is a paradigmatic example of a quantum-centric supercomputing workflow that combines the convergence structure of Krylov quantum diagonalization with classical sampling-based post-processing. It provides convergence guarantees assuming that the important computational-basis configurations can be sampled from a set of Krylov states with sufficient probability. We analyze this assumption under depolarizing noise, deriving shot-count resource estimates that expose an exponential depth penalty, and perform experiments on current noisy hardware with the one-dimensional single-impurity Anderson model on a 20-site (40-qubit) instance. Device noise breaks the practical convergence predicted by the noiseless SKQD analysis, but approximate compilation techniques can compress the Krylov time-evolution circuits before execution. The compressed circuits accumulate less hardware noise, recover the expected energy convergence, and reduce both the quantum shot budget and the classical subspace dimension, remaining beneficial even when classical configuration recovery is applied.
Quantum algorithms based on classical processing of individual samples have recently emerged as a promising route to perform large-scale quantum-chemical calculations on pre-fault-tolerant and early-fault-tolerant quantum devices. In these algorithms, the quantum computer acts as a sampling engine that generates the subspace in which the Hamiltonian is classically diagonalized. The recently proposed Sample-based Krylov Quantum Diagonalization (SKQD) uses quantum Krylov states as circuits from which samples are collected. Convergence guarantees can be derived for SKQD under assumptions similar to those of quantum phase estimation -- namely, a sufficiently large overlap between the reference and the target ground state -- with the additional requirement that the ground-state wave function be well approximated by a polynomial subset of the full Hilbert space. However, implementations of SKQD for complex many-body Hamiltonians, such as quantum chemistry ones, are limited by the depths of time-evolution circuits needed to generate Krylov vectors. In this work, we introduce a method that combines SKQD with a qDRIFT randomized compilation of the Hamiltonian propagator. The resulting algorithm, termed SqDRIFT, enables executing quantum chemistry experiments on present-day quantum processors while retaining provable convergence guarantees, which we extend to account for the error of the randomized compilation and of finite sampling. We demonstrate its viability by applying SqDRIFT to calculate the electronic ground-state energy of several polycyclic aromatic hydrocarbons, up to system sizes beyond the reach of exact diagonalization.
Predicting ground state energies of quantum many-body systems is one of the central computational challenges in quantum chemistry, physics, and materials science. Krylov subspace methods, such as Krylov Quantum Diagonalization and Sample-based Krylov Quantum Diagonalization, are promising approaches for this task on near-term quantum computers. However, both require repeated quantum circuit executions for each Krylov subspace and for every new Hamiltonian, posing a major bottleneck under noisy hardware constraints. We introduce Generative Krylov Subspace Representations (GenKSR), a framework that learns a classical generative representation of the entire Krylov diagonalization process. To enable effective modeling of quantum systems, GenKSR leverages a conditional generative model framework. We investigate two representative backbone architectures, the standard Transformer and the Mamba state-space model. By learning the distribution of measurement outcomes conditioned on Hamiltonian parameters and evolution time, GenKSR generates Krylov subspace samples for unseen Hamiltonians and for larger subspace dimensions than those used in training. This enables full energy reconstruction purely from the classical model, without additional quantum experiments. We validate our approach through simulations of 15-qubit 1D and 16-qubit 2D Heisenberg models, as well as a hardware experiment on a 20-qubit XXZ chain executed on an IBM quantum processor. Our model successfully learns the distribution from experimental data and generates a high-fidelity representation of the quantum process. This representation enables classical reproduction of experimental outcomes, supports reliable energy estimates for unseen Hamiltonians, and significantly reduces the need for further quantum computation.