77 citations · 168 across the 10 of their papers we have counts for
5 papers · 1 filter
An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
We provide an elementary proof of the quantum adiabatic theorem.
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
Oded Regev
In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-pol…
The Complexity of the Local Hamiltonian Problem
Julia Kempe, Alexei Kitaev, Oded Regev
The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for…
A Lattice Problem in Quantum NP
Dorit Aharonov, Oded Regev
We consider coGapSVP_\sqrt{n}, a gap version of the shortest vector in a lattice problem. This problem is known to be in AM\cap coNP but is not known to be in NP or in MA. We prove…
3-Local Hamiltonian is QMA-complete
Julia Kempe, Oded Regev
It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-comp…