Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Complexity of the Consistency and N-representability Problems for Quantum States
100
0
0.0
(
0
)
Authors
Yi-Kai Liu
Ask ChatGPT about the research
No Arabic abstract
QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices: given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian and ``N-representability, are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960s, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.
rate research
Read More
Consider a projector matrix P, representing the first order reduced density matrix in a basis of orthonormal atom-centric basis functions. A mathematical question arises, and that is, how to break P into its natural component kernel projector matrices, while preserving N-representability of P. The answer relies upon 2- projector triple products, PjPPj. The triple product solutions, applicable within the quantum crystallography of large molecules, are determined by a new form of the Clinton equations, which - in their original form - have long been used to ensure N-representability of density matrices consistent with X-ray diffraction scattering factors.
The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(nlog n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problems quantum time complexity. Specifically, we give an $tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $mathrm{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grovers algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grovers algorithm is optimal for CNF-SAT when the clause width is large. We show that the na{i}ve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.
Variational calculation of the ground state energy and its properties using the second-order reduced density matrix (2-RDM) is a promising approach for quantum chemistry. A major obstacle with this approach is that the $N$-representability conditions are too difficult in general. Therefore, we usually employ some approximations such as the $P$, $Q$, $G$, $T1$ and $T2^prime$ conditions, for realistic calculations. The results of using these approximations and conditions in 2-RDM are comparable to those of CCSD(T). However, these conditions do not incorporate an important property; size-consistency. Size-consistency requires that energies $E(A)$, $E(B)$ and $E(A...B)$ for two infinitely separated systems $A$, $B$, and their respective combined system $A...B$, to satisfy $E(A...B) = E(A) + E(B)$. In this study, we show that the size-consistency can be satisfied if 2-RDM satisfies the following conditions: (i) 2-RDM is unitary invariant diagonal $N$-representable; (ii) 2-RDM corresponding to each subsystem is the eigenstate of the number of corresponding electrons; and (iii) 2-RDM satisfies at least one of the $ P$, $Q$, $G$, $T1$ and $T2^prime$ conditions.
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.
This paper discusses a restriction of quantum theory, in which very complex states would be excluded. The toy theory is phrased in the language of the circuit model for quantum computing, its key ingredient being a limitation on the number of interactions that textit{each} qubit may undergo. As long as one stays in the circuit model, the toy theory is consistent and may even match what we shall be ever able to do in a controlled laboratory experiment. The direct extension of the restriction beyond the circuit model conflicts with observed facts: the possibility of restricting the complexity of quantum state, while saving phenomena, remains an open question.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
