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:quant-ph/0108110 · Physical Review Letters

Polynomial-Time Simulation of Pairing Models on a Quantum Computer

Lian-Ao Wu, Mark Byrd, Daniel A. Lidar

Published Jul 16, 2002• 107 citations
arXivHTMLPDF

Abstract

We propose a polynomial-time algorithm for simulation of the class of pairing Hamiltonians, e.g., the BCS Hamiltonian, on an NMR quantum computer. The algorithm adiabatically finds the low-lying spectrum in the vicinity of the gap between the ground and the first excited states and provides a test of the applicability of the BCS Hamiltonian to mesoscopic superconducting systems, such as ultrasmall metallic grains.

DOI
10.1103/physrevlett.89.057904

Related papers

Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian Using Nuclear Magnetic Resonance

Kenneth R. Brown, Robert Clark, Isaac L. Chuang

Quantum simulation uses a well-known quantum system to predict the behavior of another quantum system. Certain limitations in this technique arise, however, when applied to specific problems, as we demonstrate with a theoretical and experimental study of an algorithm proposed by Wu, Byrd, and Lidar [Phys. Rev. Lett. 89, 057904 (2002).10.1103/PhysRevLett.89.057904] to find the low-lying spectrum of a pairing Hamiltonian. While the number of elementary quantum gates required scales polynomially with the size of the system, it increases inversely to the desired error bound E. Making such simulations robust to decoherence using fault tolerance requires an additional factor of approximately 1/E gates. These constraints, along with the effects of control errors, are illustrated using a three qubit NMR system.

arXiv:quant-ph/0601021•Physical Review Letters•Aug 4, 2006•98 citations

Numerical Simulation Solution of the BCS Pairing Problem

Feng Xu, An-Min Wang, Xiao-Dong Yang +1 more

We propose a new simulation computational method to solve the reduced BCS Hamiltonian based on spin analogy and submatrix diagonalization. Then we further apply this method to solve superconducting energy gap and the results are well consistent with those obtained by Bogoliubov transformation method. The exponential problem of 2 N -dimensional matrix is reduced to the polynomial problem of N -dimensional matrix. It is essential to validate this method on a real quantum computer and is helpful to understanding the many-body quantum theory.

arXiv:quant-ph/0407100•Communications in Theoretical Physics•Jul 1, 2005•4 citations

Numerical Simulation Solution of the BCS Pairing Problem

Xufeng, Feng, Wang +5 more

We propose a new simulation computational method to solve the reduced BCS Hamiltonian based on spin analogy and submatrix diagonalization. Then we further apply this method to solve superconducting energy gap and the results are well consistent with those obtained by Bogoliubov transformation method. The exponential problem of 2N-dimensional matrix is reduced to the polynomial problem of N-dimensional matrix. It is essential to validate this method on a real quantum computer and is helpful to understanding the many-body quantum theory.

理论物理通讯：英文版•Jan 1, 2005•0 citations

Simulating adiabatic evolution of gapped spin systems

Tobias J. Osborne

We show that adiabatic evolution of a low-dimensional lattice of quantum spins with a spectral gap can be simulated efficiently. In particular, we show that as long as the spectral gap $\ensuremath{\Delta}E$ between the ground state and the first excited state is any constant independent of $n$, the total number of spins, then the ground-state expectation values of local operators, such as correlation functions, can be computed using polynomial space and time resources. Our results also imply that the local ground-state properties of any two spin models in the same quantum phase can be efficiently obtained from each other. A consequence of these results is that adiabatic quantum algorithms can be simulated efficiently if the spectral gap does not scale with $n$. The simulation method we describe takes place in the Heisenberg picture and does not make use of the finitely correlated state--matrix product state formalism.

arXiv:quant-ph/0601019•Physical Review A•Mar 14, 2007•91 citations

A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians

Zeph A. Landau, Umesh V. Vazirani, Thomas Vidick

Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.

arXiv:1307.5143•Jul 19, 2013•25 citations

Efficient quantum algorithm for Heisenberg spin systems

Sergey Bravyi, David Gosset, Yinchen Liu +1 more

We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by $2μ$, where $μ$ is the magnetic field along the $Z$ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.

quant-pharXiv:2607.14401•Jul 17, 2026•0 citations
We propose a polynomial-time algorithm for simulation of the class of pairing Hamiltonians, e.g., the BCS Hamiltonian, on an NMR quantum computer. The algorithm adiabatically finds the low-lying spectrum in the vicinity of the gap between the ground and the first excited states and provides a test of the applicability of the BCS Hamiltonian to mesoscopic superconducting systems, such as ultrasmall metallic grains.
Quantum simulation uses a well-known quantum system to predict the behavior of another quantum system. Certain limitations in this technique arise, however, when applied to specific problems, as we demonstrate with a theoretical and experimental study of an algorithm proposed by Wu, Byrd, and Lidar [Phys. Rev. Lett. 89, 057904 (2002).10.1103/PhysRevLett.89.057904] to find the low-lying spectrum of a pairing Hamiltonian. While the number of elementary quantum gates required scales polynomially with the size of the system, it increases inversely to the desired error bound E. Making such simulations robust to decoherence using fault tolerance requires an additional factor of approximately 1/E gates. These constraints, along with the effects of control errors, are illustrated using a three qubit NMR system.
We propose a new simulation computational method to solve the reduced BCS Hamiltonian based on spin analogy and submatrix diagonalization. Then we further apply this method to solve superconducting energy gap and the results are well consistent with those obtained by Bogoliubov transformation method. The exponential problem of 2 N -dimensional matrix is reduced to the polynomial problem of N -dimensional matrix. It is essential to validate this method on a real quantum computer and is helpful to understanding the many-body quantum theory.
We propose a new simulation computational method to solve the reduced BCS Hamiltonian based on spin analogy and submatrix diagonalization. Then we further apply this method to solve superconducting energy gap and the results are well consistent with those obtained by Bogoliubov transformation method. The exponential problem of 2N-dimensional matrix is reduced to the polynomial problem of N-dimensional matrix. It is essential to validate this method on a real quantum computer and is helpful to understanding the many-body quantum theory.
We show that adiabatic evolution of a low-dimensional lattice of quantum spins with a spectral gap can be simulated efficiently. In particular, we show that as long as the spectral gap $\ensuremath{\Delta}E$ between the ground state and the first excited state is any constant independent of nnn, the total number of spins, then the ground-state expectation values of local operators, such as correlation functions, can be computed using polynomial space and time resources. Our results also imply that the local ground-state properties of any two spin models in the same quantum phase can be efficiently obtained from each other. A consequence of these results is that adiabatic quantum algorithms can be simulated efficiently if the spectral gap does not scale with nnn. The simulation method we describe takes place in the Heisenberg picture and does not make use of the finitely correlated state--matrix product state formalism.
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.
We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by 2μ2μ2μ, where μμμ is the magnetic field along the ZZZ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.