Physics – Quantum Physics
Scientific paper
2003-03-31
Physics
Quantum Physics
15 pages
Scientific paper
We introduce the quantum complexity class FQMA. This class describes the complexity of generating a quantum state that serves as a witness for a given QMA problem. In a certain sense, FQMA is the quantum analogue of FNP (function problems associated with NP). The latter describes the complexity of finding a succinct proof for a NP decision problem. Whereas all FNP problems can be reduced to NP, there is no obvious reduction of FQMA to QMA since the solution of FQMA is a quantum state and the solution of QMA the answer yes or no. We consider quantum state generators that get classical descriptions of 3-local Hamiltonians on n qubits as input and prepare low energy states for these systems as output. We show that such state generators can be used to prepare witnesses for QMA problems. Hence low energy state preparation is FQMA-complete. Our proofs are extensions of the proofs by Kitaev et al. and Kempe and Regev for the QMA-completeness of k-local Hamiltonian problems. We show that FQMA can be solved by preparing thermal equilibrium states with an appropriate temperature decreasing as the reciprocal of a polynomial in n.
Beth Thomas
Janzing Dominik
Wocjan Pawel
No associations
LandOfFree
Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-102159