Chris Pollett > Students > Yunxuan
Print View
[Bio]
[Blog]
[First Proposal]
[Final Step of Shor's and Grover's Algorithms]
[jQuantum QFT]
[My Quantum Circuits]
[Three Models]
[Threshold of Error Correction]
[jQuantum Manual]
[Quantum State and LH]
[QHC Scientists]
[LH and Tensor Networks]
[k-LH is QMA-complete]
[Deutch Josza Algorithm]
[Semester Report]
[Second Proposal]
[SolveQ Algorithm: 2-SAT]
[Random-kSAT-Generator: Version 1]
[Freezing Point Experiment]
[Random-kQSAT-Generator: Version 2]
[Random-kQSAT-Generator: Version 3]
[Antiferromagnetic Heisenberg Model]
[Ising Model]
[Random-kQSAT-Generator: Version 4]
[Random-kQSAT-Generator: Version 5]
[Random-kQSAT-Generator: Version 6]
[SolveQ Algorithm: 2-QSAT]
[Thesis]
|
Recent Discoveries in Quantum Hamiltonian Complexity
- Kitaev proved that k-LH is in QMA for k>=1 and QMA-hard for k>=5.
- Oliveira and Terhal showed that LH with Hamiltonians restricted to nearest neighbor interaction on a 2D grid is still QMA-complete.
- Aharonov, Gottesman, Irani and Kempe showed that 2-LH with nearest neighbor interactions on the line is also QMA complete if the local system have dimension of at least 12.
- Cubitt and Montanaro established a quantum variant of Schaefers Dichotomy Theorem.
- Bravyi defined Quantum k-SAT in which all local constraints are positive semidefinite, and the question is whether the ground state energy is zero.
- Aharonov and Eldar proved that approximating the ground state energy of commuting local Hamiltonians on good locally-expanding graphs is in NP.
- Gharibian, Landau, Shin and Wang showed that the commuting variant of the Stoquastic k-SAT problem is in NP for logarithmic k and any constant d.
- Yan and Bacon showed that LH with all commuting terms are products of Pauli operators is in P.
- Schuch and Verstraete showed that Hubbard Model has QMA hardness.
- Bravyi has given a Fully Polynomial Randomized Approximation Scheme for approximating the partition function of the transverse field Ising model.
- Baharonas works showed that finding a ground state and computing the magnetic partition function of an Ising spin glass in a nonuniform magnetic field are NP hard tasks.
- Whites discovered his celebrated Density Matrix Renormalization Group.
- Verstraete and Cirac Projected entangled pair states
- Schuch, Wolf, Verstraete and Cirac found that MPS and MERA networks can be efficiently contracted.
- Arad, Kitaev, Landau, Vazirani showed that MPS with sublinear bond dimension suffices to approximate the ground state.
- A combinatorial proof improving on Hastings result for the frustration-free case was later given by Aharonov, Arad, Landau and Vazarani.
- Cubitt, Perez, Garcia, Wolf showed that determining whether a translational-invariant, nearest-neighbor Hamiltonian on a 2D square lattice is gapped is undecidable.
- Gosset, Terhal, and Vershynina showed how to perform universal adiabatic quantum computation using space-time circuit-to-Hamiltonian construction.
- Fitzsimons and Vidick gave a multiprover interactive proof system for the Local Hamiltonian problem involving a constant number of entangled provers.
- Chubb and Flamia extended the works of Landau, Vazirani and Vidick and Huang to give a polynomial time algorithm for approximating ground space projectors of gapped 1D Hamiltonians with degenerate groun spaces.
- Gharibian and Sikora showed that given a local Hamiltonian and two ground states, is there a sequence of local unitaries mapping between the two states.
- Ge and Eisert showed that in two and higher dimensions, it is not general true that an area law for the Renyi entanglement entropy implies the ability to faithfully describe a quantum many-body state by an efficient tensor network.
- Aharonov showed that a generalized version of the area law fails to hold.
- Movassah and Shor showed that a generalization of Bravyis spin-1 model to integer spin-s chains yields a power law violation of the area law.
- Brandao and Cramer showed that the exponential decay in the specific heat capacity at low temperatures yields an area law for low-energy states
- Marien proved that the stability of the area law for entanglement entropy in quantum spin systems in the setting of adiabatic and quasi-adiabatic evolutions.
|