ترغب بنشر مسار تعليمي؟ اضغط هنا

Electronic Structure in a Fixed Basis is QMA-complete

110   0   0.0 ( 0 )
 نشر من قبل Bryan O'Gorman
 تاريخ النشر 2021
والبحث باللغة English




اسأل ChatGPT حول البحث

Finding the ground state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry. We prove that this electronic-structure problem, when restricted to a fixed single-particle basis and fixed number of electrons, is QMA-complete. Schuch and Verstraete have shown hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis. In their reduction, a local Hamiltonian on qubits is encoded in the site-specific magnetic field. In our reduction, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian. As a step in their proof, Schuch and Verstraete show a reduction from the antiferromagnetic Heisenberg Hamiltonian to the Fermi-Hubbard Hamiltonian. We combine this reduction with the fact that the antiferromagnetic Heisenberg Hamiltonian is QMA-hard to observe that the Fermi-Hubbard Hamiltonian on generic graphs is QMA-hard, even when all the hopping coefficients have the same sign. We then reduce from Fermi-Hubbard by showing that an instance of Fermi-Hubbard can be closely approximated by an instance of the Electronic-Structure Hamiltonian in a fixed basis. Finally, we show that estimating the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is NP-complete for the Electronic-Structure Hamiltonian in a fixed basis.



قيم البحث

اقرأ أيضاً

90 - Y.-K. Liu , M. Christandl , 2006
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 fermioni c systems, as well as a convex optimization technique that reduces the problem of finding ground states to N-representability.
The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been show n to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.
165 - David Gosset , Daniel Nagaj 2013
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi sh owed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k greater than or equal to 4 is QMA1-complete. Quantum 3-SAT was known to be contained in QMA1, but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.
111 - Zhengfeng Ji , Xiaodi Wu 2009
The Non-Identity Check problem asks whether a given a quantum circuit is far away from the identity or not. It is well known that this problem is QMA-Complete cite{JWB05}. In this note, it is shown that the Non-Identity Check problem remains QMA-Comp lete for circuits of short depth. Specifically, we prove that for constant depth quantum circuit in which each gate is given to at least $Omega(log n)$ bits of precision, the Non-Identity Check problem is QMA-Complete. It also follows that the hardness of the problem remains for polylogarithmic depth circuit consisting of only gates from any universal gate set and for logarithmic depth circuit using some specific universal gate set.
Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). We prove that the game is complete for NP, even if the puzzle has no h ole. When all odd numbers are placed it is in P, whereas it is still NP-hard when all numbers of the form $3k+1$ are placed.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا