Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a
2n-dimensional,
poly(n)-sparse Hamiltonian has an
O(1)-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in
poly(n) time. The same conclusion follows when the
O(1)-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.
Solving the generalized eigenvalue problem is a useful method for finding energy eigenstates of large quantum systems.It uses projection onto a set of basis states which are typically not orthogonal.One needs to invert a matrix whose entries are inner products of the basis states, and the process is unfortunately susceptible to even small errors.The problem is especially bad when matrix elements are evaluated using stochastic methods and have significant error bars.In this work, we introduce the trimmed sampling algorithm in order to solve this problem.Using the framework of Bayesian inference, we sample prior probability distributions determined by uncertainty estimates of the various matrix elements and likelihood functions composed of physics-informed constraints.The result is a probability distribution for the eigenvectors and observables which automatically comes with a reliable estimate of the error and performs far better than standard regularization methods.The method should have immediate use for a wide range of applications involving classical and quantum computing calculations of large quantum systems.
Abstract Extracting eigenvalues and eigenvectors of exponentially large matrices will be an important application of near-term quantum computers. The variational quantum eigensolver (VQE) treats the case when the matrix is a Hamiltonian. Here, we address the case when the matrix is a density matrix ρ . We introduce the variational quantum state eigensolver (VQSE), which is analogous to VQE in that it variationally learns the largest eigenvalues of ρ as well as a gate sequence V that prepares the corresponding eigenvectors. VQSE exploits the connection between diagonalization and majorization to define a cost function
C=Tr(ρ~H) C = Tr ( ρ ̃ H ) where H is a non-degenerate Hamiltonian. Due to Schur-concavity, C is minimized when
ρ~=VρV† ρ ̃ = V ρ V † is diagonal in the eigenbasis of H . VQSE only requires a single copy of ρ (only n qubits) per iteration of the VQSE algorithm, making it amenable for near-term implementation. We heuristically demonstrate two applications of VQSE: (1) Principal component analysis, and (2) Error mitigation.
Quantum algorithms for selecting a subspace of Hamiltonians to diagonalize have emerged as a promising alternative to variational algorithms in the NISQ era. So far, such algorithms, which include the quantum selected configuration interaction (QSCI) and sample-based quantum diagonalization (SQD), have been formulated within second-quantization in Fock space, which leads to inefficient usage of qubit resources. We introduce the first QSCI algorithm developed in the CI-matrix (CIM) framework, which is known to have optimal qubit scaling of exactly
⌈log2(N)⌉ where
N is the size of the CIM. In addition, we introduce a novel single-bit flip error mitigation which comes at the overhead of a single qubit and we combine this with a stochastic approximate Trotterization evolution adapted from qDRIFT. Simulating benchmark N
2 and naphthalene molecules on quantum hardware, our results achieved similar accuracy as SQD methods but with significantly less quantum resources. However, our CIM-QSCI algorithm and SQD methods could not match the performance of classical heat-bath CI (HCI) for the same task. Hence, we introduce an augmented version of QSCI called quantum selected heat-bath CI (QSHCI). This variant replaces classical heat-bath sampling with quantum sampling from QSCI to achieve performance comparable to HCI. We note that a current drawback of our approach is the preprocessing cost of
O(N2logN) for constructing the CIM and performing the Pauli decomposition. This can be further improved by considering efficient CIM access models for the stochastic Trotter evolution.