N-representability is QMA-complete

Abstract

We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is QMA-complete, which is the quantum generalization of NP-complete. Our proof uses a simple mapping from spin systems to fermionic systems, as well as a convex optimization technique that reduces the problem of finding ground states to N-representability.

References in corpus (6)

• Matrix product states represent ground states faithfully
• Quantum marginal problem and N-representability
• Mapping local Hamiltonians of fermions to local Hamiltonians of spins
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• One-qubit reduced states of a pure many-qubit state: polygon inequalities
• Quantum state transformations and the Schubert calculus

Cited by in corpus (119)

• A variational eigenvalue solver on a quantum processor
• Quantum Chemistry in the Age of Quantum Computing
• Quantum information processing with superconducting circuits: a review
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Quantum Error Mitigation
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Hamiltonian complexity
• The Pauli principle revisited
• Quantum Hamiltonian Complexity
• Error Mitigation by Symmetry Verification on a Variational Quantum Eigensolver
• Preparing ground states of quantum many-body systems on a quantum computer
• A Separability-Entanglement Classifier via Machine Learning
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Quantum Computing for Molecular Biology
• Transfer Matrices and Excitations with Matrix Product States
• Computational Complexity in Electronic Structure
• Diverging exchange force and form of the exact density matrix functional
• Semidefinite programming relaxations for quantum correlations
• Interacting boson problems are QMA-hard
• Introduction to Quantum Algorithms for Physics and Chemistry
• Variational two-particle density matrix calculation for the Hubbard model below half filling using spin-adapted lifting conditions
• Quantum simulation of quantum field theories as quantum chemistry
• Gaussian quantum marginal problem
• Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
• Solving condensed-matter ground-state problems by semidefinite relaxations
• Symmetric Extension of Two-Qubit States
• QMA-complete problems for stoquastic Hamiltonians and Markov matrices
• Merlin-Arthur Games and Stoquastic Complexity
• Eigenvalue Distributions of Reduced Density Matrices
• A complete hierarchy for the pure state marginal problem in quantum mechanics
• Quantum Many-body Theory from a Solution of the $N$-representability Problem
• Natural Orbitals and Occupation Numbers for Harmonium: Fermions vs. Bosons
• Quantum de Finetti theorem under fully-one-way adaptive measurements
• Computational Difficulty of Computing the Density of States
• A quasipolynomial-time algorithm for the quantum separability problem
• Quantum Channel Marginal Problem
• Compatible quantum correlations: on extension problems for Werner and isotropic states
• Exact gate decompositions for photonic quantum computing
• Number-parity effect for confined fermions in one dimension
• Continuous-variable gate decomposition for the Bose-Hubbard model
• Pinning of Fermionic Occupation Numbers: General Concepts and One Dimension
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• Characterizing quantum states via sector lengths
• Quantum Marginal Problem and its Physical Relevance
• Approximation algorithms for QMA-complete problems
• Comment on some results of Erdahl and the convex structure of reduced density matrices
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• The quantum marginal problem for symmetric states: applications to variational optimization, nonlocality and self-testing
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
• Quantum codes give counterexamples to the unique pre-image conjecture of the N-representability problem
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Lower Bounding Ground-State Energies of Local Hamiltonians Through the Renormalization Group
• Four-qubit pure states as fermionic states
• Extendibility of bosonic Gaussian states
• Embedding qubits into fermionic Fock space, peculiarities of the four-qubit case
• The Bose-Hubbard model is QMA-complete
• Quantum interactive proofs and the complexity of separability testing
• Membership in moment polytopes is in NP and coNP
• Some Open Problems in Quantum Information Theory
• Improved Soundness for QMA with Multiple Provers
• Determining system Hamiltonian from eigenstate measurements without correlation functions
• Benchmarking the variational reduced density matrix theory in the doubly-occupied configuration interaction space with integrable pairing models
• Method For Making 2-Electron Response Reduced Density Matrices Approximately N-representable
• Semirelativistic stability of N-boson systems bound by 1/r pair potentials
• Complexity of Supersymmetric Systems and the Cohomology Problem
• An algorithm to explore entanglement in small systems
• Quantum marginals from pure doubly excited states
• On the Use of Group Theoretical and Graphical Techniques toward the Solution of the General N-body Problem
• Quantum verification of NP problems with single photons and linear optics
• Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
• Certifying ground-state properties of quantum many-body systems
• Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
• Experimental determination of multipartite entanglement with incomplete information
• Non-Identity Check Remains QMA-Complete for Short Circuits
• Quantum Earth mover's distance, No-go Quantum Kantorovich-Rubinstein theorem, and Quantum Marginal Problem
• Physical origins of ruled surfaces on the reduced density matrices geometry
• Detecting Consistency of Overlapping Quantum Marginals by Separability
• Recoupling coefficients and quantum entropies
• Solver for the electronic V-representation problem of time-dependent density functional theory
• The Complexity of the Separable Hamiltonian Problem
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Quantum Multi Prover Interactive Proofs with Communicating Provers
• Correlations in excited states of local Hamiltonians
• Reducible Correlations in Dicke States
• Antisymmetrized Geminal Powers with Larger Chemical Basis Sets
• Universal Subspaces for Local Unitary Groups of Fermionic Systems
• Algorithms for the Markov Entropy Decomposition
• Electronic Structure in a Fixed Basis is QMA-complete
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Rank Reduction for the Local Consistency Problem
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Variational approach for the electronic structure calculation on the second-order reduced density matrices and the $N$-representability problem
• Determining the N-representability of a reduced density matrix via unitary evolution and stochastic sampling
• Variational determination of the two-particle density matrix as a quantum many-body technique
• The Role of Rotational Invariance in the Properties of Hamiltonians
• The quantum moment problem and bounds on entangled multi-prover games
• Symmetric vs. bosonic extension for bipartite states
• Approximation, Proof Systems, and Correlations in a Quantum World
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• Constraints on Multipartite Quantum Entropies
• Recoverability from direct quantum correlations
• An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers
• The Power of Unentanglement
• Orthogonalization of fermion k-body operators and representability
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
• Quantum Glassiness From Efficient Learning
• Geometric Constraints on Two-electron Reduced Density Matrices
• Characterizing maximally many-body entangled fermionic states by using $M$-body density matrix
• Classifying fermionic states via many-body correlation measures
• Determining the ensemble N-representability of Reduced Density Matrices
• Testing quantum expanders is co-QMA-complete
• Is the matrix completion of reduced density matrices unique?
• A quantum algorithm for obtaining the lowest eigenstate of a Hamiltonian assisted with an ancillary qubit system
• Expanding the reach of quantum optimization with fermionic embeddings
• A favorably-scaling natural-orbital functional theory based on higher-order occupation probabilities
• Refining ensemble $N$-representability of one-body density matrices from partial information
• Spin adaptation of the cumulant expansions of reduced density matrices
• Representability for Quantum Theory beyond Particle-Number Conservation
• Detecting Entanglement by Pure Bosonic Extension