Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-Identity Check Remains QMA-Complete for Short Circuits
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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-Complete 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.
rate research
Read More
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.
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.
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 shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.
The evaluation of expectation values $Trleft[rho Oright]$ for some pure state $rho$ and Hermitian operator $O$ is of central importance in a variety of quantum algorithms. Near optimal techniques developed in the past require a number of measurements $N$ approaching the Heisenberg limit $N=mathcal{O}left(1/epsilonright)$ as a function of target accuracy $epsilon$. The use of Quantum Phase Estimation requires however long circuit depths $C=mathcal{O}left(1/epsilonright)$ making their implementation difficult on near term noisy devices. The more direct strategy of Operator Averaging is usually preferred as it can be performed using $N=mathcal{O}left(1/epsilon^2right)$ measurements and no additional gates besides those needed for the state preparation. In this work we use a simple but realistic model to describe the bound state of a neutron and a proton (the deuteron) and show that the latter strategy can require an overly large number of measurement in order to achieve a reasonably small relative target accuracy $epsilon_r$. We propose to overcome this problem using a single step of QPE and classical post-processing. This approach leads to a circuit depth $C=mathcal{O}left(epsilon^muright)$ (with $mugeq0$) and to a number of measurements $N=mathcal{O}left(1/epsilon^{2+ u}right)$ for $0< uleq1$. We provide detailed descriptions of two implementations of our strategy for $ u=1$ and $ uapprox0.5$ and derive appropriate conditions that a particular problem instance has to satisfy in order for our method to provide an advantage.
Photonic circuits in which stateful components are coupled via guided electromagnetic fields are natural candidates for native implementation of iterative stochastic algorithms based on propagation of information around a graph. Conversely, such message passing algorithms suggest novel circuit architectures for signal processing and computation that are well matched to nanophotonic device physics. Here we construct and analyze a quantum optical model of a photonic circuit for iterative decoding of a class of low-density parity-check (LDPC) codes called expander codes. Our circuit can be understood as an open quantum system whose autonomous dynamics map straightforwardly onto the subroutines of an LDPC decoding scheme, with several attractive features: it can operate in the ultra-low power regime of photonics in which quantum fluctuations become significant, is robust to noise and component imperfections, achieves comparable performance to known iterative algorithms for this class of codes, and provides an instructive example of how nanophotonic cavity quantum electrodynamic components can enable useful new information technology even if the solid-state qubits on which they are based are heavily dephased and cannot support large-scale entanglement.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
